電子情報工学特別実験 (森研究室) 制約充足問題を解くプログラムの作成 '94 --- パズル「数独(ナンバープレース)」を解こう --- 解説編 森辰則 １. はじめに 森研究室の院実験はいまのところ，毎年(といってもまだ2年目ですが:))パズ ルを解くプログラムを作成するという課題をだしています．パズルを解くとい うのは，人工知能の分野でいうところの「制約充足問題」になることが多いの でそのさわりでも実感してもらう，というのが建て前です(笑)．それも理由の 一つではあるのですが，(一般のアルゴリズムの本などで紹介されているなど という意味で)すでに解法がわかっている問題をやってもおもしろくはなかろ う，ついでに，遊び心もいれてしまえ，というのが裏の理由です． 去年は，「イラストロジック」というパズルを出題しました．このパズルは問 題を解くと絵が現れるというもので，華やかさがあるのですが，多少，難度が 高かったようで，みなさん苦労されたようです．(去年の課題ならびに解説も annonymous FTPにより公開しております．詳しくはそちらをご覧ください． ftp://ftp.forest.dnj.ynu.ac.jp/doc/MExperiment/93 にあります) その反省もありまして，今年は華やかさにかけますが，多少難度が低めの問題， 「数独」を選びました． 2. パズル「数独」とは パズル「数独」は「ナンバープレース」とも呼ばれます．「数独」の名はパズ ル雑誌「ニコリ」で使われているもので，「数字は独身者に限る」を省略した ものだそうです． 数独の盤面は9x9の広さを持つ方眼です．25x25の問題など大きいものもありま すが，ここでは9x9に限定します．この方眼は3x3の小さい方眼(ここではグルー プと呼ぶことにします)を縦横3x3に組み合わせたものとなっています．このパ ズルは以下のルールに従ってすべてのマスに1から9までのいずれかの数字を配 置することを目的とします． ルール1: 各行のそれぞれマスには1から9までの別々の数字が1つづつ 配置される． ルール2: 各列のそれぞれマスには1から9までの別々の数字が1つづつ 配置される． ルール3: 各グループのそれぞれのマスには1から9までの別々の数字 が1つづつ配置される． 百聞は一見にしかず，例を見てみましょう． +=======+=======+=======+ | A 8 2 | . . 7 | . 9 . | | 5 . . | 3 . 4 | . 2 1 | | 3 . . | 1 . . | 6 . . | +=======+=======+=======+ | . 5 8 | 7 . . | . 1 4 | | . E . | . 2 . | . . . | | 6 4 . | . B 3 | 2 8 . | +=======+=======+=======+ | . . 9 | . . 6 | C . 5 | | 8 3 . | 2 . 1 | . . 7 | | . 6 D | 9 . . | 8 4 . | +=======+=======+=======+ 図1 数独の問題例 盤面上で空白(分かり易さのために，例ではピリオド(.)を入れている)の部分 に数字を配置します．このとき，先ほど述べたルールにより，各行，各列，各 グループで重複しないように配置します．ただし，上記例において，AからDま での記号は説明上配置したものであって，ここも空白だと思ってください． この例題において，まず，1に注目してみましょう．Aのあるグループでは，下 の行と中の行には1を置くことができませんから，上の行で唯一空いているAに 1が入ります．Bのあるグループでは，左の列，右の列ならびに上の列には1を 置くことができませんので，残るBが1となります．同じように考えて，C,D,E も1となることがわかります． 同様にして，ほかの数字も埋めていくと，最終的には，図2の解を得ます． +=======+=======+=======+ | 1 8 2 | 6 5 7 | 4 9 3 | | 5 9 6 | 3 8 4 | 7 2 1 | | 3 7 4 | 1 9 2 | 6 5 8 | +=======+=======+=======+ | 2 5 8 | 7 6 9 | 3 1 4 | | 9 1 3 | 4 2 8 | 5 7 6 | | 6 4 7 | 5 1 3 | 2 8 9 | +=======+=======+=======+ | 4 2 9 | 8 7 6 | 1 3 5 | | 8 3 5 | 2 4 1 | 9 6 7 | | 7 6 1 | 9 3 5 | 8 4 2 | +=======+=======+=======+ 図2 図1の解 2. 数独解法のための基本的な考え方 前節で述べた数独を解くプログラムを作成することが，この実験の課題でした． 基本的には，ルール1からルール3までを何らかの形で制約として考え，これを 満足するように数字を配置するプログラムになります． 制約充足問題は何らかの形で解を生成しないといけません．「充足」というと 何かすでに解の候補があって，それに対して制約を満足しているかどうかを調 べるだけ，というような響きがありますが，そうではありません．その解の候 補も生成する必要があります． 制約充足可能性を判定するアルゴリズムとして最も単純なものの一つは， 生成・検査型のアルゴリズムです． 例えば，二つの制約A,Bを同時に満足する解を求めるためには，次のように制 約Aを用いてAを満足する解を生成し，次にその解が制約Bを満足するかどうか を調べます． (1) 制約Aから生成可能な解を一つ求める． (2) その解がもう一方の制約Bを満足するかを検査する． (3) 満足する場合は充足可能なので終了． (4) 満足しない場合は制約Aから別の解を生成する． 別の解が生成できないのであれば，充足不能である． 生成できる場合は(2)へ行く． 今回の問題のように解の範囲がわかる場合には一部の制約から解を生成するの ではなく，制約とは独立に生成し，上記(2)ですべての制約を満足するか検査 するようにしてもよいでしょう．たとえば，各々の空白のマスには1から9まで の数を配置できますから，はじから数字をすべて配置し，配置し終わった盤面 がルール1からルール2を満足するかどうかを調べればよいわけです．しかし， この生成・検査型のアルゴリズムをそのまま用いると，効率が非常に悪くなり ます． 生成・検査型のアルゴリズムの効率の悪さを克服するにはいくつかの方法があ りますが，この問題のように未定要素部分(この問題では各マスにあたる)が有 限の値域をもつ場合には，その値域情報を扱う方法があります．つまり，未定 要素に対して値の候補の集合を付加し，各制約によりその値域を狭めていく方 法です．値の候補が一つになったときに，その未定要素が確定します．また， 値の候補がなくなった場合にはその問題は充足不能であることがわかります． ちなみに，レポートの課題に出した問題は以下の3問でした．このうち，問1が 必修問題です．(もともと人間が解く問題ですから，このまま解いてもおもし ろいですよ．パズルがすきならば :p ) +=======+=======+=======+ | . . 5 | 1 . 4 | 3 . . | | . . 4 | 2 . 9 | 7 . . | | 9 2 . | . . . | . 4 8 | +=======+=======+=======+ | 1 9 . | 5 . 8 | . 7 3 | | . . . | . 9 . | . . . | | 5 4 . | 3 . 7 | . 1 2 | +=======+=======+=======+ | 2 1 . | . . . | . 5 4 | | . . 3 | 7 . 5 | 2 . . | | . . 9 | 8 . 2 | 1 . . | +=======+=======+=======+ 問1 +=======+=======+=======+ | . . . | . 1 2 | . . . | | . 1 4 | . . . | . . . | | . 3 6 | . . 7 | 8 . . | +=======+=======+=======+ | . . . | . . 6 | 9 . 5 | | 5 . . | . . . | . . 2 | | 4 . 7 | 3 . . | . . . | +=======+=======+=======+ | . . 1 | 9 . . | 2 3 . | | . . . | . . . | 4 8 . | | . . . | 8 4 . | . . . | +=======+=======+=======+ 問2 +=======+=======+=======+ | . . . | . . 3 | 4 . . | | 1 2 . | . . . | . 5 7 | | . . 3 | 4 . . | . . . | +=======+=======+=======+ | 7 . . | . 5 6 | . . . | | . 5 6 | . . . | 7 8 . | | . . . | 7 8 . | . . 9 | +=======+=======+=======+ | . . . | . . 1 | 2 . . | | 6 7 . | . . . | . 3 4 | | . . 8 | 9 . . | . . . | +=======+=======+=======+ 問3 3. レポート総評 みなさんの考えてくれた方法は，未定要素に値域を付加する方法と生成検査型 に大別されました．さらに詳しく分けると以下のようになりました．ただし， 同じ分類に入っているものでも，値域の取り方が様々だったり，値域を陽に与 えず，必要になるたびに計算する方法があったりするなど，若干異なるところ があります．これは，考え方の本質が同じものをまとめたためです． ------------------------------------------------------------------------------- 方法 人数 解答可能問題(3題出題) ------------------------------------------------------------------------------- 値域付加 3 1 (マス) 値域付加 1 1,2,3 (マス，候補出現回数チェック) 値域付加 1 1 (行,列,グループ) 値域付加+生成検査 2 1,2,3 (行,列,グループ) 生成検査+値域付加(一部) 1 1,3 ------------------------------------------------------------------------------ ぼくも(当然ですが)実験の問題として出題するまえにプログラムを作成するの ですが，そのプログラムで採った方法は後で述べるように「値域付加(マス， 候補出現回数チェック)」でした． さて，それぞれについてみていきましょう． まず，生成検査型のものから述べます．この方法を採っている人はグループを 中心に調べていました．具体的には， 1) グループ内で未確定の数字を取り上げ，その数字が入り得るマス を行ならびに列の制約を適用しつつ調べる． 2) それが1つなら確定．2つ以上なら，次のグループを調べる． という方法です．例えば，図1に1を配置する場合を考えます． +=======+=======+=======+ | A 8 2 | . . 7 | . 9 . | | 5 . . | 3 . 4 | . 2 1 | | 3 . . | 1 . . | 6 . . | +=======+=======+=======+ | . 5 8 | 7 . . | . 1 4 | | . E . | . 2 . | . . . | | 6 4 . | . B 3 | 2 8 . | +=======+=======+=======+ | . . 9 | . . 6 | C . 5 | | 8 3 . | 2 . 1 | . . 7 | | . 6 D | 9 . . | 8 4 . | +=======+=======+=======+ 図1 (再掲) 左上のグループにおいて，空が5箇所あります．ここに1を配置する場合を考え ます．仮に，配置可能な場所にO，配置不能な場所にxをマークすることにしま しょう．そうすると， +=======+=======+=======+ | O 8 2 | . . 7 | . 9 . | | 5 x x | 3 . 4 | . 2 1 | | 3 x x | 1 . . | 6 . . | +=======+=======+=======+ となります．ここでOは一つだけですから，1をここに配置してよいことがわか ります．これをすべてのグループ，すべての数について行います． この方法では問1しか解くことができません．そこで，この方法をとった人は さらに， 3) 決まらない場合には特定のマスについて入りうる候補を生成，候 補が1つののマスを確定する． という値域付加型の手法を部分的に取り入れて，問3を解けるようにしていま した．ただし，値域付加型でも工夫をしないと全問解けないように，この拡張 版でも全問は無理でした． 次に，主流派であるところの，値域付加型について述べます．この問題の値域 は，あるマスもしくは，行・列・グループに属す可能性のある候補の集合です． よって，初期値は，いずれも， {1,2,3,4,5,6,7,8,9} という集合になります． 上の表にあるようにこの値域をどこに付加するかによって，次の2通りがあり ました． a)マスに対する値域付加 現時点でそのマスに入り得る数字の集合．要素数が1になったとき に，そのマスを確定できる． b)行，列，グループに対する値域付加 これはその行(列，グループ)に入り得る数字の集合を表しているの ではなく，その行においてまだ配置されていない数字の集合を表し ている．よって，要素数が0になったときにその行はすべて確定し たことになる． 前者と後者は表現している情報は同じですが，変換のためには若干の計算を必 要とします．(あるマスが属する行,列,グループに付加されている値域の交わ り(intersection)を計算すると，そのマスに入り得る数字の集合を得ることが できる．) 例をみてみましょう． 1 2 3 4 5 6 7 8 9 +=======+=======+=======+ | A 8 2 | . . 7 | . 9 . | 1 | 5 . . | 3 . 4 | . 2 1 | 2 | 3 . . | 1 . . | 6 . . | 3 +=======+=======+=======+ | . 5 8 | 7 . . | . 1 4 | 4 | . E . | . 2 . | . . . | 5 | 6 4 . | . B 3 | 2 8 . | 6 +=======+=======+=======+ | . . 9 | . . 6 | C . 5 | 7 | 8 3 . | 2 . 1 | . . 7 | 8 | . 6 D | 9 . . | 8 4 . | 9 +=======+=======+=======+ 図1 (再掲) 前者の方法では，最初，第1行,第1列のマス(A)には {1,2,3,4,5,6,7,8,9} が割り当てられていますが，同じ行に，8,2,7,9, 同じ列に，5,3,6,8,同じグ ループに，8,2,5,3がありますので，ルール1,2,3に示される制約によりこれら を除いた， {1,4} が現時点でこのマスに課せられた局所制約を満足する解になります．もちろん， ほかのマスの制約を解いていませんので，これがそのまま解になるわけではあ りません．あくまでも現時点で，ということです． 現時点では{1,4}と候補が二つありますが，後に同じ行(列)に4が確定しますの で，その時点で1だけが候補になり，このマスが1に確定します． この操作を繰り返し行うことにより候補が次第に狭められます． 後者の方法では，第1行,第1列,第1グループというように，列，行，グループ に対して集合を付加します．例えば，上の例では，まず， 第1行 {1,2,3,4,5,6,7,8,9} 第1列 {1,2,3,4,5,6,7,8,9} 第1グループ {1,2,3,4,5,6,7,8,9} ですが，第1行には，この時点ですでに，8,2,7,9が配置されており，第1列に は，5,3,6,8，第1グループには 8,2,5,3が配置されていますから，以下のよう になります． 第1行 {1,3,4,5,6} 第1列 {1,2,4,7,9} 第1グループ {1,4,6,7,9} これらの交わりをとると{1,4}となり先ほどのマスに付加された値域の場合と 同じになります． しかし，これらの方法ではマスに多くの数が配置されている場合には解けます が，問2,問3のように数がすくなくなると解けません．この問題を解決一つの 方法は，確定できないマスをひとまず，ある値に仮定し，その下でほかの値を 決定し，うまくいけばOK，矛盾が生じたら最初の仮定を修正するという生成検 査型の方法を組み合わせるものです．探索を導入するわけです．これにより解 いている人が2人いました． ところで，最初の数独の説明ではAは真っ先に確定されたことを覚えています か? 前に述べた生成検査型の方法でも1サイクル目(すべてのマスに対する制約 を考慮し次の候補を決める過程を1サイクルとして)で決まりました．それに対し て，いま上に述べた普通の値域付加法では1サイクル目では決定されず，確定 までに数サイクルを必要とします．これは，まだ，使える情報があるはずであ ることを示しています．1サイクル目が終わった後の第1グループの中をみてみ ましょう． +===================+ | {1,4} 8 2 | | 5 {7,9} {6,7} | | 3 {7,9} {4,7} | +===================+ こうしてみると第1行,第1列のマスにしか1の候補がありません．また，6,4に ついてもそれぞれ1箇所にしかありません．いまはグループについてみました が，行，列についても同じことがいえます．すなわち，ある行・列・グループ において，候補となっている数字があるマスにしか現れていない場合には，そ れが確定できるということです． 実は，この情報を使うと値域付加型でも探索を使わずに問題2,3を解くことが できます．この方法を採っている人が1人いました．ぼくのつくったプログラ ムもこの方法によります． おそらく，最初にふれた生成検査型の人の方法も値域付加で扱う範囲を広げれ ば同じことになったと思います． 去年のイラストロジックの場合には探索を使わないと解けない，つまり局所的 な制約では決まらず，大域的な観点を必要としましたが，今回の数独はいまの ところそのような例はみつかっていません．ひょっとすると，探索を必要とす る問題があるかもしれません． 3. おわりに 今年は数独を題材にプログラムを作っていただきました．なにぶん，決まった アルゴリズムがある問題ではありませんから，実験をとったみなさんも多少と まどったところがあるかと思います． しかし，そのようなプログラムの方が本質的におもしろい，と僕は思うのです がいかがでしょうか? とりあえず，お疲れさまでした． さて，来年は，何を題材にしようかな :) 某メーリングリストでは「ナンバーリンク」というパズルを解くプログラムの コンテストがありましたが，これはちょっと難しいようですので，「四角に切 れ」なんてどうかとおもっておりますが... 「ナンバーリンク」とか「四角に切れ」というパズルを知りたい方は「ニコリ」 を買いましょう(編集部のまわしものではありません :) )．