アメリカのデルマガジンズ社 (http://www.dellmagazines.com/) が1979年以降にNumber Placeの名前で販売していた数字パズルです。2005年にはSudoku (数独) の名で英国で大流行し世界へ広まった。これが為に日本人が作ったと勘違いしている人が多い。
81個の空欄の中に1から9までの数字を重複しないように入れる数字パズルで、縦横の各ライン (行と列) 及び9つに分割された3x3のスクウェア (行列) に於いて重複しない様に配置していきます

ルールを初めて知ったというなら、このソフトウエアの“Practice”レベルで遊んでみるといい。一度で十分どころか、簡単過ぎて途中で飽きてしまうかも知れない。そして、もう二度と“Practice”に設定しないことだ



冒頭で特徴を記した。ソフトウエアを立ち上げてメニューを一覧すれば直感的に使えると思うけれど、ここで出来る事を概観しておく。
次のチャプターでは詳細を説明する

"Board"のプルダウンメニューから、クイズデータの消去，回答や候補のみの消去が出来る

“Puzzle”のプルダウンメニューで、パズルの作成，パズルのハンドビルドとそのロードが出来る

“Solve”のプルダウンメニューで、パズルを解く事が出来る。
基本的な手法であるPencil MarksとBacktrackingの2つの手法がある。Backtrackingは強力な手法でどんなに難易度の高いパズルでも解く事が可能だ。
候補 (candidates) の解析については、1つしか候補が無いセルは非表示にするので、パズルの難易度に応じて解析深度を変化させる。簡単なパズルでは解析深度が浅いにもかかわらず1つも候補を表示しない事がある
また、可解構造であるかどうか，唯一回答か複数回答があるかを判定する機能がある

“Option”のプルダウンメニューから、難易度レベルの設定，ブート時のデフォルトの設定等が出来る。
"Settings"によって、誤りの表示方法の設定などが出来る。
誤りの表示については、非表示 (No Express)，見掛けの誤り (Visible Mistake)，登録された正解に照応した誤り (Absolute Mistake) の3つから選択する

“File”のプルダウンメニューで、パズルデータのロードとセーブが出来る

試してみれば直感的に扱えると思う。次のチャプターで詳述する



ver.1.00.00 on --th ---- 20--
-- 1st Release

"Clear All Quiz Data"でクイズデータを消去し、ボードをクリアする。
"Erase Solving and Candidates"でクイズ以外を消去し、"Erase Candidates"で候補のみを消去する

クイズを出力、またはロードした後、回答の入力は、下方にある'Number'ボタンをタップして数字を選択し、ボードをタップする事で入力していく。
候補(Candidates)についても同様の方法で入力できる。1つのセルに最大8個の候補を入力する事が出来る。特定の数字を候補から外す場合も、入力と同じ方法でその数字だけを消去できる



“New Puzzle”により、パズルが作成される。手入力による作成については後述する。
デフォルトで難易度 (Level) は“Advanced”となっている。これはPreferenceメニューで変更できる

作成したパズルはファイルとして保存できる（File / Save）
“File / Load”でセーブしたパズルをロードする
Saveの際には、未回答，回答途中，回答済みの状態を自動判別してその状態も記録され、Loadする際の状態に反映される。つまり、一つのクイズを回答途中でSaveして、Loadによってその続きを進める事が出来る

“Preference / Level Setting”で難易度を変更する。また、“Default Settings”によりレベルを設定し、ソフトウエア立ち上げ時のデフォルトとする事も出来る。
最難問レベルのExtra-Terrestrialは目標に達していないので現行のバージョンでは封印している。と言っても、7段階あって、WorldClassでInkala2012には及ばないけれどInkala2010よりも難しいパズルを出力するので満足度に影響はしないと思う



“Hand-build Puzzle”で、手入力によるパズルを作成する事が出来る。作成したパズルはファイルとして保存する事が出来る。

ハンドビルド中に有効となる機能に、複数解答を持つか単一解答であるかのチェック，可解構造であるかどうか，候補の分析表示，候補の消去，更に、解答 (Pencil Marks, Backtracking) がある。パズル作成に有用かも知れない


次いで、各セルに正解を入力して“finish”ボタンを押すと完成です

また，一々入力しないでも、解答 (Pencil Marks, Backtracking) させる事で、正解が入力された状態になるので、あとは“finish”ボタンを押して完成です。それが唯一正解であるかどうかはパズル次第です

可解構造かどうかをチェックする事も出来ます

"finish"ボタンを押すとメニューに戻るので、続けて、"Load A Hand-build Puzzle"をタップするとボード上にパズルが展開される。
展開されれば、ファイルとしてSaveする事も出来ます



どんな難問パズルでも解く事が出来る。
世界最難問と主張されているInkala2012 (後述) でも解ける。複数解答のパズルも余裕で解ける、たとえ解く度に異なる答えを出力しようとも

“Show Candidates”により候補 (candidates) を解析表示する事が出来る。あくまでヒントとしての表示であり、1つしか候補の無いセルは何も表示されない。
複数解答でなければ各セルに候補は1つしか無い筈なので、これは矛盾している。そこで、パズルの難易度に応じて解析深度を変えて候補を抽出する仕様にしている。あまりに簡単なパズルに於いては、浅い解析深度ですら、1つとして候補が表示されない場合もある

“Open Answer”で正解を表示する。つまり投了 (resign) である。もちろん正解データのある場合に限る

“Pencil Marks”は決定論的な手法である通常の(?)方法をシミュレートしていて、書籍販売されている様な手作りパズルならほとんど一瞬で解く事が出来る。但し、複数解答のあるパズルでは、そのエリアだけ残して終了する。
また、解くにあたって再帰が深いパズルは解けない。このソフトウエアの“Expert”が出力するパズルではしばしば、“World Class”以上が出力するパズルではほとんど、解く事が出来ない

“Backtracking”を使えば、どんなパズルでも解ける。81セルで作り得る再帰がどれほど深くても解ける。更には、パズルと言えるか如何かは別にして、複数解答であろうとヒントが数個しか無くてもお構いなしに解いてしまう

“Backtracking”に関して現行のバージョンでは、素早く解答出来る経路を探索する為にrandom chanceを取り入れています。この為、同じパズルでありながら、解答に要する時間はマチマチになっています。世界最難問のパズルを一瞬で解いてしまうかと思えば、同じパズルに数秒ほど掛ったりもする。
より効率的なアルゴリズムにする事は今後の課題です


"Check Solvable"により、パズルが可解構造であるかどうかを判定出来ます。"Hand-build"によってパズルを作成した場合などに一度チェックしておくと良いでしょう。
パズル(ヒント)を一見する限りではルールに反していない様に見えても、可解不可能なパズルがあり得ます。"sample"フォルダに非可解構造の一例として"unsolvable_xx.np"を置いておきます。当然、"Backtracking"によっても解答する事はあり得ません。
解答(Pencil Marks, Backtracking)の度に事前判定するように、"Option"のメニューで設定する事も出来ます

"Check Multiple"により、パズルが複数解答を持つか単一解答のみであるかを判定出来る。同時に、可解構造であるかどうかも判定する。
この機能は、ハンドビルド中にもチェックする事が出来る。また、候補の分析表示もハンドビルド中に機能するようにした。その場合のリセット（Reset Solving）は候補のみを消去する。これは、パズル作成にも有用かも知れない



"Preference / Settings"にて、解答入力の誤りを表示する3つの選択肢がある。
“No Express”では何も指摘しない。
“Visible Mistake”では見掛けの誤りを、つまりルール上での誤りを、赤いフォントで表示する。
“Absolute Mistake”では正解 (Answer) に照応して誤りを赤いフォントで表示する。これはあくまで正解 (Answer) データがある場合に限る。後述するが、正解 (Answer) データの無いパズルも手入力で作成登録出来るからだ。
手入力によるパズルでは、複数解答のあるモノもあり得るので、“Absolute Mistake”の指摘が正しいとは限らない。あくまで登録した正解 (Answer) とは異なる入力を指摘するだけである。
デフォルトで表示は“Visible Mistake”となっている。“Default Settings”により表示を設定し、ソフトウエア立ち上げ時のデフォルトとする事も出来る

“Default Settings”でソフトウエアの立ち上げ時の設定を変えます。
LevelとExpress, Quality of puzzle creating，Confirmationに関しての設定です。ダイアログが立ち上がるので、好みの設定を選択して下さい

以降は、Windows版の画像を使用するが、機能的にAndroid版と全く同じである



このソフトウエアが作成するパズルは唯一解答のものだけで複数解答は回避している。念の為

複数解答のあるパズルが難しい訳ではない。むしろ、難易度は低くなりがちだ。しかし、解いていくプロセスのどこかで必ず一種の仮定法を使う他無くなる。それはパズルと言えるでしょうか？

解くのでは無く、見つけ出す事になってしまう

有名なパズルでは、Inkala2010 (右画像はパズルと正解) がそうでした。彼にとっては黒歴史か？

Backtracking Methodを使って何度か解いてみた (次の3枚の画像)。全て公表されている正解とは異なるが、ルール上の誤りは無い。何度と無くやってみたが、毎回異なる解答が得られる。複数解答の数はかなりありそうだ




右図は、Inkala2012。難易度もInkala2010と比べて格段に上がっている。そして唯一解答しかない



既に記しましたが、"Check Solvable"により、パズルが可解構造であるかどうかを判定出来ます。パズル(ヒント)を一見する限りではルールに反していない様に見えても、可解不可能なパズルがあり得ます。右図は非可解構造の一例です ("sample"フォルダにファイルがあります)

この例では、各セルに候補が2つづつしか無く、試しに適当なセルで候補を1つ選んで入力し、"Pencil Marks"で解答してみると下の画像の様になります

左画像は、1stRow/2ndColumnで４を選択しPencil Marksで解答した結果です。
右画像は、1stRow/1stColumnで７を選択しPencil Marksで解答した結果です。
Pencil Marksは、局所的に決定論的に逐次処理するので、非可解構造の場合に限ってはルールに反して、解答を進める事がありえます




書籍，インターネットとソフトウエア。断然、インターネットからパズルを入手するのが御薦めです。
何故かと言うに、


逆に言うと、書籍パズル集のレベルがやたら低いのである

ブームの初期こそ、当時のわたしは知る由も無かったが、数学者が提示するパズルにも複数解答のモノがあったりした。一部では、書籍のパズル作者はそういうミスをしないなどとも言われた様だ。しかし、そんな時代はとっくに過ぎている。
書籍のパズル作者は職人の域でしか無く、本人たちは意識しないまでもPencil Marksしか使う事が出来ないが為に、複数解答も避け易いというだけの事だったのだ。チャレンジの領域が違っていたのだ

今や、複数解答を排除する為の最低限のHint数なども算出され、再帰の深さによってパズルの難易度を数量化する事さえ可能になった。尤も、Dr. Arto Inkalaが言っている様に、パズルの難易度に関しては、その解法に依るところが大きく、一律に評価出来るものでは無い。
しかし、ある指標によってレベルを数段階に分けた場合に、別の指標を用いて評価してもその分類はほぼ変わらない。そして、ユーザにとって重要な事は、自分に合ったレベルで遊ぶ事が可能になることだ

インターネットで紹介されているパズルには、初心者レベルのモノから、普通の人間には到底解けない様なモノまである。その中間の層が厚い事が多くのユーザにとって利益になる。
それは、インターネットには存するが、書籍パズル集には無い。
書籍では、大雑把に言って初心者クラスから中級クラスまでのパズルしか無い。解答は単純作業でしか無い。書籍のパズル作者たちは難易度の高いパズルの作り方を知らない


インターネット上での御薦めは、数段階のレベル設定が出来るところである。自動的にパズルを作成・出力するサイトには、簡単なモノしか作成しないサイトもある。このテのサイトは沢山あるので自分に合ったところを探すのがいい。
また、難易度別にパズルを定期的に発表しているサイトなどで、良質なパズルが入手出来る。欧米のニュースサイトには、パズルのページがつきもので、このタイプのサイトが多い

幾つかURLをリストしておく



難解なパズルをどうやって創り出すか？、難解なパズルをどうやって解くか？
計算機を使えば難解なパズルを解くのは容易だが、そうしても難解なパズルを創るのは非常に難しい


(constructing ...)