プログラミングパズルに関心のある人は雑談しましょう！
独創のプログラング理論「万が一理論」（このサイトに２００６年３月２日に書き込みました）を基にエクセル＋ＶＢＡでナンプレ自動作問プログラム（論理的唯一解問題）を２００４年７月に開発しました。最近調べて見ると昨年記者会見までして発表されている記事などを見つけましたがこれって、もしかして当時発表していたら大ニュースだったのでしょうか？ともあれ、以来３年ナンプレタイプの他４Ｘ４から７Ｘ７も独自のルールを決めて開発し数字を使わず色を使った「カラープレイス」シリーズや漢字を使った漢字パズル、ことわざを使ったことわざ１００選パズル、等を本、雑誌、ＰＣソフト、携帯アプリなど様々なメディアで発表、公開しています。「カラープレイスＭＳ９９９（３００問）」はベクター様で２００６年５月から発売していましたが１０月頃に同様のＰＣソフトを発売されてしまいました。対策を検討中ですが残念！いくらパズルでもプログラムの著作物として既に周知公開された物なので、研究者の倫理として良い物を見つけたと思ったら一声かけてから商売してね。と、ここ１ヶ月にたまったストレスも書いてしまいました。携帯用アプリの方はまだ大丈夫みたいです。今年４月５日には「脳を鍛える 数字パズル ＭＳ５５+Ｘ、ＭＳ６６Ｘ、ＭＳ７７Ｘｚ」を新風舎から出版しました。よろしくお願いします。
と言うわけで問題はいろいろなタイプでいくらでもできるので、ゴールデンウィークはまた、これまでない様な脳トレパズルの制作に取り組んでいます。「万が一理論」もこれからのプログラミングには有効な発想になると思っています。プログラム研究者の皆さんこれからも頑張って下さい。 ２００７．５．４ 菅野正人
あらさんの8番目のN=17問題図を一箇所かえると、９番目になります。 0 , 9 , 8 , 0 , 0 , 0 , 0 , 0 , 0 0 , 0 , 0 , 0 , 7 , 0 , 0 , 0 , 0 0 , 0 , 0 , 0 , 1 , 5 , 0 , 0 , 0 1 , 0 , 0 , 0 , 0 , 0 , 0 , 0 , 0 0 , 0 , 0 , 2 , 0 , 0 , 0 , 0 , 9 0 , 0 , 0 , 9 , 0 , 6 , 0 , 4 , 2 0 , 0 , 0 , 0 , 0 , 0 , 0 , 3 , 0 5 , 0 , 1 , 0 , 0 , 0 , 0 , 0 , 0 0 , 0 , 0 , 4 , 0 , 0 , 0 , 2 , 0 その後の展開はどのようになっているのでしょうか？。
はじめまして ># L-U factorization LU分解、連立一次方程式の解法、ガウス−ジョルダン、リンパック... 大学の一般教養の数一に出てきます。（私は落としました）
対称形でN=64、非対称でN=62まで見つかりました。 これぐらいが現在の改良のアルゴリズムで到達できるほぼ限界点だと思います。 N=62対称形に関してはほぼ確実に存在はすると思うのですが、 盤面の改良により制限が掛かるので現在のプログラムでの発見は 難しいのではないかと思います。 N=64点対称 __ 1 __ __ __ 3 __ __ __ __ __ __ 5 __ __ __ 7 __ 8 __ __ 10 __ __ __ __ 6 __ __ __ __ __ __ __ __ __ 5 2 __ __ __ __ __ __ 13 14 __ __ __ 9 15 __ __ __ __ __ 7 11 __ __ __ __ __ __ __ 8 __ __ 6 __ __ __ __ __ __ __ 16 __ 12 5 __ __ __ __ 2 5 __ 8 __ __ __ __ 6 10 __ __ __ 15 __ __ __ __ __ __ __ 3 __ __ __ __ __ __ 13 7 __ __ __ __ __ __ 9 15 __ 1 __ __ __ __ __ __ __ __ 8 __ 15 1 __ __ __ __ __ __ 7 9 __ __ __ __ __ __ 6 __ __ __ __ __ __ __ 8 __ __ __ 5 10 __ __ __ __ 3 __ 2 16 __ __ __ __ 2 11 __ 13 __ __ __ __ __ __ __ 10 __ __ 1 __ __ __ __ __ __ __ 3 7 __ __ __ __ __ 4 15 __ __ __ 10 5 __ __ __ __ __ __ 13 6 __ __ __ __ __ __ __ __ __ 12 __ __ __ __ 11 __ __ 9 __ 7 __ __ __ 6 __ __ __ __ __ __ 4 __ __ __ 2 __ N=62非対称 __ __ 1 __ __ 2 __ __ __ __ __ __ __ __ __ __ __ __ __ __ 3 __ __ 4 5 __ __ 6 __ 7 8 __ 9 10 __ __ __ 11 1 __ __ __ __ __ __ 12 __ __ __ 2 __ 11 __ __ __ __ __ __ __ 7 __ __ __ __ __ __ __ __ __ __ __ __ __ 4 __ __ __ __ __ 6 __ __ __ __ __ __ __ __ __ __ __ __ __ 8 __ __ __ 4 __ __ __ __ __ __ __ 2 9 __ __ __ __ __ 8 __ __ 5 7 __ 6 __ 3 __ __ __ __ 13 __ __ __ __ __ 7 12 __ 3 __ __ __ __ 8 __ 6 __ __ __ __ __ __ __ __ __ 2 __ 9 __ __ 11 __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ __ 14 __ __ __ 13 __ __ __ 9 __ 14 __ 10 __ __ 4 __ __ 2 __ __ __ 15 16 __ __ __ __ __ __ __ 2 __ 9 4 __ __ __ __ __ 1 __ __ __ __ __ __ 10 __ __ 11 __ __ 4 3 5 __ 8 __ 7 __ __ 13 __ __ __ __ __ __ __ __ 13 __ __ __ 10 __ 14 5 1 __ __ __
やはりナンプレのヒント数の最終的な答えを出すには全検索しか無いのでしょうか？ 全ての作図問題を解くとして、作図問題1個辺り大雑把に計算しても 9^16/9!で約50億問、作図問題の数を考えると想像を絶する数になる気がしますが、 とりあえずヒント数16の作図問題の数だけでも調べてみませんか？ 同じブロックを含む2列が空行、L字型に並んだ3つのブロックが空 3x9の大ブロック内に数字が2個、等の不可能性が自明な配置を除いた時 どれぐらいの数になるのかがわかればN=17の証明（もしくはN=16の発見） の手がかりになるような気がします。 ところで、評価99の2番目の盤面は8と9が1つも入っていませんが、 8と9を入れないと他の数字の位置が確定しないという不思議な盤面ですね。
あらさん、お久しぶりです。 16個入れた段階での「全てのマスに入る数字の候補の合計」ですが、こちらで見つけた最小のものは、 99 でした。(下表参照) 当然ですがその近傍に評価値=81は存在しませんでした。近傍とは多少の改悪を 許しながら盤面を変化させていくという意味です。 とくしんさんの推察に同感なのですが、もし仮に、いんヴぃごさんの分析理論として、N=16が１個だけ 存在するはずだとしたら、山登り方式を基本にしたアルゴリズムでは見つからないような気がします。 000000000000001002034000050000000060000002000006000340000340000700000000120000008=(99-81=18) 000000000000001023045060000000000001006500000200000007000000500020000400100007000=(99-81=18) 000000000000001002034000050000000300050000640100027000000400000000600000700000008=(104-81=23) 000000000000000012003045000000000000000603007450000001000200000000170000006000500=(105-81=24) 000000000000000012003004000000005300010000000260000000000060400000710000008200900=(111-81=30) 000000000000000001002003000000002340015006000700000000000070000000410800006000900=(112-81=31) 000000000000000001002003000000002340050000000016007000000050000000410800007000900=(112-81=31) 000000000000000012003045000000000000006000400070100000000806300004000070100200000=(112-81=31) 000000001000000002003004000000003450010000000060000000000170006005000800800002000=(112-81=31) いんヴぃごさんは、おそらく外国の学校で勉強しておられると推察しているのですが、専門用語が英語 なので、web検索で理論の補習をするには無理があるようです。でも、とても興味があります。
「全てのマスに入る数字の候補の合計 - 81」だと調べた限りでは 31が最小です。それ以降は34、38、39、43、44、 ・・・といった数値が何度も出てきます。 恐らくN=16の時の比較的評価の高い盤面というのが数える程しか存在しないのが 同じ評価の盤面が何度も見つかる理由だと思います。 もしN=16が存在するとしたら、 上級手筋もしくは総当りをしなければ解けない非常に難易度の高い盤面か、 1個でも数字の入る場所を変えると途端に評価が物凄く落ちるけど その特定の配置の時のみぴったり成立するという盤面になる筈です。 盤面の評価には処理速度の速いロジックしか使っていないので もう少し減る可能性はありますが、恐らくどんな手筋を使っても 最大の評価が大きく変わる事は無いと思います
大変ご無沙汰しております、あらです。 なんか数独のN=17問題がすごいことになっていますね。 私もやってみたいのはやまやまなんですが、なかなか時間が… それでひとつお聞きしたいのですが、 16個入れた段階での「全てのマスに入る数字の候補の合計」 というのはどのくらいになっているのでしょうか？ これを見れば、N=16がもう少しで出そうかどうかというのが、 少しは分かると思うのですが。 また、1つ入れた段階、2つ入れた段階...でのその数字の動きも気になります。 それぞれの段階での最小値を見れば、 もしかしてN=16がないことの証明のヒントが得られるかもしれないと思うわけです。
高橋謙一郎さん、レス有難うございます。 処理自体はそんなに難しいことはしていないのですが、私の説明不足が多いと思います。（爆）テヘ。 概念的には高橋謙一郎さんの思っている処理で合っています。 一般的なgaussian algorithm の一部（変化形？）です。 （すみません、日本語でなんて呼ばれているか分からなかったので。。。） array a[] から、L-U fatorizarion でL,U 、二種類の配列を求め、そこから解を求める奴です。 でも、これだけでは意味が無いので、同時に盤面を解くには何が必要か調べてみたわけです。 盤面を一種の圧縮された情報だとすると、シャノン系の情報処理理論の応用で一定の 空間に劣化しないで収まる情報量を求めることが出来るので、 設けられている制限に沿って、盤面を「展開」すると１種類しか回答がでないかどうか わかるわけです。 情報量が足りない＝たとえ盤面を「展開」しても、制約が完全に全ての マスに行き渡らないつー意味です。 これだけだと理解しにくいですが、結論から言うと、 row にせよ、columnにせよ、ゲームを遊ぶ上では何処から他に使われている数字、 使われていない数字、等の「制約」が十分に無いと、どの数字が当てはまるか分からないのです。 今の数独のプログラムの殆どは、「解凍」はまあ有る程度brute forceなり、標準的な マスからの情収集なりで出来ますが、「圧縮」の分野については殆未解析の状態です。 （まあ、みんなプログラム作る上である程度はしているけど） （この掲示板を読んでる人には 当り前 かもしれませんが、まあそう言わずに 読んでやってください） 例えば、３＊３で １２３ ４ .６ ７８９ なら、かなりあかるさまに、「５」であることが分かります。そーふぁーそーgood? そんな感じで、これを９＊９で、一行ごとで当てはめてみる。 これが一行。 [x][x][x][x][x][x][x][x][x] この１行にはいる数字の順番が「確定」するのが、最小で、 ８マスを外部からの「ヒント」で、さらに「ルール上の制限」を加えた事で、 分かるのですが、それでも、両端はつながっているので、最低でも１つ、実際の数字で 位置を固定する意味で必要。 もし、外部からの「ヒント」が７しか無い場合。。。 [1][8][3][5][6][7][9][x][x] [1][8][3][5][6][7][9][4][2] [1][8][3][5][6][7][9][2][4] ４、２ どの順番で入るか分からない。 実際の数字が１つも無い場合 [2][3][5][6][7][9][x][x][1] [3][5][6][7][9][x][x][1][2] ... [7][9][x][x][1][2][3][5][6] どれが当てはまるか分からない。。。 ほんでもって、これがタテヨコ両方からかかるのですが、 今のところちゃんとした情報理論として（途中経過だけでも）発表されたのが見当たりません。 結果的にみんなそれぞれ同じ事を「再発見」なんて事になっています。 プログラミングの問題としては（後に書いてある物以外で） １-ゲームツリーの分岐点、つまり数独ルールの一覧の解析が出来る人誰か。 情報処理理論を当てはめて理論（最小）値を証明するにも、「隠れルール」 が構造上存在すれば、意味が無いので。 （前回のレスはこの辺りをこねくり回した結果、１６は無理っぽいと出たと報告） ２-上の解析で、ルール一覧、及び最小情報量が分かった時点で、 n=16は可能か、不可能か分かるのですが、それはあくまでルールを守った時の話し。 ここまで来ていれば、まるで「圧縮」「解凍」の様に自由自在に最小値で盤面を 作り出せるので、今までいろいろ温めてきた盤面評価アルゴが使えます。 私の考えでは、9*9の盤面は3*3のブロックが、9つ有る方法です。 まず第一の制約として、3*3で1から9まで使いきる事を先に処理すると、 3*3の盤面でルールを満たす事が出来るのは 362880盤面です。 ですが、数独では「外部」からの（1 から9 で１行）制約が有るので、実際の「検索領域」 は遥かに少ないです。 この、9*9では f(f()) の様な、3*3の状態より多くの制約が有る事を利用すると、 検索は全ての領域では無く、 一つ目の制約を考えに入れただけで、9ブロック のうち 5ブロックだけ最小＋１の 情報量で済むのですが、こうやって、情報量の制限を重ねていくと問題が有り、 プログラムとして 9*9 の 81 element で盤面を表現することが出来ないつーのが あります。各ブロックごとに、 周辺（[x,y+1],[x,y-1],[x-1,y],[x+1,y]）から得られる 4ブロック分（36マス）の外部からの間接的な情報の記録が必要なのです。 ポインタを除いて、(362880盤面) 3265920 byte（約3MByte）のランダムアクセスメモリは まあ、許せるのですが、ポインタをint32、element=int8 としても、 9(block)*9(element)*4(address)今は使っているのです。（汗） 現在の（アイデア上の一番少ないメモリfootyprint）アルゴリズムでも一盤面あたり ビット演算と逆time-memory trade off でint8 でも2 element収まるのですが... それでも324bit(40byte)を、(盤面indexは含まれていない)必要なんです。 この「検索領域」は少ないんですけどねえ。。。 とくしんさんのプログラムは時間が無くまだ見ていないのですが、読む限りでは 何らかの「ダーウインの進化論」的なインプリメントがされているようですね。 （間違っていたらごめんなさい） ＞初期値を決める時に全ての盤面を作り評価しておきます。 より良いもの（盤面）を残し、後は絶対的な処理量を減らす意味も兼ねて テンプレート／もしくは検索領域への位置マーカ的なモノを用意しているみたいですね。 かなり（分かっていると思うので）省きますが、数独のように 1-全体の構造の「完全」解析が済んでいない（数学的に、と言う意味で） 2-サンプル数がすくない（n=16 はまだ出ていない） 場合は、プログラムの癖が出やすいです。 王道は、probability なり cluster analysis なり、何らかのstatical test を行い、初期値を（回答が有りそうッぽい位置を）決めるのですが、 現在の状態ではそれも出来ませんし。（唯一の証明も今はまだbrute force ぐらいです） ただ、「仮に」 数独 の内部構造上、function が 「可逆」 であるのならば、 （プログラムが全てのルールを、「隠れた」のも含めて、アルゴリズムで実装していれば） いずれ n=16 まで ツリーを上り詰める事が出来るはずです。 （今はn=17 の 12半固定、5 ランダムでやっているみたいですが。）
いんヴぃご さん、こんばんは。 難かし過ぎて全く理解できないのですが、いんヴぃごさんの解析内容というのは数独の構造 やルールをマトリックス化して、それを因数分解(?)すると因子の数が17個とか16個とかに なり、それでも、理論上は、N=16の問題が1個だけ(対称解を除いて)存在するはずだという ことなのでしょうか。(自分でも何を言っているのか分からない) とくしんさんの報告といい、いんヴぃごさんの報告といい、凄い高レベルになってきました。 残念ながら自分のレベルの限界を超えてきたので、応援団の立場として協力したいのですが プログラミング上の部分問題がありましたら、何か協力できるかも知れませんので遠慮なく 書き込みをお願いします。 # L-U factorization という単語は日本語ＨＰの検索では皆無に等しいですね。