Nonogram Puzzle에 관한 수학적 탐구

Abstract

Nonogram Puzzle은 주위의 수를 기반으로 가운데 표에 색칠을 하여 형상을 만드는 것이다. 이 퍼즐에서는 행과 열을 구분 짓기 때문에 칸이 존재하는데, 한 칸을 결정할 때는 행과 열의 구분이 없다는 것을 증명하고, 이를 이용하여 여러 가지 풀이 기법을 이끌어낼 것이다. 풀이 기법에서 공통적으로 사용된 발상의 방식을 따 그것을 일반화한 정리를 통해, 결정 가능한 줄의 비율을 황금비와 관련지어 쓸 것이다. 중복해란 단서에 의해 무모순적으로 결정될 수 있는 모든 칸의 상태가 서로 다른 것이 두 개 이상 존재하는 경우이다. [eqn: n times n] 퍼즐에서 중복해인 퍼즐의 개수와 그 비율을 어림해 볼 것이다.

Ⅰ. 서 론

Nonogram Puzzle(이하 노노그램)은 일반적으로는 주위에 있는 수들을 단서로 하여 가운데의 흑백 그림을 채워 나가는 퍼즐이다. 이 퍼즐은 한 행 또는 한 열에 주어진 연속된 수들이 그 행 또는 열의 색칠을 좌우한다. [1] 다음과 같은 예가 있을 수 있다. 그림 1은 맞추기 전의 퍼즐이고, 그림 2는 완성된 퍼즐이다.

영미권에서는 Nonogram 이외에도 Hanjie, Griddlers, Picross, Pic-a-Pix 등 이 퍼즐을 부르는 이름은 다양하다. 대한민국에서는 주로 '네모네모 로직' 혹은 '로직'이라는 이름으로 자주 불린다. 하지만 대한민국에서의 정식 명칭이 확실하지 않으므로 부득이하게 영미권 정식 용어인 Nonogram을 사용하기로 한다.

		2	2	5	1	2
	2
1	1
1	1
	3
	3
		그림 1. 풀기 전의 노노그램

		2	2	5	1	2
	2
1	1
1	1
	3
	3
		그림 2. 풀고 난 후의 노노그램

그림 2의 각 열을 보면, 각 수에 대응되는 색칠이 존재함을 알 수 있다. 5라고 적힌 열에는 다섯 칸이 모두 색칠되어 있고, 2라고 적힌 열에는 두 칸이 색칠되어 있음을 알 수 있다. 또한 2행을 주목하면, 1 1이라고 적힌 행에는 두 칸이 색칠되어 있으나, 한 칸과 한 칸 사이에 간격이 있음을 알 수 있다.

위에서 노노그램의 일반적인 정의를 언급했는데, 그림 3과 같은 아류작도 존재하기 때문이다. 이것을 컬러 노노그램이라고 하는데, [2] 규칙은 비슷하지만 다른 색 사이에는 빈 칸이 없을 수도 있다는 것이 일반적인 노노그램과 다른 점이다. 우리가 다룰 것은 흑백의 것이다. 첨언하자면, 다양한 색이 있는 것이 풀기 더 어려울 것 같지만, 실제로는 그렇지 않다. 특정 색이 있을 수 있는 구간이 제한되어 있기 때문이다. 이는 흑백의 것을 색의 수만큼 푸는 것과 크게 다르지 않다.

							1
					6	6	4	6	7	5	3
			4	6	2	2	2	2	1	1	2	5
	3	3
	5	5
	4	6
4	4	1
4	4	1
3	3	2
	1	4
	2	2
		3
		1									l
			그림 3. 컬러 노노그램

우리는 이러한 노노그램의 풀이 기법과 완성되지 않은 노노그램의 중복해 판별에 대해서 생각할 것이다.

Ⅱ. 재료 및 방법

1. 노노그램에서의 용어 정의

논문의 가독성을 위하여 용어는 최소한으로 자연스럽게 정의하여 쉽게 받아들일 수 있도록 한다. 퍼즐을 익히 잘 아는, 주위의 수가 적혀 있는 우리가 주요하게 풀어야 할 것으로 정의한다. 여기서 주위의 수를 단서라고 한다. 행은 퍼즐의 가로 줄과 그 줄의 단서, 열은 마찬가지로 세로 줄과 그 줄의 단서이다.

