我了解到,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,则可解性检查将起作用。但是,如果目标状态为 Goal state1,则它不起作用。
反转计数可以是奇数或偶数,简而言之,我们可以将状态称为偶数或奇数。这称为州平价。如果开始状态是偶数,那么它是可解的。在引用的文章中,这确实意味着目标必须是具有增量顺序的目标。
但是,由于实际上存在两类状态(基于平价),并且您只能通过采取合法行动来保持在这两类状态之一内 - 即当您采取合法行动时,奇偶校验是不变的 - 这个原则可以扩展到任何目标状态:
如果起始状态的奇偶校验与目标状态的奇偶校验相同,则它是可访问的(可解决的)。
在您给出的示例状态中,起始状态是奇数,第一个目标状态也是奇数。所以它们属于同一类,一个可以从另一个到达。
下面是 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>
是的,它确实有效。有一种非常微不足道的方式来显示这一点。只需将解决方案中的值映射到假设您的 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
...
现在,将此表应用于开始状态,方法是将每个值替换为映射到的值,以过去对 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答案。