How to programmatically solve the 15 (moving numbers) puzzle?
all of you have probably seen the moving number/picture puzzle. The one where you have numbers from 1 to 15 in a 4x4 grid, and are trying to get them from random starting position to
1 2 3 4
5 6 7 8
9 10 11 12
13 14 15
My girlfriend or some of my non-programmer friends can solve this with some mumbo-jumbo magic, that they can't explain to me. I can't solve the puzzle.
The most promising approach I have found out is to solve first row, then I'd get
1 2 3 4
X X X X
X X X X
X X X
then first column without touching solved cells
1 2 3 4
5 X X X
9 X X X
13 X X
then second row to
1 2 3 4
5 6 7 8
9 X X X
13 X X
then second column
1 2 3 4
5 6 7 8
9 10 X X
13 14 X
the problem is, that remaining X (random) tiles are sometimes in unsolvable position and this is where my solution fails. But I feel as if I'm on the right path.
My program does the solving of specified row/column by trying to get number X to specified position without messing up the correct cells, if possible. But it can't do the last 3 tiles on 2x2 grid. What am I missing?
3 ответа
Вы определенно на правильном пути, но вместо того, чтобы итеративно решать по строкам/столбцам до точки 2x2, решайте до тех пор, пока у вас не будет минимум 3x3, а затем решайте только эту сетку. 3x3 — это наименьший размер, необходимый для правильного изменения порядка сетки (в то время как 2x2 не дает вам полной гибкости, которая может вам понадобиться, как вы уже обсуждали). Этот подход также является масштабируемым — вы можете решить 5x5, 10x10 и т. д.
На этом сайте есть хорошее объяснение сетки 3x3, вы, вероятно, могли бы легко расширить его до 4x4.
Редукцией единственный возможный случай, который вы не можете решить, должен иметь вид
1 3
2 X
, и вы хотите получить его к
1 2
3 X
с помощью дополнительной строки и столбца вы можете переместить их в нужные позиции с помощью простой предварительно вычисленной последовательности