네모로직 알고리즘 – 당연히 채워지는 셀 구하는 공식, simple boxes

이 방법은 풀이 테크닉 중에 simple boxes라고도 합니다.

7

1

위와 같은 네모로직의 한 줄에 대해서 생각해보겠습니다.

위와 같이 10 X 1의 격자(grid)에 대해서 풀이할 때 채울 수 있는 경우는 무엇 무엇이 있을까요?

7	1
7	1
7	1

하나 하나 가능 한 경우를 가정해보면 위와 같이 3 가지 경우가 나옵니다.

그렇다면 위의 경우 모두에서 겹치는 부분은 항상 채워지는 박스입니다.

7

1

이렇게 2번째 셀부터 시작하여 6칸은 항상 채워지는 박스 입니다.

 

 

이번 시간에는 이와 같은 박스를 찾는 공식에 대해서 알아보겠습니다.

예시에서 7, 1 과 같이 채워지는 블록들을 집합의 원소로 표현하면,

 

라고 합시다.

 

L 을 한 라인의 개수,

B 를 라인에 들어가는 블록들의 개수,

식에 대해서 설명하자면,

블록 i가 채워질 가능성이 있는 박스들의 개수 합 = 전체 라인 개수 – 블록들의 개수 + 1 – 블록i를 제외한 블록들의 개수 합

 

예시에 적용해보면,

 

 

7

1

빨강색 8개 셀이 블록1이 채워질 수 있는 가능성이 있는 박스들, 파랑색 2개 셀이 블록2가 채워질 가능성이 있는 박스들 입니다.

 

한편, 격자 상에서 블록i의 채워지기 시작하는 첫 지점을 찾아보는 공식은

 

 

공식을 설명하자면, 블록i가 첫번째 블록일 때 시작지점은 1, 그 이외의 경우일 때는 바로 전 블록i-1의 시작지점 + 블록i의 크기 + 1 입니다. 네모로직의 규칙이 블록들의 사이는 최소 1개 이상의 셀이 비어있어야 하므로 당연하네요.

 

역시 예시에 적용해보면,

 

 

7

1

위 공식은 블록들이 채워질 가능성이 있는 가장 앞쪽의 셀의 위치를 알려줍니다. 공식에 따라, 빨강색 셀이 블록1의 가장 앞의 시작가능지점, 파랑색 셀이 블록2의 가장 앞의 시작가능지점 입니다.

 

다음으로 당연하게 채워지는 블록을 구하는 공식입니다.

 

 

 

당연하게 채워지는 블록i의 크기 = 블록i의 크기 2배 - 블록i의 채워질 가능성 있는 박스의 개수

 

역시 위의 예시에 적용해보면

 

 

마지막으로 당연하게 채워지는 블록의 시작지점은

 

 

당연하게 채워지는 블록i의 시작지점 = 블록i의 시작지점 + 블록i의 채워질 가능성 있는 박스의 개수 – 블록i의 크기. 단, 당연하게 채워지는 블록i의 크기는 0보다 크다

 

마지막으로 예시에 대입하면

위와 같은 공식들의 흐름에 따라 당연하게 채워지는 블록은 블록1(블록의 개수가 7인 첫번째 블록)이고, 당연하게 채워지는 박스의 개수는 6개, 그 시작 지점은 2 입니다.

그림으로 표현하면

7

1

처음에 손으로 직접 풀어서 확인해본 결과와 같네요.

 

원문: 리스본의 New University, 정보공학과 석사논문, Solving Colored Nonograms, Luis Pedro Canas Ferreira Mingote, 2009

(This article is translated Korean and modified for study solving Nonograms, educational purpose : Solving Colored Nonograms, Luis Pedro Canas Ferreira Mingote, 2009)