노노그램이 쉬운지 어려운지를 결정하는 것

더 큰 격자는 실제로 추적할 줄이 더 많아지고 교차 확인도 더 많아지므로, 큰 퍼즐은 시간이 더 걸립니다. 하지만 길이만으로 줄이 어려워지지는 않습니다 — 큰 연속 하나만 있는 폭 20짜리 행은 시시하지만, 작은 연속과 빡빡한 틈으로 가득 찬 짧은 행은 진짜 사고를 요구할 수 있습니다. 크기는 각 단계가 얼마나 어려운지보다 퍼즐이 얼마나 오래 걸리는지에 훨씬 더 영향을 줍니다.

난이도의 가장 참된 척도는 퍼즐이 어떤 종류의 추론을 요구하는가입니다. 가장 쉬운 퍼즐은 「줄 단위로 풀리는」 것으로, 한 번에 한 행이나 열을 보고 그 하나의 줄이 강제하는 것을 채우기만 하면 끝낼 수 있으며, 두 줄을 동시에 머릿속에 담을 필요가 전혀 없습니다. 대부분의 순한 퍼즐이 바로 이렇습니다.

더 어려운 퍼즐은 정보를 결합할 것을 요구합니다 — 어떤 칸의 상태가 행과 열을 함께, 또는 몇 개의 줄로 이루어진 작은 무리를 한꺼번에 고려해야 비로소 강제된다는 것을 알아차리는 것입니다. 다음 칸이 강제되기까지 그 결합이 깊이 들어가야 할수록, 크기와 상관없이 퍼즐은 더 어렵게 느껴집니다.

여기 안심되는 부분이 있습니다. 노노그램 풀이에 관한 학술 연구(Batenburg and Kosters, 2012)는 유일하게 풀 수 있는 퍼즐이 실제로 얼마나 많은 추론을 요구하는지 측정했습니다. 단순한 줄별 풀이를 넘어서는 다음 단계는 잘 정의된, 여전히 결정론적인 기법 — 줄의 쌍을 결합하는 것 — 이며, 그들의 철저한 열거는 단순하지 않은 퍼즐의 93.8–95.5%가 바로 그것만으로, 전혀 추측 없이 풀린다는 것을 발견했습니다.

더욱 놀랍게도, 유일하게 풀 수 있는 모든 퍼즐 중 그 줄의 쌍 추론을 넘어서는 무언가를 필요로 하는 것은 약 0.06–0.14%에 불과합니다. 다시 말해, 잘 만들어진 노노그램의 압도적 다수는 — 보통의 플레이에서 만나는 모든 어려운 것을 포함해 — 순수하고 유한한 논리만으로 풀 수 있습니다. 진짜 시행착오는 공정한 퍼즐에서는 사라질 만큼 드물며, 그래서 「절대 추측하지 말라」가 그토록 믿을 만한 조언인 것입니다.

이 모든 것의 밑바탕에는 이론적 결과가 있습니다. 임의의 행과 열 단서 집합이 애초에 어떤 해라도 갖는지를 판정하는 것은 NP-완전임이 증명되었습니다(Ueda and Nagao, 1996) — 외판원 문제처럼 악명 높게 완고한 문제와 같은 복잡도 부류입니다. 쉽게 말하면, 상상할 수 있는 모든 노노그램을 빠르게 푸는 방법은 아무도 모르며, 최악의 경우 격자가 커질수록 필요한 작업량이 폭발합니다.

이는 「상상할 수 있는 모든 노노그램」과 「사람들이 실제로 출판하는 노노그램」의 차이를 알아차리기 전까지는 놀랍게 들립니다. NP-완전성 결과는 임의의, 적대적인 단서 집합에 관한 것이며 — 그중 다수는 해가 없거나 여러 개입니다. 진짜 퍼즐은 반대 방향으로 만들어집니다 — 그림에서 시작해, 논리가 실제로 도달할 수 있는 해를 정확히 하나만 가질 때에만 출판됩니다. 그래서 앞 절의 숫자가 실제로 성립하며, 눈앞의 퍼즐이 잔혹하게 느껴질 때조차 거의 확실히 공정한 것입니다.

추론 깊이 외에도 몇 가지 표면적 특징이 난이도를 밀고 당깁니다. 매우 성긴 그림(대부분 비어 있음)과 매우 빽빽한 그림(대부분 채워짐)은 극단이 초반에 많은 강제된 칸을 주기 때문에 대체로 더 쉽습니다. 가장 까다로운 퍼즐은 보통 중간에 있으며, 채움과 비움이 균형 있게 섞이고 빠른 첫 수에 저항하는 짧고 끊긴 연속이 잔뜩 있습니다. 깨끗하고 알아보기 쉬운 소재도 바탕에 깔린 논리를 바꾸지는 않지만 푸는 이가 방향을 잃지 않게 도와줍니다.

이 사이트에서 퍼즐의 등급은 그것을 푸는 추론이 얼마나 깊어지는가와, 격자가 얼마나 채워져 있는가 같은 형태 통계를 결합해 나옵니다. 줄 단위로 풀리는 퍼즐은 쉬움에 들어가고, 진정한 줄 간 결합을 요하는 것은 어려움 쪽으로 옮겨가며, 추측을 요구할 만한 것은 출판되지 않고 곧바로 거부됩니다. 전체 과정은 「우리가 노노그램을 만드는 방법」 페이지에 설명되어 있지만, 요컨대 여기서 난이도는 측정되는 것이지 추측되는 것이 아닙니다.