칸은 어떤 한 행과 한 열에 공통적으로 속한 부분이며, 우리는 퍼즐을 풀 때 이 부분을 색칠하거나, 어떻게 해도 칸이 색칠되지 않음을 증명할 수 있다. 보통 칸이 색칠되지 않음이 증명되면 다른 곳에 도움이 되도록 X로 표시하는 것이 일반적이다. 여기에서도 보통의 표기를 따라, 그러한 칸을 X로 표시하기로 한다. 칸이 색칠된 것을 채워진다고 하고, 칸이 어떻게든 색칠되지 않음이 밝혀졌다면 비워진다고 한다.

이 두 가지에 해당하지 않고 현재의 단서로는 해결할 수 없는 칸도 존재하는데, 그런 칸은 모른다고 한다. 모르는 칸은 채워지거나 비워질 수 있는데 이렇게 하는 것을 결정한다고 한다. 칸의 채워짐, 비워짐, 모름 여부는 상태라고 할 수 있겠다.

모든 칸을 모순 없이 결정했다면 퍼즐을 풀었다고 할 수 있다. 또한 논리적 무모순이란 말은 조금 확장하여, 현재는 결정되지 않았고 이후에 결정될 칸의 상태까지 고려해서 모순이 없는 것을 그렇게 이르기로 한다.

