<< 2024 年 3 月 >>
25
26
27
28
29
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
1
2
3
4
5
6


 トップ > プログラミング > Sudoku  ナンバープレイスを課題にしたプログラム作りです。

 1 2 3 4 5 6 7 8 9 10 11 12 13 
2010/08/23 14:01
9. 難易度の高い数独の問題

次の例題も私が作成したものですが、難易度の高い問題になります。先の例題との違いは、解法手順の繰り返しを単純に実行するだけでは、解答が求められないところにあります。

難易度の高い例題
7 8
13
6
9 2
3
94
3
2 6
5
9
7
6
1
8
5
3
6
24
   
難易度の高い例題の解答
654
718
293
137
429
568
982
635
417
581
942
367
296
753
814
374
861
529
829
475
136
641
382
975
753
196
248

では、作成したプログラムでこの難易度の高い例題を解いてみます。結果は次のとおりです。

数独パズルを解く。
 [1] .....................g(6,2)=6....g(7,4)=6.f(8,7)=1.
 [2] ...g(4,7)=3......g(1,1)=6.f(1,2)=5........f(1,3)=4.........
 [3] .g(2,7)=6..............g(3,7)=4.g(5,8)=6.......g(6,8)=2....
 [4] ....g(5,3)=2.......................
 [5] ...........................

1 6     5     4     1     3      (78)   9   (78)  2      
2 7     (129) 8     (459) (2459) (249)  6   3     (15)   
3 (12)  (1239)(13)  (5789)6      (2789) 4   (1578)(1578) 
4 (158) (18)  (157) 2     (14579)6      3   (1789)(14789)
5 9     4     2     (3578)(157)  (378)  (78)6     (178)  
6 3     6     (17)  (4789)(1479) (4789) 5   2     (14789)
7 (2458)(28)  9     6     (247)  1      (78)(578) 3      
8 (245) 7     (35)  (349) 8      (2349) 1   (59)  6      
9 (18)  (138) 6     (379) (79)   5      2   4     (789)  

確定したマス目の数は初期状態で24個、解法手順を4回適用して12個増の合計36個、手順の5回目の適用ではそれ以上増やすことはできませんでした。1行目のマス目を見ると、6列目と8列目がどちらも7と8を候補に持つ状態です。どちらかが決まるともう一方も決まるのですが、この二つを含む残り55個のマス目を確定させるにはどのように進めていったらよいのでしょうか。

ここから先はちょっとした工夫が必要になります。その工夫とは、候補値の一つを確定値と仮定して手順を適用することです。こうすることで、すべてのマス目に入る数字が確定すればよいのですが、再び確定値が増えない状況になれば、さらに候補値の一つを確定値と仮定して手順を適用します。手順を適用していく過程で、マス目の数字に重複が出る場合も有り得ます。この場合は仮定が誤っていたと結論づけて、次の候補値を新たな確定値と仮定することで、手順を適用します。


(Sudoku) 2010/08/23 14:01

名前:
コメント:
投稿キー: ※右の文字列を入力してください。