<body leftmargin=0 topmargin=0 marginwidth=0 marginheight=0>
 
 

top page, english, japanese


高水準での、パズルの作成,解答 (solve),候補 (candidate) の解析,パズルの手入力作成,ファイル入出力,等々――

・7段階のレベル設定。初心者レベルから世界レベルの難問まで
・唯一解答のパズル作成。当然とは言え複数解答を回避
・どんなに難しいパズルでも解いてしまう。複数解答パズルでも余裕
・可解構造であるかどうかの判定
・複数解答であるか単一解答であるかの判定
・候補 (candidates) の容易なメモと解析表示
・見かけの誤りや不正解入力の表示
・手入力によるパズル・ファイルの作成
・パズルの作成パターンは天文学的な数

マルチパーパスにして扱い易く強力なナンバープレイス・ソフトウエアに仕上がっていると思う。先ずは動かしてみて下さい。

numberplace for Androidを作成しています。機能はこのWindows版と全く同じです。パズルデータのファイルも互換性があります。チュートリアルページはこちら。近いうちにGoogle Playにアップロードします

Windows版ver.0.23.00よりメニューを簡潔化し、Android版のメニュー構造もこれに準じました
 


 
numberPlace, ナンバープレイス 数独 ソフトウエア
last updated on 7th January 2024 since 7th November 2018
Download ver.0.23.01 for Windows x86 -- it might be worked on Windows XP, 7, 8.x, 10 (32 bits)
Download ver.0.23.01 for Windows x64 -- it might be worked on Windows XP, 7, 8.x, 10 (64 bits)
 
はじめに
 
1. ナンバープレイスと数独
2. このソフトウエアの使い方概要
3. 履 歴
 
chapter1: 使い方
 
1-1. Puzzle
1-2. Express
1-3. Solve
1-4. Hand-build
1-5. Option
 
chapter2: 雑 記
 
2-1. 契 機
2-2. 複数解答について
2-3. 非可解構造
2-4. パズルの入手
2-5. アルゴリズム
 


はじめに


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

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



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

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

“Express”のプルダウンメニューで、誤りの表示方法の選択,候補(Candidates)と回答の消去が出来る。
誤りの表示については、非表示 (No Express),見掛けの誤り (Visible Mistake),登録された正解に照応した誤り (Absolute Mistake) の3つから選択する。

“Solve”のプルダウンメニューで、パズルを解く事が出来る。
基本的な手法であるPencil MarksとBacktrackingの2つの手法がある。Backtrackingは強力な手法でどんなに難易度の高いパズルでも解く事が可能だ。ver.0.20.00より可解構造であるかどうかを判定する機能を追加した。これらは次のチャプターで詳述する
候補 (candidates) の解析については、1つしか候補が無いセルは非表示にする。パズルの難易度に応じて解析深度を変化させるので、簡単なパズルでは解析深度が浅いにもかかわらず1つも候補を表示しない事がある

“Option”のプルダウンメニューで、難易度レベルの設定やブート時のデフォルトの設定が出来る。
試してみれば直感的に扱えると思う。次のチャプターで詳述する

プログラム・フォルダーの下位にある“sample”フォルダーに幾つかのサンプル・ファイルを置いています。Dr. Arto Inkalaの作成した有名な難問パズルなどもあります
 



ver.0.23.00 on 28th April 2023
-- メニューの簡潔化
-- パズルのハンドビルド時の解析に於いて誤回答を無視

ver.0.21.12 on 27th December 2019
-- ターゲットプラットフォームへの最適化
-- リファクタリング

ver.0.20.20 on 28th June 2019
-- バグフィックス, メニューイネーブラーに間違いがありました
-- ハンドビルドパズル処理の最適化

ver.0.20.11 on 28th December 2018
・バグフィックス,幾つかのケースで解答評価に影響するハンドビルドパズルのデータ処理の修正

ver.0.20.10 on 23th December 2018
・パズルが複数解答であるか単一解答であるかを判定する機能を追加。これはパズルのハンドビルド中にチェックする事が出来、同時に可解構造であるかどうかも判定する
・可解構造を判定する機能の最適化

ver.0.20.00 on 4th December 2018
・パズルが可解構造であるかどうかを判定する機能を追加
・パズルの特性に応じたbacktrackingのアプローチの最適化による解答の高速化
・パズル作成の質を向上。パラメータ“quality”により調整可能
 (あまり大きな数値を設定すると時間がかかります)
・マルチスレッドの再構成 (時間のかかる処理への対応)