또한 퍼즐을 푸는 데는 단서가 중요하므로, 한 줄의 단서의 [eqn: k]번째 수를 [eqn: bold a _{k} it]로 표시하기로 한다. 또한 [eqn: bold sum _{k=1}^{n} {bold a_{k} it}it]라는 표현을 단서 [eqn: n]개를 모두 더한 값으로 정의한다. 단서의 개수를 알 필요가 없고, 혼동이 없으면 이를 간단히 [eqn: bold sum`{bold a_{k} it} it]로 표시하기로 한다.

2. 노노그램 풀이 기법과 중복해 판별

풀이 기법에 관해서는 정의된 용어와 수학적 고찰을 통해 여러 가지 경우의 풀이 기법을 증명하고, 이를 통해 일반화된 풀이 기법을 증명한다. 중복해에 관해서는 그와 밀접한 관련이 있는 퍼즐들을 보이고, 퍼즐 하나뿐 아니라 그 칸에 있을 수 있는 총체적인 퍼즐들에 관해 생각할 것이다.

Ⅲ. 결과 및 고찰

1. 풀이 기법

이 절에서는 몇몇 정리에 풀이 기법이라는 말이 있다. 여기서 풀이 기법은 정리를 사용하여 퍼즐의 하나 이상의 칸을 바로 결정할 수 있는 것을 일러 말한다.

[eqn: n times m] 퍼즐은 칸이 [eqn: nm]개이므로 [eqn: nm]번 결정하면 풀 수 있다. 여기서 생각해 볼 수 있는 방법은, 한꺼번에 여러 개를 생각하면 복잡하므로 그런 식의 접근을 지양하고, 한 번에 한 칸만을 결정하는 것이다. 한 칸은 그 정의에서 속한 하나의 열과 속한 하나의 행의 영향을 받는다. 하지만, 다음 정리에 의해, 한 칸을 결정할 때는 그를 포함하는 한 열과 한 행을 동시에 생각할 필요가 없다는 것을 알 수 있다:

정리 1. (행-열 동등성 정리) 한 칸을 논리적 무모순을 갖고 결정할 충분조건은 한 열 또는 한 행에서의 논리적 무모순이다.

증명. 한 칸이 한 행에 의해 논리적 무모순을 갖고 결정되었다고 하자. 이 칸을 한 열에 의해 반대 쪽으로 다시 결정하면, 한 행의 단서들에 모순이 되는 칸이 존재하게 된다. 이는 퍼즐의 풀이에 모순이다. 따라서 한 열에 의해서 반대쪽으로 다시 결정할 수 없으므로, 주어진 정리를 얻는다. 한 열에 의해 논리적 무모순을 갖고 결정되었을 때에도 마찬가지 방법으로 증명한다. □

상태가 채워짐이라면 비워짐으로, 비워짐이라면 채워짐으로

행-열 동등성 정리는 정리의 이름 그대로 행과 열의 구분을 무의미하게 만든다. 이런 맥락에서, 열 또는 행을 줄이라 부르는 것은 적절하게 느껴진다. 여기서 줄이 [eqn: k]개의 칸으로 구성되었다면 [eqn: bold k it]-줄이라고 부르기로 하자. 이제 다음의 정리를 생각한다.

정리 2. 한 줄에 논리적 무모순을 갖고 채워진 칸의 개수는 단서의 합보다 클 수 없다.

증명. 한 줄에서의 단서 안의 수의 개수를 [eqn: n]이라고 하자. 여기서 임의의 자연수 [eqn: m le n]에 대해 [eqn: a_m]에 해당하는 부분에 채워진 칸은 [eqn: a_m]개를 넘을 수 없다. 따라서 [eqn: sum_{k=1}^{n}a_{k} ge] (채워진 칸의 개수)가 성립한다. □

정리 2와, 어떤 줄의 단서 안의 모든 수들의 합은 결국 그 줄에 채워진 칸의 개수와 같다는 자명한 점에 의해 다음의 풀이 기법을 얻을 수 있다.

풀이 기법 1. 어떤 논리적 무모순을 갖는 줄의 단서 안의 모든 수들의 합을 [eqn: s], 채워진 칸의 수를 [eqn: f], 모르는 칸의 수를 [eqn: u]라 할 때

1) [eqn: s=f]라면 모르는 칸을 모두 비우기로 결정한다.

2) [eqn: s=f+u]라면 모르는 칸을 모두 채우기로 결정한다.

증명. 1) 정리 2에서 [eqn: s=f]라면 [eqn: sum a_{k} = s ge f]에 의해 모르는 칸이 모두 비워져야 한다.

2) 모르는 칸 중 하나를 비우기로 결정하자. 나머지 칸을 모두 채워서 결정한다고 해도 [eqn: s>f]이다. 이는 모순이다. □

풀이 기법 1에서 [eqn: k]-줄에서 [eqn: a_{1} = 0]이고 [eqn: a_{2}]가 존재하지 않으면 모든 칸을 비우고, [eqn: k]-줄에서 [eqn: a_{1}=k]이면 모든 칸을 채운다는 것도 알 수 있다.

이제, 단서의 수들의 최솟값과 최댓값에 주목하자. 단서는 tuple이므로 그 안의 최솟값과 최댓값이 존재한다. 결국에는 연속된 칸의 채워짐과 비워짐의 상태가 그 단서 안의 수와 일치해야 하므로, 다음과 같은 정리를 이끌어낼 수 있다.

정리 3. 논리적 무모순이 없는 줄에서 연속되게 채워진 칸의 개수는 결국에는 단서 안의 수들의 최솟값 [eqn: m]보다 작을 수 없고, 최댓값 [eqn: M]보다 클 수 없다.

증명. 모르는 칸의 개수를 [eqn: u], 어떤 칸으로부터 연속되게 채워진 칸의 개수를 [eqn: c]라 하자. [eqn: u=0]이라면 연속된 칸의 개수에 일치하는 단서가 있어야 한다. 그런데 [eqn: c < m]이라면 [eqn: m le a_{k}]이므로 [eqn: c < a_{k}]에서 칸의 개수가 절대 단서와 일치할 수 없다. 이는 모순이므로 [eqn: c ge m]이다. 마찬가지로 하여 [eqn: m LEQ c LEQ M]을 이끌어낼 수 있다. □

여기서 단서 안의 각각의 수들의 최솟값에 관한 풀이 기법을 이끌어낼 수 있다.

풀이 기법 2. (최솟값 채우기) 어떤 논리적 무모순을 갖는 [eqn: k]-줄에서 [eqn: a_k] 중 최솟값을 [eqn: m]이라 한다. 어떤 줄의 [eqn: n]번째 칸이 채워져 있을 때

1) [eqn: (n-1)]번째 칸이 비워져 있으면 [eqn: n]번째 칸부터 [eqn: (n+m-1)]번째 칸까지 모두 채운다.

2) [eqn: (n+1)]번째 칸이 비워져 있으면 [eqn: (n-m+1)]번째 칸부터 [eqn: n]번째 칸까지 모두 채운다.

단, [eqn: 0]번째 칸과 [eqn: (k+1)]번째 칸은 비워져 있는 것으로 간주한다.

증명. 2)는 1)과 같이 증명하면 되므로 1)만 증명한다.

1) [eqn: a_k] 중 최솟값을 [eqn: m]이라 했으므로, 정리 3에 의해 [eqn: n]번째 칸이 채워져 있으면 결국에는 [eqn: n]번째 칸과 연속되게 채워진 칸이 [eqn: m]보다 작을 수 없다. 여기서 [eqn: (n+1)]번째 칸을 비우면, [eqn: n]번째 칸에서 연속된 칸들이 정리 3에 모순이므로, [eqn: (n+1)]번째 칸이 채워져야 한다. 이와 같은 방법을 [eqn: m]번 반복하여 주어진 풀이 기법을 얻는다. □

풀이 기법 3. (최솟값 비우기) 어떤 논리적 무모순을 갖는 [eqn: k]-줄에서 [eqn: a_{k}] 중 최솟값을 [eqn: m]이라 한다. 어떤 [eqn: k le m]이 존재하여 [eqn: n]번째 칸과 [eqn: (n+k)]번째 칸이 비워져 있으면 [eqn: (n+1)]번째 칸부터 [eqn: (n+k)]번째 칸까지를 모두 비운다.

단, [eqn: 0]번째 칸과 [eqn: (k+1)]번째 칸은 비워져 있는 것으로 간주한다.

증명. [eqn: (n+1)]번째 칸이 채워진다고 가정하면, 풀이 기법 2에서 [eqn: n := n + 1]일 때 1)에서 [eqn: (n+1)]번째 칸부터 [eqn: (n+m)]번째 칸까지 모두 채워져야 하는데, [eqn: (n+k)]번째 칸이 비워져 있으므로 이는 모순이다. 따라서 [eqn: (n+1)]번째 칸을 비운다. 이와 같은 방법을 [eqn: (k-1)]번 반복하여 주어진 풀이 기법을 얻는다. □

이러한 방식으로 단서와 그 최대·최소, 단서의 합 등을 이용하여 계속해서 풀이 기법을 만들어낼 수 있다. 그러나 이런 식으로 풀이 기법을 만드는 것은 힘든 일이기도 할뿐더러 지루하다.

이전의 증명에서 귀류법을 썼다는 것을 주의 깊게 보자. 한 줄에서 원하는 것과 반대로 결정하여 모순을 이끌어내었다. 그러므로 애초에 한 줄에서 모순이 생기지 않게 결정할 수 있다면 위의 정리를 모두 포함하는 어떠한 정리를 찾을 수 있을 것이다. 그리고 그것이 바로 아래의 정리이다.

정리 4. 어떤 줄에서 무모순적으로 결정된 줄에 모순되지 않게 모든 칸을 결정할 수 있는 모든 방법 중에서 일관된 상태를 가진 칸을 그 상태로 결정해도 무모순성을 유지한다.

증명. 결론을 부정하여, 임의의 칸을 그와 반대로 결정하면 모순을 갖게 됨을 보이면 된다. 일관된 상태를 가진 칸이므로 한 칸이라도 반대로 가정하면 모순되지 않게 모든 칸을 결정할 수 있는 모든 방법에 모두 들어맞지 않으므로 모순된 줄이라는 결론을 얻는다. □

정리 4 역시 귀류법으로 증명하였다. 이 정리는 실제로 시행하려면 줄의 수가 충분히 줄었을 때나 가능하다. 그래서 이로부터 이전 정리들을 이끌어내어 풀이할 때 편하게 사용할 수 있도록 한 것이다. 이에 반해, 다음 정리는 이와는 성격이 전혀 다른 확률론적 풀이로, 실제의 풀이에서는 사용하기 힘드나 위의 모든 방법이 적용되지 않을 때 최후의 방법으로 사용해 볼 만하다.

정리 5. (가정법) 한 칸을 결정하고 풀이 기법을 적용시켜 모순을 발견하면 결정된 칸의 반대로 결정해야 무모순성을 유지한다.

2. 중복해 판별

노노그램의 목적은 퍼즐을 풀어 어떤 형상이 나오게 하는 것이므로, 만약 어떠한 단서가 두 개 이상의 최종 그림을 포함한다면 그 퍼즐은 아무런 의미가 없다. 이러한 것을 중복해라고 하기로 하자. 엄밀히 말하면 중복해는 단서에 의해 무모순적으로 결정될 수 있는 모든 칸의 상태가 서로 다른 것이 두 개 이상 존재하는 경우이다. 중복해가 있는 퍼즐을 푸는 것은 아무런 의미가 없다. 따라서 중복해를 판단하는 것은 매우 중요하다. 가정법에 의존하는 다음의 강력한 정리는 중복해를 조금 더 쉽게 이해하는 데 도움이 된다.

정리 6. (퍼즐 풀이-중복해 판별 동등성 정리) 단서에 의해 모든 칸을 결정할 수 있으면 그 해는 유일하다.

증명. 단서에 의해 모든 칸을 결정할 수 있음은 어떤 칸을 반대로 결정하면 단서에 모순이 됨을 뜻한다. 가정법에 의해 어떤 칸을 반대로 결정했을 때 모순을 발견하면 반대로 결정된 칸을 반대로 결정해야 무모순성을 유지하게 된다. 이는 원래의 상태가 반드시 유지되어야 한다는 의미이다. 따라서 그 해가 유일할 수밖에 없다. □

이 정리는 퍼즐의 대부분인 결정 가능한 퍼즐을 모두 유일해로 만들어줌으로써, 퍼즐을 푸는 것이 실제로 퍼즐의 중복해를 구하는 과정과 다를 게 없다는 것을 보여준다.

중복해 판별을 총체적 관점에서 보기로 하자. 행-열 동등성 정리에서 열과 행의 구분이 없음을 보였지만, 총체적으로는 [eqn: n]-줄과 [eqn: m]-줄을 따로 계산해야 하므로 이러한 불편함을 줄이기 위해서 이 절에서는 [eqn: n times n] 퍼즐만 고려한다.

[eqn: n times n] 퍼즐의 총 개수는 몇 개인가? 단서가 [eqn: m]개의 중복해를 가진다면 그 퍼즐은 [eqn: m]개로 세는 것이 합리적일 것 같다. 한 개의 완성된 퍼즐은 하나의 단서 묶음에 대응되므로, [eqn: n times n] 퍼즐의 전체 개수는 단서에 상관없이 [eqn: 2^{n^{2}}]개다.

임의의 퍼즐을 푸는 것은 NP-난해(NP-hard)이다. [1] 여기서 유일해가 존재함을 판별하려면 그 퍼즐을 풀어야 하므로 중복해 판별도 결국엔 NP-난해일 수밖에 없다. 따라서 가장 단순하게 생각할 수 있는 지수 시간 방법론(exponential-time algorithm)은 각각의 칸을 채우거나 비우는 것으로 가정하여 확인한 후, 개수를 확인하는 것으로 O([eqn: NM cdot 2^{NM}]) 시간이 걸린다.

여기서 한 칸을 결정하는 데 걸리는 시간인 O([eqn: max(N, M) cdot 2^{max(N, M)}]) 시간을 고려하자. 우리의 문제는 결정 문제(decision problem)이지 개수를 구해야 하는 문제가 아니므로, 모든 칸을 단서로 결정할 수 있다면, 정리 6에 의해 이 결정 시간은 O([eqn: NM cdot max(N, M) cdot 2^{max(N, M)}]) 시간밖에 걸리지 않는다. 이는 이 문제를 푸는 것이 NP-난해라는 것을 감안했을 때 상당히 빠른 복잡도이다. 따라서 이 방법이 결정론적이기 위해 증명되어야 할 명제는 정리 6의 역인 "해가 유일하면 단서에 의해 모든 칸을 결정할 수 있다" [eqn: LRARROW] "단서에 의해서만 모든 칸을 결정할 수 없으면 해가 유일하지 않다"가 성립해야 한다. 불행하게도 이것은 참이 아니다:

						1			1
						1	1	1	1
					1	1	1	1	1	1
				8	1	1	1	1	1	1	8
			8
		1	1
1	1	1	1			➀	➁	➁	➀
		1	1
1	1	1	1			➂	➃	➄	➅
	1	2	1			➆	➇	➈	➉
		1	1
			8
				그림 5. 웃는 모양

그림 5를 보자. 단서에 의해 결정론적이 될 수 있는 것은 모두 색칠하거나 X 표시를 함으로써 표기해 두었다. 3열과 6열에 정리 4를 적용시키면 ➀ 부분이 채워짐을 알 수 있고, 이후 3행에서 풀이 기법 1에 의해 ➁ 부분이 비워짐을 알 수 있다. 하지만 가정법을 사용하지 않으면 ➂부터 ➉까지의 부분이 채워지는지 비워지는지를 알 길은 없다. 만약 정리 6의 역이 참이라면 이 퍼즐은 유일해를 갖지 않을 것이다. 하지만 여기서 가정법을 활용하여 ➂을 비움으로 가정하면 ➆이 채워지고 ➇ 또한 채워져 ➃가 비게 되어, 5행의 단서에 모순이므로, ➂이 채워지고, ➆이 비워지고, ➈가 채워지고, ➄와 ➃가 비워지고, ➅이 채워지고, ➉이 비워지고, ➇이 채워지게 되어 모든 칸을 결정할 수 있으므로 해가 유일하다.

따라서 이러한 접근을 결정론적으로 하기 위해서는 모든 반례들이 필요하다. 하지만 만약 퍼즐의 칸이 하나 이상 결정 가능하다면 자명하게 더 작은 퍼즐로 줄여나가며 퍼즐을 풀 수 있기 때문에, 단서로는 모든 칸을 결정할 수 없으면서 유일해를 갖는 퍼즐만을 고려하면 되므로, 이는 그리 많지 않다고 추측할 수 있다.

이제 이렇게 되는 모든 퍼즐을 고려했을 때, [eqn: 2 times 2], [eqn: 3 times 3] 등의 퍼즐은 그러한 경우가 없다는 것을 쉽게 보일 수 있고, [eqn: 4 times 2]에서는 딱 두 개(그림 5에서 단서에 의해 결정된 부분을 제외하고 그린 것과 그 상하 반전)를 제외하고는 없음을 보일 수 있다. 여기서 [eqn: 4 times 4] 퍼즐의 반례는 많아야 [eqn: 16]개라고 추측했지만, 찾아본 결과 회전이나 대칭을 중복으로 세어 총 [eqn: 680]개가 있었다. 회전이나 대칭을 하나로 세어도 최소한 [eqn: 680 / 8 = 85]개 이상 있을 수 있다. [eqn: 5 times 5]에서는 [eqn: 1056]개의 반례가 있었다. [eqn: n times n] 퍼즐에서 이러한 반례 퍼즐의 개수를 [eqn: c(n)]이라 표기하자. 그렇다면 반례 퍼즐이 차지하는 비율은 [eqn: p(n):= {c(n)} over {2 ^{n ^{2}}}]이 되겠다.

컴퓨터로 계산하였다. 주목할 만한 부분: 동등성을 확인할 때 O([eqn: 1])의 복잡도(complexity)를 보장하기 위해 미리 계산하는 방법을 사용하였다. 정수 s에 대해 s&-s는 마지막의 [eqn: 0]이 아닌 bit를 계산하는 코드로 유명하다. 이 코드를 개선하여 O([eqn: N])임에도 불구하고 직접 계산하는 것보다 2배 정도의 속도로 계산하였다.

정리 7. [eqn: n]-줄에서 단서가 [eqn: 1]개일 때 [eqn: {a _{1}} over {n} > {1} over {2}]라면 단서만으로 가운데의 [eqn: 2a_{1}-n]칸이 채워진다.

증명. 탐욕적 방법론(Greedy Algorithm)의 원리를 이용한다. 단서가 [eqn: 1]개이므로, 맨 왼쪽에서부터 채울 때와 맨 오른쪽에서 채울 때, 사이의 부분이 겹치면 그 부분을 결정할 수 있다. 이 때 겹칠 조건은 양쪽의 [eqn: a_{1}] 두 개가 [eqn: n]보다 크면 되므로(그림 6을 참고하자) [eqn: 2a _{1} >n`` LRARROW ``{a _{1}}over {n} > {1} over {2}]이면 되고, 개수는 [eqn: 2a_{1}-n]이면 된다. □

탐욕적 방법론이란 부분문제로 나눌 수 있는 문제에 대해 모든 부분문제에서 최적의 해를 채택하는 것을 말한다. 여기서는 단순히 앞 혹은 뒤에서부터 순서대로 채워서 결정한다는 의미로 사용하였다.

1
2
3
	그림 6. 겹치는 부분

이 정리를 기반으로 하여 다음의 정리를 이끌어낼 수 있다.

정리 8. [eqn: m]-줄에서 [eqn: sum _{k=1} ^{n} `a _{k} =:s]라 할 때

