8 个难题可解性规则是否适用于任何目标状态？

Question

我了解到可以通过遵循特定规则来检查 8 字谜题的可解性。 https://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html

http://ldc.usb.ve/~gpalma/ci2693sd08/puzzleFactible.txt.

我的问题是这种可解性检查是否仅在目标状态（解决方案）处于正确的升序时才适用？示例：

   Start state
    3   1   5 
    6   0   4 
    2   7   8

    Goal state1        Goal State2
    3   1   5           1   2   3
    6   4   8           4   5   6
    2   0   7           7   8   0

现在我的观察是，如果示例中的目标状态是目标状态 2，则可解决性检查将起作用。但是如果目标状态是目标状态1，它就不起作用了。

Answer 1

反转计数可以是奇数也可以是偶数，简而言之，我们可以称一个状态为偶数或奇数。这被称为状态的 parity。如果起始状态是偶数，那么它是可解的。在参考文章中，这确实意味着目标必须是具有增量顺序的目标。

但由于实际上有两个 class 状态（基于奇偶校验），您只能通过合法移动保持在这两个 classes 之一内 - 即奇偶校验当你进行合法移动时是不变的——这个原则可以扩展到任何目标状态：

如果起始状态的奇偶校验与目标状态的奇偶校验相同，那么它是可达的（可解的）。

在你给出的示例状态中，起始状态是奇数，第一个目标状态也是奇数。所以他们属于同一个class，一个可以从另一个到达。

这里是 JavaScript 中奇偶校验的简单实现。它也适用于均匀大小的网格：

function parity(grid) {
    var inversions = 0;
    // take copy and remove blank (0) from it.
    var arr = grid.slice(0);
    arr.splice(arr.indexOf(0), 1);
    // perform sort and count swaps
    for (var i = 1; i < arr.length; i++) {
        for (var j = i - 1; j >= 0; j--) {
            if (arr[j] <= arr[j+1]) break;
            [arr[j+1], arr[j]] = [arr[j], arr[j+1]];
            inversions++;
        };
    }
    if (grid.length % 2 == 0) { // even grid width
        var size = Math.round(Math.sqrt(grid.length));
        var blankRow = Math.floor((grid.length - 1 - grid.indexOf(0)) / size);
        inversions += blankRow;
    }
    return inversions & 1; // only odd/even is needed as info
}

document.querySelector('button').onclick = function() {
    var res = '';
    var txt = document.querySelector('textarea');
    var grid = txt.value.trim().split(/[,\s]+/g).map(Number);
    var size = Math.round(Math.sqrt(grid.length));
    var res = size*size !== grid.length
            ? 'input is not a complete square matrix of data'
            : 'parity = ' + parity(grid);
    document.querySelector('pre').textContent = res;
}

Enter grid. 0 represents empty slot.<br>
<textarea rows=4>3   1   5 
6   0   4 
2   7   8
</textarea><button>Verify</button><br>
<pre></pre>

Answer 2

是的，它确实有效。有一种非常简单的方式来展示这一点。只需将解决方案中的值映射到假设您的 GoalState2 的值，检查对其有效：

state we want to reach   Goal State2
3   1   5                1   2   3
6   4   8                4   5   6
2   0   7                7   8   0

map:
3 -> 1
1 -> 2
3 -> 5
...

现在将此 table 应用到您的起始状态，通过将每个值替换为它映射到的值，以您用于 GoalState2 的方式解决整个问题，并反转最终的映射-状态。如果存在，您就会得到想要的结果。并且可以重用可解性规则而无需对其进行任何更改，只需使用简单的重新映射即可。

这是如何工作的示例：

state we want to reach   Goal State2
3   1   5                1   2   3
6   4   8                4   5   6
2   0   7                7   8   0

build map

map:
3 -> 1
1 -> 2
3 -> 5
...

Start state
3   1   5   apply map  1  2  3  solve for  1  2  3  apply        3  1  5
6   0   4   -------->  4  8  5  -------->  4  5  6  --------->   6  4  8
2   7   8              7  0  6   GoalS2    7  8  0  reverse map  2  0  7

这是最简单的解决方法。只要将数字视为没有任何意义的标签，您就已经完成了一半。

要获得更复杂的答案，让您更好地理解规则本身，请查看@trincots 的答案。

8 个难题可解性规则是否适用于任何目标状态？

Does 8 puzzle solvability rules work for any goal state?

algorithm

sliding-tile-puzzle