ver.0.11.00 on 11th November 2018
・backtrackingに於ける枝狩りの最適化による解答の高速化
・x64互換の為のリファクタリング。リリースは未だですが…

ver.0.10.00
・1st Release on 7th November 2018
 




chapter1: 使い方


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

“Level Setting”で難易度を変更する。また、“Default Settings”によりレベルを設定し、ソフトウエア立ち上げ時のデフォルトとする事も出来る

作成したパズルはファイルとして保存できる(File / Save)

“File / Load”でセーブしたパズルをロードする

最難問レベルのExtra-Terrestrialは目標に達していないので現行のバージョンでは封印している。と言っても、7段階あって、WorldClassでInkala2012には及ばないけれどInkala2010よりも難しいパズルを出力するので満足度に影響はしないと思う
 



"Erase Solving and Candidates"でクイズ以外を消去する

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

候補 (candidates) のメモは容易だ。
セルにフォーカスを当てると (選択すると)、フォントサイズが小さくなり、複数の数字を入力する事が出来る。フォーカスを外すと、1つの数字だけ入力していた場合は元のフォントサイズで大きく表示され、複数の数字であれば小さなフォントのまま候補として表示させておく事が出来る。
候補を1つだけメモしておきたい場合は、その数字を2つ入力しておく事だ
 



どんな難問パズルでも解く事が出来る。
世界最難問と主張されている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)は候補のみを消去する。これは、パズル作成にも有用かも知れない

 
 



“Hand-build Puzzle”で、手入力によるパズルを作成する事が出来る。作成したパズルはファイルとして保存する事が出来る。
2つのステップがあり、先ず最初に、パズルを登録する。ヒント (cell opened an answer) を入力して“Registre”ボタンを押す

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

 

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

正解の入力をスキップして、正解無しのパズルとして作成する事も出来ます。その場合は“Without Answer”を押して完成です

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




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




chapter 2: 雑 記


今年2018年の9月末、喫茶店でたまたま隣席になったフランス人と日本人 (イギリス人だったかも) のカップルからナンバープレイスの名を初めて聞いた。欧米では大流行したのに日本では誰も知らないと聞かされ、簡単なルールを聞きながら彼が手にしているパズルブックを目にした。
彼等はコスモポリタンな人達で別世界の住人でした (具体は伏せる)。彼等に感謝を伝えられればいいのですが

10年前ならもっと良かったのだろうけれど、遅れ馳せでも知る事が出来て良かった。なんとなくだったが、これはプログラミングの為のパズルでは無いかと感じ、興味を覚えた。それがmomentumだった

プロジェクトを立ち上げたのは、その一週間後の10月7日。そして、このページも作り、1st Releaseがその1ヶ月後の今日11月7日。
公開しているプログラムの中では最速記録かな

すっかりのめり込んでしまった故の記録だが、パズルを解いたのは数回だけで、それも自分が作っているソフトウエアが出力するパズルのみ。何に夢中になったかと言うと、パズルの作成と解答のアルゴリズムだった。
最初は、作成に於いて複数解答の回避方法に試行錯誤を繰り返したりした。その事で自然と解答の手法も深く研究するようになった。ゲームソフトならではのインターフェイスの作り方なども楽しめた

そして、難解なパズルをどうやって創り出すか、難解なパズルをどうやって解くか?

いずれもワールドクラスに手は届いたと思うが、少しづつ足りないモノを感じてもいる。
レベル設定の“Extra-Terrestrial”では世界最難問と同等の難易度で出力するのが目標だったが、これは簡単に達成出来る様な目標では無いとわかったので、“Extra-Terrestrial”は封印した。身の丈を知りました…。
“Backtracking”による解答はかなり満足しているアルゴリズムだが、最適化,効率化の余地が未だ未だありそうだ

そんな感じで、まだまだ楽しめそうです

近い内にスマートフォンのアプリケーションにも移植します。データファイルは互換で
 



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

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

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

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

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

 
 



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



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

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

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

 



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

・レベルの高いパズルが入手出来る
・もちろん初心者向きから超難解なモノまで膨大な数がある
・難解なパズルは書籍では入手出来無い
・Webベースが主流でプラットフォームを選ばない
・情報が豊富で解法などの解説も多い
・興味があれば数学的な側面やアルゴリズムなどの情報もある
・メモ(候補)はスマホやPC上での方が扱いが容易い
・パズルをファイルとして保存したりと自由度も高い(ソフトウエア)
・無料で入手出来る

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

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

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

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

 

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

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



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


(constructing ...)


 




御感想でもありましたら
 


e_mail to webmaster