Що робить нонограму легкою чи складною

Більша сітка справді означає більше рядків для відстеження та більше перехресних перевірок, тож великі головоломки забирають більше часу. Але сама лише довжина не робить рядок складним — рядок завширшки 20 клітинок з однією великою послідовністю тривіальний, тоді як короткий рядок, набитий дрібними послідовностями та тісними проміжками, може потребувати справжніх роздумів. Розмір впливає на те, скільки часу займає головоломка, набагато більше, ніж на те, наскільки складний кожен крок.

Найточніша міра складності — це те, який тип міркувань вимагає головоломка. Найлегші головоломки «розв'язуються по рядках»: їх можна завершити, розглядаючи по одному рядку чи стовпцю за раз, заповнюючи все, що змушує окрема лінія, і жодного разу не тримаючи дві лінії в голові одночасно. Більшість простих головоломок саме такі.

Складніші головоломки вимагають поєднання інформації — помітити, що стан клітинки стає вимушеним лише тоді, коли ви розглядаєте рядок і стовпець разом або невеликий кластер ліній одночасно. Що глибше має заходити це поєднання, перш ніж наступна клітинка стане вимушеною, то складнішою відчувається головоломка, незалежно від її розміру.

Ось заспокійлива частина. Наукова праця про розв'язання нонограм (Batenburg and Kosters, 2012) виміряла, скільки міркувань насправді потребують однозначно розв'язувані головоломки. Окрім простого розв'язання по рядках, наступний крок — це чітко визначена, все ще детермінована техніка — поєднання пар ліній — і їхнє вичерпне перерахування виявило, що 93.8–95.5% непростих головоломок розв'язуються саме цим, узагалі без вгадування.

Ще більш вражаюче: лише близько 0.06–0.14% усіх однозначно розв'язуваних головоломок потребують чогось поза цим міркуванням про пари ліній. Іншими словами, переважна більшість правильно складених нонограм — включно з кожною складною, яку ви зустрінете у звичайній грі — розв'язується чистою, обмеженою логікою. Справжній метод спроб і помилок надзвичайно рідкісний у чесній головоломці, і саме тому «ніколи не вгадуй» — така надійна порада.

За всім цим стоїть теоретичний результат. Задачу «чи має довільний набір підказок рядків і стовпців хоч якийсь розв'язок» було доведено як NP-повну (Ueda and Nagao, 1996) — той самий клас складності, що й у горезвісної задачі комівояжера. Простими словами: ніхто не знає методу, який швидко розв'яже будь-яку мислиму нонограму, і в найгірших випадках обсяг обчислень вибухає зі зростанням сітки.

Звучить лячно — доки не помітиш різницю між «будь-якою мислимою нонограмою» і «нонограмами, які реально публікують». Результат про NP-повноту стосується довільних, зумисне ворожих наборів підказок, багато з яких не мають розв'язку взагалі або мають кілька. Справжню головоломку роблять навпаки: вона починається з картинки і потрапляє в публікацію лише тоді, коли має рівно один розв'язок, до якого логіка справді може дійти. Саме тому цифри з попереднього розділу працюють на практиці — і саме тому головоломка перед вами майже напевно чесна, навіть якщо здається звірячою.

Окрім глибини висновків, кілька поверхневих ознак підштовхують складність. Дуже розріджені картинки (переважно порожні) та дуже щільні (переважно заповнені) зазвичай легші, бо крайнощі дають багато вимушених клітинок на початку. Найхитріші головоломки зазвичай посередині, зі збалансованим поєднанням заповненого й порожнього та безліччю коротких, розірваних послідовностей, які опираються швидким першим ходам. Чіткий, упізнаваний сюжет також допомагає гравцеві не втрачати орієнтації, навіть якщо він не змінює базової логіки.

На цьому сайті оцінка головоломки визначається тим, наскільки глибокими є міркування для її розв'язання, у поєднанні зі статистикою форми, як-от наскільки заповнена сітка. Головоломки, що розв'язуються по рядках, потрапляють у легкі; ті, що потребують справжнього міжлінійного поєднання, зсуваються до складних; усе, що вимагало б вгадування, відхиляється відразу, а не публікується. Повний процес описано на сторінці «як ми створюємо наші нонограми» — але коротко: складність тут вимірюється, а не вгадується.