数独プログラミング
ホームズくんの数独が理詰めでは解けない、ってのが発端w 手詰まりの図↓ ここからはバックトラック 1○○ 238 ○○○ ○○8 ○67 5○○ ○7○ ○○5 ○○8 ○○3 ○○6 ○29 ○1○ 593 48○ 98○ ○24 ○35 ○6○ ○○○ ○○1 ○○1 6○○ ○7○ 8○○ 371 ○○4 > 239 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/16(月) 08:58:19 > ねぇねぇ。演繹的って、たとえば > 「ここに、4か9が入る。他の可能性はない」 > まで論理で詰めたとするでしょ? > > ・仮に4だとして→やってみたら全部きれい埋まった ←←これはダメだよな。アフォの > オレでもわかる > > ・仮に9入れてみると→10手先で矛盾がおきる→だから9はありえない→よって4 > > 後者はいいの??? > 242 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/16(月) 09:01:45 > だめー。それバックトラック=帰納法。 > 243 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/16(月) 09:02:32 > この数独は仮置きしなくても全部理詰めでできるよ この 243( 2010/08/16(月) 09:02:32 )氏が釣りであったというのが興味深い どうせバックトラックするなら最初からバックトラックしてやれ、ということでperl(結果的に 十分実用的であったw)で書いてみた。 @mat=( 1,0,0, 2,3,0, 0,0,0, 0,0,8, 0,6,0, 5,0,0, 0,0,0, 0,0,5, 0,0,8, 0,0,3, 0,0,0, 0,2,9, 0,0,0, 5,0,0, 4,0,0, 9,0,0, 0,0,4, 0,3,0, 0,6,0, 0,0,0, 0,0,0, 0,0,1, 6,0,0, 0,7,0, 8,0,0, 0,7,0, 0,0,4 ); $t1 = (times)[0]; find(0); sub find { my $k; my $p=$_[0]; if( $p >= 80) { printdata(); $t2 = (times)[0]; $t3 = $t2 - $t1; print "$t3 秒\n"; exit; } if( $mat[$p]) {find( $p+1);} else { for( $k=1; $k<= 9; $k++) { if( IsThisOK( $p, $k)) { $mat[$p] = $k; find( $p+1); $mat[$p] = 0; } } } } ※インテンドの空白が全角になってるので注意 <続き> sub IsThisOK( ) { my $p=$_[0]; my $k=$_[1]; $row=int($p/9); $col=$p%9; for( $i=0; $i< 9; $i++) { # 同じ行にkが使われていないか? if( $mat[$row*9+$i] == $k) {return 0;} } for( $i=0; $i< 9; $i++) { # 同じ列にkが使われていないか? if( $mat[$i*9+$col] == $k) {return 0;} } #// 同じブロックにkが使われていないか? $rowBlock = int($row/3)*3; $colBlock = int($col/3)*3; for( $i=0; $i< 3; $i++) { for( $j=0; $j< 3; $j++) { if( $mat[($rowBlock+$i)*9+($colBlock+$j)] == $k) {return 0;} } } return 1; } sub printdata{ print("\n"); for( $row=0; $row< 9; $row++) { for( $col=0; $col< 9; $col++) { print $mat[$row*9+$col]; } print("\n"); } } ※インテンドの空白が全角になってるので注意 【実行結果】 154238796 298467513 376915248 543786129 612593487 987124635 769842351 431659872 825371964 7.925 秒 ↑ ちと待つが、十分実用的。 結論→仮置き=バックトラックが許されるのであれば、プログラム書いた方が 早いw さて、ここで、数独って1〜9でやるが、数字の大きさは意味がない訳で A〜I でも あ〜け でも言い訳で。 だから、「1番上の行は"1,2,3,4,5,6,7,8,9"」と仮定することができる(たとえば、 2と3が全部入れ替わってる解答というのは同型とみなす) そこで、レス3の一番上を @mat=( 1,2,3, 4,5,6, 7,8,9, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, 0,0,0, ); にして解いてみよう。 これは一瞬で解けてw 123456789 456789123 789123456 214365897 365897214 897214365 531642978 642978531 978531640 0.062 秒 165 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/24(火) 12:04:23 >>50 の次の一手は>>116 で出せる。 ttp://www.uproda.net/down/uproda131259.jpg C行で3が入るのは1列か7列のみ。G行でも1列か7列のみ。 よって3が入るのは、C-1 and G-7 か、C-7 and G-1 に絞られる。 いずれにしても、1、7列のC、G行以外の3は消去できる。 177 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/24(火) 12:32:08 >>165 ええとw どこからツッコんでいいものかwww 1.まずそもそも「次の一手」が示せてないじゃんw 2.対角だのX-Wing だのは型はめして解答時間を早くする or 説明を簡単に できるようにするための便法であって、「論理」で説明できる。 3.貴殿の例でも、「B−1にもし”3”が入ると仮置きすると」→1-Cに3が入らないことになる →すると、横列をみると、C-7に3が入る→G-7には3は入らない→するとG列ではG-1 に居れざるを得ないが、これはB-1に置いた(仮置きの)3と conflict する。 よって、B−1は、”3”ではない というだけ。類型・公式化しとけば、論理追わなくてすむってだけw 4.でもって、B-1の例でいえば、「3で仮置きして矛盾が出たの→バックトラッキングで →次に2か4を試す」ってことだから、(このスレで出てる最狭義の)「理詰め」にはならないよ 180 名前:( ・∀・)つ〃∩ヘェーヘェーヘェー[sage] 投稿日:2010/08/24(火) 12:49:32 >>177 お前のその説明だったら、 A-2に1を仮置きするとA-1の1がA-2に仮置きした1と衝突するのでA-2は1ではない ということで全ての手がバックトラックになるよね ↑これは理解できたの? >>8 頭悪い人? 同じブロックに1が既にあるんだから、「A-2に1を仮置きする」 なんて有り得ないよ??? >>9 じゃあ本題に戻ると、 B-1に3が入らないことがわかってるんだからそこに仮置きするなんてあり得ない ってことは理解できた? >>9 >>3 のプログラムはそういうことをやってるんだよ プログラムを書くときはそういう風に書くほうがシンプルに書ける >>7 あと何通りの答えがあるかわかれば 数独の答えのパターン数がわかるね 週末の朝日新聞に載ってた超良問 すべて演繹法(推理だけ。バックトラックしない)で解ける したがって「難問」ではないが、論理性が試される「良問」(テクニック不要) ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓ ┃ │ │ ┃ 4│ │ 1┃ │ 2│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 1│ ┃ │ 7│ ┃ │ │ 6┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 5┃ │ │ ┃8 │ │ ┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ 6│ │ ┃1 │ │ ┃ │ 9│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 9┃ │ 2│ ┃ 6│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 2│ ┃ │ │ 8┃ │ │ 3┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ │ │ 7┃ │ │ ┃ 3│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 8│ │ ┃ │ 5│ ┃ │ 1│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 4│ ┃ 3│ │ 7┃ │ │ ┃ ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛ ・ぱっと見のとおり1がすぐ埋まる ・簡単に埋まるのは1だけでしばし熟考。次の一手! ・その一手は論理だけで決めることができる(テクニック使ってもできるのかもしれないけど 演繹的論理だけで決められる) ・その一手が決まるとその次も論理的にすぐ埋まる(同じ数字) ・↑を先に埋めたか関係なく別の数字で次の2手 この4手↑(序盤の1をほぼ埋めた後の4手)を論理的に導き出せれば論理力がかなりあるとみていいかとw 要するに・・・ ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓ ┃ │ │ ┃ 4│ │ 1┃ │ 2│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 1│ ┃ │ 7│ ┃ │ │ 6┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 5┃ │ │ ┃8 │ │ 1┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ 6│ │ ┃1 │ │ ┃ │ 9│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 1│ │ 9┃ │ 2│ ┃ 6│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 2│ ┃ │ │ 8┃1 │ │ 3┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ │ │ 7┃ │ 1│ ┃ 3│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 8│ │ ┃ │ 5│ ┃ │ 1│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 4│1 ┃ 3│ │ 7┃ │ │ ┃ ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛ これの「次の一手」を演繹的に詰めろ、ってことか。 その次3手も。。。 >>14 わーい。できたー。 1の次に埋めるとこが>>14 と違うみたいで言ってることがわからなかった >>16 > わーい。できたー。 うそつけwwww 本当にできたなら、「次の一手」を論理的に書くわいw てか、ムズいなこれw ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓ ┃ │ │ ┃ 4│ │ 1┃ │ 2│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 1│ ┃ │ 7│ ┃ │ │ 6┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 5┃ │ │ ┃8 │ │ 1┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ 6│ │ ┃1 │ │ ┃ │ 9│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 1│ │ 9┃ │ 2│ ┃ 6│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 2│★┃ │ │ 8┃1 │ │ 3┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ │ │ 7┃ │ 1│ ┃ 3│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 8│ │ ┃ │ 5│ ┃ │ 1│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 4│1 ┃ 3│ │ 7┃ │ │ ┃ ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛ 次の一手は★で、数字は4 ★の縦で1、5、7、9は無い ★の横で、2、3、8も無い そしてBOXでみると6も無い →よって演繹的に★には4しか入り得ない、といえる ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓ ┃ │ │ ┃ 4│ │ 1┃ │ 2│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 1│ ┃ │ 7│ ┃ │ │ 6┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 5┃ │ │ ┃8 │ │ 1┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ 6│ │ ┃1 │A │ ┃ │ 9│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 1│ │ 9┃B │ 2│ ┃ 6│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 2│4 ┃★│★│ 8┃1 │ │ 3┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ │ │ 7┃ │ 1│ ┃ 3│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 8│ │ ┃ │ 5│ ┃ │ 1│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 4│1 ┃ 3│ │ 7┃ │ │ ┃ ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛ 1.Aのところを縦にみていく (1)Aより上は同一ボックスに4があるから入り得ない (2)Aの下(★)は同一行に4があるから★は4ではない (3)同様に一番下も4ではない →よって、4はAにしか入らない。A=4 2.★2つのところの上2行をみると、6と9がある。 よってこのボックスで6と9が入り得るのは★の2か所だけ この★のどちらかが6でどちらかが9。たとえば7は入らない。 今度は縦にみるとAの右の列も7があるから縦2マスの空白 は7ではない。 よって、このボックスで7が入るのはBのみ。B=7 ┏━┯━┯━┳━┯━┯━┳━┯━┯━┓ ┃ │ │ ┃ 4│ │ 1┃ │ 2│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 1│ ┃★│ 7│ ┃ │ │ 6┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ │ 5┃ │ │ ┃8 │ │ 1┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ 6│ │ ┃1 │4 │ ┃ │ 9│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 1│ │ 9┃7 │ 2│ ┃ 6│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 2│4 ┃69│69│ 8┃1 │ │ 3┃ ┣━┿━┿━╋━┿━┿━╋━┿━┿━┫ ┃ │ │ 7┃ │ 1│ ┃ 3│ │ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ 8│ │ ┃ │ 5│ ┃ │ 1│ ┃ ┠─┼─┼─╂─┼─┼─╂─┼─┼─┨ ┃ │ 4│1 ┃ 3│ │ 7┃ │ │ ┃ ┗━┷━┷━┻━┷━┷━┻━┷━┷━┛ 次に真ん中のボックスの縦空白2マスは、どちらかに5 が入ることがわかる(残りは3か5) そうするとその上のボックスの一番右の列には5は 入らないことがわかる 真ん中の列は下の方に5があるからやはり5は入らない 左の列(★のある列)の一番下はその左に5があるから やはり5は入らない よって、★=5 >>17 次の一手を書かなかったのは俺が答え書いちゃったらダメかと思ったから。 もう埋め方出てるので>>19 の★埋める前に>>20 のA埋める方法書きます。 説明の為に列を左から右にABCDEFGHIとし、行を上から下に123456789とします。 D1とB9にある4により、下段中央のBOXの4はF7・F8のどちらかに入ります。 なので他のBOXのF列には4は入りません。これと、D1にある4により中段中央のBOXの4はE4かE6に入ります。 このときD6・E6には6と9が入るので(これは>>20 と同じ考え方で)、E6に4が入ることはありません。 なので中段中央の4はE4に入ります。 どうでもいいが、バックトラックは立派な演繹法の一種。 理詰めの部類なんだが・・・ >>24 論理的にはそのとおりなんだが、PCの普及・高性能化で、バックトラック認めると 「コンピュータで左上から1から順に入れてバックトラックしまくったら0.07秒で答えがわかりました」 が蔓延してしまう (´・ω・`) 904 名前:水先案名無い人[sage] 投稿日:2011/07/04(月) 09:41:58.44 ID:TNhScJ0z0 [1/2] い…石原殿…今月のジャンプSQ…あれはエロ漫画雑誌にござるか? 908 名前:水先案名無い人[sage] 投稿日:2011/07/04(月) 13:02:08.43 ID:DYEfQDZp0 [1/2] 今月の四角も ただならぬ仕上がり であった 909 名前:水先案名無い人[sage] 投稿日:2011/07/04(月) 13:10:29.41 ID:YBfGpSdQ0 加減しろ莫迦!一般誌だぞ 矢吹神も長谷見も一切詫びなかった 911 名前:水先案名無い人[sage] 投稿日:2011/07/04(月) 13:56:36.92 ID:qNWXKw9HO おそるべしは 画太郎に萌え絵で乳揉みを描かせるSQ 己の評価はそのようなものに落ち着いた 914 名前:水先案名無い人[sage] 投稿日:2011/07/04(月) 15:20:39.86 ID:tkTlqKkOO [2/2] こ、こは何事!? こは創刊当初の意気込み通りの「月ジャンより広い層へ向けた総合少年漫画誌」などにあらず! ダークネスが当然顔で毎度表紙を張る… ぬふぅ 青少年健全育成条例の恐怖に怯えていたのはむしろ 初心者です、解けません。。。 29〇○○846○ ○○421○○○9 ○○○○○6○○○ ○25○○○6○3 ○76○○○1○4 3○○○○○○5○ ○○713○○○2 ○○○○○2○○○ 152○○734○ >>27 真ん中の9マスの左上(6の下で、6の左)に1が入る。 けっこう簡単な問題だと思う。 がんばって。 ありがとうございます。(1)わかりました。次が???です。 何で1が入るかは分かりました? ○25 ○76 3○○ 左中央の9マスですが、3の右かその右にしか、1は入れませんよね。 ということで、上に書いた位置に1が入ります。 次は左上の 29○ ○○4 ○○○ の9の下に6が入ります。 ヒントは縦の列の5・7と、横の列の6かな。 ってほとんど答えですけど^^; はい、1はあの場所しかありませんね。あと29○の○が1かどうかまよいます。 正直何日も考えています。 http://eroerodouga3825.dti blog.com/ 私のお部屋に遊びに来てアソコを熱くして…! 体が溶けるようなHをしよぅ☆ ぃぇーぃヽ(^o^)丿 ガバッ ∧_∧ __(;・∀・)_ ⊂L/ ( )丶⊃ ( | つ| ) )_/ ∧ 丶( (__)(__) ∧_∧ __( ・∀・)_ ⊂L/ ( )\⊃ ( | | ) )_/ っノ_( (_フ(_フ ∧_∧ ( ・∀・) `____/|\/丶__ (⊇__/ Y_ _丶_⊆) | /、 i / \ / /|□■□■□ /// ■□■□■ / / / \ \ | |( ( ) ) | | \ \_/ / /| レ-⊂⌒_)(_⌒つ<ノ 見られたままの方が都合のいいこともある 完全に削除するのはやめておこう 数独は IQテストの動作とも似ている 適正検査やその他の検査にもあるが(数独ではないパターンのが) 稀に企業の試験でも似たようなのが使われることがある それを高度にした形 単純作業能力よりもさらに高度な能力を測ることができる 独学で全ての数字が埋まってる状態を作った 左上からランダムに数字を入れていって 都度重複チェック駄目なら別の数字を入れチャレンジ 1〜9全て入れてみても駄目なら行の始めから入れ直し ってルーチンで出来た 凡才と言ったばばあは一週間で解析プログラムを作ってみろよ。 あと全敗だと言ったじじいと、使い捨ての技術と言ったじじいもな。 てめぇら調子に乗りすぎw こちらが誰だか分からない人間、知らないあるいは見えないところから 誹謗・中傷をするというのは卑怯そのもの。 訂正 こちらが誰だか分からない人間、知らない人物であったり、見えないところから 誹謗・中傷をするのは卑怯・卑劣そのもの。 うるさいから外からガタガタ言うのをやめろよ。 勘違いがいると不愉快なので明確に言っておくが、全て独自開発を行ったものであり 本体部分の他のソースの流用は全くない。 訂正 本体部分以外での、他のソースの流用は全くない 2012年世界で一番難しい問題 800000000003600000070090200050007000000045700000100030001000068008500010090000400 では世界最速といっているソフトより、2.5倍速いにも関わらず、何の反響もない 再訂正 本体部分での、他のソースの流用は全くない 「嘘書かなくていいよ」というようなことが何回か聞こえてくるが 私は2chに虚偽の内容を書いたことは一度もない。 The next version will be compatible with following function. ・group interconnect links in the box (Grouped X-Cycle/Nice Loop) ・strong link in the group (Grouped Nice Loop) 負けてくやしい方が多数おられるようですね、ナイス! The next version will be compatible with following function. ・Grouped Nice Loop with ALS links ・ALS-XZ/ALS-XY-Wing/ALS-Chain/Death Blossom 3714でもいいよ、世界最速の解析システムを。 次のversionではperfectになるからね。 多くの馬鹿には無理だろうけど。 今公開されているものの、UIに不具合が見つかった。ここの部分は前回の更新で、変更を加えていない部分 だった。そこで考えられるのは、以前所属していた会社の人間が行ったことと同じように、誰かがこの場所に 来て、人の知らない間に、不具合が盛り込まれるように改竄を行ったか、それをリモートから行ったかのどちらかだ。 そんなに人の足を引っ張りたいのかね。笑える。 それから、「盗んだものを評価できるか。」という誹謗が聞こえてきたような気がするが、お前らカスは本当に 卑劣な人間性で、その根拠もないことを人の耳に入れればいいと考えているのか。 幼稚極まりない。今も聞こえてきているが、愚劣な誹謗中傷を言うのを止めろ。 まともな文句があるのであれば、直接私の前で言うかそれか文章をメールなりでよこせ。 >>54 ああ、キミ!また会えたね。久しぶりだ。どうだいあの件は?どうなったか説明したまえな。 神戸市の東、芦屋西宮の知的障害者施設で未成年利用者に性的な行為をして淫行条例で逮捕された三田谷学園元職員の堂垣直人(西宮市老松町)は、結局どういう罪になったの? 被害者家族のケアを芦屋市役所と兵庫県警はちゃんとやったのか? 差別や虐待は環境を選べない子供には関係ない。 http://www.youtube.com/watch?v=JxMzW3ZlV4g& ;sns=em まあ、こっちに座れよ。ゆっくり話そうじゃないか。 warezで世界最速は実現できない。レッテル張りは不愉快極まりない。 前回の放送でアンビリバボーの酔った人間に対して丸太を投げるというのがあったが T字路でナンバープレート3番の丸太を積載した車両が私の前を通過していった。 当然、一時停止で止まらなければ私はこの世にいない。 もう私に森ビルで嫌がらせをしたおした、自民党の財務政務官は終わりだ。 そのクズはテレビで意味不明に頭を下げていたが、そういうことだろう。 こいつの誹謗中傷のおかげで、ただ机の脚を蹴ったぐらいのことで解雇だ。 轢こうとしたクズも取り合えず、死んどけ。 馬鹿なラジオが黒黒うるさかったり、有線で負け犬だとか 全く事実とことなる心理操作お疲れ様です。 次のversionで勝者になることができました。 read.cgi ver 07.5.5 2024/06/08 Walang Kapalit ★ | Donguri System Team 5ちゃんねる