27 1 NP NP-completeness of Picross 3D without segment-information and that with height of one 115282 216 2 26
1 NP.,,., NP, 1 P.,, 1 NP, 3-SAT., NP, i
Abstract NP-completeness of Picross 3D without segment-information and that with height of one Tatsuro IKARASHI Picross 3D is a puzzle. An instance of the puzzle consists of a rectangular solid made of small cubes and hints on the surfaces of the rectangular solid. Players remove unnecessary cubes according to the hints and find the object hidden in the rectangular solid. Kusano et al. have shown that deciding whether a given Picross 3D instance has solutions is NP-complete, and if the height or an instance is restricted to one and segment-information is not given in the hints, then we can decide the existence of solutions in polynomial time. In this thesis, we show that it is NP-complete to decide the existence of solutions of a Picross 3D instance in the following two cases: (1) the segment-information is not given and the height is not restricted, and (2) the segment-information is given and the height is restricted to one. The NP-completeness is shown by reducing the 3-SAT to the above-mentioned problems. key words Computational complexity, NP-complete, Puzzle games ii
1 1 1.1,.............................. 1 2 3 2.1............................. 3 2.2.................................. 6 2.2.1................ 6 2.2.2................. 6 2.2.3 1........... 6 3 NP 7 3.1.................................. 7 3.1.1............................... 7 3.1.2................... 7 3.2..................... 8 3.2.1........................... 8 3.2.2............................ 13 3.2.3 NP........................... 15 3.3 1............... 16 3.3.1........................... 16 3.3.2............................ 23 3.3.3 NP........................... 25 4 27 4.1...................................... 27 iii
4.2.................................. 27 28 29 iv
1 1.1,, 29 [1].,,,. 1.1., [2].. 1 2 1 3 1 2 1 1 1 4 1 1 3 3 2 1 2 2 3 1 1 3 1 2 2 1.1, NP [3]., 1,,.,, NP. 1
1.1,,,, 1. 3-SAT NP, NP. 2
2 2.1,. 1.1,,.,, [3].,,.,,, w, h, d. 1 x w, 1 y h, 1 z d, (x, y, z) p x,y,z. 3, P p 1,h,1 p 2,h,1... p w,h,1 p 1,h 1,1 p 2,h 1,1... p w,h 1,1 P =...... p 1,1,1 p 2,1,1... p w,1,1 p 1,h,d p 2,h,d... p w,h,d p 1,h 1,d p 2,h 1,d... p w,h 1,d........ p 1,1,d p 2,1,d... p w,1,d p 1,h,2 p 2,h,2... p w,h,2 p 1,h 1,2 p 2,h 1,2... p w,h 1,2...... p 1,1,2 p 2,1,2... p w,1,2....,. 3
2.1 1,, 1.1 P = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1.,,,. h w F, h d S, d w T. F, S, T f 1,h f 2,h... f w,h f 1,h 1 f 2,h 1... f w,h 1 F =...... f 1,1 f 2,1... f w,1 s h,1 s h,2... s h,d s h 1,1 s h 1,2... s h 1,d S =...... s 1,1 s 1,2... s 1,d t d,1 t d,2... t d,w t d 1,1 t d 1,2... t d 1,w T =...... t 1,1 t 1,2... t d,w. 1.1, F, S, T F = 1 1 2 1 3 1 1 3 4
2.1 4 4 4 4 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2.1 4 S = T = 1 1 3 1 2 1 2 3 2 4 2 1 1 2 2 1 3.,,.,,., 1.1 F 4,3 = 1, p 4,3,1, p 4,3,2, p 4,3,3, 1.,., ( ),. 2, 3., 4, 2.1.,.,. 5
2.2 2.2,. 2.2.1 PICROSS-3D. : w, h, d, h w F, h d S, d w T : yes, no 2.2.2 NOSEG-PICROSS-3D. : w, h, d, h w F, h d S, d w T : yes, no, F, S, T.,,. 2.2.3 1, PICROSS-3D, h 1. 6
3 NP 3.1,. 3.1.1 2 2 NP, 3-SAT. 3-SAT, 3,, 1., 3-SAT,., 3-SAT,. 3.1.2., 1,. F, S, T, 1,,, 2. 7
3.2 3.2 NP. 3.2.1 NOSEG-PICROSS-3D NP. 3-SAT m (x 1, x 2,.., x m ) k,. = (a 1 b 1 c 1 ) (a 2 b 2 c 2 ) (a k b k c k ) NOSEG-PICROSS-3D. w = m + 2 + (2m + 2)(k 1) h = k d = 2m + 2 F : y = 1 f 1,1 = f 1,2 = = f 1,m = 1 f 1,m+1 = f 1,m+2 = 2. y = 2 f 2,1 = f 2,2 = = f 2,m = 1 f 2,m+1 = f 2,m+2 = f 2,m+2+1 = f 2,m+2+2 = = f 2,m+2+2m = 1 f 2,3m+3 = f 2,3m+4 =. 8
3.2 2 < y h, x = 1 X Xplace Xplace(y, m) = m + 3 + (y 2)(2m + 2), f y,xplace(y,m) = f y,xplace(y,m)+1 = = f y,xplace(y,m)+2m = f y,xplace(y,m)+2m+1 = f y,xplace(y,m)+2m+2 = f y,xplace(y,m)+2m+3 = f y,xplace(y,m)+2m+4 = = f y,xplace(y,m)+2m+3+2m = 1 f y,xplace(y,m)+4m+3+1 = f y,xplace(y,m)+4m+3+2 =. S : z 2m 1 z = 2m + 1 z = 2m + 2 s 1,2m+2 = 2 T :,, exist(x i, k), exist2(x i, k). A 1,k = exist(x 1, k) A 2,k = exist(x 1, k) A 3,k = exist(x 2, k) A 4,k = exist(x 2, k) A 5,k = exist(x 3, k) A 6,k = exist(x 3, k). 9
3.2 A 2m 1,k = exist(x m, k) A 2m,k = exist(x m, k) B 1,k = exist2(x 1, k) B 2,k = exist2(x 1, k) B 3,k = exist2(x 2, k) B 4,k = exist2(x 2, k) B 5,k = exist2(x 3, k) B 6,k = exist2(x 3, k). B 2m 1,k = exist2(x m, k) B 2m,k = exist2(x m, k) 1 x m (x k ) exist(x, k) = (x k ) (x k ) exist2(x, k) = (x k ) t 1,1 = t 1,2 = t 2,3 = t 2,4 =,, = t m,2m 1 = t m,2m = 1. x = m + 1, 1 z 2m t z,x = A z,1 x = m + 1, 2m + 1 z 2m + 2 t 2m+1,x = t 2m+2,x = x = m + 2, 1 z 2m t z,x = B z,1 x = m + 2, 2m + 1 z 2m + 2 1
3.2 t 2m+1,x = t 2m+2,x = m + 1 x w, 2m (2m + 2) L M, 2 (2m + 2) N n (n = 2, 3, 4,.., k) N n =... 1... 1 L =......... 1... 1......... M =............... ( ) B1,n B 2,n... B k 1,n B k,n A 1,n A 2,n... A k 1,n A k,n. T L, M, N 2, N 3,.., N k,............ N 2 N 3... N k 1 N k... 1 A 2m,1 B 2m,1... 1 A 2m 1,1 B 2m 1,1... 1 A 2m 2,1 B 2m 2,1... 1 A 2m 3,1 B 2m 3,1 T =.................. 1... A 4,1 B 4,1 1... A 3,1 B 3,1 1... A 2,1 B 2,1 1... A 1,1 B 1,1. L L... L M., L (k 2). 11
3.2 1: 3 3-SAT = (x 1 x 2 x 3 ) (x 1 x 2 x 2 ) (x 1 x 2 x 3 ) NOSEG-PICROSS-3D Q w=21, h=3, d=8, F = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2 1 1 1 1 1 1 2 S = 1 1 1 1 1 1 2, 1 1 1 1 1 1 1 1 1 1 T = 1 1 1 1 1 1 1 1. 3-SAT, x 1 = T rue, x 2 = T rue, x 3 = F alse,.. Q P = ( 1 1 1 1 1 1,, 12
3.2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ). p 2i 1,1,i x i, p 2i,1,i x i. F, T, p 2i 1,1,i, p 2i,1,i 1,.,,,,,. 3.2.2 y = 1 p 2i 1,1,i, p 2i,1,i x i, x i, 3-SAT 1 y = 1. 2 j (2 j h), y = j., 2, y = 1, 2., y = 1, y = 2. 13
3.2, j.j x i, x wherex, p wherex(j,i,m),j,2i 1 wherex(j, i, m) = m + 2 + (2m + 2)(j 2) + 2i 1., j x i, x wherexbar, p wherexbar(j,i,m),j,2i wherexbar(j, i, m) = m + 2 + (2m + 2)(j 2) + 2i. 1, 2 x 3, p wherex(2,3,3),2,2 3 1 = p 1,2,5. (i) 2 1 2. 1 x i p i,1,2i 1.x i = 1, T 2i 1,i = 1 F, p i,2,2i 1 =. S 2,2i 1 = 1, p 1,2,q (q = 1, 2, 3,..., 3m + 3), 1 p i,2,2i 1 p m+2+1,2,2i 1 2. p i,2,2i 1 =, p m+2+1,2,2i 1 = 1, p i,1,2i 1. x i =, x i. (ii) k (k 2) k (k + 1). k, x i = 1, p wherex(k,i,m),k,2i 1 = 1. T 2i 1,whereX(k,i,m) = 1, F k+1,wherex(k,i,m) =. F r,wherex (r = 1, 2,..., k, k + 2, k + 3,..., h) =, p wherex(k,i,m),k+1,2i 1 =. p wherex(k,i,m),k+1,2i 1 =, S k+1,2i 1 = 1, p wherex(k,i,m),k+1,2i 1 = 1, p wherex(k,i,m),k,2i 1. p wherex(k,i,m),k,2i 1 =, x i. 14
3.2,. 1. NOSEG-PICROSS-3D,, y = 1 x i, x i p 2i 1,1,i, p 2i,1,i, y = 2(y h) p wherex(j,i,m),j,2i 1, p wherexbar(j,i,m),j,2i. 3.2.3 NP,, 3-SAT. 3-SAT., p 1,1,1, p 1,1,2,.., p i,1,2i 1. (i) 1 T, 1 p m+2,1,l (l = 1, 2,.., 2m), Z 1., p m+2,1,l 1 2., 1 n, p m+2,1,2m+1, p m+2,1,2m+2 (2 n) 1,. (ii) k (k 2) 1, k, 1. T, k, p wherex(k,i,m)+l,k,2m+2 (l =, 1, 2,.., 5), X 1., p (wherex(k,i,m)+l,k,2m+2) 1 2., 1 n, p wherex(k,i,m)+6,k,2m+2, p wherex(k,i,m)+7,k,2m+2 (2 n) 1,.,,.. (i) y = 1 15
3.3 1, T, 1 p m+2,1,l (l = 1, 2,.., 6) 1 2 p 1,1,1, p 1,1,2,..., p i,1,2i 1,1 R., 1 1. (ii) y = 2 1, (i) 2,, k (k 2) p wherex(k,1,m)+l,k,2m+2 (l =, 1, 2,.., 5), 1 2, 1, R 1., k (k 2) 1, (i).,,.,. 3.2.1. NOSEG-PICROSS-3D NP.,, NP. 3.3 1, 1 NP. 3.3.1 PICROSS-3D h 1 NP. m (x 1, x 2,, x m ) k,. = (a 1 b 1 c 1 ) (a 2 b 2 c 2 ) (a 3 b 3 c 3 ) PICROSS-3D ( 1). 16
3.3 1 m i (i = 1, 2,..., m) x i, x i, w = 4 + (m 1) + m i=1 capx(m i) h = 1 d = 2k + m i=1 capz(m i) 2 (i = 1) capx(i) = 5 (i = 2) 5 + 4(i 2) (i > 2) 1 (i < 3) capz(i) = i 1 (i 3) capx, capz, X, Z (x i, x i ). F : 1 x 4 f 1,1 = f 1,3 = f 1,2 = f 1,4 = 5 x w m 1, m 2,.., m j capx capsumx(j)(j m).capsumx, j i=1 capsumx(j) = capx(m i) (j 1) (j = ) f 1,4+1+camsumX(1) = f 1,4+2+capsumX(2) =... = f 1,4+m 1+capsum(m 1) = 1 S : 1 z capz(m 1 ) 1 (capz(m 1 ) = 1) s 1,1 = s 1,2 =... = s 1,capZ(m1 ) = 3 (capz(m 1 ) > 1) 17
3.3 1 m 1, m 2,.., m j capz capsumz(j)(j m) j i=1 capsumz(j) = capz(m i) (j 1) (j = ). capsumz, capz(m 1 ) + 1 z d 2k, p(p = 1, 2,.., m 1), 1 (cap(m p ) = 1) s 1,capsumZ(p)+1 = s 1,capsumZ(p)+2 =... = s 1,capsumZ(p+1) = 3 (cap(m p ) > 1) d 2k + 1 z d, (s 1,d 2k+1, s 1,d 2k+2 ) = (s 1,d 2k+3, s 1,d 2k+4 ) =... = (s 1,d 1, s 1,d ) = (, 2 ) T : 1 x 4, 1 z capsumz(m) 5 x w, 1 z capsumz(m) m i (i = 1, 2,.., m),. m i = 1 t capsumz(mi )+1,5+capsum(m i )X+i 1 = t capsumz(mi )+1,6+capsumX(m i )+i 1 = m i = 2 t capsumz(i 1)+1,5+capsumX(i 1)+i 1 = t capsumz(i 1)+1,5+1+capsumX(i 1)+i 1 = t capsumz(i 1)+1,5+2+capsumX(i 1)+i 1 = 1 t capsumz(i 1)+1,5+3+capsumX(i 1)+i 1 = t capsumz(i 1)+1,5+4+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+4+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+5+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+6+capsumX(i 1)+i 1 = 1 t capsumz(i 1)+2,5+7+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+8+capsumX(i 1)+i 1 = m i 2 t capsumz(i 1)+1,5+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+4+capsumX(i 1)+i 1 =.. = t capsumz(i 1)+mi 1,5+4(m i 1)+capsumX(i 1)+i 1 = 18
3.3 1 t capsumz(i 1)+1,5+1+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+1+4+capsumX(i 1)+i 1 =.. = t capsumz(i 1)+mi 1,5+1+4(m i 1)+capsumX(i 1)+i 1 = t capsumz(i 1)+1,5+2+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+2+4+capsumX(i 1)+i 1 =.. = t capsumz(i 1)+mi 1,5+2+4(m i 1)+capsumX(i 1)+i 1 = 1 t capsumz(i 1)+1,5+3+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+3+4+capsumX(i 1)+i 1 =.. = t capsumz(i 1)+mi 1,5+3+4(m i 1)+capsumX(i 1)+i 1 = t capsumz(i 1)+1,5+4+capsumX(i 1)+i 1 = t capsumz(i 1)+2,5+4+4+capsumX(i 1)+i 1 =.. = t capsumz(i 1)+mi 1,5+4+4(m i 1)+capsumX(i 1)+i 1 = 1 x 4, capsumz(m) + 1 z d t capsumz(m)+2,1 = t capsumz(m)+4,1 =.. = t capsumz(m)+2k,1 = t capsumz(m)+2,3 = t capsumz(m)+4,3 =.. = t capsumz(m)+2k,3 = 5 x w, capsumz(m) + 1 z d z = capsumz(m) + 2j(j = 1, 2,.., k), j (a j b j c j ). a j = x i x i, x i, x i p j. a j = x i (A, B) = (, ), a j = x i (A, B) = (, ), m i = 1 t capsumz(mi )+1+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+2j,5+capsumX(m i )+i = A t capsumz(mi )+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+1+2j,5+capsumX(m i )+i = B m i = 2, p j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i = 2, p j = 2 t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i = B 19
3.3 1 m i > 2, p j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i > 2, 1 < p j < m i t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = B m i > 2, p j = m i t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i = B b j = x i x i, (j a j )x i, x i q j. b j = x i (A, B) = (, ), b = x i (A, B) = (, ), m i = 1 t capsumz(mi )+1+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+2j,5+capsumX(m i )+i = A t capsumz(mi )+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+1+2j,5+capsumX(m i )+i = B m i = 2, q j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i = 2, q j = 2 t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i = B m i > 2, q j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A 2
3.3 1 t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i > 2, 1 < q j < m i t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = B m i > 2, q j = m i t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i = B c j = x i x i, (j a j, b j )x i, x i r j. c j = x i (A, B) = (, ), c = x i (A, B) = (, ), m i = 1 t capsumz(mi )+1+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+2j,5+capsumX(m i )+i = A t capsumz(mi )+2j,5+capsumX(m i )+i 1 = t capsumz(mi )+1+2j,5+capsumX(m i )+i = B m i = 2, r j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i = 2, r j = 2 t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+capsumX(i 1)+i = B m i > 2, r j = 1 t capsumz(mi )+1+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+capsumX(i 1)+i = A t capsumz(mi )+2j,5+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+capsumX(i 1)+i = B m i > 2, 1 < r j < m i 21
3.3 1 t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i+1 = B m i > 2, r j = m i t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i = A t capsumz(mi )+2j,5+3+4k(k 2)+capsumX(i 1)+i 1 = t capsumz(mi )+1+2j,5+3+4k(k 2)+capsumX(i 1)+i = B. = (x 1 x 2 x 3 ) (x 1 x 2 x 2 ) NOSEG-PICROSS-3D Q w=22, h=1, d=8, ( ) F = 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1. ( ) S = 3 3 3 1 2 2, T = 1 1 1.. 3-SAT, x 1 = T rue, x 2 = T rue, x 3 = F alse. Q 22
3.3 1 P =. 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1. 3.3.2 x i, x i, 1, 2., m i., 1,. (i) m i = 1 1 x i, x i p 5+capsum(mi )+i 1,1,capsum(m i )+1, p 6+capsum(mi )+i 1,1,capsum(m i )+1., 1,. S, 1,. (ii) m i = 2. m i = 2, 1, 2 (x i, x i ) = (p 5+capsumX(i 1)+i 1,1,capsumZ(i 1)+1, p 5+1+capsumX(i 1)+i 1,1,capsumZ(i 1)+1 ) (1 ) (x i, x i ) = (p 5+3+capsumX(i 1)+i 1,1,capsumZ(i 1)+1, p 5+4+capsumX(i 1)+i 1,1,capsumZ(i 1)+1 ) (2 ). 3.1. 23
3.3 1 3 1 1 1 1 1 1 3.1 (m i = 2), T,,., S 3, (1,, 1, 1, ) (, 1, 1,, 1)., 1 2 1, 4 5 2, 2., 1,. (iii) m i > 2 1, k (x i, x i ) = (p 5+capsumX(i 1)+i 1,1,capsumZ(i 1)+1, p 5+1+capsumX(i 1)+i 1,1,capsumZ(i 1)+1 ) (k = 1) (x i, x i ) = (p 5+3+4k(k 2)+capsumX(i 1)+i 1,1,capsumZ(i 1)+k 1, p 5+5+4k(k 2)+capsumX(i 1)+i 1,1,capsumZ(i 1)+k ) (2 k < m i ) (x i, x i ) = (p 5+3+4k(k 2)+capsumX(i 1)+i 1,1,capsumZ(i 1)+k 1, p 5+4+capsumX(i 1)+i 1,1,capsumZ(i 1)+k 1 ) (k = m i ) 3 1 3 1 3 1 3 1 3 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 3.2 (m i 2)., 3.2. 1 24
3.3 1 1, 2, 2 2, 2 2. k (k 1) 2, k 2, m i (k 1) 1, 2. 1 (1,, 1, 1, ), (, 1, 1,, 1), 2 (1,, 1, 1, ) 1, (, 1, 1,, 1)., 2 1., k (1,, 1, 1, ), (, 1, 1,, 1), k + 1,., 1, 2, 1, 2, 2 2,.m i > 2,., 1,.,. 2. PICROSS-3D ( 1),, 1 x i, x i p 5+capsumX(i 1)+i 1,1,capsumZ(i 1)+1, p 5+1+capsumX(i 1)+i 1,1,capsumZ(i 1)+1, 2 x i, x i. 3.3.3 NP,, PICROSS-3D ( 1) NP.. (i) 1, 1. 2, 2, 1.T, 1 X, z = capsumz(m) + 2 25
3.3 1 1, 2. 1 n, p 1,1,capsumZ(m)+2, p 3,1,capsumZ(m)+2 (2 n) 1,. (ii) k (2 k) k,, 2., X z = capsumz(m) + 2k 1, 2. 1 n, p 1,1,capsumZ(m)+2k, p 3,1,capsumZ(m)+2k (2 n) 1,.,,.. (i) 1 z capsumz(m) + 2, T, p 1,1,capsumZ(m)+2, p 3,1,capsumZ(m)+2 z = capsumz(m) + 2 1, 2 1, 1 R., 1 1. (ii) capsumz(m) + 2 z d 2, (i) 2,, j (j = 2, 3,.., k) z = capsumz(m) + 2j, p 1,1,capsumZ(m)+2, p 3,1,capsumZ(m)+2 1, j 2 R 1., j 1, (i).,,.,. 3.3.1. PICROSS-3D ( 1) NP. 26
4 4.1,, 1 NP. [3],, NP, NP. 4.2 [3], 4 NP. NP,, NP.,. 27
,,,.,,.,,. 28
[1],, http://www.nintendo.co.jp/ds/c6pj/, 216 1 27. [2], NP, http://www-imai.is.s.u-tokyo. ac.jp/~yato/data2/puzcc.pdf, 216 2 1. [3],,, NP, 21, pp.18 113, 21. 29