@Mohit: I dont think it really matters here.We just have to validate the snapshot of the game board.Number of players should not have any relevance here.
On Sat, Sep 25, 2010 at 2:46 PM, mohit ranjan <[email protected]>wrote: > @Ashita, > > Your logic is fine for one vs one game, but as per question it's "one vs > many game" > Any idea what is that ? > > > Mohit > > On Sat, Sep 25, 2010 at 1:18 PM, ashita dadlani <[email protected]> wrote: > >> 1.The soldiers are initially placed at row 2 or row 7th(each-one of white >> and either of black).Also let white ones be at row 2.So they can never be at >> row 1st.Incase it is so in the game,its not a valid game. >> 2.There are Bishops.Each color has one of its Bishop which moves >> diagonally on all white squares,and the other on all black squares.Incase it >> is not so,the game cannot be valid. >> 3.Now suppose,no black soldier ever moved.That is,all the black soldiers >> are at row 7th.This means that the elephant(i am sorry,I generally mess up >> with their names..:P) of any other player(except horse) cannot be in any row >> but 8th one. >> >> I know only 3 test cases.Incase any one has more,please elaborate. >> PS:Vrinda,I also got the same question..:P >> >> >> On Sat, Sep 25, 2010 at 2:49 AM, Gene <[email protected]> wrote: >> >>> Valid must mean that you can get from an initial board to the the >>> current game state by a series of legal moves. >>> >>> This is a classic branch and bound game tree search problem. You >>> could search either from a starting configuration and try to "find" >>> the current game state. Or start from the current state, use >>> 'backward' moves, and try to find the initial configuration. In this >>> case, you'd have to include backward moves that 'untake' pieces that >>> are missing from the current state. >>> >>> Or you could do a simultaneous search from both ends, looking for >>> common states in the middle. >>> >>> You'd generally use a heuristic search. Problems like this often work >>> well with A-Star. The heuristic evaluator would favor states closer >>> to the desired end (either start or current). >>> >>> Gene >>> >>> On Sep 24, 6:26 am, vrinda vasishth <[email protected]> wrote: >>> > Asked in microsoft interview >>> > >>> > "Given a snapshot of an ongoing chess game, which probably is a one vs >>> many >>> > game, identify whether it is a valid game or not." >>> > >>> > It would be great if someone would clarify on what conditions does >>> > "validity" of the game depend.. >>> > >>> > --Vrinda >>> >>> -- >>> You received this message because you are subscribed to the Google Groups >>> "Algorithm Geeks" group. >>> To post to this group, send email to [email protected]. >>> To unsubscribe from this group, send email to >>> [email protected]<algogeeks%[email protected]> >>> . >>> For more options, visit this group at >>> http://groups.google.com/group/algogeeks?hl=en. >>> >>> >> -- >> You received this message because you are subscribed to the Google Groups >> "Algorithm Geeks" group. >> To post to this group, send email to [email protected]. >> To unsubscribe from this group, send email to >> [email protected]<algogeeks%[email protected]> >> . >> For more options, visit this group at >> http://groups.google.com/group/algogeeks?hl=en. >> > > -- > You received this message because you are subscribed to the Google Groups > "Algorithm Geeks" group. > To post to this group, send email to [email protected]. > To unsubscribe from this group, send email to > [email protected]<algogeeks%[email protected]> > . > For more options, visit this group at > http://groups.google.com/group/algogeeks?hl=en. > -- You received this message because you are subscribed to the Google Groups "Algorithm Geeks" group. To post to this group, send email to [email protected]. To unsubscribe from this group, send email to [email protected]. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
