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. For more options, visit this group at http://groups.google.com/group/algogeeks?hl=en.
