アクセス解析、ナンプレ
exciteではネームカード登録をすると、ある程度のアクセス解析を見ることができます。
それを眺めていたところ、"ナンプレ" "解読" "ソース"という検索キーワードから、ここを訪問する方がちらほらいる事に気付きました。
以前投稿した記事がヒットしているようです。試しにGoogleで検索をかけてみたところ、かなり上位にヒット…(゚Д゚;)ヌヲッ
なるほど、ここに迷い込んでくるのはこれが原因でしたか…。Googleの中核要素技術の一つであるページランクは、どうしてここをヒットしてしまうのか…、とても興味深いですが、その技術については話が長くなりそうなので別の機会にしておきましょう。

ここにはナンプレ解読のアルゴリズムやソースは公開されていません。他にもっと詳しく解説されているHPや、詳しい方々が熱く意見を出し合っている掲示板もあります。そちらを参照されたほうが有意義かと思います(`・ω・)b
しかし、ここに訪れたのも何かの縁かもしれませんし、少しだけ解読法を書きたいと思います。あくまで考え方の1つですので、ほかにもっとスマートな解読法があるかもしれません。



まず、アルゴリズムを理解して頂くに当たって確認しておきたいことが1つあります。
ナンプレを楽しんでいる方なら理解されているかと思いますが、答えを出す手順は至ってシンプルです。候補を絞っていくこと。いわゆる"消去法"です。「なにを当たり前なことを言っているんだ」と思われるでしょうが、ここが一番肝心です。

まずは簡単な問題を解きながら、解き方の基礎と、そこに隠された法則を見つけていくことにしましょう。
e0012883_22211482.gif
e0012883_22212635.gifまず最初に空欄に入る数字の候補を絞ります。
小さく書かれた数字は、現段階で入る可能性がある数字の候補です。
ピンク色に塗られたマスは候補が1つに絞られたマスです。この数字を確定すると同時にそのマスに関わる、縦、横、3x3ブロック内の候補を消去できます。
e0012883_22213839.gif再び確定したマスが現れました。
e0012883_22214681.gif連鎖的に候補が絞られていきます。
e0012883_22215684.gif残念。ここまでのようです。
ここまででやってきた事は、既に確定している数字を元に候補を1つに絞って確定し、更に候補を絞る。という作業でした。
1マス内の候補が1つに絞られ数字が確定することから、これを仮に"純単騎確定"と呼ぶことにしましょう。
これが一番シンプルで分かりやすい問題の解き方と言えるでしょう。

純単騎確定以外に数字を確定する方法は無いでしょうか。
図5を使い、解き方を考えてみましょう。
e0012883_011113.gif赤く囲まれたラインに注目してみると、候補9が座標F1にしかありません。
F1には他にも、3、5、8の候補がありますが、それは自動的に消去されることになり、F1は9で確定となります。
e0012883_0114053.gif赤く囲まれたブロックに注目してみると、候補3が座標H7にしかありません。
H7には他にも、1の候補がありますが、それは自動的に消去されることになり、H7は3で確定となります。
縦横のラインや3x3のブロック内から候補が1つに絞られ数字が確定することから、これを仮に"範囲単騎確定"と呼ぶことにしましょう。

"純"と"範囲"、2つの"単騎確定"は対象マスの数字を確定し、それに関わる範囲内の他マスの候補を削除することができます。これがナンプレの基礎中の基礎です。
この問題は、この単騎確定のみで答えを出すことができます。


しかし、これだけでは解くことのできない問題があります。
次に単騎確定のみでは答えがでない問題を例に挙げて説明をしていきたいと思いますが、その前に知っておいて頂きたいことがあるので、それを先に紹介しましょう。

下は問題の一部分です。どうやら単騎確定はできないようですが、よく見ると糸口を掴めそうな所があります。
e0012883_1491178.gif
ピンク色に塗られたマスに注目してください。2つのマスは4、9の候補だけしかありません。という事は、この2つのマスには4、9のどちらかが必ず入るという事です。逆に言えばその他のマスには4と9は入らない、と言えるので、青色の数字の候補は消去できます。
e0012883_156159.gif
候補を絞ることができればこっちのものです。単騎確定でどんどん攻めましょう。
e0012883_263789.gif
e0012883_264867.gif
e0012883_265723.gif
他のパターンもあるので紹介しておきます。e0012883_2364112.gif
ピンク色に塗られたマスに注目してください。1と3が含まれる候補はこの2マスしかありません。この2マスには1と3のどちらかが必ず入る事が分かります。という事は、この2マスには1と3以外は入らない、と言えるので、青色の数字の候補は消去できます。
e0012883_252154.gif
e0012883_2532510.gif
e0012883_2533374.gif
e0012883_2534699.gif
e0012883_253536.gif
これを踏まえた上で、次の問題を考えて見ましょう。
e0012883_2583287.gif
e0012883_301485.gif単騎確定でここまで数字を確定できました。
ここから先は別の方法が必要のようです。
e0012883_41494.gifピンク色に塗られたマスに注目してください。
図7と同じパターンです。候補6、7が含まれるマスはこの2つしかありません。という事はこの2つのマスには6、7のどちらかが必ず入るということになります。同時に、それ以外の候補は消去する事ができます。
e0012883_435665.gif次は少し難しくなってますが、考え方は図7と同じです。
候補2、4、7が含まれるマスは3つしかありません。という事はこのマスには2、4、7のどれかが必ず入る事になり、他の候補は消去できます。
もし、この3マスに2、4、7以外の数字が入ってしまったら、2、4、7のどれかの数字があぶれてしまう事からお解かり頂けると思います。

さて、ここまで色々なパターンで数字を確定してきました。
勘の良い方ならお気づきでしょう。実は図1~図10まででやってきた事は、ある1つの法則で解決できます。それぞれにパターン化して候補を絞るプログラムを組む必要はありません。
その法則こそがナンプレ解読のミソと言えるかもしれません。

法則の説明に入りますが、文章のみの説明になると分かりにくくなりそうなので、"集合"を用いて説明します。
それぞれのマスが1つの集合であると考えてください。集合の要素は候補の数字です。例えば図11の座標D4は、集合{1,2,4,7,8,9}というような具合です。

任意のn個の要素を持つ集合X(要素には同じ数字が含まれないものとする。既に確定している数字も含まないものとする)と、範囲内(縦、横、3x3ブロックのどれか)の集合Y()との間に Y()∩X≠φ の数式が成り立つ数をm個としたとき、n=mの場合、m個の該当する集合は ∩X(Xc の候補を消去できる)となる。

という法則が成り立ちます。Y()の部分が意味不明な表記なんですが…、範囲内のそれぞれの集合ということでご容赦ください(^^;;
ちょっと分かりづらいので図11に当てはめてみます。
"任意のn個の要素を持つ集合X"とはこの場合、集合X={2,4,7} 要素は3個です。
"Y()∩X≠φ の数式が成り立つ範囲内の集合をm個"とはこの場合、範囲は D4,E4,F4,D5,E5,F5,D6,E6(,F6)で、数式が成り立つ集合は D4,F4,D6の3個です。
n=mになっています。という事は ∩X(Xc の候補を消去できる)ですから、{2,4,7}以外の候補は消去できるわけです。
図10と図7も同じ法則から候補を絞れます。
図6はどうでしょう。説明では4と9の候補に着目しましたが、それは逆に集合X={2,3,5,7,8}とする事もできます。これで法則が使えます。
図5' はどうでしょう。この場合も、集合X={9}として考えれば、この法則がなりたっている事がわかります。
図2~図4にもこの法則が使えますが、既に候補は1つになっているので無意味でしょう。あとは確定処理と関連する範囲の候補を消去するだけです。
集合Xの要素数が4個や5個になっても、この法則を使えば簡単に候補が絞れる事が分かります。人の頭で考えるのは面倒ですが、コンピュータならあっという間に候補を絞ってくれるでしょう。

さて、この法則を使い、図11から更に候補を絞っていきます。下の図が候補を絞りきったものです。
e0012883_7141314.gif
一見万能に見えた法則ですが、それだけでは答えは出ません。更に一捻りしていく必要がありそうです。

e0012883_7241148.gif赤い枠で囲まれた3x3ブロックに注目してください。
候補9が含まれるマスはE4とE6です。この2つのマスのどちらかに9は必ず入ります。
よく見ると、E4もE6も青い枠で囲まれた列E上にあることが分かります。E7にも候補9がありますが、9はE4かE6のどちらかに入ることは確定しています。という事はE7に9は入らないので候補9は消去できます。
e0012883_7365751.gif今度は赤い枠で囲まれた列Eに注目してください。
候補6が含まれるマスはE5とE6です。この2つのマスのどちらかに6は必ず入ります。
よく見ると、E4もE6も青い枠で囲まれた3x3ブロック内にあることが分かります。F5にも候補6がありますが、6はE5かE6のどちらかに入ることは確定しています。という事はF5に6は入らないので候補6は消去できます。
2つの関連する範囲をクロスさせ候補を絞る。ナンプレは良くできたパズルです。

さて、このクロス方法と先程の法則を組み合わせ候補を絞っていくと…、
e0012883_7523784.gif
見事答えを出すことができました(´∀`*)

