27 1 NP NP-completeness of Picross 3D without segment-information and that with height of one
|
|
- れれ つなかわ
- 5 years ago
- Views:
Transcription
1 27 1 NP NP-completeness of Picross 3D without segment-information and that with height of one
2 1 NP.,,., NP, 1 P.,, 1 NP, 3-SAT., NP, i
3 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
4 , NP NP NP iii
5 iv
6 1 1.1,, 29 [1].,,,. 1.1., [2] , NP [3]., 1,,.,, NP. 1
7 1.1,,,, 1. 3-SAT NP, NP. 2
8 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, p 1,1,2 p 2,1,2... p w,1,2....,. 3
9 2.1 1,, 1.1 P = ,,,. 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 =
10 S = T = ,,.,,., 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
11 , PICROSS-3D. : w, h, d, h w F, h d S, d w T : yes, no NOSEG-PICROSS-3D. : w, h, d, h w F, h d S, d w T : yes, no, F, S, T.,, , PICROSS-3D, h 1. 6
12 3 NP 3.1, NP, 3-SAT. 3-SAT, 3,, 1., 3-SAT,., 3-SAT, , 1,. F, S, T, 1,,, 2. 7
13 NP 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 (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
14 3.2 2 < y h, x = 1 X Xplace Xplace(y, m) = m (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
15 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
16 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 = L = 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, A 2m 1,1 B 2m 1, A 2m 2,1 B 2m 2, A 2m 3,1 B 2m 3,1 T = A 4,1 B 4, A 3,1 B 3, A 2,1 B 2, A 1,1 B 1,1. L L... L M., L (k 2). 11
17 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 = S = , T = SAT, x 1 = T rue, x 2 = T rue, x 3 = F alse,.. Q P = ( ,, 12
18 ). 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,.,,,,, 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
19 3.2, j.j x i, x wherex, p wherex(j,i,m),j,2i 1 wherex(j, i, m) = m (2m + 2)(j 2) + 2i 1., j x i, x wherexbar, p wherexbar(j,i,m),j,2i wherexbar(j, i, m) = m (2m + 2)(j 2) + 2i. 1, 2 x 3, p wherex(2,3,3),2,2 3 1 = p 1,2,5. (i) 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
20 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 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
21 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).,,., NOSEG-PICROSS-3D NP.,, NP , 1 NP 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
22 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
23 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
24 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
25 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
26 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
27 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 = ( ) S = , T = SAT, x 1 = T rue, x 2 = T rue, x 3 = F alse. Q 22
28 3.3 1 P = 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 )
29 (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 ) (m i 2).,
30 , 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 NP,, PICROSS-3D ( 1) NP.. (i) 1, 1. 2, 2, 1.T, 1 X, z = capsumz(m)
31 , 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).,,., PICROSS-3D ( 1) NP. 26
32 4 4.1,, 1 NP. [3],, NP, NP. 4.2 [3], 4 NP. NP,, NP.,. 27
33 ,,,.,,.,,. 28
34 [1],, [2], NP, ac.jp/~yato/data2/puzcc.pdf, [3],,, NP, 21, pp ,
n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i
15 Comparison and Evaluation of Dynamic Programming and Genetic Algorithm for a Knapsack Problem 1040277 2004 2 25 n 2 n (Dynamic Programming : DP) (Genetic Algorithm : GA) 2 i Abstract Comparison and
More information203 x, y, z (x, y, z) x 6 + y 6 + z 6 = 3xyz ( 203 5) a 0, b 0, c 0 a3 + b 3 + c 3 abc 3 a = b = c 3xyz = x 6 + y 6 + z 6 = (x 2 ) 3 + (y 2 ) 3
203 24 203 x, y, z (x, y, z) x 6 + y 6 + z 6 = 3xyz ( 203 5) 202 20 a 0, b 0, c 0 a3 + b 3 + c 3 abc 3 a = b = c 3xyz = x 6 + y 6 + z 6 = (x 2 ) 3 + (y 2 ) 3 + (z 2 ) 3 3x 2 y 2 z 2 ( ) 3xyz 3(xyz) 2.
More information25 Removal of the fricative sounds that occur in the electronic stethoscope
25 Removal of the fricative sounds that occur in the electronic stethoscope 1140311 2014 3 7 ,.,.,.,.,.,.,.,,.,.,.,.,,. i Abstract Removal of the fricative sounds that occur in the electronic stethoscope
More information44 4 I (1) ( ) (10 15 ) ( 17 ) ( 3 1 ) (2)
(1) I 44 II 45 III 47 IV 52 44 4 I (1) ( ) 1945 8 9 (10 15 ) ( 17 ) ( 3 1 ) (2) 45 II 1 (3) 511 ( 451 1 ) ( ) 365 1 2 512 1 2 365 1 2 363 2 ( ) 3 ( ) ( 451 2 ( 314 1 ) ( 339 1 4 ) 337 2 3 ) 363 (4) 46
More informationi ii i iii iv 1 3 3 10 14 17 17 18 22 23 28 29 31 36 37 39 40 43 48 59 70 75 75 77 90 95 102 107 109 110 118 125 128 130 132 134 48 43 43 51 52 61 61 64 62 124 70 58 3 10 17 29 78 82 85 102 95 109 iii
More information25 II :30 16:00 (1),. Do not open this problem booklet until the start of the examination is announced. (2) 3.. Answer the following 3 proble
25 II 25 2 6 13:30 16:00 (1),. Do not open this problem boolet until the start of the examination is announced. (2) 3.. Answer the following 3 problems. Use the designated answer sheet for each problem.
More informationPage 1 of 6 B (The World of Mathematics) November 20, 2006 Final Exam 2006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (10pts) (a
Page 1 of 6 B (The World of Mathematics) November 0, 006 Final Exam 006 Division: ID#: Name: 1. p, q, r (Let p, q, r are propositions. ) (a) (Decide whether the following holds by completing the truth
More information2 ( ) i
25 Study on Rating System in Multi-player Games with Imperfect Information 1165069 2014 2 28 2 ( ) i ii Abstract Study on Rating System in Multi-player Games with Imperfect Information Shigehiko MORITA
More informationron.dvi
12 Effect of occlusion and perception of shadow in depth perception caused by moving shadow. 1010361 2001 2 5 (Occlusion), i Abstract Effect of occlusion and perception of shadow in depth perception caused
More information, IT.,.,..,.. i
25 To construct the system that promote a interactive method as a knowledge acquisition 1140317 2014 2 28 , IT.,.,..,.. i Abstract To construct the system that promote a interactive method as a knowledge
More informationsoturon.dvi
12 Exploration Method of Various Routes with Genetic Algorithm 1010369 2001 2 5 ( Genetic Algorithm: GA ) GA 2 3 Dijkstra Dijkstra i Abstract Exploration Method of Various Routes with Genetic Algorithm
More information,,.,.,,.,.,.,.,,.,..,,,, i
22 A person recognition using color information 1110372 2011 2 13 ,,.,.,,.,.,.,.,,.,..,,,, i Abstract A person recognition using color information Tatsumo HOJI Recently, for the purpose of collection of
More informationFAX-760CLT
FAX-760CLT ;; yy 1 f a n l p w s m t v y k u c j 09,. i 09 V X Q ( < N > O P Z R Q: W Y M S T U V 1 2 3 4 2 1 1 2 1 2 j 11 dd e i j i 1 ; 3 oo c o 1 2 3 4 5 6 j12 00 9 i 0 9 i 0 9 i 0 9 i oo
More information24 LED A visual programming environment for art work using a LED matrix
24 LED A visual programming environment for art work using a LED matrix 1130302 2013 3 1 LED,,,.,. Arduino. Arduino,,,., Arduino,.,, LED,., Arduino, LED, i Abstract A visual programming environment for
More information2007-Kanai-paper.dvi
19 Estimation of Sound Source Zone using The Arrival Time Interval 1080351 2008 3 7 S/N 2 2 2 i Abstract Estimation of Sound Source Zone using The Arrival Time Interval Koichiro Kanai The microphone array
More information7,, i
23 Research of the authentication method on the two dimensional code 1145111 2012 2 13 7,, i Abstract Research of the authentication method on the two dimensional code Karita Koichiro Recently, the two
More information, (GPS: Global Positioning Systemg),.,, (LBS: Local Based Services).. GPS,.,. RFID LAN,.,.,.,,,.,..,.,.,,, i
25 Estimation scheme of indoor positioning using difference of times which chirp signals arrive 114348 214 3 6 , (GPS: Global Positioning Systemg),.,, (LBS: Local Based Services).. GPS,.,. RFID LAN,.,.,.,,,.,..,.,.,,,
More information23 Study on Generation of Sudoku Problems with Fewer Clues
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
More information2 1 ( ) 2 ( ) i
21 Perceptual relation bettween shadow, reflectance and luminance under aambiguous illuminations. 1100302 2010 3 1 2 1 ( ) 2 ( ) i Abstract Perceptual relation bettween shadow, reflectance and luminance
More information06_学術.indd
Arts and Sciences Development and usefulness evaluation of a remote control pressured pillow for prone position 1 36057 2 45258 2 29275 3 3 4 1 2 3 4 Key words: pressured pillow prone position, stomach
More information01-加藤 実-5.02
Bull. Natl. Mus. Nat. Sci., Ser. E, 30, pp. 1 13, December 21, 2007 1 2 3 1 169 0073 3 23 1 2 523 0058 961 3 248 0036 3 5 6 The Mechanism of the Automatic Wari-koma Dial in the Japanese Clocks and its
More information2
2011 8 6 2011 5 7 [1] 1 2 i ii iii i 3 [2] 4 5 ii 6 7 iii 8 [3] 9 10 11 cf. Abstracts in English In terms of democracy, the patience and the kindness Tohoku people have shown will be dealt with as an exception.
More information2 236
28 2004 pp. 235 245 1 Received November 5, 2004 In the eighth volume of Confessiones is a famous and critical passage in which Augustine describes the process leading to his conversion. It is a long and
More information〈論文〉興行データベースから「古典芸能」の定義を考える
Abstract The long performance database of rakugo and kabuki was totaled, and it is found that few programs are repeated in both genres both have the frequency differential of performance. It is a question
More information駒田朋子.indd
2 2 44 6 6 6 6 2006 p. 5 2009 p. 6 49 12 2006 p. 6 2009 p. 9 2009 p. 6 2006 pp. 12 20 2005 2005 2 3 2005 An Integrated Approach to Intermediate Japanese 13 12 10 2005 8 p. 23 2005 2 50 p. 157 2 3 1 2010
More information24 Depth scaling of binocular stereopsis by observer s own movements
24 Depth scaling of binocular stereopsis by observer s own movements 1130313 2013 3 1 3D 3D 3D 2 2 i Abstract Depth scaling of binocular stereopsis by observer s own movements It will become more usual
More informationi
14 i ii iii iv v vi 14 13 86 13 12 28 14 16 14 15 31 (1) 13 12 28 20 (2) (3) 2 (4) (5) 14 14 50 48 3 11 11 22 14 15 10 14 20 21 20 (1) 14 (2) 14 4 (3) (4) (5) 12 12 (6) 14 15 5 6 7 8 9 10 7
More informationFAX780CL_chap-first.fm
FAX-780CL ABCDEFGHIα 01041115:10 :01 FAX-780CL α 1 1 2 3 1 2 f k b a FAX-780CL α n p q 09,. v m t w FAX-780CL A BC B C D E F G H I c i c s s i 0 9 V X Q ( < N > O P Z R Q: W Y M S T U V i c i k
More information..,,,, , ( ) 3.,., 3.,., 500, 233.,, 3,,.,, i
25 Feature Selection for Prediction of Stock Price Time Series 1140357 2014 2 28 ..,,,,. 2013 1 1 12 31, ( ) 3.,., 3.,., 500, 233.,, 3,,.,, i Abstract Feature Selection for Prediction of Stock Price Time
More informationDTN DTN DTN DTN i
28 DTN Proposal of the Aggregation Message Ferrying for Evacuee s Data Delivery in DTN Environment 1170302 2017 2 28 DTN DTN DTN DTN i Abstract Proposal of the Aggregation Message Ferrying for Evacuee
More information第1部 一般的コメント
(( 2000 11 24 2003 12 31 3122 94 2332 508 26 a () () i ii iii iv (i) (ii) (i) (ii) (iii) (iv) (a) (b)(c)(d) a) / (i) (ii) (iii) (iv) 1996 7 1996 12
More informationkut-paper-template.dvi
26 Discrimination of abnormal breath sound by using the features of breath sound 1150313 ,,,,,,,,,,,,, i Abstract Discrimination of abnormal breath sound by using the features of breath sound SATO Ryo
More informationII
No. 19 January 19 2013 19 Regionalism at the 19 th National Assembly Elections Focusing on the Yeongnam and Honam Region Yasurou Mori As the biggest issue of contemporary politics at South Korea, there
More informationuntitled
13 50 15 6.0 0.25 220 23 92 960 16 16 3.9 3.9 12.8 83.3 7 10 1150 90 1035 1981 1850 4700 4700 15 15 1150 1150 10 12 31 1.5 3.7%(224 ) 1.0 1.5 25.4%(1522 ) 0.7 30.6 1835 ) 0.7 1.0 40.3 (2421 ) 7.3
More information23 A Comparison of Flick and Ring Document Scrolling in Touch-based Mobile Phones
23 A Comparison of Flick and Ring Document Scrolling in Touch-based Mobile Phones 1120220 2012 3 1 iphone..,. 2 (, ) 3 (,, ),,,.,..,. HCI i Abstract A Comparison of Flick and Ring Document Scrolling in
More informationNotePC 8 10cd=m 2 965cd=m 2 1.2 Note-PC Weber L,M,S { i {
12 The eect of a surrounding light to color discrimination 1010425 2001 2 5 NotePC 8 10cd=m 2 965cd=m 2 1.2 Note-PC Weber L,M,S { i { Abstract The eect of a surrounding light to color discrimination Ynka
More information第1章 国民年金における無年金
1 2 3 4 ILO ILO 5 i ii 6 7 8 9 10 ( ) 3 2 ( ) 3 2 2 2 11 20 60 12 1 2 3 4 5 6 7 8 9 10 11 12 13 13 14 15 16 17 14 15 8 16 2003 1 17 18 iii 19 iv 20 21 22 23 24 25 ,,, 26 27 28 29 30 (1) (2) (3) 31 1 20
More information1 (1) (2)
1 2 (1) (2) (3) 3-78 - 1 (1) (2) - 79 - i) ii) iii) (3) (4) (5) (6) - 80 - (7) (8) (9) (10) 2 (1) (2) (3) (4) i) - 81 - ii) (a) (b) 3 (1) (2) - 82 - - 83 - - 84 - - 85 - - 86 - (1) (2) (3) (4) (5) (6)
More information- 2 -
- 2 - - 3 - (1) (2) (3) (1) - 4 - ~ - 5 - (2) - 6 - (1) (1) - 7 - - 8 - (i) (ii) (iii) (ii) (iii) (ii) 10 - 9 - (3) - 10 - (3) - 11 - - 12 - (1) - 13 - - 14 - (2) - 15 - - 16 - (3) - 17 - - 18 - (4) -
More information2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4 4 4 2 5 5 2 4 4 4 0 3 3 0 9 10 10 9 1 1
1 1979 6 24 3 4 4 4 4 3 4 4 2 3 4 4 6 0 0 6 2 4 4 4 3 0 0 3 3 3 4 3 2 4 3? 4 3 4 3 4 4 4 4 3 3 4 4 4 4 2 1 1 2 15 4 4 15 0 1 2 1980 8 4 4 4 4 4 3 4 2 4 4 2 4 6 0 0 6 4 2 4 1 2 2 1 4 4 4 2 3 3 3 4 3 4 4
More information20 15 14.6 15.3 14.9 15.7 16.0 15.7 13.4 14.5 13.7 14.2 10 10 13 16 19 22 1 70,000 60,000 50,000 40,000 30,000 20,000 10,000 0 2,500 59,862 56,384 2,000 42,662 44,211 40,639 37,323 1,500 33,408 34,472
More informationI? 3 1 3 1.1?................................. 3 1.2?............................... 3 1.3!................................... 3 2 4 2.1........................................ 4 2.2.......................................
More information,,,,., C Java,,.,,.,., ,,.,, i
24 Development of the programming s learning tool for children be derived from maze 1130353 2013 3 1 ,,,,., C Java,,.,,.,., 1 6 1 2.,,.,, i Abstract Development of the programming s learning tool for children
More informationISSN NII Technical Report Patent application and industry-university cooperation: Analysis of joint applications for patent in the Universit
ISSN 1346-5597 NII Technical Report Patent application and industry-university cooperation: Analysis of joint applications for patent in the University of Tokyo Morio SHIBAYAMA, Masaharu YANO, Kiminori
More informationStudies of Foot Form for Footwear Design (Part 9) : Characteristics of the Foot Form of Young and Elder Women Based on their Sizes of Ball Joint Girth
Studies of Foot Form for Footwear Design (Part 9) : Characteristics of the Foot Form of Young and Elder Women Based on their Sizes of Ball Joint Girth and Foot Breadth Akiko Yamamoto Fukuoka Women's University,
More information立命館21_松本先生.indd
2143-552010 1 2 () 1 2 3 456 78- Key Words 1 3 12007 2 3 508 19992008 1 23 4 43 2120107 4 2008 1992 2003 2005 1989 2008 4 2 2-1 10 4 4 6 5 4 5 2946 1 155 11 41 44 45 4 2-2 2003 1 21 2 1 3 4 5 6 7 3 2120107
More information立命館20_服部先生.indd
20 93-105 2010 2 () ' - 1 ( ) ( ' 2005) Key Words 2 1967 93 20 2010 1 94 1 ' 2002 2 2 1996 1996 1999 2 2 2 1993 1999 4 1 2 1985 1989 1986 1994 4 1 2 1 1 4 2 4 4 1 4 1966 4 10-1970 20 1993-1972 95 20 2010
More information1996 2000 2004 1984 2005 7150 000 9 500 9 4 13 10 95 11 11 12 20002004 9 70
14 2006 1 Key Words 2002 3 1 2 3 3 1 2 3 1969 1987 69 1996 2000 2004 1984 2005 7150 000 9 500 9 4 13 10 95 11 11 12 20002004 9 70 14 2006 1 15 71 72 1 22 6 32 9 200 6 3 1 2 2000 10 1 2003 10 2005 6 5 4
More information立命館16_坂下.indd
1669-792008 1 - ' 85- -108 ' Key words 1 2 2003 69 1620082 5 3 1990 1997 4 5 2001 1307 6 7 1 1 1 1996 100 2 1997 71 3 1998 71 4 1999 96 5 2000 95 6 2001 145 7 2002 191 8 2003 174 9 2004 120 10 2005 122
More information立命館人間科学研究No.10
1 77 5 Key words 1 23 3 11417 14310045 20022004 2 2003 20022005 20022004 2 10200511 3 2003 1152003 59 1995 3 32003 19932002 20032003 2005 20052005 4 1997 2000521986 2001 42001 3 1981 6 1 7 5 1000248 1632647
More information立命館21_川端先生.indd
21 119-132 2010 ( ) ' Key Words 119 21 2010 7 1962 2001 2001 2007 1982 1988 1997 2007 1997 1998 1863 1880 1 1998 1998 2001 1599 120 121 1599 1695 8 1695 1714 4 1714 1715 5 1715 100 1812 9 1812 1864 2001
More information立命館14_前田.indd
1499-1122007 1 ) ) ) ) ) (1) -- ) ) ) ) ) ) ( ) ) ' ) ) ) ) - 1) 2)' 3) Key words 19811994 1721 99 1420073 100 20012004 2005 2004 2002 33 34 10 1987 45 20002003 2002 1 1 2000 1 1 2001 2 200341 12004 2
More information立命館17_坂下.indd
1793-1052008 1 () -- -- - Key words 1 93 1720088 2 3 2003 15 1996 50 3040 2 3 4050 50 10 1980 1995 1950 1958 1968 1972 94 95 1987 4 4 70 3 3 1 2000 2001 4 1720088 96 2001 2003 2 1978 1990 1997 130 2 3
More information立命館人間科学研究No.10
49 00 7 Key words 980 995 50 0005 90 997 99 990 994 99 99 99990 99 996 988988 994 99 995 995 995 994 984 988 986 997 997 00 995 00 5 7 5 5 999 997 997 998 6 998 999 997 997 998 0040000 994 996 000 00 5
More information立命館19_椎原他.indd
191-132009 1 ( ) ' Key Words 1 11 12007 2007 200520062 201120062 7558 4009 1 1920098 2007 2 2000 028 2005 1999 12 1999 13 1968 2 3 '1992 2007 2001 20052001 1977 2005 2005 2007 21 21 22 461927 3 13 1920098
More information立命館人間科学研究No.10
61 10 1990 Key words 1 102005 11 62 2000 1 1920 10 1892 63 1 1 19 100 1914 100 1 1 20 1 2 102005 11 64 1946 21 4 1947 1949 1947 22 1 3 1956 1959 1958 2 1964 65 2 10 1975 7080 70 2 1 1987 1990 40 1989 1989
More information立命館19_徳田.indd
1991-1022009 1 2 () )--) 28 2827 1 2 Key Words 1 (1721 2000 20012001 20082009 91 1920098 92 20042004 2004 2001 12 2005 20082009 2005 3 1997 200820096 2007 2 20082009 93 20012001 12 2008 2009 19611966 1
More informationBreastfeedin g among Mothers at One Month Postpartum: Structure of Intentions Department of Maternal and Child Health Nursing, Midwifery, School of Nursing, Faculty of Medical Sciences, University of Fukui
More information16_.....E...._.I.v2006
55 1 18 Bull. Nara Univ. Educ., Vol. 55, No.1 (Cult. & Soc.), 2006 165 2002 * 18 Collaboration Between a School Athletic Club and a Community Sports Club A Case Study of SOLESTRELLA NARA 2002 Rie TAKAMURA
More information表1票4.qx4
iii iv v 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 22 23 10 11 24 25 26 27 10 56 28 11 29 30 12 13 14 15 16 17 18 19 2010 2111 22 23 2412 2513 14 31 17 32 18 33 19 34 20 35 21 36 24 37 25 38 2614
More informationAtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(
AtCoder Regular Contest 073 Editorial Kohei Morita(yosupo) 29 4 29 A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(b)-1] == c[0]: print( YES ) else: print( NO ) 1 B:
More informationSOM SOM(Self-Organizing Maps) SOM SOM SOM SOM SOM SOM i
20 SOM Development of Syllabus Vsualization System using Spherical Self-Organizing Maps 1090366 2009 3 5 SOM SOM(Self-Organizing Maps) SOM SOM SOM SOM SOM SOM i Abstract Development of Syllabus Vsualization
More information28 Horizontal angle correction using straight line detection in an equirectangular image
28 Horizontal angle correction using straight line detection in an equirectangular image 1170283 2017 3 1 2 i Abstract Horizontal angle correction using straight line detection in an equirectangular image
More informationNINJAL Research Papers No.3
(NINJAL Research Papers) 3: 143 159 (2012) ISSN: 2186-134X print/2186-1358 online 143 2012.03 i ii iii 2003 2004 Tsunoda forthcoming * 1. clause-linkage marker CLM 2003 2004 Tsunoda forthcoming 2 3 CLM
More information橡最終原稿.PDF
GIS Simulation analysis of disseminate of disaster information using GIS * ** *** Toshitaka KATADAJunsaku ASADA and Noriyuki KUWASAWA GIS GIS AbstractWe have developed the simulation model expressing the
More informationo 2o 3o 3 1. I o 3. 1o 2o 31. I 3o PDF Adobe Reader 4o 2 1o I 2o 3o 4o 5o 6o 7o 2197/ o 1o 1 1o
78 2 78... 2 22201011... 4... 9... 7... 29 1 1214 2 7 1 8 2 2 3 1 2 1o 2o 3o 3 1. I 1124 4o 3. 1o 2o 31. I 3o PDF Adobe Reader 4o 2 1o 72 1. I 2o 3o 4o 5o 6o 7o 2197/6 9. 9 8o 1o 1 1o 2o / 3o 4o 5o 6o
More informationWeb 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
More informationIT,, i
22 Retrieval support system using bookmarks that are shared in an organization 1110250 2011 3 17 IT,, i Abstract Retrieval support system using bookmarks that are shared in an organization Yoshihiko Komaki
More information社会学部紀要 114号☆/22.松村
March 2012 1 1 1 2005 : 261 1 100 2 22 15.1 41.8 10.3 100 3 2008 : 282 23 34 70 3 114 30 4 1 2 1 2 2 1 1998 1999 2004 N 3 4 7 9 3 100 1970 March 2012 15900 42 10 15000 4 K 40 2 2 2 3 5 100 DVD 6 http :
More informationWeb Web ID Web 16 Web Web i
24 Web Proposal of Web Application Password Operations Management System 1130343 2013 3 1 Web Web ID Web 16 Web Web i Abstract Proposal of Web Application Password Operations Management System Tatsuro
More information04長谷川英伸_様.indd
20 2013 pp. 37 52 1 Robinson, E. A. G. 2013 10 16 37 1 2 3 3 2 1 Robinson, E. A. G. (1931) Hobson, J. A. (1909) 3 Marshall, A. (1890) 4 Steindl, J. (1947) 5 Robinson, E. A. G. Robinson, E. A. G. 6 Robinson,
More informationKyushu Communication Studies 第2号
Kyushu Communication Studies. 2004. 2:1-11 2004 How College Students Use and Perceive Pictographs in Cell Phone E-mail Messages IGARASHI Noriko (Niigata University of Health and Welfare) ITOI Emi (Bunkyo
More information