노노그램에 backjumping을 붙이려던 시도

줄 단위로 채워 나가다 막히면 바로 앞 줄로 한 칸 돌아간다. 그런데 막힌 원인이 훨씬 앞의 줄인 경우가 있다. 그러면 앞 줄의 다른 후보를 아무리 시도해도 계속 막힌다.

원인이 된 줄까지 한 번에 돌아가자는 게 backjumping이다.

어느 줄 때문에 막혔는지 모으기

원래 코드는 부딪히면 그냥 break 로 그 후보를 버렸다. 여기서는 부딪힌 상대를 기록한다.

for cur in poss:
    conflict = False
    if dir == 'r':
        for i, o in enumerate(m[idx]):
            if cur[i] != o and f'c{i}' in h:
                local_problems.add(f'c{i}')
                conflict = True
                break

local_problems 에 부딪힌 열 이름이 쌓인다. 이 줄의 후보를 다 시도했는데 전부 막혔다면, 그 원인은 local_problems 안의 줄들이다.

위로 넘기고, 관계없으면 건너뛰기

def nonogram(q, problems=set()):
    ...
    if problems and f'{dir}{idx}' not in problems:
        return problems

위에서 "이 줄들 때문에 막혔다"는 목록을 받으면, 지금 줄이 거기 없는 경우 아무것도 하지 않고 그대로 돌려준다. 이 줄의 후보를 바꿔봐야 원인이 그대로라 소용없기 때문이다.

원인이 된 줄에 닿을 때까지 이렇게 미끄러져 올라간다. 한 칸씩 되돌아가는 것과 달리 중간 줄들의 후보를 다시 시도하지 않는다.

sub_problems = nonogram(q[1:], local_problems)
...
local_problems |= sub_problems

return local_problems

아래에서 올라온 원인 목록을 자기 것에 합쳐서 다시 위로 올린다.

완성하지 못했다

파일 이름이 backjump_doing.py 다. 하다 만 상태 그대로다.

성공했을 때 돌아가는 자리가 비어 있다.

if len(q) == 0:
    for line in m:
        print(*line)
    return

여기서 아무것도 돌려주지 않는다. 부르는 쪽은 sub_problems 에 그걸 받아 local_problems |= sub_problems 를 하므로, 답을 찾은 순간 집합이 아닌 값과 합집합을 하려다 멈춘다.

원인 목록을 돌려주는 것과 "다 풀었다"를 알리는 것이 같은 반환값을 쓰고 있는 게 문제다. 둘을 구분하려면 반환값을 나누거나 답을 찾은 시점에 탐색 전체를 빠져나가는 별도의 길이 있어야 한다.

local_problems 를 다루는 자리도 정리가 덜 됐다. 부딪혀서 버린 후보에서 모은 것과, 내려갔다 올라온 것이 같은 집합에 섞인다. 앞의 것은 이 줄에서 막힌 원인이고 뒤의 것은 더 아래에서 막힌 원인이라 성격이 다르다.