네모로직 알고리즘 - 박스로 채우거나 빈 셀로 가정하고 모순을 찾아서 푸는 테크닉, contradiction.

네모로직(노노그램, nonogram) 풀이 테크닉 모순(contradiction)입니다. 셀을 채울지 말지 가정하고, 모순이 생기는지 확인하고 판단하는 테크닉입니다.

이름에서 느껴지듯 난이도 있는 퍼즐에서 사용하는 추론 방법입니다. 앞서 사용했던 간단한 테크닉을 모두 적용하고, 더이상 박스 찾기가 어려울 때 쓸 수 있습니다.

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

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

2015/02/20 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - simple spaces를 찾은 이후에 simple boxes하는 방법, forcing

2015/02/20 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - 채워진 셀로 simple boxes를 구하는 방법, glue.

2015/02/24 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - 채워진 셀 사이를 채울지 말지 결정하는 방법, joining and splitting

2015/02/26 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - 중단점으로 박스 구분하기, punctuating

2015/03/01 - [노트정리/알고리즘 놀이] - 네모로직 알고리즘 - 뭉친 박스에서 비워야할 빈 칸을 찾는 테크닉, mercury.

손으로 풀 때는 연필로 표시했다가 지우개를 써서 표시를 지우거나, 볼펜으로 다시 박스를 확정하면 되겠죠. 프로그래밍한다면 셀 하나하나에 대한 자료구조를 지정해줘야 할 듯합니다. 스도쿠를 풀이할 때는 스도쿠 셀 하나하나에 대해서 클래스로 지정했습니다. 셀 클래스는 불린으로 박스를 채울지 말지 결정할 수 있을듯 합니다. 모순 테크닉 풀이 절차는 스택 자료구조로 풀이가 성공하면 스택은 초기화하고, 모순이 발생하면 스택을 돌아가서 모순이 발생한 가정의 불린 값을 반대값으로 지정하면 될겁니다.

모순 테크닉은 다음 절차를 따라 풀이합니다.

1. 비어있는 셀을 박스로 채운다(또는 빈 셀로 남겨둔다). 이때, 연필로 표시합니다.

2. 위 상태에서 간단한 테크닉을 이용해 문제를 풀어갑니다.

3. 문제를 풀다 에러가 발생하면, 채웠던 박스는 빈 셀로 남겨둡니다(빈 셀로 남겨뒀었다면 박스를 채워야합니다).

그림의 예시에서 1행 1열을 빈 셀로 가정하고 비워둡니다(사선으로 표기). 그리고 지금까지 배운 테크닉을 이용해 힌트를 풀어갑니다. 그러면 1행 3열이 박스로 채워집니다(동그라미로 표기). 그러면, 4행의 힌트 3과 3열의 힌트 2에 관해 모순이 발생합니다. 따라서 1행 1열의 빈 셀로 가정했던 부분은 빈 칸이 아닙니다(박스로 채워야 합니다).

그림. contradiction 테크닉 적용 절차 예시.

이 테크닉을 적용할 때 어느 셀을 빈 셀로 가정할지 정하는 문제가 있습니다. 어떤 셀은 이 테크닉으로 적은 시도를 통해서 모순을 찾을 수 있지만, 어떤 셀은 모순을 찾을 수 없을 수 있습니다. 이 테크닉을 적용하기 알맞은 셀은 인접한 셀이 박스로 채워졌거나 빈 셀로 확정된 경우입니다. 또는 같은 행(또는 열)에 박스로 채워진 칸이 많거나 빈 셀이 확정된 셀이 많은 경우입니다.

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