1) ([eqn: n]에 관해) [eqn: s>(m+2)-{m+2}over{n+1}-n]이거나

2) ([eqn: n]에 관련 없이) [eqn: s > (root{m+2}-1)^{2}]이면

그 줄은 한 칸 이상 결정 가능하다.

증명. [eqn: s := sum_{k=1}^{n}{a_k}]라 두고 탐욕적 방법론을 이용한다. 모두 한 쪽으로 되었다면 단서에 의한 칸의 길이는 [eqn: s+(n-1)] 칸이 되고, 어떤 단서의 수 [eqn: M]에 대해 나머지의 것들은 [eqn: (s+n-1)-M]만큼의 칸을 쓰는 셈이 되므로 [eqn: M]이 차지할 수 있는 칸은 [eqn: m-(s+n-1)+M]만큼이다. 이것이 결정되려면, 정리 7에 의해 어떤 단서의 수 하나만에 대해서라도 다음 식을 만족하면 된다.

[eqn: {M} over {m - (s + n - 1)+M} > {1} over {2}]

이 식은 [eqn: {M+s+n-1} over {m} >1]과 동치인데, 좌변이 [eqn: M]에 대한 증가함수이다. [eqn: M:=max(a_{k})]로 두면, [eqn: a _{k} >M]을 만족시키는 임의의 [eqn: k]가 존재하지 않으므로, 모든 경우를 생각할 수 있을 것이다. 이러한 [eqn: M]들 중에서 가장 작은 [eqn: M]은 산술기하평균에 의해 [eqn: M:= rm ceil it LEFT ( {s} over {n} RIGHT )]으로 두는 것이다. [eqn: rm ceil it left({s} over {n} right) ge {s} over {n}]이므로 간단히 [eqn: M:={s}over{n}]으로 두어도 문제가 없다. 여기서 다음과 같은 식을 만족하면 그 줄은 한 칸 이상 결정 가능하다는 것을 곧바로 알 수 있다.