これでナンプレ解読の基礎と、法則が解って頂けたと思います。
これをどうやってプログラムするかは、アナタの腕次第です。ポイントの1つは候補データの持ち方でしょう。候補同士の比較や抽出、書き換えが頻繁に行われます。それを考えれば間違っても、

  Dim choices(1 to 9) As Boolean    ' ( ※VisualBasic言語です )

なんてデータの持ち方をしない事です。地獄を見ること間違いなしです(^^;;

  Public Type num_type
   settled As Integer       ' 確定
   choices As Integer       ' 候補
  End Type
  Public map(0 To 8, 0 To 8) As num_type

こうするのはどうでしょう。
変数 settled は確定した数字です。確定前は0を入れておくと良いかもしれません。0⇒未確定 となり、フラグの役目もできます。
変数 choices が候補一覧です。1~9までの候補はビットで管理します。候補は9個あるので16bit以上の変数を使わなくてはなりません。
settled と choices を1つのグループにし、二次元配列で宣言してみました。構造体です。こうしたほうが扱いやすいかと思います。

候補をビット管理する事により、候補の操作が簡単にできるようになります。
例えば図11の座標F4、集合X={2,4,7}以外の候補を消去したい場合、

  X = 74   ' bit ( 0 0100 1010 )
  map(5,3).choices = map(5,3).choices and X       ' F4 ∩ X

とすれば簡単に済みます。
他にも色々なテクニックを駆使し、エレガントなコード組んでください。


最後に、今まで説明してきた法則を使っても解けない問題があります。
以前の記事にも書きましたが、そのような問題には背理法を使う必要があります。
候補の中から適当に数字を選び解いていきます。その結果、問題なく最後まで解ければ良し、矛盾が生じるのであれば、選んだ数字が間違えていた事になり、その数字は候補から消去されます。
当然、適当に選んだ1つ前の段階まで変数を元に戻さなければなりませんが、それは簡単にできるでしょう。注意すべき点は、背理法を使い解いていく先で再び背理法を使わなくてはならなくなる場合があることです。ツリー構造のようになるので、復帰ポイントをきちんと管理し、データをスタックしなければなりません。
それを理解していれば、それほど難しい事ではないはずです。

あとは地道にLet's プログラムヽ(*´▽`*)ノ


■更新2010/08/19
ナンプレ解読プログラムはこちら

[PR]
by angrywaves | 2006-08-05 11:03 | 雑記


<< 映画「さとうきび畑の唄」 関東地方、梅雨明け >>