<p>This article has an extensive discussion of the solution:</p>

<p><a href="http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html" rel="nofollow">http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html</a></p>

<p>The summary for the 3x3 board is:</p>

<blockquote>
  <p>Lay out the board as a 9x1 row (row 1, then row 2, then row 3).  Count the number of inversions (instances of a higher number coming before a lower number on this row).  The board is solvable if and only if the number of inversions is even.</p>
</blockquote>

<p>For example, </p>

<pre><code>8   1   3
2       5
7   6   4
</code></pre>

<p>Written as a row is:</p>

<pre><code>8, 1, 3, 2, , 5, 7, 6, 4
</code></pre>

<p>The 8 gives 7 inversions, the 1 gives none, the 3 gives 1 inversion, the 2 gives none, the 5 gives 1, the 7 gives 2, and the 6 gives 1.  This example has a total of 12 inversions, which is even, so it is solvable.</p>

CC BY-SA 3.0
2014-11-24T19:02:28.297Z
2015-05-27T00:21:56.350Z
2015-05-27T00:21:56.350Z
Zags
<p>I'm working on 8 number puzzle, where 8 numbers are randomly generated and placed in 9 cell board. One cell at bottom right corner is kept empty where we can swap with adjacent (top-bottom-left-right) cells if any available.</p>

<p><img src="https://i.sstatic.net/dbXGC.jpg" alt="enter image description here">
<img src="https://i.sstatic.net/WFMEn.jpg" alt="enter image description here">
<img src="https://i.sstatic.net/bMhCc.jpg" alt="enter image description here"></p>

<p>The puzzle can be solved if all numbers are arranged in sequence starting from top left cell.
<img src="https://i.sstatic.net/JskRB.jpg" alt="enter image description here"></p>

<p>Now after some trials, I found that some arrangements of (randomly generated) numbers in starting of the game are not solvable.</p>

<p><img src="https://i.sstatic.net/9XL45.jpg" alt="enter image description here">
<img src="https://i.sstatic.net/30ZbA.jpg" alt="enter image description here"></p>

<p>I think, after generating random numbers, we can find mathematically that random numbers can be solved after placing on board or not.</p>

<p>Can anybody help to find the solution/algorithm/mathematical formula to determine that numbers can be solvable or not?</p>

CC BY-SA 3.0
2014-08-10T18:12:58.963Z
This probably fits in better over at math.stackexchange under game theory: http://math.stackexchange.com/questions/754827/does-a-15-puzzle-always-have-a-solution
Hao Ye
CC BY-SA 3.0
2014-08-12T23:40:18.543Z
The mathematics is studied using Permutation Groups. Essentially all boards can be solved to either the correct solution, or the pseudo-solution with the 7 and the 8 swapped. An algorithm to generate valid boards might start by applying 1,000s of swaps randomly to a board that is known to be valid.
Joshua Shane Liberman
CC BY-SA 3.0
2014-08-15T20:08:29.493Z
Or perhaps even better yet: the puzzling stack at http://puzzling.stackexchange.com/
SQB
<puzzles><board-game-adaptations>
how to find that 8 number puzzle is solvable or not?
Kulin Choksi
# how to find that 8 number puzzle is solvable or not?

(Asked by: username_0 on 2014-08-10)

I'm working on 8 number puzzle, where 8 numbers are randomly generated and placed in 9 cell board. One cell at bottom right corner is kept empty where we can swap with adjacent (top-bottom-left-right) cells if any available.

![enter image description here](https://i.sstatic.net/dbXGC.jpg)
![enter image description here](https://i.sstatic.net/WFMEn.jpg)
![enter image description here](https://i.sstatic.net/bMhCc.jpg)

The puzzle can be solved if all numbers are arranged in sequence starting from top left cell.
![enter image description here](https://i.sstatic.net/JskRB.jpg)

Now after some trials, I found that some arrangements of (randomly generated) numbers in starting of the game are not solvable.

![enter image description here](https://i.sstatic.net/9XL45.jpg)
![enter image description here](https://i.sstatic.net/30ZbA.jpg)

I think, after generating random numbers, we can find mathematically that random numbers can be solved after placing on board or not.

Can anybody help to find the solution/algorithm/mathematical formula to determine that numbers can be solvable or not?

**Tags:** puzzles, board-game-adaptations

> **Comments:**
> **username_1**: This probably fits in better over at math.stackexchange under game theory: http://math.stackexchange.com/questions/754827/does-a-15-puzzle-always-have-a-solution  
> **username_2**: The mathematics is studied using Permutation Groups. Essentially all boards can be solved to either the correct solution, or the pseudo-solution with the 7 and the 8 swapped. An algorithm to generate valid boards might start by applying 1,000s of swaps randomly to a board that is known to be valid.  
> **username_3**: Or perhaps even better yet: the puzzling stack at http://puzzling.stackexchange.com/  

---

## 1 answers

### Answer by username_4 on 2014-11-24. Score: 7 | Accepted answer

This article has an extensive discussion of the solution:

<http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html>

The summary for the 3x3 board is:

> Lay out the board as a 9x1 row (row 1, then row 2, then row 3). Count the number of inversions (instances of a higher number coming before a lower number on this row). The board is solvable if and only if the number of inversions is even.

For example,

```
8   1   3
2       5
7   6   4

```

Written as a row is:

```
8, 1, 3, 2, , 5, 7, 6, 4

```

The 8 gives 7 inversions, the 1 gives none, the 3 gives 1 inversion, the 2 gives none, the 5 gives 1, the 7 gives 2, and the 6 gives 1. This example has a total of 12 inversions, which is even, so it is solvable.


---

