The puzzle goes like this: Essentially, each row and column of a rectangular bitmap is annotated with the respective lengths of its distinct strings of occupied cells. The person who solves the puzzle must complete the bitmap given only these lengths.
For the example above, the problem can be stated as the two lists [[3],[2,1],[3,2],[2,2],[6],[1,5],[6],[1],[2]] and [[1,2],[3,1],[1,5],[7,1],[5],[3],[4],[3]] which give the "solid" lengths of the rows and columns, top-to-bottom and left-to-right, respectively. Published puzzles are larger than this example, e.g. 25×20, and apparently always have unique solutions.
한국에서는 네모네모로직이라는 이름으로 더 알려진 노노그램을 푸는 문제.
노노그램은 숫자가 있는 줄에 숫자만큼 칸을 칠해 그림을 그려내는 퀴즈다.
숫자가 둘 이상이라면 최소 한 칸 이상 떨어져 있어야 한다.
왼쪽 그림은 오른쪽 그림과 같은 답이 나온다.
열의 힌트가 없어 두 가지 경우가 나왔지만 노노그램은 원래 하나의 답만을 가진다.
왼쪽 그림과 같은 문제가 주어졌다면 오른쪽 두 그림과 같은 답이 나온다.
글로 설명하는 것보다 간단한 문제를 직접 하나 풀어보는 것이 빠를 것 같다.
노노그램은 NP 완전 문제로도 유명하다. NP문제의 특성상 풀어내기가 어렵고, 오랜 시간이 소요 될 수 있다.
풀기 위한 많은 알고리즘이 있지만 일단 풀어내는 데에 의의를 두고 사람이 푸는 것과 같은 간단한 방법으로 풀어보았다.
먼저 노노그램의 몇 가지 특징에 대해 생각해보자.
첫 번째, '무조건 칠해지는 부분'이 있다.
왼쪽 문제에서 나올 수 있는 경우의 수는 세가지.
그 경우의 수들의 공통된 부분은 아래 회색으로 칠해진 부분이다.
그림과 같이 힌트로 만들어지는 경우의 수들은 공통된 부분을 가진다.
칠한 부분을 이용하면 다른 방향(행->열, 열->행) 힌트로 얻는 경우의 수를 극단적으로 줄여 나갈 수 있다.
'무조건 칠해지는 부분'은 힌트 숫자나 갯수에 따라 존재하지 않을 수도 있지만 문제에 따라서는 이 방법의 반복만으로 답을 얻을 수 있다.
두 번째, 일부분이 칠해지면 '칠해지지 않는' 부분도 알 수 있다.
노노그램은 특성상 힌트의 숫자들이 이어져 있어야 한다. 일부가 칠해지면 나머지 힌트를 통해 '칠해지지 않는' 부분도 알 수 있게 된다.
왼쪽 위 문제로부터 진행한 결과.
초록색 부분은 '칠해질 수도 있는' 범위다.
그림을 보면 쉽게 알 수 있듯 일부가 칠해짐으로써 나머지 힌트를 통해 '칠해지지 않는' 범위도 알 수 있게 된다.
'칠해지지 않는' 범위를 알게 됨으로써 힌트로 만들 수 있는 경우의 수가 줄어들고,
줄어든 경우의 수의 공통된 부분을 칠해 다른 부분의 힌트를 만들어 냄으로써 문제를 쉽게 풀 수 있다.
위 특징을 바탕으로 풀면 아래와 같다.
4번 과정에서 1행 두 곳이 칠해지지 않았지만 칠하는 것이 맞다.
확정된 값과 다른 경우의 수들을 제외하고 공통된 부분을 칠하기 때문이다.
수정하고 싶지만 그림 파일을 지워버렸다...
이 알고리즘을 다음 글에서 스칼라 코드로 구현해 본다.
'Scala > Scala Ninety-Nine Problems' 카테고리의 다른 글
| P98. Scala로 풀어본 Nonogram(노노그램, 네모네모로직) - 2 (0) | 2017.03.25 |
|---|---|
| P97. Scala로 풀어본 Sudoku(스도쿠) (0) | 2017.03.20 |
| P94. Scala로 만들어본 K-regular simple graph(정규 그래프) (0) | 2017.03.16 |
| P93. Scala로 풀어본 Arithmetic Puzzle (0) | 2017.03.09 |
| P92. Scala로 풀어본 Von Koch's conjection (0) | 2017.03.06 |