48332


**8パズルで、解けないような配置になることはありますか？**  
・最初にシャッフルさせる場合、単純にランダム配置させるだけでは駄目？

[code]

    123
    456
    78
    
[/code]

* * *

**経緯**  
・ネットに掲載されていた8パズルを試しているのですが、どうしても解けないときがあります  
・コード内容によっては、解けない8パズルが出来ることもある？

**分からないこと**  
・参考にしているコードが、そもそも正しいか分からない  
・８パズルのコードを探すときはどこに注目すればよいですか？


CC BY-SA 4.0
2018-09-11T04:00:11.880
48268
2018-09-12T18:50:32.767
7886
question
javascript アルゴリズム
８パズルで、最初にシャッフルさせる時の考え方


> 8パズルで、解けないような配置になることはありますか？

あります。より単純化した2x2の3パズルで、以下の例を考えると良いでしょう。

[code]

    |1, 2|
    |3, _|
    
[/code]

上記のパズルを以下のようにスライドさせることは不可能です。

[code]

    |1, 3|
    |2, _|
    
[/code]


CC BY-SA 4.0
2018-09-11T04:04:32.753
48269
2018-09-11T04:13:11.857
2018-09-11T04:13:11.857
29826
29826
48268
answer


# どうやってランダム生成するか?

  1. 1~9 の並べ替えをランダムに生成する
  2. 以下の判定問題を解く
  3. (もし解けないことが分かったら) 9 (空ブロック) 以外の2つの異なるブロックをランダムに選んで入れ替える

## 問題の定式化

[code]

    問題    正解
    31_    123
    275 -> 456
    684    78_
    
[/code]

上記のような盤面であったとき、これは以下のような並べ替え問題であると考える。

[code]

    3  1  _  2  7  5  6  8  4
                ↓
    1  2  3  4  5  6  7  8  _
    
[/code]

## 解けるかどうかの判定方法:

  * とにかく何も考えずに、与えられた状態から2要素を入れ替えていって、何回入れ替えを行ったらゴールに辿りつくかを数える (A とする)
  * 空きブロックが、最終的な到達地点(この場合は右下)から、何マス離れているか数える (B とする)

A と B の偶奇が一致していれば解ける。

## 実際に解く

### A の求め方例

[code]

    3  1  _  2  7  5  6  8  4  // (1 3) を入れ替え
    1  3  _  2  7  5  6  8  4  // (2 3) を入れ替え
    1  2  _  3  7  5  6  8  4  // (3 _) を入れ替え
    1  2  3  _  7  5  6  8  4  // (4 _) を入れ替え
    1  2  3  4  7  5  6  8  _  // (5 7) を入れ替え
    1  2  3  4  5  7  6  8  _  // (6 7) を入れ替え
    1  2  3  4  5  6  7  8  _  // ゴール
    
[/code]

### B の求め方

[code]

    31_
    275
    684
    
[/code]

の場合、`_`は右下から上*2 だけ離れている。なので B は 2.

A=6, B=2 と、それぞれが両方とも偶数なので、このパズルは解けることが分かる。

# javascript のコードにしてみると

[code]

    const randomN = (n) => Math.floor(Math.random() * n)
    
    const swap = (arr, i, j) => {
      const tmp = arr[i]
      arr[i] = arr[j]
      arr[j] = tmp
    }
    
    const numSwap = (arr, verbose = false) => {
      const copied = [].concat(arr)
      let count = 0
      for (let i = 0; i<copied.length; i++ ) {
        if (copied[i] != i+1) {
          const j = copied[i] - 1
          swap(copied, i, j)
          i--
          count++
          if (verbose)
            console.log(`[ ${copied.join(', ')} ]`)
        }
      }
      return count
    }
    
    const blankGoalDistance = (arr, n, m) => {
      const blank_index = arr.indexOf(n * m)
      return m - 1 - blank_index % m + n - 1 - Math.floor(blank_index / m)
    }
    
    const generate = (n, m = n) => {
      const total = n * m
      const vals = Array.from(new Array(total),(val,index)=>index+1)
      const ret = []
      while (vals.length > 0) {
        ret.push(vals.splice(randomN(vals.length),1)[0])
      }
      blank_index = ret.indexOf(total)
      const distance_to_bottom_right = blankGoalDistance(ret, n, m)
      if ((distance_to_bottom_right + numSwap(ret)) % 2) {
        let i = randomN(total - 1)
        if (i >= blank_index)
          i++
        let j = randomN(total - 2)
        if (j >= Math.min(i, blank_index))
          j++
        if (j >= Math.max(i, blank_index))
          j++
        swap(ret, i, j)
      }
      return ret
    }
    
    
    board = generate(3)
    console.log("----")
    console.log(`[ ${board.join(', ')} ]`)
    console.log("----")
    console.log("board swaps: " + numSwap(board, true))
    console.log("dist: " + blankGoalDistance(board, 3, 3))
[/code]

### 出力例

[code]

    ----
    [ 1, 9, 8, 6, 5, 2, 4, 3, 7 ]
    ----
    [ 1, 7, 8, 6, 5, 2, 4, 3, 9 ]
    [ 1, 4, 8, 6, 5, 2, 7, 3, 9 ]
    [ 1, 6, 8, 4, 5, 2, 7, 3, 9 ]
    [ 1, 2, 8, 4, 5, 6, 7, 3, 9 ]
    [ 1, 2, 3, 4, 5, 6, 7, 8, 9 ]
    board swaps: 5
    dist: 3
    
[/code]

# 何故解けないかの数学的な説明

上記のように、 8 パズルは、要素9の並べ替え問題とみたてることができる。並べ替えは、上記の具体例のように、2要素の入れ替えを組み合わせることで実現できる。

数学的には、ある並べ替えが与えられたとき、それを2要素の入れ替えの組み合わせとして表わしたときに、その2要素入れ替えの個数の偶奇が、必ず一定になることが分かっている。
<https://ja.wikipedia.org/wiki/%E7%BD%AE%E6%8F%9B%E3%81%AE%E7%AC%A6%E5%8F%B7>

8
パズルを実際に解いているところを想像すると、ブロックを動かすことは、その2つの要素を入れ替えていることに相当するので、この問題は、ある種の制限がかかった、並べ替えの入れ替えへの分解問題だと見ることができる。

その中でも、空ブロックは毎回動かなれけばならない、という性質がある。毎回動くので、ゴール地点からの距離の偶奇も、毎回変わる。このゴール地点からの距離の偶奇と、並べ替えを入れ替えへと分解したときの偶奇が一致していなければ、そもそもその盤面は解くことができないことがわかる。

# 偶奇さえ一致していれば必ず解けることの説明

Modern Treatment of the 15 Puzzle
参照。<http://www.cs.cmu.edu/afs/cs/academic/class/15859-f01/www/notes/15-puzzle.pdf>

15 パズルの操作を合成することでたしかにすべての偶数並べ替えが生成されることを示している。

おおまかな証明の流れ:

  1. 空きブロックをスキップしてラベリングして 1~15 の並べ替え問題に帰着
  2. 3-cycle (ある3つの要素のみを循環させる並べ替え) のみで全ての偶並べ替えが生成できること
  3. consecutive 3-cycle たちからすべての 3-cycle が生成されること
  4. 実際に 15 puzzle 入れ替えオペレーションからすべての consecutive 3-cycle が生成できること


CC BY-SA 4.0
2018-09-12T16:55:28.213
48332
2018-09-12T18:50:32.767
2018-09-12T18:50:32.767
754
754
48268
answer