노노그램에서 어떤 줄부터 채울지 정하기

15x15 노노그램에서 행 15개와 열 15개, 총 30줄을 어떤 순서로 처리할지 정해야 한다. 순서가 답을 바꾸지는 않지만 탐색량은 크게 바꾼다.

기준으로 잡은 건 이거다.

가능성이 적다는 건 합이 크다는 것.

한 줄의 최소 길이

블록 목록이 주어지면 그 줄이 최소 몇 칸을 차지하는지 정해진다. 블록을 다 붙여놓고 사이에 한 칸씩만 비우는 경우다.

[3]     -> 3
[1, 3]  -> 5   (10111)

[1, 3] 은 1과 3에 사이 한 칸을 더해 5다. 식으로는 블록 합에 개수를 더하고 1을 빼면 된다.

d = {}

for i, cur in enumerate(r):
    curl = sum(cur) + len(cur) - 1
    d[(i, 'r')] = curl

for i, cur in enumerate(c):
    curl = sum(cur) + len(cur) - 1
    d[(i, 'c')] = curl

q = sorted(d, key=lambda i: d[i], reverse=True)

행과 열을 한 dict에 같이 담는다. 키에 'r' 인지 'c' 인지를 넣어서 나중에 어느 쪽인지 알 수 있게 했다. 그래야 행과 열을 섞어서 하나의 순서로 정렬할 수 있다.

최소 길이가 큰 것부터 내림차순으로 정렬한다.

왜 그게 후보가 적은가

줄 길이에서 최소 길이를 뺀 만큼이 블록들이 움직일 수 있는 여유다. 최소 길이가 클수록 여유가 작고, 여유가 작을수록 배치가 적다.

실제로 이 퍼즐의 줄들을 세어보면 이렇다.

최소 길이가 줄 길이와 같으면 놓을 수 있는 방법이 하나뿐이다. 반대로 [1] 하나짜리는 15군데 아무 데나 갈 수 있다.

후보가 하나뿐인 줄을 먼저 확정하면 그 줄이 지나는 15개 열에 값이 박힌다. 그 뒤에 열을 처리할 때는 이미 박힌 값과 부딪히는 후보가 걸러진다.

반대로 [1] 짜리를 먼저 하면 15갈래로 갈라지는데, 그 15갈래 대부분은 나중에 가서야 틀렸다는 게 드러난다.

정렬은 한 번만

q 를 처음에 한 번 만들고 탐색 중에는 다시 정렬하지 않는다. nonogram(q[1:]) 로 앞에서부터 하나씩 떼어 쓴다.

줄을 채워 나가면 다른 줄의 후보도 줄어드는데, 그걸 반영해서 순서를 다시 매기지는 않는다. 매번 다시 세는 비용과 순서가 나아지는 이득을 비교해야 하는 부분인데 거기까지는 안 갔다.