2010/08/31 11:53
12. 難易度の高い例題を解くプログラムの実行結果
難易度の高い問題では、単純に解法手順を適用するだけでは解けませんでした。マス目に仮の確定値を設定したうえで、手順を適用する。この方法で解答を探すコードを書きました。このプログラムを使って、難易度の高い例題を解いてみました。実行結果は次のようになります。
数独パズルを解く。 [1-1].....................g25(6,2)=6....g26(7,4)=6.f27(8,7)=1. [1-2]...g28(4,7)=3......g29(1,1)=6.f30(1,2)=5........f31(1,3)=4....... .. [1-3].g32(2,7)=6..............g33(3,7)=4.g34(5,8)=6.......g35(6,8)=2.. .. [1-4]....g36(5,3)=2....................... [1-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) t37(1,6)=7 from (78) [2-1]f38(1,8)=8........................... [2-2]........................... 1 6 5 4 1 3 7 9 8 2 2 7 (129) 8 (459) (2459) (249) 6 3 (15) 3 (12) (1239)(13) (589) 6 (289) 4 (157)(157) 4 (158) (18) (157) 2 (14579)6 3 (179)(14789) 5 9 4 2 (3578)(157) (38) (78)6 (178) 6 3 6 (17) (4789)(1479) (489) 5 2 (14789) 7 (2458)(28) 9 6 (247) 1 (78)(57) 3 8 (245) 7 (35) (349) 8 (2349) 1 (59) 6 9 (18) (138) 6 (379) (79) 5 2 4 (789) t39(2,2)=1 from (129) [3-1].f40(2,9)=5.........f41(4,2)=8f42(7,2)=2f43(9,2)=3f44(3,2)=9..... ...f45(3,1)=2f46(3,3)=3.g47(3,4)=5.....f48(8,3)=5g49(9,1)=1... [3-2]..f50(3,6)=8.....f51(8,1)=4f52(8,8)=9g53(8,6)=2.g54(9,9)=8.f55(4, 1)=5g56(7,1)=8....g57(2,5)=2.f58(5,6)=3..g59(7,8)=5.......g60(5,7)=8.. g61(8,4)=3.f62(7,7)=7. [3-3]....f63(5,4)=7g64(5,5)=5.g65(6,4)=8.f66(7,5)=4......f67(9,4)=9f68 (2,4)=4.......f69(2,6)=9...g70(6,6)=4...f71(9,5)=7.. [3-4]...g72(4,9)=4.f73(5,9)=1.............f74(3,9)=7g75(6,9)=9...f76(3 ,8)=1...f77(4,8)=7.... [3-5]...f78(4,3)=1g79(4,5)=9..f80(6,5)=1g81(6,3)=7.................... .. 解答1 1 654 137 982 2 718 429 635 3 293 568 417 4 581 296 374 5 942 753 861 6 367 814 529 7 829 641 753 8 475 382 196 9 136 975 248 t39(2,2)=2 from (129) [4-1].g40(2,9)=1.........f41(7,2)=8f42(4,2)=1g43(3,2)=9...g44(7,5)=2.. ..g45(3,9)=5.f46(3,1)=1f47(3,3)=3.g48(3,6)=2.f49(3,8)=7.f50(6,3)=7f51( 4,3)=5g52(4,1)=8..g53(4,8)=1 Duplicate (4,2) t39(2,2)=9 from (129) [5-1].g40(2,9)=1................g41(3,9)=5...f42(3,8)=7...g43(4,8)=1.. .. [5-2]...f44(4,2)=8.g45(5,5)=1......f46(7,2)=2......f47(7,8)=5f48(8,8)= 9..g49(3,1)=2...f50(4,1)=5g51(6,3)=1...... [5-3]...f52(4,3)=7.g53(5,4)=5...g54(8,6)=2..f55(8,1)=4f56(7,1)=8g57(9, 1)=1..f58(3,3)=3g59(8,3)=5.f60(2,4)=4.g61(2,5)=2.f62(2,6)=4 Duplicate (2,4) t37(1,6)=8 from (78) [6-1]f38(1,8)=7........................... [6-2]........................... 1 6 5 4 1 3 8 9 7 2 2 7 (129) 8 (459) (2459) (249) 6 3 (15) 3 (12) (1239)(13) (579) 6 (279) 4 (158)(158) 4 (158) (18) (157) 2 (14579)6 3 (189)(14789) 5 9 4 2 (3578)(157) (37) (78)6 (178) 6 3 6 (17) (4789)(1479) (479) 5 2 (14789) 7 (2458)(28) 9 6 (247) 1 (78)(58) 3 8 (245) 7 (35) (349) 8 (2349) 1 (59) 6 9 (18) (138) 6 (379) (79) 5 2 4 (789) t39(2,2)=1 from (129) [7-1].f40(2,9)=5.........f41(4,2)=8f42(7,2)=2f43(9,2)=3f44(3,2)=9..... ...f45(3,1)=2f46(3,3)=3.g47(3,4)=5.....f48(8,3)=5g49(9,1)=1... [7-2]..f50(3,6)=7.....f51(8,1)=4f52(8,8)=9g53(8,6)=2.g54(9,9)=8.f55(4, 1)=5g56(7,1)=8....g57(2,5)=2.f58(5,6)=3..f59(4,8)=1g60(7,8)=5.f61(3,9) =1...f62(3,8)=8...f63(5,9)=7f64(5,7)=8..g65(8,4)=3.f66(7,7)=7. [7-3]...f67(4,3)=7.f68(5,4)=7 Duplicate (5,9) t39(2,2)=2 from (129) [8-1].g40(2,9)=1.........f41(7,2)=8f42(4,2)=1g43(3,2)=9...g44(7,5)=2.. ..g45(3,9)=5.f46(3,1)=1f47(3,3)=3.g48(3,6)=2.f49(3,8)=8.f50(6,3)=7f51( 4,3)=5g52(4,1)=8..g53(4,8)=1 Duplicate (4,2) t39(2,2)=9 from (129) [9-1].g40(2,9)=1................g41(3,9)=5...f42(3,8)=8...g43(4,8)=1.. .. [9-2]...f44(4,2)=8.g45(5,5)=1......f46(7,2)=2......f47(7,8)=5f48(8,8)= 9..g49(3,1)=2...f50(4,1)=5g51(6,3)=1...... [9-3]...f52(4,3)=7.g53(5,4)=5...g54(8,6)=2..f55(8,1)=4f56(7,1)=8g57(9, 1)=1..f58(3,3)=3g59(8,3)=5.f60(2,4)=4g61(6,4)=8.g62(2,5)=2.f63(2,6)=4 Duplicate (2,4) 解答数 1
導きだされた解答の数は一個でした。例題は問題として妥当であったことがわかります。初期値の与え方によっては、解答が複数になる場合があります。そのため、先のプログラムでは'define(MAXANSWERS, 300);'と、解答の数が300になったらそれ以上の解答探しを中止するようにしています。
(Sudoku)
2010/08/31 11:53
コメント