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
203 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.
25 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
44 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
i 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
25 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.
Page 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
2 ( ) 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
ron.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
, 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
soturon.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
,,.,.,,.,.,.,.,,.,..,,,, 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
FAX-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
24 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
2007-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
7,, 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
, (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,.,.,.,,,.,..,.,.,,,
23 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
2 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
06_学術.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
![ESD-巻頭言[003-004].indd](/thumbs/41/22693718.jpg "ESD-巻頭言[003-004].indd")
01-加藤 実-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
2
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.
2 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
〈論文〉興行データベースから「古典芸能」の定義を考える
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
駒田朋子.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
24 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
i
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
FAX780CL_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
..,,,, , ( ) 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
DTN 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
第１部 一般的コメント
(( 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
kut-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
II
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
untitled
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
23 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
NotePC 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
第１章 国民年金における無年金
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
1 (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)
- 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) -
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 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
20 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
I? 3 1 3 1.1?................................. 3 1.2?............................... 3 1.3!................................... 3 2 4 2.1........................................ 4 2.2.......................................
,,,,., 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
ISSN 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
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
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,
立命館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
立命館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
1996 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
立命館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
立命館人間科学研究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
立命館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
立命館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
立命館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
立命館人間科学研究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
立命館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
立命館人間科学研究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
立命館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
Breastfeedin 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
16_.....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
表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
AtCoder 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) A: Shiritori if python3 a, b, c = input().split() if a[len(a)-1] == b[0] and b[len(](/thumbs/104/161880166.jpg "AtCoder 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:
SOM 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
28 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
NINJAL 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
橡最終原稿.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
o 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
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
IT,, 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
社会学部紀要 １１４号☆／２２．松村
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 :
Web 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
04長谷川英伸_様.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,
Kyushu Communication Studies 第２号
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