プログラミングパズルに関心のある人は雑談しましょう！
数学全般に苦手ですが投稿させてもらいます。 間違っていたらごめんなさい。 私は、盤面の最小情報量からNの最小値を求めてみました。 （かなり略しますが）9*9マス 数独（一般ルールで）では、制約自体が 回帰的に折り重なっているので 3*3 マス（1ブロック）合計=45、 9ブロック合計=405 の制約があります。 １マスには1から9の数字のどれかが入る（アラビア10進数の1-9）。。。 問題を一般化すると、w=abs(base!=0); sqrt(w) = x = y = 整数； n*n マスの盤面で、１マスあたりに入る種類をwとする。（Let w=9） 1マスは必ずw種類の中の一つが入らなければならない；マスの一つを x,y とします。 1ブロック = w ; 盤面 ＝ w^2；ブロックの数の合計＝w 1ブロック に含まれるマス の合計値 ＝(w+1)*w/2 盤面は端がつながっていると仮定し（完全な球状）。 つまり w進数では、最小で1マスあたり w-1 の数の 最も近くの位置のマス への盤面アクセスが必要になります。（有効な解がほしければ） 逆に言えば、 w種類が w row, もしくは w column に（何らかの形で）分散されており、 １マスあたりには（情報量として）４種類の意味が含まれています。 (1)-マスが受け付ける種類 (2)-マスが位置する row が受け付ける種類 (3)-マスが位置する column が受け付ける種類 (4)-周辺のマスが必要としている種類 かなり省くと、結果的に、 L-U factorization/decomposition を使い、解が求められ無ければ、有効な解答が存在しないので （絶対的な盤面から得られる情報量が不足している状態） そこからは解答は出来るけど、複数の解が存在する（標準的な数独ルールでは無い） 盤面ができあがります。 L-U factorization 単体では意味がありませんが、 わかりやすくすると +-+-+-+ |a|b|c| n |d|e|f| t |g|h|i| k +-+-+-+ m p r で、 a+b+c+d+... g+h+i = 45 a+d+g=m b+e+h=p ... a+b+c=n g+h+i=k などと式をリストアップし、解を求める方法の一部です。 ちなみに、最小情報量は 1row / 1column あたり１マスなので、 9*9 では （１マス ダブりなので） 9+8=N=17 なんてモノが当方ではでました。 ただし、これには少しおかしなところがあり、理論上では N=16 は （盤面は端がつながっていると仮定しているので） 81面（理論上）存在します。 問題は、simmeterical を外すと、１面 しか 存在しないことです。 形もおかしいです。 1 element あたりの effect = 5 を満たしていません。 つまり、盤面の何処か１箇所に、通常では「導火線」なるモノが存在しますが （自己解答盤面） これ（N-16）では 解答者/program が 導火線を捜し出して、 「試し撃ち」（複数ある有効解答から１つ選び）しないといけません。 一見、解が複数あるようなので、ルールから外れているように見えますが、 形が十字、そして始めに記入するマスが強制的に決まっているのがミソなようです。 . . . . x . . . . . . . . x . . . . . . . . x . . . . . . . . x . . . . x x x x . x x x x . . . . x . . . . . . . . x . . . . . . . . x . . . . . . . . x . . . . （xに入る数字は まだ 求めていません） 今の私の環境では、ここまでしかわかりません。 どなたかよろしければ、あっているか（間違っているか）、等 お返事ください。 暫く書いていなかったもので、見苦しい日本語を済みません。
並列処理の部分についてちょっと補足しておきます。 あらかじめ遺伝子の最大数を決めておいて、初期値を決める時に全ての盤面を作り評価しておきます。 盤面をランダムに変化させた時は元の盤面を残したまま変化後の盤面を評価して、 今生きている遺伝子の中で評価の最も低い（同じ物が複数ある時は最も古い） 遺伝子を消して新しい盤面に置き換えるようにしました。 こうすると変化の途中で山を下る事が出来るので、局所解に陥る危険性が低くなります。 また、評価の高い盤面は少し変化させてもまた評価の高い盤面になる可能性が高いので、 優秀な盤面はそこから派生する盤面を評価する機会も増え、 個別の盤面で山登りを行う時に比べて効率良く優秀な盤面を残す事が出来るようになります。 前のn=17集にダブりがあったのでソートし直して更に増やしてみました。 今の状態だと新しく作った問題の99.5%ぐらいがダブりです。10万問作ってやっと500問。 n=12の対角線ナンプレ。11個は無理かもしれない・・・ . . 8 . . . . . . . . 4 . 7 . . . . . . . . 3 2 . . 1 . . . 6 . . . . . . . . . . . . . . . . . . . 1 . . 2 . . 7 . . . . 4 . . 5 . . . . . . . . . . . . . . . .
とくしんさんの報告に強い刺激を受けて久しぶりに私もプログラムを書いてみました。 並列処理は装備していませんが、とくしんさんの次の部分だけを自分なりに再現しました。 解答図もヒントの配置も両方とも固定せずに、ヒントの配置とそこに置く数字の両方を ランダムに変化しながら「解けるまで解いた時に全てのマスに入る数字の候補の合計」が 少ない程優秀な盤面として山登り法で少しずつ改良して「盤面の評価＝81」の物を抽出する。 実行した結果、睡眠中の昨晩（約８時間）でＮ＝１７を２０個見つけることが出来ました。 2秒に1問ぐらいのペースで量産できるとくしんさんのプログラムには足元にも及びませんが それでも驚いています。1個見つかってもやめずに暫く探索を続けるというのもいい結果 をもたらしているようです。 000000000400098000000000045015200000000000390006000000900000800002070000000500001 000006080007100000000000040000700002040000000060090000030004000000020507900000001 000006080450009000070000000017000030000504000000000000000300000000700500006008900 000006700400080000009000050000905060000000000380000000000020408000000003005007000 000050009407000200006000000002000070000018000000590000000007060090000000030000001 000400000050000063000000005000200400008900000030060000000073000204000800009000000 020450000007000060000300000600000078040200000000000010001007000030000900000000400 100000000050000003000020040000000506204010000900000000700800000000000020080503000 100000000050000003000020040000000507204010000900000000000800000000000024080503000 100000000050000003000020040000000507204010000900000000000800000000000820080503000 100000000050000003000020040000000507204010000900000000000800000030000020080503000 100000000050000003000020040000000507204010000900000000000800006000000020080503000 100000000050000003000020040000000507204010000900000000000800300000000020080503000 100000000050000003000020040000000507204010000900000000040800000000000020080503000 100000000050000003000020040000000507204010008900000000000800000000000020080503000 100000000050000003000020040000000508204010000900000000000800000030000020060503000 100000089000000003000027000000004200070000006900800000000900000000060000042000500 100006000050000003000020040000000507204010000900000000000000000000000620080503000 103000000000009200680000000000072090800000006000004000000600000002000400000300001 103000000000098060000020000000200403000000007900000000080000090004300000000005001 交叉させない並列処理というものにどんな期待が持てるのかというのも含め、その他にも とくしんさんのプログラムにはプラスアルファの隠し味があるのかも知れません。 ただ、あれだけ量産されてしまうとＮ＝１７の量産が目標ではなく、Ｎ＝１６の発見か、 あるいは究極がＮ＝１７であるという立証に移行せざるを得ないでしょうね。 数独が国際化しているので海外の研究者に先に解決されてしまいそうな予感もします。
確かに今のプログラムだとそこそこ好成績でN=17の問題を探す事が出来るのですが、 どうやら解の見つかりやすい探索空間に絞って探索をする方法では限界があるようです。 今のプログラムだと重複を除いても1時間に1000問ぐらいは見つかるのですが、 今までに出来た問題リスト（13000問程度）にマージすると9割方が重複していて、 結局100問ぐらいしか増えていない、という状況になっています。 あと、どうやらN=16とN=17対称形は存在しないようです。 解が存在するのならその周辺に全2解の盤面が沢山存在しても良さそうなのですが それすら見つからないので・・・ 参考にN=17対称形の解の数が比較的少ない問題。 対称形にする事によって存在自体が難しくなる事は無いと思うのですが、 どうやら解の存在し得る空間が狭すぎる事が問題なようです。 N=17対称形の探索をするとこれと同形の図が何回も見つかってしまうので。 . . . 8 4 . . . . 5 . 6 . . . . 3 . 1 . . . . . . . . . 4 . 7 . . . . . . . . . 2 . . . . . . . . . 6 . 5 . . . . . . . . . 2 . 2 . . . . 7 . 4 . . . . 1 5 . . . . 4 . . . . . . . 5 . . . . 2 . . . . 1 . . . . 7 . . . . . 1 . . 4 . . . . 3 . 8 . 1 . . . . 2 . . 3 . . . . . 8 . . . . 2 . . . . 4 . . . . 6 . . . . . . . 3 . ↓のファイルはN=17探索プログラムと今までに見つかった問題リストです。 探索プログラムは1時間ごとに約2000個の問題図を出力する気の長いプログラムです（笑 問題リストは解答図を高橋さんの方法で標準化した後に問題図でソートをかけてあります。 :の後はその問題が発見された回数です。探索空間内の網羅率等を推定できる指標になるかもしれません
とくしんさん、お久しぶりです。 何かすごいプログラムを作ったようですね。そんなにすごい成績が出せるということは どんなアルゴリズムなのかは当然ですが、もしかしたら「Ｎ＝１６」が発見されるのでは という興味も沸いてきます。 Ｎ＝１７の問題が３万問ほどデータベース化されているというのも驚きです。 究極のナンプレはＮ＝１７なのかという可能性が濃厚になってきたのでしょうか。 Ｎ＝１６が見つかるといいですね。
以前に作ったプログラムを色々改良していたら2秒に1問ぐらいのペースで量産出来るプログラムが出来てしまった・・・ 英語版WikipediaからN=17の問題が3万問ほどデータベース化されているページに飛べますが それぐらいなら軽く作れそうな勢いです。 今回のプログラムは、解答図もヒントの配置も両方とも固定せずに、 ヒントの配置とそこに置く数字の両方をランダムに変化しながら 「解けるまで解いた時に全てのマスに入る数字の候補の合計」が少ない程優秀な盤面として 並列山登り法（勝手に命名。交差させない遺伝的アルゴリズムと言った方がわかりやすい？） で少しずつ改良していくという方法を使用しました。 この方法だと並列させる数を多くすると1回の探索で複数の問題が見つかるので 1個見つかってもやめずに暫く探索を続けて、 全ての「盤面の評価＝81」の物を抽出するという方法で10分で数百個〜30分で1000個ぐらいの盤面を 一度に出力させるようにしました。
パズルの作問について 独創のプログラミング 「万が一理論」のプログラミング手法について ここで、今回公開したこれらのパズルの作問の手法について少しだけ解説する。 近年パソコンが普及し性能の高い物が自由に使えるようになり、これまでは出来なかったような事がプログラム次第で色々と可能になってきた。 「万が一理論」はパソコンの出始めの頃から、私が２０年来温めているプログラミング理論である。 メインクロックが１ＧＨｚ超の昨今のパソコンの世界では「万が一」（１万回に１回）の事が毎秒１０万回も起こっている。人間にとっての「万が一」は不可能とか滅多にないというイメージであるが、パソコンの世界では「万が一」は一秒間に１０万回も起こる。極めて日常的に当たり前に起こる事象という事になる。 つまり、人間が一生掛けても実現出来なかったような事が、「万が一」でも出来る可能性があればパソコンの世界ではできると言う事である。 私が最初にこのプログラミング手法を考えたのは今から２０年程前の事である。 高校で電気基礎という教科を教えているときに、生徒が最初につまずく「キルヒホッフの法則」という単元がある。生徒は法則自体はすぐに理解して３元１次連立方程式を作ることが出来るようになるのだがその計算が出来ない。基本的には中学の数学で解ける方程式だが、半数以上の生徒が計算途中の小数や分数の計算で間違えたりして、お手上げの状態になってしまう状況だった。本当は計算が出来ないだけなのに、結果的に「キルヒホッフの法則」は難しくて理解出来なかったという印象を生徒が持ってしまうのが非常に残念だったので、出来るだけ途中の計算が簡単な問題を作問しようと考えて、答えが簡単な整数になる問題を自動的にたくさん作れないかと考えたときに思い付いたのがこのプログラミング手法である。 具体的な例を挙げて説明すると 例えば未知数Ｘ，Ｙ，Ｚの３元１次連立方程式の問題を作問するとしよう。 易しい問題にして途中の計算が簡単になるように答えが１，２，３などの単純な整数になるような問題を作りたい。 Ｘ，Ｙ，Ｚの係数をあらかじめ適当に決めて ３Ｘ＋４Ｙ＋５Ｚ＝ａ ４Ｘ−２Ｙ＋６Ｚ＝ｂ −２Ｘ＋３Ｙ＋２Ｚ＝ｃ とする。 次に、答えをＸ＝１，Ｙ＝２，Ｚ＝３と決めて ａ，ｂ，ｃを求めると ａ＝ ３×１＋４×２＋５×３＝２６ ｂ＝ ４×１−２×２＋６×３＝１８ ｃ＝−２×１＋３×２＋２×３＝１０ となるので ３Ｘ＋４Ｙ＋５Ｚ＝２６ ４Ｘ−２Ｙ＋６Ｚ＝１８ −２Ｘ＋３Ｙ＋２Ｚ＝１０ このように、はじめに答えを特定の整数の数値に決めておいてから式を作ればとりあえず当初の目的を満足する問題が一問出来るので、「世の中に目的とする形の問題は存在している」と言える。 このような作問法は一般的なプログラミングの手法であるが、「万が一理論」のプログラミングでは「世の中に目的とする形の問題は存在している」と言う点に着目してプログラムのアルゴリズムを考える。 Ｘ，Ｙ，Ｚにかかるすべての係数を乱数で全く無作為に設定し行列式で計算し答えをチェックする。そして、その答えが「３つとも整数になった時に完成」と言うアルゴリズムを組む。いつ出来上がるかは分からないが、前述の式のように「世の中に目的とする形の問題は存在している」ので何万回、何億回試行したとしてもいつかは必ず出来る。 このプログラムで１００問程問題を作り実際に授業で使ってみたところ途中の計算が簡単なのでほとんどの生徒が自分の力で解けるようになった。自分の力で答えを出すことが出来たという正解のよろこびはその後の学習にも非常に大きく良い影響を与える。現在でも使っている最初の実用的な「万が一理論」のプログラムである。そのプログラムは当時の東京都工業高等学校電気教育研究会で発表した。 このようなプログラムでも、パソコンの性能がどんどん向上しているので結果が出るまでの時間もどんどん私達の生活時間に近づいてきた。これまでのプログラムミングは一行でも短く１秒でも早く情報を処理できるようなアルゴリズムが要求されていた。それに対し「万が一理論」ではあえて遠回りをしながら「万が一」の可能性を模索する。予め作為的に色々な要素を設定しないので出来上がった問題が非常に新鮮である。「万が一理論」によるプログラミングは一見邪道のようなプログラミング手法であるが、現在のようにパソコンの性能がどんどん向上していく中で十分実用的な新しいプログラミング理論として面白いのではないかと思う。 「万が一理論」では、ルールに合った問題を作ると言う以外の作為的な指示は一切与えていないので、どんな問題が出来上がるかは（またはルールによっては出来ないかも含めて）プログラム制作者にとってもまったくの未知数なのだ。 今回の５種類の新作パズルも「万が一理論」で作成した。これからも「万が一理論」のプログラミング手法から実用的な物を生み出す「ものづくり」の可能性を追究していきたい。
英語版Wikipediaに載っていますね。 対称変換で重なる回答図を別々にカウントすると 6,670,903,752,021,072,936,960 同一とカウントすると 5,472,730,538 だそうです。数独盤面に対する対称変換の総数は 1,218,998,108,160 で、全パターン/対称除去パターンは約 1,218,935,174,261.1 なので自己対称形の問題図は意外と少ないという事になりますね。 個人的には100個に1個ぐらいは自己対称形だと思ってました。
とりあえず全てのピースの形を巡回するプログラムを書いてみました。 対称形の排除まで行っていて、18ominoを求めるのに9時間半掛かりました。 この方法だとnが1増える毎に計算時間が4倍になるのでこれぐらいが限界です・・・
1)パズルを手をつかって握る 2)ひねるようにして切断面に対して回転方向のエネルギーを与える 3)立方体に戻るまで切断面を回転させる 4)2〜3を繰り返し実行する事により表面の色を崩したり揃えたりする これじゃダメでしょうか？ さてと本題。 ポリオミノの数え上げの世界記録はインターネット上で見つけた限りでは Fixed（回転無し）の場合(1,2,6,19,63,...)はn=56で、 回転反転ありの場合 (1,1,2, 5,12,...)はn=28だそうです。 この回転ありの場合の記録を何とかして更新出来ないでしょうか？ Fixedの数え上げ結果なら出ているので、 そこから線対称、点対称等のピースを対称軸毎に計算して 重み付けをする事により実際に全てのピースを数え上げる事無く 数を調べられるので今の世界記録なら簡単に抜けると思うのですけど・・・ 回転ありの場合の世界記録 http://kevingong.com/Polyominoes/Enumeration.html 回転無しの場合の世界記録 http://www.ms.unimelb.edu.au/~iwan/animals/series/square.site.ser 数え上げのアルゴリズム（英語、Fixedの高速な数え上げ方法の説明有り） http://en.wikipedia.org/wiki/Polyomino