Menu
The classical 8-puzzle belongs to the family of sliding blocks. My book (Artificial intelligence A modern approach by Stuart Russell and peter Norwig) says that the 8-puzzle has 9!/2 possible states. But WHY the /2 ? How do you get this?
906
Following is simple rule to check if a 8 puzzle is solvable. It is not possible to solve an instance of 8 puzzle if number of inversions is odd in the input state. In the examples given in above figure, the first example has 10 inversions, therefore solvable. The second example has 11 inversions, therefore unsolvable.
– 8‐puzzle: we could specify 4 possible moves for each of the 8 cles, resulcng in a total of 4*8=32 operators.
An 8 puzzle is a simple game consisting of a 3 x 3 grid (containing 9 squares). One of the squares is empty. The object is to move to squares around into different positions and having the numbers displayed in the "goal state".
Given a 3×3 board with 8 tiles (every tile has one number from 1 to 8) and one empty space. The objective is to place the numbers on tiles to match the final configuration using the empty space. We can slide four adjacent (left, right, above, and below) tiles into the empty space.
9! is the total number of possible configurations of the puzzle, whereas 9!/2 is the total number of solvable configurations. For example, this configuration doesn't have a solution:
1 2 3 4 5 6 8 7 Read more about the solvability of certain configurations of the n-puzzle in this Wikipedia article, or as pointed out by @dasblinkenlight in this MathWorld explanation.
One possible way to find out that 9!/2 is the number of solvable configurations is to start from a solved puzzle and generate all the possible valid, non-repeating movements from it.
85
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With
