지난 글 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

Posted by 도전하는 공돌이pooh

댓글을 달아 주세요

  1. 대학생 2016.11.01 19:57  댓글주소  수정/삭제  댓글쓰기

    올려주신 글 하나씩 읽으면서 파이썬 코드로 구현해보고 있는 중입니다.
    생각보다 단순할 줄 알았던 곳에서 막히는 중이네요..
    simple spaces가 사람이 풀면 정말 간단한 이론이지만
    컴퓨터가 풀게 하려니 예외 케이스가 많아 감이 잡히지를 않네요..
    많이 배우고 있습니다 감사합니다.