作成中
数独(ナンバープレース)は人気の高いパズルである.本屋のゲーム・パズルのコーナーに行けば数多くの問題本が並んでいる.将棋や囲碁の本に比べ圧倒的な数である.数独は2004年に英国の新聞タイムズに掲載されたのが始まりと言われている.今年でまだ6年しか経っていない比較的新しいパズルであるが,人気は今後も続くのであろうか.数独のよさは,ルールが単純で一人でできること,問題を解いたときの達成感が心地よいことなどであろう.解けないときは時間が瞬く間に過ぎてしまう.寝る前にはしない方がよい.睡眠不足に陥ること必定である.
 1. 数独のルールと解き方の基本 
   

数独の解法

解を演繹的に求めるための基本的方法は,空白のセルに入る候補数字を絞り込む(削減する)ことである.候補数字が1個に絞り込まれたとき,そのセルに入る数字が決定される.そこで候補数字削減のための具体的手法を以下に示す.
 2. テクニック1 
  条件1: 1行(1列)中の候補数aが同じボックスに含まれる.
処理:当該ボックスに含まれる他の候補数aを削除する.
  (例:第1, 6ボックス)

条件2:ボックス中の候補数aが1行(1列)のみに存在する.
処理:当該行(列)の他のボックスに含まれる候補数aを削除する.
  (例:第8ボックス)
 3. テクニック2 
  条件1:候補数aが第 i1行(列)と第 i2行(列)のそれぞれ2セルのみ
     に存在する.
条件2:条件1の下で,2組のaが同じ列(行)に含まれる.
    (aは長方形の頂点に位置する) 
処理:当該列(行)において,当該セル以外に存在するaを削除する.
条件3:条件1の下で,候補数bが2個ずつ同じボックスに含まれる.
処理1:ボックスに存在する他のbを削除する.
処理2:2個のbが同一列(行)に含まれる場合,当該列(行)の他のb
を削除する.
条件4:条件1の下で,3個のbが同じボックスに含まれる.
処理:残りのbは当該セルに決定する.
4. テクニック3  
  条件1:行または列を共有する2つのボックスにおいて,2つの同じ行
    (列)のそれぞれに1個の候補数aが存在する.
処理:当該行(列)の他のセルに含まれるaを削除する.

条件2:条件1の下で,候補数aが同じ列(行)に存在する.
処理:当該列(行)の他のセルに含まれるaを削除する.
 (例:第1,3ボックスで,第3ボックスのaは同じ第8列に存在する.
  従って,第8列の他のセルに含まれるaを削除.第7,8ボックスの
  第8行についても同様である.)
 5. テクニック4 
  条件1:a,bのみを候補とするセルが同一行(列)に2セル存在する.
処理:当該セルを含む行(列)とボックスに含まれる他のセルから候補
    a,bを削除する.
条件2:c,dを候補とするセルが同一行(列,ボックス)に2セル存在す
     る.
処理:当該セルからc,d以外の候補x,zを削除する.
条件3:c,dを候補とする2個のセルが同一行(列)かつ同じボックスに
     存在する.
処理:当該セルからc,d以外の候補x,yを削除し,更に同じボックスの
    他のセルからc,dを削除する. 
6. テクニック5 
   
 テクニック4の3候補数への拡張.
人が数独問題を解く際に使っているであろうテクニックをいくつか示した.人の記憶はあてにならないし,間違いを起こしやすい.そこで,上記のテクニックをパソコンのプログラムに組み込んでみた
( SUDOKU_SOLVER2010_VER2.EXE ).これ以外にも色々なテクニックが知られているし,まだ知られていないテクニックも存在すると思われる.演繹的に解を求めるために知られたテクニックを全て組み込むべきであるが,所要時間を考慮して,上記のテクニックで解けない場合は試行錯誤を実施することにしている.試行錯誤の方法は,空白セルに残された候補数字を選び,上記テクニックによる解法を進める.途中で手詰まりになったら次の候補数字に移る.最後に矛盾が生じた場合は,選んだ候補数字を削除して次の候補数字に移る.いずれかの候補数字を試して解に至ればそれを解として示す.複数解が存在する場合もあるが,それは無視している.また,残された候補数字全てを試しても解に至らない場合がある.このときは,第2レイヤーの探索をしなければなないが,時間がかかりすぎるためお手上げとしている.
数独問題の作成

数独問題の作成には,まず解答を用意して,そこから空白セルを設定し,演繹的に解けることを確認しなければならない.作ることのできる解答数はいくつ存在するかを知ることは興味深い問題である.9×9の盤面上,制約なしに1から9の数字を配置する場合の数は,(9!)91.1×10500.011恒河沙)である.しかし,図1に示した数独の規則があるため,解答数はずっと少なくなる.場合分けでカウントすると,1,783,937,121,022,672,675,799,0401.78×10241.78?となり,とても少ないと言える数ではない(この数字が正しいかどうか未確認).ただし,ランダムに数字を配置して解答となる確率は1.6×10-261.6涅槃寂静)であるから,規則に従う制約条件を入れて数独問題の作成プログラムを作成した(PROBLEM_MAKER2010_VER2.EXE.空白セルを多くする(開示セルが少ない)と解の一意性が小さくなるため,問題として成立する確率が極端に小さくなり,開示セル20以下を作成するのは容易でない.


パソコンゲームに戻る