数独プログラミング

1 ：（　･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ：2010/08/26(木) 11:05:03 〜 最終レス ：ヒロチ：2011/11/20(日) 22:19:11.36

ホームズくんの数独が理詰めでは解けない、ってのが発端ｗ
手詰まりの図↓　ここからはバックトラック
１○○　２３８　　○○○
○○８　○６７　５○○
○７○　○○５　○○８
○○３　○○６　○２９
○１○　５９３　　４８○
９８○　○２４　　○３５
○６○　○○○　○○１
○○１　６○○　○７○
８○○　３７１　　○○４

2 ：

> 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　）氏が釣りであったというのが興味深い

3 ：

どうせバックトラックするなら最初からバックトラックしてやれ、ということでperl（結果的に
十分実用的であったｗ）で書いてみた。
@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;
　　　}
　　}
　}
}
※インテンドの空白が全角になってるので注意

4 ：

＜続き＞
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");
　}
}
※インテンドの空白が全角になってるので注意

5 ：

【実行結果】
154238796
298467513
376915248
543786129
612593487
987124635
769842351
431659872
825371964
7.925 秒
　↑
ちと待つが、十分実用的。
結論→仮置き＝バックトラックが許されるのであれば、プログラム書いた方が
早いｗ

6 ：

さて、ここで、数独って１〜９でやるが、数字の大きさは意味がない訳で
A〜I　でも　あ〜け　でも言い訳で。
だから、「１番上の行は"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,
);
にして解いてみよう。

7 ：

これは一瞬で解けてｗ
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531640
0.062 秒

8 ：

165 名前：（　･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ[sage] 投稿日：2010/08/24(火) 12:04:23
>>50の次の一手は>>116で出せる。
ttp://www.uproda.net/down/uproda131259.jpg
C行で３が入るのは1列か7列のみ。G行でも1列か7列のみ。
よって３が入るのは、C-1 and G-7 か、C-7 and G-1 に絞られる。
いずれにしても、1、7列のC、G行以外の３は消去できる。
177 名前：（　･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ[sage] 投稿日：2010/08/24(火) 12:32:08
>>165
ええとｗ
どこからツッコんでいいものかｗｗｗ
１．まずそもそも「次の一手」が示せてないじゃんｗ
２．対角だのX-Wing だのは型はめして解答時間を早くする　or 説明を簡単に
　できるようにするための便法であって、「論理」で説明できる。
３．貴殿の例でも、「B−１にもし”３”が入ると仮置きすると」→１-Cに３が入らないことになる
→すると、横列をみると、C-７に３が入る→G-7には３は入らない→するとG列ではG-1
に居れざるを得ないが、これはB-1に置いた（仮置きの）３と　conflict する。
　よって、B−１は、”３”ではない
というだけ。類型・公式化しとけば、論理追わなくてすむってだけｗ
４．でもって、B-1の例でいえば、「３で仮置きして矛盾が出たの→バックトラッキングで
→次に２か４を試す」ってことだから、（このスレで出てる最狭義の）「理詰め」にはならないよ
180 名前：（　･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ[sage] 投稿日：2010/08/24(火) 12:49:32
>>177
お前のその説明だったら、
A-2に１を仮置きするとA-1の１がA-2に仮置きした１と衝突するのでA-2は１ではない
ということで全ての手がバックトラックになるよね
↑これは理解できたの？

9 ：

>>8
頭悪い人？
同じブロックに１が既にあるんだから、「A-2に１を仮置きする」
なんて有り得ないよ？？？

10 ：

>>9
じゃあ本題に戻ると、
B-1に３が入らないことがわかってるんだからそこに仮置きするなんてあり得ない
ってことは理解できた？

11 ：

>>9
>>3のプログラムはそういうことをやってるんだよ
プログラムを書くときはそういう風に書くほうがシンプルに書ける

12 ：

>>7
あと何通りの答えがあるかわかれば
数独の答えのパターン数がわかるね

13 ：

マ板かパズル板住人のほうが詳しいんじゃないの？

14 ：

