检查 15 个谜题是否可解

Question

我正在尝试测试是否可以解决 15 的难题。我写了一个适用于大多数谜题的方法，但对某些谜题无效。

例如这个谜题可以用两步 (0, 11), (0, 12)

1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 0, 11, 13, 14, 15, 12

这里是更直观的拼图：

1   2   3   4   

5   6   7   8   

9   10  0   11  

13  14  15  12

但是这个谜题的奇校验为 3，所以应该无法解开。

public boolean isSolvable(int[] puzzle)
{
    int parity = 0;

    for (int i = 0; i < puzzle.length; i++)
    {
        for (int j = i + 1; j < puzzle.length; j++)
        {
            if (puzzle[i] > puzzle[j] && puzzle[i] != 0 && puzzle[j] != 0)
            {
                parity++;
            }
        }
    }

    if (parity % 2 == 0)
    {
        return true;
    }
    return false;
}

我做错了什么？

Answer 1

I found these 任何 N x N 谜题需要检查的条件，以确定它是否可解。

显然，由于你的空白图块在偶数行（从底部开始计算），奇偶校验是奇数，而你的 grid-width 是偶数，所以这个谜题是可以解决的。

这是根据link中的规则进行检查的算法：

public boolean isSolvable(int[] puzzle)
{
    int parity = 0;
    int gridWidth = (int) Math.sqrt(puzzle.length);
    int row = 0; // the current row we are on
    int blankRow = 0; // the row with the blank tile

    for (int i = 0; i < puzzle.length; i++)
    {
        if (i % gridWidth == 0) { // advance to next row
            row++;
        }
        if (puzzle[i] == 0) { // the blank tile
            blankRow = row; // save the row on which encountered
            continue;
        }
        for (int j = i + 1; j < puzzle.length; j++)
        {
            if (puzzle[i] > puzzle[j] && puzzle[j] != 0)
            {
                parity++;
            }
        }
    }

    if (gridWidth % 2 == 0) { // even grid
        if (blankRow % 2 == 0) { // blank on odd row; counting from bottom
            return parity % 2 == 0;
        } else { // blank on even row; counting from bottom
            return parity % 2 != 0;
        }
    } else { // odd grid
        return parity % 2 == 0;
    }
}

检查 15 个谜题是否可解

Check if 15 puzzle is solvable

java

sliding-tile-puzzle