노노그램은 각 행과 열에 [3, 2] 같은 숫자 묶음이 주어지고, 그대로 칠해지는 판을 찾는 문제다.
칸 하나씩 칠할지 말지 정하는 방식으로 가면 15x15에서 2의 225제곱이 된다. 대신 한 줄을 통째로 정하는 단위로 갔다.
한 줄의 가능한 배치를 전부 만들기
def findall(tl, que, ans=''):
if len(que) == 0:
ans += '0' * (tl - len(ans))
return [ans]
results = []
cur = que[0]
if cur <= tl - len(ans):
results += findall(tl, que[1:], ans + '1' * cur + ('0' if len(que) != 1 else ''))
results += findall(tl, que, ans + '0')
return results
tl 은 줄 길이, que 는 남은 블록 목록이다. 매 단계에서 두 가지를 한다.
- 지금 위치에 블록을 놓는다.
'1' * cur로 칠하고 뒤에'0'을 하나 붙인다. 블록 사이에는 최소 한 칸이 비어야 하기 때문이다. 마지막 블록이면 안 붙인다. - 블록을 놓지 않고
'0'하나만 놓고 넘어간다.
if cur <= tl - len(ans) 가 가지치기다. 남은 자리보다 블록이 크면 놓을 수도 없고 밀어서 될 일도 아니므로 그 가지를 통째로 접는다.
블록을 다 놓았으면 남은 자리를 '0' 으로 채워 완성한다. [3, 2] 를 길이 7에 놓는 경우처럼 답이 여러 개 나온다.
확정된 줄과 부딪히는지 본다
행과 열을 순서대로 처리하는데, 행을 정하면 그 행이 지나가는 열들의 값이 정해진다. 나중에 그 열을 처리할 때 이미 정해진 값과 어긋나면 안 된다.
h = set()
h 는 지금까지 확정한 줄의 이름을 담는다. r3, c7 처럼 방향과 번호를 붙여 넣는다.
for cur in poss:
if dir == 'r':
for i, o in enumerate(m[idx]):
if cur[i] != o and f'c{i}' in h:
break
else:
old_row = m[idx][:]
m[idx] = list(cur)
h.add(f'r{idx}')
nonogram(q[1:])
h.remove(f'r{idx}')
m[idx] = old_row
이 행 후보를 판에 놓았을 때 값이 달라지는 칸이 있으면, 그 칸이 속한 열이 이미 확정됐는지 본다. 확정된 열이면 이 후보는 쓸 수 없으므로 break 로 버린다.
확정되지 않은 열이면 지금 덮어써도 된다. 그 열은 아직 아무것도 정하지 않았기 때문이다.
for ... else 를 썼다. break 없이 반복이 끝났을 때만 else 가 돈다. 부딪히는 칸이 하나도 없었다는 뜻이다. 플래그 변수를 따로 두지 않아도 된다.
되돌리는 것도 세 가지를 같이 한다. 판의 그 줄, h 에서 이름, 그리고 다음 줄로 내려가기 전 상태다. 열 쪽은 세로로 흩어져 있어 old_col 에 따로 담아뒀다 되돌린다.