週末の朝日新聞に載ってた超良問
すべて演繹法（推理だけ。バックトラックしない）で解ける
したがって「難問」ではないが、論理性が試される「良問」（テクニック不要）
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ 　│ 　│ 　┃ ４│ 　│ １┃ 　│ ２│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃　 │ １│ 　┃ 　│ ７│　 ┃ 　│ 　│ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ５┃ 　│ 　│ 　┃８ │ 　│ 　┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ 　│ 　┃１ │ 　│ 　┃ 　│ ９│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ９┃ 　│ ２│ 　┃ ６│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ２│ 　┃ 　│ 　│ ８┃ 　│ 　│ ３┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ 　│ 　│ ７┃　 │ 　│ 　┃ ３│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ ８│ 　│ 　┃ 　│ ５│ 　┃ 　│ １│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ４│ 　┃ ３│ 　│ ７┃ 　│ 　│ 　┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
・ぱっと見のとおり１がすぐ埋まる
・簡単に埋まるのは１だけでしばし熟考。次の一手！
・その一手は論理だけで決めることができる（テクニック使ってもできるのかもしれないけど
　演繹的論理だけで決められる）
・その一手が決まるとその次も論理的にすぐ埋まる（同じ数字）
・↑を先に埋めたか関係なく別の数字で次の２手
この４手↑（序盤の１をほぼ埋めた後の４手）を論理的に導き出せれば論理力がかなりあるとみていいかとｗ

15 ：

要するに・・・
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ 　│ 　│ 　┃ ４│ 　│ １┃ 　│ ２│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃　 │ １│ 　┃ 　│ ７│　 ┃ 　│ 　│ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ５┃ 　│ 　│ 　┃８ │ 　│ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ 　│ 　┃１ │ 　│ 　┃ 　│ ９│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ 　│ ９┃ 　│ ２│ 　┃ ６│ 　│　 ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ２│ 　┃ 　│ 　│ ８┃１ │ 　│ ３┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ 　│ 　│ ７┃　 │ １│ 　┃ ３│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ ８│ 　│ 　┃ 　│ ５│ 　┃ 　│ １│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ４│１ ┃ ３│ 　│ ７┃ 　│ 　│ 　┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
これの「次の一手」を演繹的に詰めろ、ってことか。
その次３手も。。。

16 ：

>>14
わーい。できたー。
1の次に埋めるとこが>>14と違うみたいで言ってることがわからなかった

17 ：

>>16
> わーい。できたー。
うそつけｗｗｗｗ
本当にできたなら、「次の一手」を論理的に書くわいｗ
てか、ムズいなこれｗ

18 ：

ナンプレ 数独 Sudoku 5
http://toki.2ch.net/test/read.cgi/puzzle/1276492054/

19 ：

┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ 　│ 　│ 　┃ ４│ 　│ １┃ 　│ ２│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃　 │ １│ 　┃ 　│ ７│　 ┃ 　│ 　│ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ５┃ 　│ 　│ 　┃８ │ 　│ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ 　│ 　┃１ │ 　│ 　┃ 　│ ９│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ 　│ ９┃ 　│ ２│ 　┃ ６│ 　│　 ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ２│★┃ 　│ 　│ ８┃１ │ 　│ ３┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ 　│ 　│ ７┃　 │ １│ 　┃ ３│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ ８│ 　│ 　┃ 　│ ５│ 　┃ 　│ １│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ４│１ ┃ ３│ 　│ ７┃ 　│ 　│ 　┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
次の一手は★で、数字は４
★の縦で１、５、７、９は無い
★の横で、２、３、８も無い
そしてBOXでみると６も無い
→よって演繹的に★には４しか入り得ない、といえる

20 ：

┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ 　│ 　│ 　┃ ４│ 　│ １┃ 　│ ２│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃　 │ １│ 　┃ 　│ ７│　 ┃ 　│ 　│ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ５┃ 　│ 　│ 　┃８ │ 　│ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ 　│ 　┃１ │A │ 　┃ 　│ ９│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ 　│ ９┃B │ ２│ 　┃ ６│ 　│　 ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ２│４ ┃★│★│ ８┃１ │ 　│ ３┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ 　│ 　│ ７┃　 │ １│ 　┃ ３│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ ８│ 　│ 　┃ 　│ ５│ 　┃ 　│ １│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ４│１ ┃ ３│ 　│ ７┃ 　│ 　│ 　┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
１．Aのところを縦にみていく
（１）Aより上は同一ボックスに４があるから入り得ない
（２）Aの下（★）は同一行に４があるから★は４ではない
（３）同様に一番下も４ではない
→よって、４はAにしか入らない。A=４
２．★２つのところの上２行をみると、６と９がある。
　よってこのボックスで６と９が入り得るのは★の２か所だけ
　この★のどちらかが６でどちらかが９。たとえば７は入らない。
　今度は縦にみるとAの右の列も７があるから縦２マスの空白
　は７ではない。
　よって、このボックスで７が入るのはBのみ。B=7

21 ：

┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ 　│ 　│ 　┃ ４│ 　│ １┃ 　│ ２│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃　 │ １│ 　┃★│ ７│　 ┃ 　│ 　│ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ 　│ ５┃ 　│ 　│ 　┃８ │ 　│ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ 　│ 　┃１ │４ │ 　┃ 　│ ９│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ 　│ ９┃７ │ ２│ 　┃ ６│ 　│　 ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ２│４ ┃69│69│ ８┃１ │ 　│ ３┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ 　│ 　│ ７┃　 │ １│ 　┃ ３│ 　│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ ８│ 　│ 　┃ 　│ ５│ 　┃ 　│ １│ 　┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ 　│ ４│１ ┃ ３│ 　│ ７┃ 　│ 　│ 　┃
┗━┷━┷━┻━┷━┷━┻━┷━┷━┛
次に真ん中のボックスの縦空白２マスは、どちらかに５
が入ることがわかる（残りは３か５）
そうするとその上のボックスの一番右の列には５は
入らないことがわかる
真ん中の列は下の方に５があるからやはり５は入らない
左の列（★のある列）の一番下はその左に５があるから
やはり５は入らない
よって、★＝５

22 ：

先に>>20のA,B埋めたわ。

23 ：

>>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 ：

どうでもいいが、バックトラックは立派な演繹法の一種。
理詰めの部類なんだが・・・

25 ：

>>24
論理的にはそのとおりなんだが、PCの普及・高性能化で、バックトラック認めると
　　「コンピュータで左上から１から順に入れてバックトラックしまくったら0.07秒で答えがわかりました」
が蔓延してしまう　(´・ω・｀)

26 ：

904 名前：水先案名無い人[sage] 投稿日：2011/07/04(月) 09:41:58.44 ID:TNhScJ0z0 [1/2]
い…石原殿…今月のジャンプＳＱ…あれはエロ漫画雑誌にござるか？
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]
こ、こは何事！？
こは創刊当初の意気込み通りの「月ジャンより広い層へ向けた総合少年漫画誌」などにあらず！
ダークネスが当然顔で毎度表紙を張る…
ぬふぅ
青少年健全育成条例の恐怖に怯えていたのはむしろ　

27 ：

初心者です、解けません。。。
２９〇○○８４６○
○○４２１○○○９
○○○○○６○○○
○２５○○○６○３
○７６○○○１○４
３○○○○○○５○
○○７１３○○○２
○○○○○２○○○
１５２○○７３４○

28 ：

>>27
真ん中の9マスの左上（6の下で、6の左）に1が入る。
けっこう簡単な問題だと思う。
がんばって。

29 ：

間違い、左上じゃなくて右上。

30 ：

ありがとうございます。（1）わかりました。次が？？？です。

31 ：

何で１が入るかは分かりました？
○２５
○７６
３○○
左中央の９マスですが、３の右かその右にしか、１は入れませんよね。
ということで、上に書いた位置に１が入ります。
次は左上の
２９○
○○４
○○○
の９の下に６が入ります。
ヒントは縦の列の５･７と、横の列の６かな。
ってほとんど答えですけど＾＾；

32 ：

はい、１はあの場所しかありませんね。あと２９○の○が1かどうかまよいます。
正直何日も考えています。

33 ：ヒロチ：2011/11/20(日) 22:19:11.36

がんばれ〜