네모로직 알고리즘 - 마땅히 비워야할 셀 구하는 방법, simple spaces

지난 글 2014/01/01 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 – 당연히 채워지는 셀 구하는 공식, simple boxes에 이어서 네모로직(노노그램, nonogram)의 풀이 테크닉을 알아보겠습니다.

이 방법은 네모로직에서 당연히 빈 칸이어야 할 셀을 구하는 방법입니다.

지난 방법에서 당연히 채워지는 셀을 구했습니다(simple boxes technique). 심플박스 테크닉으로 구한 셀을 채우면, 숫자에 따른 candidate가 칠해질 수 있는 범위가 지정됩니다. 그러면 당연히 비어있어야 할 셀도 알 수 있습니다.

순서대로 다시 풀어 설명하면,

1. simple boxes로 셀을 채운다.

2. 채워진 셀에 따라 절대로 그려지지 않을 곳을 표시한다.

그림은 simple spaces 테크닉을 순서대로 적용한 모습입니다. 

그림. simple spaces 예시

그림의 셀에 X표 된 곳이 simple spaces로 구한 space입니다.

원문: http://en.wikipedia.org/wiki/Nonogram#Simple_spaces