23 Study on Generation of Sudoku Problems with Fewer Clues

Size: px

Start display at page:

Download "23 Study on Generation of Sudoku Problems with Fewer Clues"

はなあわたけ
5 years ago
Views:

1 23 Study on Generation of Sudoku Problems with Fewer Clues

2 i

3 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

4 iii

5 24 iv

6 Line Unique Block Unique Cell Unique Naked Pair Naked Pair Hidden Pair Hidden Pair X-Wing X-Wing (x7,y9) (x8,y5) v

7 vi

8 1 1.1 [1] Sudoku Number place 2006 [2] [3] [4] [1] [5] [2] [3] [4] 9 9 McGuire 17 [6] Hitting-Set Algorithm CPU [7] [7] 1

9 CPU [3] 9 9 [4] [5]

10 1.4 Intel(R) Core(TM) i3 3.07GHz 4GB OS:Windows7 Home Premium 32bit 3

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.

12 Line Unique Block Unique Cell Unique Line Unique 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 y y1 1 (x5,y1) (x5,y1) 1 5

13 Line Unique Block Unique 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) (x4,y4) (x4,y4) 3 6

14 Block Unique Cell Unique 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

15 Cell Unique 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) (x2,y2) (x3,y2)

16 Naked Pair Naked Pair Hidden Pair Hidden Pair n n 2.10 n=2 (x2,y1) (x3,y1) (x2,y1) (x3,y1) X-Wing X-Wing X-Wing(1) 9

17 Hidden Pair 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

18 X-Wing X-Wing X-Wing

19 3 3.1 Java

20 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

21 [ ] Web [9] GPCC [7] %

23 4 4.1 while( < ){ (x,y) (x,y) if( ){ (x,y)

24 [ ]

25 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 ,3,4,6, (x7,y9) ,3,6, (x8,y5) 3 18

26 (x7,y9) (x8,y5)

27 [ ]

30 23

31 [1] :, pp ,, Vol.53, No.2, 563,, [2], :,. GI, [ ] 2011-GI-25(8), 1-6, [3] : (5), , [4] : (4), , [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: , [7] :, [8] Felgenhauer and Jarvis : Enumerating possible Sudoku grids, [9] -,

Web Web Web Web Web, i

22 Web Research of a Web search support system based on individual sensitivity 1135117 2011 2 14 Web Web Web Web Web, i Abstract Research of a Web search support system based on individual sensitivity