네모네모 로직(nonogram) 풀기 - 1

머리를 말랑말랑하게 만들어주는 퍼즐 게임들은 여러가지가 있습니다.  대표적인 것은 스도쿠, 네모네모로직 등이 아닐까 합니다.  오늘 하려는 것은 네모네모로직을 풀어보는 것입니다.  그런데 사람이 풀자고 하는 것은 아니고, 컴퓨터가 네모네모 로직을 푸는 것이죠.

 

 

 

네모네모로직은 영어로는 nonogram이라고 불리며, 위 그림처럼, 모눈종이처럼 칸이 쳐져 있는 곳에 색을 칠해가는 게임입니다.

색을 아무렇게나 칠할 수는 없고, 왼쪽과 위족에 숫자가 있는데, 그 숫자는 연달아 색칠되는 모눈칸의 갯수를 나열한 것입니다. 

 

예를 들어서 3 4 가 써져있다면, 3개를 연달아 색칠한 후에 한개 이상의 빈칸을 둔 이 후에 다시 연달아 4개의 칸을 색칠하는 것입니다.

예를 들어서 10개의 칸이 있다면, 3 4 의 숫자는 다음과 같이 여러 종류로 색을 칠할 수 있습니다.

 

 

■■■□■■■■□□

 

■■■□□■■■■□

■■■□□□■■■■

 

□■■■□■■■■□

 

□■■■□□■■■■

 

□□■■■□■■■■

 

 

네모네모로직을 풀기 위해서는 위의 모든 경우를 대입해봐야 하겠지만, 그러기에는 인간이 할 수 있는 시간적 여유는 없습니다.  그래서 머리를 쓰게 되는데, 위의 모든 경우를 해보면, 반드시 색칠되어야 하는 칸들이 생깁니다.  위의 6가지 경우를 모두 종합해보면 다음과 같은 결론을 얻을 수 있습니다.

 

□□■□□□■■□□

 

즉, 위에처럼 3칸은 반드시 색칠될거라는 것입니다.

 

이것을 공식화해서 칠하는 것도 가능합니다.

 

10개의 칸에 3 4 란 칸을 채운다면, 3+4 = 7 을 계산하고, 총 숫자의 갯수-1만큼을 더합니다. .  총 숫자의 갯수는 2이므로, 7에 1을 더하면 8이 됩니다.  그러면, 8은 3 4를 그리기 위해 꼭 필요한 칸의 갯수가 됩니다.  이 숫자가 총 칸의 갯수와 같다면, 그대로 숫자 나오는대로 칠하면 됩니다.  총 칸수가 10이므로 8과는 2가 차이가 납니다.

 

그러면 2보다 큰 숫자만 생각하면 됩니다.

첫번째 3이란 숫자는 2보다 크죠.  차이는 1입니다.  그러면 3칸 중 앞의 두칸을 비우고 하나를 그립니다. 그리고 그 다음칸 한칸을 빈칸으로 둡니다.

 

□□■□▨▨▨▨▨▨

 

 

그 다음 숫자 4도 2보다 큽니다.  그러면 앞의 두 칸을 비우고, 2개를 그립니다.

 

□□■□□□■■▨▨

 

그러면 자연스럽게 두칸이 남는다면, 올바르게 칠한 셈이 됩니다.

 

또 다시 예를 들자면, 10칸에 1 2 4 란 숫자가 있습니다.  같은 방법으로 색칠한다면,

 

총 숫자의 합은 7, 숫자의 갯수는 3이므로 꼭 필요한 칸들의 숫자는 9입니다.  여분은 1이네요.

 

1 표시

□□▨▨▨▨▨▨▨▨

 

2 표시

□□□■□▨▨▨▨▨

 

4 표시

□□□■□□■■■▨

 

처음은 이렇게 풀어나가면 됩니다.

 

그러면, 과연 가능한 패턴의 갯수는 얼마일까요?  이것은 수학적 방법으로 찾으면 됩니다.

 

위 방법대로 여분의 갯수를 구한 후에, 그것을 숫자의 갯수+1의 칸에 배분하는 것이면 됩니다.  10칸에 3 4가 있다면, 가능한 패턴의 갯수는 \(_{3}H_{2}\)가 됩니다.  계산해보면, 6가지가 나온다는 것을 알 수 있습니다. 

 

총 칸의 갯수는 n, 숫자의 갯수를 k, 숫자의 합을 s라고 한다면,  필요한 최소 칸수는 \(k+s-1\), 여분의 칸 수는 \(n-k-s+1\), 이 값을 r이라고 한다면, 나올 수 있는 패턴의 갯수는 \(_{k+1}H_{r}\)이 됩니다.