2009年8月2日日曜日

(30) Aサーチ(仮定法)の候補の選択方法

 Sudoku_Ver.14 において、新しく購入した「激辛1」の衝撃の105問を、Sheet12のインプット・シートとして使う。(isheet) Sheet13 は dsheet (解答シート)とする。

 A サーチは二つの候補を持つセルを選び、そのうちの一つを仮定して先の計算を進める。どちらかが正解なのだが、選びようによっては、また仮定する必要がでてくる。プログラムでは、5階層まで扱えるようにはなっているが、計算時間が掛かったり、答えに至らない場合がある。

そこで、二つの候補をもつセルの選び方を変えてその状況を調べてみた。正回転はBlock 1 から最初に出てきたセルを選択、逆回転とは、Block 9 から逆に探し出したセルから取り出す。中央回転とは、empty_cell の真ん中から最初のものをとる場合である。

 「激辛 Vol.3」の問題を例にとり、試してみた結果は次の通りである。
            正回転     逆回転   中央回転
 問題 32番    47         19      7 
 問題 35番    9          57      52
 問題 44番    27         -      61
 問題 68番    28         -      24
 問題 70番    58         22      29
 問題 80番    31         68      19
 問題 90番    15         80      12
 問題 99番    65         -      60
 問題 100番   -         18      10
 問題 104番   61         25      48
 ここに、「-」は解が得られなかったもの(5階層以上)である。

仮定法において、どのセルの候補を選ぶと効率よく解がえられるかはまだ理論はない。

0 件のコメント:

コメントを投稿