プログラミングパズルに関心のある人は雑談しましょう!
1.rubikcubeの解読プログラムの追求、まだ執拗に追いかけております。3ステップまでは何とかなりそうですが、そこまでと思っています。センスの良い人が取り組めば一週間で今までの分を追い越されそうな気もいたしますが、もう少し続けます。都度改訂版をupしております。 2.suudoku\\\\さんの投稿の主旨はなんなんですか? 両題とも確かな問題であることは確認いたしましたが、ただ単なる出題なのか、ヒント17問題が新題と言われているのか他に意味があるのかつかめておりません。 3.「パズル&ゲーム10種競技」と称する出し物を公開いたしました。 このサイトの多くを参考にさせていただきましたが、「WATTA]君や倉庫番には遠く及びませんでした。でも一応、Guest参加型です。一度訪問してください
簡単 ヒント数19 000700040 030000018 000590000 801000000 004000500 000000709 000081000 560000000 090002000 ヒント数17 008000000 601400007 000050000 007006000 030020500 000000004 000701000 250000800 000000000
imageを16分割し、それをバラバラにセットした局面から、15パズル式に元図に戻す遊び物を、以前からHPに upしていました。ただし、そこには15パズルの解読プログラムは搭載しておりませんでした。今回、純粋15 パズルを追加するに当たりプログラム開発を試みたのですが、うまく出来ず結局このサイトの公開プログラム 「15パズル解読プログラムの作り方」をそのまま移植させていただきました。 別件1 rubikcube 改訂しました(2008/12/24) 別件2 自分のHPにも「数独solver」をupしております。 南無さんのように広範にその性能を確かめてはおりませんが、人(自分)が解くのに準ずる道筋で何段階か ステップを踏んで解を出しております。
>中目さん コメントありがとうございました。反応をいただけるのは何かと嬉しいですね。 試行錯誤については、確かに最初からこれを使えば比較的短いプログラムにて瞬時に解が得られます。 解を得ることだけが目的なら、試行錯誤の全面使用がお勧めです。 ところで、その後小生のソフトにつき、さらに手を入れて機能の向上を図りましたので、改めて紹介します。 これに組み込んだ手法は、http://www.geocities.jp/master_mishichan(ナンバープレ−ス,数独解法まとめ)に記さ れるところに準じた表現によれば次のとおりです。 基本:略 中級:多国同盟、多国同盟(Hidden)、X-Wing、他 上級:XY-Wing、浜田ロジック、Remote Pairs、Finned Fish、Sashimi Fish、Sword Fish、Simple Chain 超上級:Empty Rectangle、Multi Coloring、Advanced Coloring、Aligned Pair Exclusion、Jelly Fish、Headless Fish、 Finned Sword Fish、X-Cycle、XY-Chain、Broken Wing、Almost Locked Set、Death Blossom 超弩級:Pattern Overlay Method、Alternate Inference Chain、Nice Loop なおこの他にUnique Rectangleも用意してありますが、これは解がユニークであることを前提とした手法なので、原則 として外してあります。 また以上にて解けなかった場合の試行錯誤については次のとおりで、試行錯誤Uは試行錯誤Tで解決できなかった場合 のものです。 試行錯誤T:未解決のマスにつき候補数字のうちの一つを仮置きして解法を進め、矛盾を生じたらその仮置き数字を候補 数字から削除する。これを未解決のマスの各候補数字について繰り返す。(解のユニーク性を担保) 試行錯誤U:未解決のマスにつき候補数字のうちの一つを仮置きして解法を進め、矛盾が生じたらその仮置き数字を別の 候補に置き換えるか、仮置き数字を元の状態に戻して他の未解決のマスに移る。矛盾を生じなければ仮置き 数字をそのままにして、順次他の未解決のマスに移り同様のことを繰り返し、全てのマスが埋まる組み合わ せをいくらでも探す。 また、世間で極めて難問と思われるナンプレ問題集に改めてこのソフトを適用してみた結果は次のとおりでした。 @まず、世界文化社の「難問ナンプレに挑戦」@〜Cについては、その全てについて超上級以下の手法にて試行錯誤なし に解け、かつその9割以上は上級以下の手法で解けます。 A次に、廣済堂出版の「ナンプレ」超難問編及び限界編(これらはいずれも試行錯誤を要する前提での問題の造りと想定 される)については次のとおりです。 ┏━━━━━━┳━━━━━━━━━━━━┳━━━━━━━━━━━━━━━━━━┓ ┃ ┃ 超難問編 ┃ 限界編 ┃ ┣━━━━━━╋━┯━┯━┯━┯━┯━━╋━┯━┯━┯━┯━┯━┯━┯━┯━━┫ ┃ Level ┃10│11│12│13│14│ 計 ┃11│12│13│14│15│16│17│18│ 計 ┃ ┣━━━━━━╋━┿━┿━┿━┿━┿━━╋━┿━┿━┿━┿━┿━┿━┿━┿━━┫ ┃ 問題数 ┃22│17│23│17│26│105 ┃10│17│15│20│11│12│10│10│105 ┃ ┣━┯━━━━╋━┿━┿━┿━┿━┿━━╋━┿━┿━┿━┿━┿━┿━┿━┿━━┫ ┃所│ 中級 ┃ 5│ 4│ 2│ 0│ 3│ 14 ┃ 0│ 3│ 4│ 3│ 2│ 1│ 3│ 0│ 16 ┃ ┃要├────╂─┼─┼─┼─┼─┼──╂─┼─┼─┼─┼─┼─┼─┼─┼──┨ ┃最│ 上級 ┃ 6│ 4│ 3│ 1│ 5│ 19 ┃ 1│ 1│ 3│ 5│ 3│ 2│ 0│ 0│ 15 ┃ ┃高├────╂─┼─┼─┼─┼─┼──╂─┼─┼─┼─┼─┼─┼─┼─┼──┨ ┃手│ 超上級 ┃ 6│ 4│ 7│ 7│ 4│ 28 ┃ 2│ 7│ 1│ 4│ 2│ 3│ 3│ 1│ 23 ┃ ┃法├────╂─┼─┼─┼─┼─┼──╂─┼─┼─┼─┼─┼─┼─┼─┼──┨ ┃別│ 超弩級 ┃ 5│ 5│ 8│ 7│11│ 36 ┃ 6│ 5│ 5│ 6│ 3│ 4│ 3│ 6│ 38 ┃ ┃件├────╂─┼─┼─┼─┼─┼──╂─┼─┼─┼─┼─┼─┼─┼─┼──┨ ┃数│試行錯誤┃ 0│ 0│ 3│ 2│ 3│ 8 ┃ 1│ 1│ 2│ 2│ 1│ 2│ 1│ 3│ 13 ┃ ┗━┷━━━━┻━┷━┷━┷━┷━┷━━┻━┷━┷━┷━┷━┷━┷━┷━┷━━┛ 上は、当該本が超難問、限界とのうたい文句にしては、中級手法でも解けるものが混じっていること、問題の約9割は 試行錯誤なしに解けること,本に表示されている難易のLevelの基準が少々曖昧であることなどを示していますが、総体 的に難問であることは認められます。 Bさらにhttp://www.sudoku.org.uk/daily.asp(Sudoku Online : Sudoku of the Day)なるHP(英国)に掲載されている 「Sudoku.Extreme」の問題(目下計104題)については、さすがにすべてが超上級以上の手法を必要とします。目下の状 況は、小生のソフトにて超上級までにて解けるものが26件、超弩級までにて解けるものが65件、試行錯誤を要するも のが13件です。 なおこのHPには、「Sudoku Solver」なる強力な解法ツールが備わっており、これを使ってみた結果は上と殆ど一緒で したが、試行錯誤(BowmanBingo)を要したものが少なくとも14件ありました。 小生のソフトと「Sudoku Solver」との比較では、Almost Locked Set及びDeath Blossomの扱いに関し、小生のソフト の方が強力であり、これが上の違いに表れています。 Cその他の例では、ニコリの「激辛数独」、世界文化社の「ナンプレ」超上級編は、チェックした範囲内において、殆ど が中級以下の手法にて解けます。 以上ご参考まで。
もはやだいぶ前から諦めてるんですが、久々に見たらコメントがあったので 最新版の417バイトを置いておきます。誰か5行に収めてくれませんかね。 class Q{public static void main(String[]a){for(;s<82;n=-7)for(c=new int[730],c[ 40]=s%3;n<l;l=730)if(c[y=n++/9]>(n<0?c[m=(int)(Math.random()*81)]=m:0))for(c[y% 9*9-y/9+8]+=s=1;l-->0;c[y]^=v,c[z]^=v)c[z=l/9+300]^=v=z>(y=c[l]|=l<84?0:511)&(( v=(y>0?1<<y%9:-1)&c[z]&c[y=84+l%9]&c[z+=y/3-z%3])&v-1)*2<v?v+=(l=84)-++s<m?n=0& m--:0:0;for(;y-->0;)System.out.print(--c[y]%9+1+(y%9<1?"\n":" "));}static int y,z,s,l,m,n,v,c[];}
中目さん、「ルービックキューブの解読プログラム」への反応ありがとうございます。 1.javaが表示されないとのこと、残念です。 解読プログラムそのものの評価も、勿論、気にしておりますが、実は ・解読結果のアニメーション表示 ・キューブを解体した状態(6つのセンターキューブとばらばらにされた20ケ)から 任意に組み立てそれをスタート状態とできること を可能にしてます。 このことは HP の出し物としての価値を上げていると自負いたしております。 ただ、これらの機能が他の人のパソコン環境でも働いているか不安なところです。 2.解読プログラムについて ・3*3*3 のみの思考です。 ・但し、2*2*2については一作目の解読プログラムの第一ステップで8角を揃えました。 勿論、最短手順です 10手以下だったと思います。 ・今の解読プログラムver2では以下の4ステップになっております。 @1面を揃える(プログラムによる最短手順の探索 10手以下) A中段を揃える(最短手順の探索 12手以下) B残り一面の角を揃える(最短手順の探索 13手以下) C残りを揃える(最短手順の探索 14手以下) このように各ステップ間では最短手順ですが、3回も寄り道をしております。 多くは40手前後、最悪45手(? 記録を残しておりません) なお中段を回す手は2手として計算しております。 >正六面体の回転⇒1手目は12手、2手目は11手.. 理解できないのですが! ・今、ver2 のBとCの統合に挑戦中です。まだ途中ですが 多くは13手以下、最大15手との感触を得ています。 すなわち、残り一面をステップなしで揃えるならば、2手ほどの増加でできます。 ・「スパコンの26手以内」の詳細は分かりませんが、スタートから一気の最短手順なら 20手前後に解があるような感触を持っております。もっともパソコン環境では 12手を越える頃からの解読時間は分単位となり、一手増すごとに20倍費やします。 とにかく、コメントありがとうございました。
高橋さん、はじめまして?(かなり昔から勝手にこちらに訪問させて頂いておりますが... 「倉庫番を解く for Windows」がバージョンアップされていたのですね?(半年も気づきませんでしたw しっかり頂戴し、その解法能力にも驚いておりますw ネットにて「一万盤面程度」収集して倉庫番を解くのを楽しんでおり、小生もプログラミングが趣味なのでその解答プログラムもと思っているのですがなかなかですw... >稲葉直貴さん 「少ないバイト数で数独の問題作成するスクリプト」という分野も確かにありですネ。 >南無さん 「試行錯誤」=「バックトラック手法」だと思うのですが、プログラムではバックトラックしてしまえば「数独」なんて簡単に解けてしまいますが、如何にバックトラックなしで解くかという楽しみもあるのですよネ。 御二人かとも素晴らしいですわ... 過去に「ヒント数<17に出来るか?」という事のカキコがありますが、これも課題ですよネ。 小生も昔、数独自動生成プログラムを組んでいましたが、ヒント数=16は出来ていません(当然? でも、「ヒント数=17」にて自動作成させたら、 7 12 5 5 3 4 6 1 3 8 2 7 3 4 1 6 なんて、ヒント数が17と少なくてもわりと簡単に解けてしまいますよネ! この「ヒント数>16でなくてはいけない?」なども凄く探究心をそそられます。 >tsuyoshikさん 小生のネット環境ではホームページ表示にてjavaが表示なれないので詳細は解かりませんが、 「ルービックキューブは26(25?)手にて解ける!」と言われても異次元の世界ですよネ? 手持ちのキューブを完成状態にしたいという事で昔作ったプログラムを動かしてみたところ、 @2x2x2 ・10手前後(これはプログラムにて完全に最善手を探索していました。 A3x3x3 1)底面の十字(中間ピース)を揃える(プログラムにて手順探索1回 2)底面及び中段の角(下2段の角)を揃える(プログラムにて手順探索4回 3)上段の上面色を揃える(パターン化したテーブル参照1回 4)上段の位置を揃える(パターン化したテーブル参照1回 以上の手順にて、50数手前後(最悪65手くらい? B4x4x4及び5x5x5 ・中央の2列又は3列を揃えて3x3x3のパターンにして解いていました(手抜きだわ! ・従って、4x4x4=150±40手、5x5x5=270±90手 くらいにて解いていました。 正六面体の回転⇒1手目は12手、2手目は11手...で、二十数手なんて無理!だと思っていましたが、何かいい手がとそそられますw...
全便への補足です。 ○ニコリ社「激辛数独」1〜4については約95%が中級手法以内にて、かつ全てが上級手法以内にて解けます。 @世界文化社の「難問ナンプレに挑戦」@〜Cについては、そのすべてが超上級手法以内にて解けます。 (所要手法の分類はhttp://www.geocities.jp/master_mishichan「ナンバープレ−ス,数独解法まとめ」に記されるものに準じています)
小生ここ何年来かナンプレ/数独の自動解法ソフト作成を趣味としてきました。そのソフトはまず演繹的に解くことを進め、それでも解けない時には試行錯誤を使うという造りなのですが、ここでいかにして試行錯誤への依存度を減らすかに特に取り組んでいたのでした。 ところで、しばらく前にhttp://www.geocities.jp/master_mishichan(ナンバープレ−ス,数独解法まとめ)なるHPを目にし、これが眼にウロコで、以来そこに紹介されている高度手法(特に超上級、超弩級など)の大部分ををソフトに取り込んで来ました。 最近この作業が一段落し、さて、世間で極めて難問とみなされるナンプレ問題にこのソフトを適用するといかなるものかをチェックしてみたところ、次のような結果でした。 @まず、世界文化社の「難問ナンプレに挑戦」@〜Cについては、そのすべてについて試行錯誤なしに解けました。 A次に、廣済堂出版の「ナンプレ」超難問編及び限界編(これらはいずれも試行錯誤を要するのが前提の造りと想定されている)については次のとおりでした。(最高所要手法の分類は「ナンバープレ−ス,数独解法まとめ」に準じています) ・超難問編 Level 10 11 12 13 14 計 問題数 22 17 23 17 26 105 中級 5 4 2 0 3 14 最高 上級 6 4 3 1 5 19 所要 超上級 6 4 6 5 4 25 手法 超弩級 3 4 6 5 8 26 試行錯誤 2 1 6 6 6 21 ・限界編 Level 11 12 13 14 15 16 17 18 計 問題数 10 17 15 20 11 12 10 10 105 中級 0 3 4 3 2 1 3 0 16 最高 上級 1 1 3 5 3 2 0 0 15 所要 超上級 2 6 1 4 2 3 1 0 19 手法 超弩級 4 6 2 3 2 2 0 4 23 試行錯誤 3 1 5 5 2 4 6 6 32 上は、当該本が超難問、限界とのうたい文句にしては、中級、上級で解けるものが混じっていること、本に表示されている難易のLevelの基準が少々曖昧であること、問題の7〜8割は試行錯誤なしに解けることを示しています。 Bhttp://www.sudoku.org.uk/daily.asp(Sudoku Online : Sudoku of the Day)なるHP(英国)に掲載されている 「Sudoku.Extreme」の問題(目下計95題)については、さすがにすべてが超上級以上の手法を必要とし、超上級までにて解けたものが15件、超弩級までにて解けたものが54件、試行錯誤を要したものが26件でした。 以上ご参考まで。 なお小生のソフトは自家使用の範疇であればフリーとすることも想定しています。関心のある方のレスポンスを待ちます。
反応してくださる方が現れてうれしい限りです。 あれからまた削ったので最新版の450バイトを置いておきます。 残念ながらスピードはかなり落ちてしまいました。 class Q{static int e=81,x,y,z,s,k,l,m,n,v,c[];public static void main(String[]a ){for(;s<e;){for(c=new int[810];n>1;n/=3)c[m=(int)(Math.random()*e)]=m;for(c[40 ]=s;++n<(l=9*e);)if(c[k=n/9]>0)for(c[k%9*9-k/9+8]+=s=1;l-->0;)if((k=c[l]|=l>=e? 511:0)<c[l+e]&(-k|(v=c[x=l/9+2*e]&c[y=171+l%9]&c[z=y/3+x-x%3])&v-1)<1){c[x]^=k> 0?v&=1<<k%9:v;c[y]^=v;c[z]^=v;n=m<++s?m-++m:n;c[l+(l=e)]=v<1?s=0:0;}}for(;e-->0 ;)System.out.print(--c[e]%9+1+(e%9<1?"\n":" "));}} こちらも協力してくださる方がいたらお願いします。 0 1 0 0 0 0 4 3 0 7 0 0 6 0 0 0 0 5 8 0 9 0 0 3 2 0 0 0 0 6 0 0 0 0 1 0 0 0 0 0 2 0 0 0 0 0 4 0 0 0 0 7 0 0 0 0 2 5 0 0 8 0 4 6 0 0 0 0 9 0 0 7 0 7 3 0 0 0 0 5 0