Title: Finding Solution to puzzles using Trees.
Question: How do you find the moves to solve puzzles involving moving pieces on a board.
Answer:
You must be familiar with many puzzles involving moving pieces on a board to get the desired position.
Let us take an example.
Consider the 4 Knights puzzle in which 2 white knights and 2 black knights are placed on a 3X3 square board. The two white knights are on the top two corners of the board while the two black knights are placed at the bottom two corners of the board. The objective is to move the white knights to the bottom two corners and the black knights to the two top corners. The knights move in L shape as in Chess. The white knight moves first and the black and white knights move alternately
Trees can be used to find the minimum number of moves necessary to do this.
Each node of the tree defines a problem state. The root node of the tree represents the initial state of the board. By moving one piece to a valid position on the board we get another problem state. This state will be represented by a node that is the child of the root node. The idea is to generate all the immediate children of the root node by moving each piece to every valid position possible on the board.
The next thing is to do is to check whether any of the children represent the solution state. If it does then the path from the root node to this child node represents the moves that are required to move the pieces from initial position.
If none of the children represent the solution state then with each child node generate all its children by moving each piece to all valid positions on the board and generate its children. Again check if these node represent the solution state. Repeat the process until the solution is found.
As each node can generate many nodes, The tree will soon grow very large. To prevent this some conditions must be applied before generating a child node. The conditions depend upon the nature of the puzzle In this example the condition I chose was that each piece should not move to the same square twice. This condition considerably reduced the size of the tree.
The figure below shows a portion of the Tree
The code can be downloaded using the download option available.