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 <gene.ress...@gmail.com> 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 <vrindavasis...@gmail.com> 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 algoge...@googlegroups.com. > To unsubscribe from this group, send email to > algogeeks+unsubscr...@googlegroups.com<algogeeks%2bunsubscr...@googlegroups.com> > . > 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 algoge...@googlegroups.com. To unsubscribe from this group, send email to algogeeks+unsubscr...@googlegroups.com. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
