네모로직 알고리즘 - simple spaces를 찾은 이후에 simple boxes하는 방법, forcing

지난 번에 알아본 네모로직(nonogram, 노노그램)의 simple boxes 방법으로 당연히 채워지는 셀을 채웁니다. 긜고 simple spaces로 마땅히 비워야할 셀을 구합니다.

2014/01/01 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 – 당연히 채워지는 셀 구하는 공식, simple boxes

2015/02/18 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - 마땅히 비워야할 셀 구하는 테크닉, simple spaces

Forcing 테크닉은 비워져야할 셀을 구한 다음, 비울 셀과 채울 셀을 찾는 방법입니다.

힌트 숫자 보다 비어있는 셀의 크기가 작으면 당연히 그 셀은 채워질 수 없습니다.

아래 그림을 보면, X표시 된 두 곳을 찾았습니다. 힌트가 3과 2인데, X 사이에 한 칸 밖에 없으므로, 그 칸은 채울 수 없습니다. 그래서 비어있는 칸이 됩니다(파란색 X로 표시). 그 다음 나머지 칸에 관해 simple boxes로 칸을 채웁니다.

그림. forcing 예시

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