[eqn: rm ceil it (x)]는 [eqn: x]보다 작지 않은 정수 중 가장 작은 정수이다.

[eqn: {{s}over{n}+n+s-1}over{m}>1] [eqn: cdots cdots cdots] ➀

이제 식을 [eqn: s]에 관한 일차부등식으로 보면, [eqn: left({1+{1}over{n}}right)s>m-n+1]에서 곧바로 1)을 얻는다. ➀에서 [eqn: n]이 포함된 앞 두 항을 묶어 산술기하평균을 적용하면

[eqn: {left ( {s} over {n} + n right) + s - 1} over {m} ge {2 root{s} + s - 1} over {m} = {(root{s}+1)^{2} - 2}over{m}]

이 성립하므로 [eqn: {(root{s} +1)^{2} - 2}over {m} >1]인 [eqn: s]는 우리가 원하는 것이다.  [eqn: m >0]임은 당연하므로

[eqn: ( sqrt {s} +1) ^{2} >m+2>0`` RARROW `` sqrt {s} +1> sqrt {m+2} >0]

에서 2)를 얻을 수 있다. □

이 정리의 2)에 의해서 [eqn: n times n] 퍼즐의 열 또는 행의 모든 단서의 수들의 합이 [eqn: n LEFT lfloor ( sqrt {n+2} -1) ^{2} RIGHT rfloor]을 넘는다면 모든 줄이 결정 불가능하지 않다. 앞서 살펴본 [eqn: 4 times 4]의 경우에는 [eqn: 4 left lfloor (root{6} - 1)^{2} right rfloor = 8]칸보다 많은 칸이 채워져 있으면 되므로, [eqn: sum _{k=9} ^{16} {pmatrix{16#k}} =26333]개의 퍼즐은 최소한 결정 가능하다.

이 방법으로의 비율은 [eqn: t:=n left lfloor (sqrt{n+2}-1)^{2} right rfloor+1]일 때 [eqn: p(n)<1- {1}over{2^{n^{2}}}sum _{k=t} ^{n ^{2}} {pmatrix{n^2#k}}]이다. [eqn: n]이 커지면 커질수록 늘어나지만, 실제적인 계산은 O([eqn: n^{3}]) 안에 행해지므로 계산하기에는 만족스러운 결과라고 할 수 있다.

하지만 이러한 계산은 컴퓨터의 이용을 필요로 한다. 유한 번의 계산을 통해 어림짐작을 하는 방법은 없을까? 다음 두 정리를 통해 생각해 보자.

저 식이 유한 번 안에 계산 가능하다는 것을 충분히 간단한 식, 곧 [eqn: n] 또는 [eqn: m]에 관계없이 같은 횟수의 초등적 연산이 필요한 식으로 표현되는 것으로 생각했을 때, 임의의 정수 [eqn: m]과 정수 [eqn: n LEQ m]에 대해 [eqn: sum _{k=1} ^{n} {pmatrix{m#k}}]의 값이 간단한 식으로 표현되어야 한다. 하지만 이것을 표현할 충분히 간단한 식은 없을뿐더러, 있다고 해도 계산 횟수가 충분히 많다.

정리 9. [eqn: m]-줄에서 [eqn: sum_{k=1}^{n}a_{k} = 0]이거나 [eqn: sum _{k=1}^{n} a_{k} + n = m + 1]이라면 모든 칸이 결정 가능하다. 역도 성립한다.

증명. (개략적인) 정리 8의 접근 방법과 비슷하게 하여 채워지는 칸을 모두 알 수 있고, 남은 칸은 풀이 기법 1을 이용하여 결정할 수 있다. 역은 그 대우를 취하여 정리 8의 접근 방법과 비슷하게 하면 증명할 수 있다.

정리 10. [eqn: m]-줄에서 모든 칸이 결정 가능한 줄의 개수는 [eqn: F _{m} + 1]이다. 여기서 [eqn: F_{m}]은 [eqn: m]번째 피보나치 수이다.

증명. [eqn: sum_{k=1}^{n}`{a_k}=:s]라고 하자. 모든 칸이 결정 가능한 줄은 [eqn: s+n=m+1]이 성립함과 동치이다. 여기서 [eqn: n-1=m-s]이 되어야 한다. [1]

식을 [eqn: n-1]에 관해 정리하는 이유는 그것이 빈 칸의 개수이기 때문이다. 결정 가능하다면 시작 칸과 마지막 칸이 차 있어야 함은 자명하므로, 단서 사이의 개수가 빈 칸의 개수가 된다.

○	○	○	○	○	○	○	○
그림 7. [eqn: m=10], [eqn: n=3], [eqn: s=8]의 예시

빈 칸 [eqn: n-1]개를 넣는 경우의 수를 구하는 문제는 그림 7처럼 겹치는 부분이 [eqn: s]개의 공을 [eqn: n]개로 분할할 때 [eqn: n-1]개의 구분선을 넣는 경우의 수를 구하는 문제와 정확히 같고, 이 경우의 수는 [eqn: {pmatrix{s-1#n-1}}={pmatrix{s-1#m-s}}]이다. 이를 모든 가능한 [eqn: s]들, 즉 [eqn: 0<s LEQ m]인 모든 정수 [eqn: s]들에 대해서 모두 고려해서 더하면 [eqn: sum _{k=1} ^{m}{pmatrix{k-1#m-k}} = sum _{k=0} ^{m-1} {pmatrix{k#(m-1)-k}} =F _{m}]이다. 그런데, 줄 [eqn: bold{0} it]도 항상 모두 빈 칸으로 결정할 수 있으므로 이것을 고려해야 한다. 따라서 이 식에서 [eqn: 1]을 더한 것을 계산하면 우리가 구하고자 하는 값이 나온다. 여기서 곧바로 정리를 얻는다. □

개략적 증명: [eqn: m=1]일 때 [eqn: 1]이고 [eqn: m=2]일 때도 [eqn: 1]이다. 조합의 성질 [eqn: pmatrix{n#k}=pmatrix{n-1#k-1}+pmatrix{n-1#k}]을 이용하여  [eqn: m=u+2]일 때의 값이 [eqn: m=u]일 때의 값과 [eqn: m=u+1]일 때의 값의 합임을 보인다.

[eqn: F _{n} = {varphi ^{n} -(- varphi ) ^{-n}} over {root5}]에서 [eqn: (- varphi ) ^{-n} le varphi ^{-n} =1/ varphi ^{n} <1]이므로 [eqn: F _{n} +1 ge{varphi ^{n}} over {sqrt {5}}]이다. 따라서 [eqn: 1-c(n) GEQ LEFT ( {varphi ^{n}} over {sqrt {5}} RIGHT ) ^{n}]이고 비율은 [eqn: p(n) le1- {1} over {sqrt {5 ^{n}}} LEFT ( {varphi } over {2} RIGHT ) ^{n ^{2}}]이다. 우변이 [eqn: n]에 관계없이 유한 번 계산된다.

Ⅳ. 결 론

1. 칸은 한 행과 열에 공통적으로 속하지만 한 쪽으로 결정해도 된다.

2. 단서에 의해 모든 칸을 결정할 수 있으면 해가 유일하다.

3. [eqn: bold {p(n) le1- {1} over {sqrt {5 ^{n}}} LEFT ( {varphi } over {2} RIGHT ) ^{n ^{2}}} it]이다.

Ⅴ. 참고문헌

[1] 알 수 없음, "Nonogram", Wikipedia, 618321272, 전체, 2014

[2] 알 수 없음, "Pic-a-Pix", Conceptis Logic Puzzles, 알 수 없음, Color Pic-a-Pix, 알 수 없음.