数独プログラミング (209ﾚｽ)
上下前次1-新
1: 2010/08/26(木)11:05 AAS
ホームズくんの数独が理詰めでは解けない、ってのが発端ｗ
手詰まりの図↓ ここからはバックトラック
１○○ ２３８ ○○○
○○８ ○６７ ５○○
○７○ ○○５ ○○８
○○３ ○○６ ○２９
○１○ ５９３ ４８○
９８○ ○２４ ○３５
○６○ ○○○ ○○１
○○１ ６○○ ○７○
省1
2: 2010/08/26(木)11:05 AAS
> 239 名前：（ ･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ[sage] 投稿日：2010/08/16(月) 08:58:19
> ねぇねぇ。演繹的って、たとえば
> 「ここに、4か9が入る。他の可能性はない」
> まで論理で詰めたとするでしょ？
>
> ・仮に4だとして→やってみたら全部きれい埋まった ←←これはﾀﾞﾒだよな。ｱﾌｫの
> ｵﾚでもわかる
>
> ・仮に9入れてみると→10手先で矛盾がおきる→だから9はありえない→よって4
>
省6
3(1): 2010/08/26(木)11:12 AAS
どうせバックトラックするなら最初からバックトラックしてやれ、ということで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,
省29
4: 2010/08/26(木)11:14 AAS
＜続き＞
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;}
}
省23
5: 2010/08/26(木)11:17 AAS
【実行結果】
154238796
298467513
376915248
543786129
612593487
987124635
769842351
431659872
825371964
省5
6: 2010/08/26(木)11:21 AAS
さて、ここで、数独って１〜９でやるが、数字の大きさは意味がない訳で
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,
省7
7(1): 2010/08/26(木)11:23 AAS
これは一瞬で解けてｗ
123456789
456789123
789123456
214365897
365897214
897214365
531642978
642978531
978531640
省1
8(1): 2010/08/26(木)11:36 AAS
165 名前：（ ･∀･）つ〃∩ﾍｪｰﾍｪｰﾍｪｰ[sage] 投稿日：2010/08/24(火) 12:04:23
>>50の次の一手は>>116で出せる。
http://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
ええとｗ
どこからツッコんでいいものかｗｗｗ
省16
9(2): 2010/08/26(木)14:45 AAS
>>8
頭悪い人？
同じブロックに１が既にあるんだから、「A-2に１を仮置きする」
なんて有り得ないよ？？？
10: 2010/08/26(木)15:07 AAS
>>9
じゃあ本題に戻ると、
B-1に３が入らないことがわかってるんだからそこに仮置きするなんてあり得ない
ってことは理解できた？
11: 2010/08/26(木)15:18 AAS
>>9
>>3のプログラムはそういうことをやってるんだよ
プログラムを書くときはそういう風に書くほうがシンプルに書ける
12: 2010/08/27(金)10:29 AAS
>>7
あと何通りの答えがあるかわかれば
数独の答えのパターン数がわかるね
13: 2010/09/01(水)10:35 AAS
マ板かパズル板住人のほうが詳しいんじゃないの？
14(1): 2010/09/21(火)15:02 AAS
週末の朝日新聞に載ってた超良問
すべて演繹法（推理だけ。バックトラックしない）で解ける
したがって「難問」ではないが、論理性が試される「良問」（テクニック不要）
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ │ │ ┃ ４│ │ １┃ │ ２│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ １│ ┃ │ ７│ ┃ │ │ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ │ ５┃ │ │ ┃８ │ │ ┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
省19
15: 2010/09/22(水)15:59 AAS
要するに・・・
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ │ │ ┃ ４│ │ １┃ │ ２│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ １│ ┃ │ ７│ ┃ │ │ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ │ ５┃ │ │ ┃８ │ │ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ │ ┃１ │ │ ┃ │ ９│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
省12
16(3): 2010/09/23(木)19:44 AAS
>>14
わーい。できたー。
1の次に埋めるとこが>>14と違うみたいで言ってることがわからなかった
17(1): 2010/09/24(金)09:01 AAS
>>16
> わーい。できたー。
うそつけｗｗｗｗ
本当にできたなら、「次の一手」を論理的に書くわいｗ
てか、ムズいなこれｗ
18: 2010/09/24(金)11:39 AAS
ナンプレ 数独 Sudoku 5
2chｽﾚ:puzzle
19(1): 2010/09/24(金)12:46 AAS
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ │ │ ┃ ４│ │ １┃ │ ２│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ １│ ┃ │ ７│ ┃ │ │ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ │ ５┃ │ │ ┃８ │ │ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ │ ┃１ │ │ ┃ │ ９│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ │ ９┃ │ ２│ ┃ ６│ │ ┃
省14
20(2): 2010/09/24(金)15:17 AAS
┏━┯━┯━┳━┯━┯━┳━┯━┯━┓
┃ │ │ ┃ ４│ │ １┃ │ ２│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ １│ ┃ │ ７│ ┃ │ │ ６┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ │ │ ５┃ │ │ ┃８ │ │ １┃
┣━┿━┿━╋━┿━┿━╋━┿━┿━┫
┃ ６│ │ ┃１ │A │ ┃ │ ９│ ┃
┠─┼─┼─╂─┼─┼─╂─┼─┼─┨
┃ １│ │ ９┃B │ ２│ ┃ ６│ │ ┃
省20
上下前次1-新書関写板覧索設栞歴
あと 189 ﾚｽあります
ｽﾚ情報 赤ﾚｽ抽出 画像ﾚｽ抽出 歴の未読ｽﾚ AAｻﾑﾈｲﾙ
ぬこの手 ぬこTOP 0.903s*