Bulletin of JSSAC(2014) Vol. 20, No. 2, pp. 3-22 (Received 2013/11/27 Revised 2014/3/27 Accepted 2014/5/26) It is known that some of number puzzles can be solved by using Gröbner bases. In this paper, we discuss methods for solving four kinds of number puzzles (Sudoku, Kakkuro, Hashiwokakero and Tile Paint) by using Gröbner bases. Especially, we study the following question. Of what kind of difficulty can Gröbner bases computation programs solve number puzzles? In order to give some answers of this question, we analyze data of the computation experiments. Moreover, in this paper, we introduce efficient techniques for solving number puzzles. Number puzzles have a lot of hidden mathematics rules and useful properties. We introduce these rules and properties, and describe how to translate these ones into algebraic systems of polynomial equations. In general, the Gröbner bases technique for solving number puzzles, is not considered as a good solver for number puzzles, but we show that the Gröbner bases technique can be a good solver for one of the four puzzles (Tile Paint). 1 [1, 2, 3, 4, 7, 9] 1 Risa/Asir[18] nabeshima@tokushima-u.ac.jp c 2014 Japan Society for Symbolic and Algebraic Computation
4 20 2 2014 Risa/Asir 1 2 3 3 (1) (2) [1, 3, 4] (3) [3, 7] 2 PC1: PC2: PC OS:Windows 7 Professional (64bit)CPU: Intel(R) Xeon (R) X560@ 2.67GHz 2.66GHzRAM:48GB PC OS:Windows 7 Home Premium(64bit)CPU: Intel(R) Core (TM) i7-2600 CPU@ 3.40GHz 3.40GHzRAM:4GB time CPU seconds> 2h> 3h > 5h 2 3 5 Risa/Asir version 20121217 Kobe Distribution x i [3] Proposition 3 [3] Proposition 3
Bulletin of JSSACVol. 20, No. 2, 2014 5 I x 1... x n I {x i a i i = 1,..., n} a i { } 2 n n n 1 x i i 1 1 n 1 1. x i F i := n (x i j) j=1 2. 1 n 2 x i x j G i j := F i F j x i x j [3] 2.1 3 3 9 9 1 9 [1, 2, 3, 5, 6, 7, 16] [5, 6, 7] Risa/Asir dp_gr_main [1, 3, 16] Risa/Asir dp_gr_main x j x j [3]
6 20 2 2014 1) 400 30 1 1 10 11 30 dp_gr_main 1 PC2 Risa/Asir 1 time time time 1 45 14.04 1 17 > 2h 1 17 > 2h 2 45 15.24 2 17 > 2h 2 17 > 2h 3 43 15.72 3 17 > 2h 3 17 > 2h 4 42 17.42 4 25 3971 4 18 > 2h 5 42 15.99 5 17 > 2h 5 18 > 2h 6 46 15.88 6 26 > 2h 6 25 > 2h 7 44 16.44 7 24 > 2h 7 17 > 2h 8 43 15.9 8 17 > 2h 8 17 > 2h 9 42 16.5 9 17 > 2h 9 17 > 2h 10 44 15.49 10 17 > 2h 10 26 7.644 1: 2.2 (1) 1 9 1 (2) (3) 1 1) http://www.sudokugame.org/
Bulletin of JSSACVol. 20, No. 2, 2014 7 1 [10] Web 1 2 1 1 2 1 2 (1) (3) (2) [3] 1: 2: Risa/Asir 2 kakuro([[5,[x1,x2]],[17,[x3,x4,x5,x6]],[6,[x7,x8]],[4,[x9,x10]],[10,[x11,x 12,x13,x14]],[3,[x15,x16]],[14,[x3,x7]],[11,[x1,x4,x8,x11]],[4,[x2,x5]],[3,[x12,x15]],[10,[x6,x9,x13,x16]],[3,[x10,x14]]]); [x5-1,-x16+1,x15-2,-x14+2,x13-4,-x12+1,-x11+3,x10-1,-x9+3,-x8+1,-x6+2,-x4+ 5,-x2+3,x1-2,x7-5,-x3+9] 2 x 1 = 2x 2 = 3x 3 = 9x 4 = 5x 5 = 1x 6 = 2x 7 = 5 x 8 = 1x 9 = 3x 10 = 1x 11 = 3x 12 = 1x 13 = 4x 14 = 2x 15 = 2x 16 = 1 [3] [3] 1 2
8 20 2 2014 [3] 1 Wikipedia 1 2) E EPSILON DELTA 3) 2 4) 4 2 1 6 6 PC1 time 1 6 6 16 31.64 [3] 8 8 36 4098 Wikipedia (2007/10/25) 8 8 36 > 5h "E " 1 9 9 44 1668 "E " 2 9 9 48 > 5h 1 9 11 73 > 5h 2 9 11 73 > 5h 3 9 11 73 > 5h 4 9 11 70 > 5h 2: 6 6 1 3 1 9 9 1 2 2 1 9 19 11 2) http://upload.wikimedia.org/wikipedia/commons/c/c8/kakuro_black_box.svg Wikipedia 2007 10 25 06:50 3) http://www20.big.or.jp/~morm-e/ 4) http://www.nikoli.com/ja/puzzles/kakuro/
Bulletin of JSSACVol. 20, No. 2, 2014 9 100 2.3 9 9 9 4 4 [16] [17] 1 [20] 9 9 1 [5, 6, 7, 16] 2 [4] 2 [8, 9] 3 5) (1) (2) (3) 2 (4) (5) 5) 1990
10 20 2 2014 3 4 [3] [3] 3 3 x 1 3 x 6 3 3 3 x 2 x 4 x 5 3 3 3 x 3 3: 4: 3 5: 3.1 [3] 1. (2) 2. (3) 0 1 2 x 1 x(x 1)(x 2) = 0 3. (4) 4. (5) 0 3 5 (3) x i 012 x i (x i 1)(x i 2) = 0 i = 1,..., 6 (4) x 1 + x 5 2 = 0x 1 + x 6 3 = 0x 2 + x 6 2 = 0x 2 + x 4 3 = 0x 3 + x 4 3 = 0 x 3 + x 5 1 = 0 (5) x 2 x 5 0 x 2 x 5 = 0 6 4 3 x 1 = 2x 2 = 1x 3 = 1x 4 = 2x 5 = 0
Bulletin of JSSACVol. 20, No. 2, 2014 11 x 6 = 1 (2)(3)(4)(5) (1) (1) (1) 6 7 6: 7: (1) [3] (1) 3.2 3.1 (1) 8 1 3 8 8:
12 20 2 2014 8 3 8 (1) (1) x 2 2 2 1 1 x(x 1) = 0 3: (1) 8 (2) (3) 2 (4) (5) (1) 3.1 4 5 i = 1, 2, 3, 4 j = 1, 2, 3k = 1, 2 2 Risa/Asir 6 2 1[11] [11] 1 1 52 1 19 easy easy 3
Bulletin of JSSACVol. 20, No. 2, 2014 13 x 2 x 1 x 3 8 () x 2 x 1 x 7 3 x 2 x 1 x 3 6 x 4 x 4 8 4 2 7 4 1 6 3 3 2 x i 2 = 0 (x i 2)(x i 1) = 0 x j 2 = 0 () x 2 x 1 x 5 3 5 3 3 1 x 1 x 2 x 4 1 x 2 3 4 2 2 2 3 2 2 1 (x j 2)(x j 1) = 0 x k 2 = 0 (x k 2)(x k 1) = 0 4: I 11718 3 6 PC2 9 9 3 1 9 16 3.3 9 9 easy 9 16
14 20 2 2014 () x x x 1 x 2 x 4 x 3 2 1 2 1 1 1 1 (1 4 ) 2 x 2 = 0 x 1 = 0 x i (x i 1) = 0 5: II easymedium 22 13 3 4 (1) (2) 1 (3) 6) 9 web [10] [12, 13, 14, 15] 10 6) 53
Bulletin of JSSACVol. 20, No. 2, 2014 15 size time time 1 9 9 40 1 0.078 30 1 0.016 17 9 9 40 1 0.14 37 1 0.047 18 9 9 46 1 0.437 39 1 0.031 19 9 9 48 5 2.106 46 2 0.109 20 16 9 69 1 89.34 61 1 0.047 21 16 9 61 3 55.96 57 3 0.109 22 16 9 73 > 3h 67 1 32.12 23 16 9 76 > 3h 68 1 0.343 24 16 9 77 > 3h 70 1 0.484 25 16 9 73 > 3h 67 2 2.761 26 16 9 87 > 3h 83 2 158 27 16 9 71 1 > 3h 66 1 0.125 28 16 9 73 1 > 3h 66 1 0.14 29 16 9 79 > 3h 67 2 0.109 30 16 9 71 > 3h 69 1 88.14 31 16 9 91 > 3h 87 1 129.8 32 16 9 87 > 3h 85 > 3h 33 16 9 59 1 > 3h 52 4 0.047 34 16 9 91 > 3h 89 1 > 3h 35 16 9 83 > 3h 77 3 2.2 36 16 9 63 1 > 3h 63 1 1.825 37 16 9 67 1 > 3h 66 1 0.265 38 16 9 71 > 3h 66 2 2.964 39 16 9 63 9 > 3h 61 9 0.14 40 16 9 67 2 > 3h 65 2 0.39 41 16 9 75 > 3h 71 1 0.14 42 16 9 77 > 3h 77 > 3h 43 16 9 101 > 3h 101 > 3h 44 16 9 107 > 3h 105 > 3h 45 16 9 81 > 3h 80 1 1354 46 16 9 85 > 3h 78 3 6.443 47 16 9 87 > 3h 84 > 3h 48 16 9 75 > 3h 74 1 > 3h 49 22 13 125 > 3h 113 1 163.4 50 22 13 141 > 3h 132 > 3h 51 22 13 134 > 3h 129 > 3h 52 22 13 145 > 3h 134 > 3h 6:
16 20 2 2014 9: 10: 9 11: 4.1 1 1 1 1 0 1. 2. 0 1 x 1 x(x 1) = 0 3. 1 9 11 2 x i (x i 1) = 0 i = 1,..., 11 1 x 1 + x 5 + x 6 + x 9 = 12x 2 + x 7 + x 10 = 4x 3 + x 4 + x 7 + x 11 = 12x 4 + 2x 8 = 2 x 1 + x 2 + x 3 + x 4 = 1x 5 + x 2 + 2x 4 = 2x 6 + 2x 7 + x 8 = 3 x 9 + x 10 + x 11 + x 8 = 2 Risa/Asir [113] gr([x1+x5+x6+x9-1,2*x2+x7+x10-4,x3+x4+x7+x11-1,2*x4+2*x8-2,x1+x2+x3+ x4-1, x5+x2+2*x4-2,x6+2*x7+x8-3,x9+x10+x11+x8-2,x11^2-x11,x10^2-x10,x9^2-x 9,x8^2-x8,x7^2-x7,x6^2-x6,x5^2-x5,x4^2-x4,x3^2-x3,x2^2-x2,x1^2-x1],[x1,x2, x3,x4,x5,x6,x7,x8,x9,x10,x11],2); [x11,x10-1,-x9,-x8+1,-x7+1,-x6,-x5+1,x4,-x3,-x2+1,x1] x 1 = x 3 = x 4 = x 6 = x 9 = x 11 = 0 x 2 = x 5 = x 7 = x 8 = x 10 = 1
Bulletin of JSSACVol. 20, No. 2, 2014 17 Step 1 Step 2 Step 1. Step 2. 4.2 1 k 1 n 12 1. n k = s 1 s 1 2. 1 k 0 12 k = 0n = k 0 1 1 n k = s s 0 1 2 0 12 1 10 7 10 7 = 3 4 3 < 4 0 1 9 10 9 = 1 1 1 1 1 0 12 12 1 Step 1 Step 3 Step 1. Step 2. Step 3. 01 1 2
18 20 2 2014 12: 7 8 2 web [12] p.49 1 10 10 time PC1 () time 1 11 (4 4) 11 0.016 2 [19] No.00 (6 6) 20 0.032 3 [19] No.01(10 10) 49 47.66 4 [19] No.04 (10 10) 43 32.78 5 [12] p.49, 1 (10 10) 27 0.063 6 [13] p.39, 1 (10 10) 42 > 5h 7 [14] p.41, 1 (10 10) 38 > 5h 8 [15] p.71, 1 (10 10) 41 401.3 9 [15] p.71, 2 (10 10) 39 > 5h 10 [19] No.02 (10 10) 51 > 5h 11 [19] No.03 (10 15) 64 > 5h 12 [13] p.39, 2 (25 25) 199 > 5h () time 1 11 (4 4) 8 0.016 2 [19] No.00 (6 6) 18 0.016 3 [19] No.01(10 10) 33 0.062 4 [19] No.04 (10 10) 26 0.031 5 [12] p.49, 1 (10 10) 26 0.031 6 [13] p.39, 1 (10 10) 34 1.529 7 [14] p.41, 1 (10 10) 26 0.062 8 [15] p.71, 1 (10 10) 26 0.081 9 [15] p.71, 2 (10 10) 31 2.059 10 [19] No.02 (10 10) 41 7.925 11 [19] No.03 (10 15) 52 9.216 12 [13] p.39, 2 (25 25) 144 > 5h 7: 8: 10 10 10 10 12 25 25
Bulletin of JSSACVol. 20, No. 2, 2014 19 5 [12, 13, 14, 15] 25 25 10 10 10 15 1 l m 1 n 1 m n m l 13 13 10 1 2 13 1 7 10 7 3 13 3 1 2 13 13: 1 Step 1 Step 3 Step 1. Step 2. Step 3. 1 2 9 10 PC1 time 25 25 10 0 time 0
20 20 2 2014 () time 12 [13] p.39, 2 (25 25) 199 > 5h 13 [12] p.49, 2 (25 25) 129 > 5h 14 [14] p.41, 2 (25 25) 137 > 5h 15 [15] p.71, 3 (25 25) 173 > 5h 9: () time 12 [13] p.39, 2 (25 25) 0 0 13 [12] p.49, 2 (25 25) 0 0 14 [14] p.41, 2 (25 25) 0 0 15 [15] p.71, 3 (25 25) 0 0 10: 25 25 11 11 1 11 () time 1 11 (4 4) 0 0 2 [19] No.00 (6 6) 0 0 3 [19] No.01(10 10) 0 0 4 [19] No.04 (10 10) 0 0 5 [12] p.49, 1 (10 10) 26 0.031 6 [13] p.39, 1 (10 10) 0 0 7 [14] p.41, 1 (10 10) 0 0 8 [15] p.71, 1 (10 10) 0 0 9 [15] p.71, 2 (10 10) 0 0 10 [19] No.02 (10 10) 22 0.015 11 [19] No.03 (10 15) 0 0 11: 11 5 10 5 10 121314 15 1213 1415
Bulletin of JSSACVol. 20, No. 2, 2014 21 4.3 1 2 9 Risa/Asir 5 Risa/Asir dp_gr_main 2 [1] Elizabeth Arnold, Stephen Lucas and Laura Taalman, Gröbner basis representations of Sudoku, The College Mathematics Journal, Vol. 41(2), pp. 101-112, 2010 [2] R. M. Falcón and J. Martín-Morales, Gröbner bases and the number of Latin squares related to autotopisms of order 7, Journal of Symbolic Computation, Vol.43(11-12), pp.1142 1154, 2007 [3] Jesús Gago-Vargas, Isabel Hartillo-Hermoso, Jorge Martín-Morales and José María Ucha- Enríquez, Sudokus and Gröbner bases: not only a divertimento, Proc. Computer Algera in Scientific Computing, LNCS, Vol. 4194, pp.155 165, Springer, 2006 [4] Alex Griffith and Adam Parker, A Gröbner basis approach to number puzzles, Proc. Midstates Conference for Undergraduate Research in Computer Science and Mathematics, pp.57 64, Oberlin College, 2009
22 20 2 2014 [5] Shutaro Inoue, Efficient singleton set constraint solving by Boolean Gröbner bases, Communication of JSSAC, Vol. 1, pp. 27 38, 2012 [6] 1785 pp. 51 562012 [7] 1666 pp. 1 52009 [8] JST CREST ()2011 [9] ( )& 2012 [10] http://www.nikoli.com/ja/ [11] 73 12001 [12] Vol. 1202007 [13] Vol. 1222008 [14] Vol. 1242008 [15] Vol. 1352011 [16] 2012 [17] Vol.18-2 pp. 21 242012 [18] Masayuki Noro and Taku Takeshima, Risa/Asir- A Computer Algebra System, Proc. ISSAC 1992, pp. 387 396, ACM-Press, 1992 http://www.math.kobe-u.ac.jp/asir/asir-ja.html [19] () http://indi.s58.xrea.com/ [20] Yosuke Sato, Shutaro Inoue, Akira Suzuki, Katsusuke Nabeshima and Ko Sakai, Boolean Gröbner bases, Journal of Symbolic Computation, Vol.46(5), pp.622 632, 2011