23 Study on Generation of Sudoku Problems with Fewer Clues 1120254 2012 3 1
9 9 21 18 i
Abstract Study on Generation of Sudoku Problems with Fewer Clues Norimasa NASU Sudoku is puzzle a kind of pencil puzzle, and popular on global. And more, Sudoku is target of Research to Mathmatics, game programing and computer science. In Sudoku, the problem of the minimum clue has been researched. This problems focus is the smallest clues that can be unique answer of problem in sudoku. Focus of this research is method of generate for problem of sudoku to computer, and made program for generate of sudoku. Focus of this research is method of generate for problem of sudoku to computer, and made program for generate of sudoku. First, made program for search answer of sudoku problem. This program searching answer, and judging answer number of problem. Result of the test, program to solve the problem so fast, that passes the test. Next, made and tested program for generate of sudoku. Result of the test, the successful generation of 18 clues problem. key words Sudoku, Minimum clues of sudoku, Generate of Sudoku problems. ii
1 1 1.1............................. 1 1.2................................... 2 1.3................................. 2 1.4........................... 2 2 4 2.1.............................. 4 2.2.................................. 4 2.2.1............................. 5 2.2.2................................ 8 2.2.3................................ 9 2.3....................... 11 3 12 3.1....................... 12 3.2....................... 14 4 16 4.1....................... 16 4.2.................... 17 5 21 23 iii
24 iv
2.1............................ 5 2.2 2.1............................. 5 2.3 Line Unique....................... 6 2.4 2.3 1......... 6 2.5 Block Unique...................... 7 2.6 2.5 3......... 7 2.7 Cell Unique....................... 8 2.8 Naked Pair....................... 9 2.9 2.8 Naked Pair................. 9 2.10 Hidden Pair....................... 10 2.11 2.10 Hidden Pair................ 10 2.12 X-Wing......................... 11 2.13 2.12 X-Wing.................. 11 3.1.................... 15 4.1................................. 19 4.2 (x7,y9) 4....................... 19 4.3 (x8,y5) 3....................... 19 4.4............................. 19 v
3.1 9 9..................... 14 3.2 16 16................... 15 4.1................ 17 4.2............. 20 vi
1 1.1 [1] Sudoku Number place 2006 [2] [3] [4] [1] [5] [2] [3] [4] 9 9 McGuire 17 [6] Hitting-Set Algorithm 16 700 CPU [7] 16 16 2011 4 9 56 [7] 1
1.2 9 9 700 CPU 16 16 1.2 [3] 9 9 [4] [5]. 1.3 2 3 4 5 1.4 2
1.4 Intel(R) Core(TM) i3 540 @ 3.07GHz 4GB OS:Windows7 Home Premium 32bit 3
2 2.1 9 9 2.1 3 3 1 9 1 2 3 1 1 1 1 9 1 1 1 9 1 2.1 2.2 2.2 2.2 2.1 9 9 4
2.2 2.1 2.2 2.1 2.2.1 Line Unique Block Unique Cell Unique Line Unique 1 1 1 9 1 Line Unique Line Unique x 1 x 2.3 y1 (x1,y2) 1 (x1,y1) (x2,y1) (x3,y1) 1 (x9,y3) 1 (x7,y1) (x8,y1) (x9,y1) 1 (x4,y4) 1 (x4,y1) 1 (x6,y7) 1 (x6,y1) 1 y1 1 2.4 2.4 y1 1 (x5,y1) (x5,y1) 1 5
2.2 2.3 Line Unique 2.4 2.3 1 Block Unique 1 1 1 9 1 Block Unique Block Unique x 1 x 2.5 x4 x6, y4 x6 (x5,y2) 3 (x5,y4),(x5,y5),(x5,y6) 3 (x6,y9) 3 (x6,y4),(x6,y5),(x6,y6) 3 (x7,y5) 3 (x4,y5),(x5,y5),(x6,y5) 3 (x2,y6) 3 (x4,y6),(x5,y6),(x6,y6) 3 3 2.6 2.4 3 (x4,y4) (x4,y4) 3 6
2.2 2.5 Block Unique 2.6 2.5 3 Cell Unique 1 1 9 1 Cell Unique Cell Unique x x 2.7 (x5,y1) 1,3,4,8,9 (x5,y1) y1 2,7 x5 6 (x5,y1) (x5,y1) 5 (x5,y1) 5 7
2.2 2.7 Cell Unique 2.2.2 Naked Pair Hidden Pair Naked Pair Hidden Pair Naked Pair Naked Pair n n 2.8 n=2 2.8 x1 x3 y1 y3 (x1,y1) 7 (x1,y2) 8 (x2,y2) (x3,y2) 2 2 5 6 (x2,y2) (x3,y2) 5 6 5 6 2.9 8
2.2 2.8 Naked Pair 2.9 2.8 Naked Pair Hidden Pair Hidden Pair n n 2.10 n=2 (x2,y1) (x3,y1) 4 9 2 (x2,y1) (x3,y1) 4 9 2 4 9 2.11 2.2.3 X-Wing X-Wing X-Wing(1) 9
2.2 2.10 Hidden Pair 2.11 2.10 Hidden Pair n x n n x X-Wing(2) n x n n x X-Wing n = 2 n = 3 Sword fish n = 4 Jelly fish n X-Wing 2.12 n = 2 x x y2 y6 x3 x6 x 2 x (x3,y2) (x6,y6) (x6,y2) (x3,y6) x3 x6 x 10
2.3 2.12 X-Wing 2.13 2.12 X-Wing X-Wing 2.13 2.3 1 2 1 1 2 2 1 11
3 3.1 Java 2.1 1 1 12
3.1 Solve (, ){ for( ){ X-Wing Pair Naked, Pair Hidden Line Unique Block Unique Cell Unique if( ){ if( ){ +1; return; if( ){ return; if( ){ break; (x,y) for(i = 1; i <= 9; i++){ if( (x,y) i ){ (x,y) i Solve (, ) if( 2 ){ return; return; 13
3.2 3.1 9 9 [ ] 15 249 29.7 3.2 9 9 16 16 9 9 Web [9] 30 16 16 GPCC2011 16 16 [7] 56 60 9 9 3.1 3.2 3.1 249 29.72 3.2 90% 70 1 9 9 16 16 3.2 16 16 58 9 59 7 4 1 10 16 16 14
3.2 3.1 3.2 16 16 60 59 58 57 56 30 22 56 9 59 7 1 24 52 15
4 4.1 while( < ){ (x,y) (x,y) 1 9 1 if( ){ (x,y) 10000 4.1 20 17 21 16
4.2 4.1 [ ] 21 3 5948 4049 133 20 0 6817 3183 242 19 0 7728 2272 788 18 0 8295 1705 1315 17 0 8826 1174 1554 4.2 17
4.2 while( < ){ min = 32 table = for(y = 0; y < 9; y++){ for(x = 0; x < 9; x++){ if( (x,y) ){ continue; for(i = 1; i < 9; i++){ (x,y) i now = if(now >= min){ if(now > min){ table table (x,y) i (x,y) // table // (x,y) i table 1 (x,y) i 4.1 4.1 596 1 1,3,4,6,9 567 1 (x7,y9) 4 4.2 4.2 1,3,6,9 538 1 (x8,y5) 3 18
4.2 4.1 4.2 (x7,y9) 4 4.3 (x8,y5) 3 4.4 4.3 20 4.4 4.4 231 10000 19
4.2 4.2 [ ] 21 82 1386 8532 186 20 61 3624 6315 212 19 32 6995 2973 271 18 7 9064 929 320 17 0 9615 385 323 4.2 4.2 18 4.1 19 21 1 17 20
5 9 9 249 29.72 16 16 1 10 9 9 21 20 18 9 9 17 16 16 21
9 9 17 16 16 22
23
[1] :, pp107 111,, Vol.53, No.2, 563,, 2012. [2], :,. GI, [ ] 2011-GI-25(8), 1-6, 2011. [3] : 70 20 (5), 5-253 - 5-254, 2008. [4] : 71 21 (4), 4-741 - 4-742, 2009. [5] : EC, 2006(134), 1-6, 2006 [6] Gary McGuire : There is no 16-Clue Sudoku: Solving the Sudoku Minimum Number of Clues Problem, eprint arxiv:1201.0749, 2012. [7] :, http://hp.vector.co.jp/authors/va003988/gpcc/11p1.htm, 2011. [8] Felgenhauer and Jarvis : Enumerating possible Sudoku grids, 2005. [9] -, http://www.sudokugame.org/, 2012. 24