読者です 読者をやめる 読者になる 読者になる

15パズルの課題(工事中)

目次へ

課題1

  • 本論文では生成元として3項巡回置換を使っている。本論文のように取り上げた理由と背景を理解する。

課題2 ( 解決済み )

  • 実際のゲームではブランクをスライドして解答を求める。3項巡回置換をブランクのスライドの手順として求める。
  • ブランク(16) の移動を、番号のついたタイルとブランクの"互換"として表現する。
  • ブランク(16) の移動に関してはルールベースプログラムで実現する。
  • 2つの関数 try12 と tryBlankMoveFixedCycles で実現できた。
  • 関数 try12 の説明
    1. 初めの配置を start とし3項巡回置換を cycles をする。
    2. cycle を start に作用させた後の配置を destination をする。
    3. try12[ start, desination, cycles ] でブランクの互換として求めることができる。
    4. しかしながら効率が悪いことが分かった。その解決方法として次の関数を作った。
  • 関数 p = tryBlankMoveFixedCycles の説明
    1. cycles に含まれる数のタイルからマンハッタン距離が最も小さい位置 neibour を決める。
    2. cycles に含まれる数のタイルを固定してブランクを位置 neibour に移動させる手順を求める。
  • 以上の関数を使って形式的に次のように表現できる。ここで  p^-1 は p の逆とする。
      p^-1 [ try12[ p[ start, destination, cycles ] ] ]

課題3

  • ブランクの位置は右下端以外の場所にある配置からゲームを始める場合、この論文の方法では答えを見つけることができない。何故ならブランク(16)を含む3項巡回置換の生成元を含んでいないからである。従ってこの論文は特殊なケースについての解法である。
  • ブランクが右下端以外の場所にある配置からゲームを始める場合、次のように実行すればよいことに気がついた。
    1. 
    ブランクを右下端に移動する。
    2. この配置で 群論を使った解法手順を決める。
  • ブランクを右下端に移動させる関数として tryBlankMove44 を作ることができた。

課題4 ( 解決済み )

15パズルを Grid を使って表示する。3項巡回のタイルに色を付けて表示する。

課題5 ( 解決済み )

3 項巡回をブランクのスライドで表現する"互換"を求める関数 try12 を作ったが、効率が悪いので改善を試みる。その方策として

  • ブランクの移動を3項巡回置換の付近に制限すればよい。

目次へ