8つのパズルソルバビリティルールはどの目標状態でも機能しますか？

Question

Iveは、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 

今私のobeservationがゴール状態は一例でゴールSTATE2であれば可解性のチェックが働くだろう、ということです。しかし、目標状態が目標状態1であれば動作しません。

Answer 1

反転カウントは奇数または偶数にすることができ、簡単に偶数または奇数を呼び出すことができます。これは、状態のパリティと呼ばれます。開始状態が偶数の場合、それは解決可能です。参照されている記事では、実際には、ターゲットがインクリメンタルオーダーのターゲットでなければなりません。

しかし実際には（パリティに基づいて）州の2つのクラスがあり、法的手続きを行うことによってこれらの2つのクラスのうちの1つにしか入らないことができます。

開始状態のパリティがターゲット状態のパリティと同じ場合、それは到達可能（解決可能）です。

例の状態では、開始状態は奇数で、最初のターゲット状態も奇数です。だから彼らは同じ階級に属し、もうひとつは他の階に到達することができます。

ここでは、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 
... 

は今それがマッピングされています1でそれぞれの値を置き換えることで、あなたのスタート状態にこの表を適用し、 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 answerをご覧ください。