Судоку (数独, sūdoku) (понякога изписван като Su Doku, но наричан още Number Place или Nanpure) е пъзел, който е много популярен в Япония. Създаден е в Индианаполис през 1979 г. от Хауърд Гарнс и след това се появява в списанията на Dell.

Пъзелите Судоку се решават с помощта на логиката и не се изисква математика. Както се вижда вдясно, той се състои от мрежа, която обикновено се състои от девет реда, девет колони и девет полета, разделени с по-дебели и по-тъмни линии. Някои от тези полета съдържат цифри от 1 до 9. За да реши пъзела, човек трябва да попълни всички празни квадратчета, без да използва една и съща цифра два пъти във всяка колона, ред или квадратче и без да променя цифрите, които вече са в решетката.

Тези пъзели са създадени, за да се решават с молив и хартия, и има много книги, които съдържат колекции от такива пъзели със съвети и стратегии за решаването им. Те се появяват и във вестници и списания: обикновено всеки ден се появява различен пъзел, а решението е отпечатано някъде другаде или в следващия брой. По-късно бяха създадени малки преносими машини, които генерират пъзели Судоку за решаване от потребителя. Напоследък обаче играта може да се играе в интернет или чрез мобилни приложения.

Правила и основни понятия

Класическото судоку е 9×9 решетка, разделена на девет 3×3 полета (кутии). Целта е да се попълнят празните клетки с числа от 1 до 9 така, че:

  • във всеки ред да присъстват всички числа от 1 до 9 точно по веднъж;
  • във всяка колона да присъстват всички числа от 1 до 9 точно по веднъж;
  • във всяко 3×3 поле (кутийка) да присъстват всички числа от 1 до 9 точно по веднъж.

Някои публикации изискват пъзелът да има единствено решение (уникалност), но това не е част от основните правила — все пак повечето публикувани пъзели са конструирани да имат единствено решение. За класическото 9×9 е доказано чрез изчерпателни компютърни проверки, че минималният брой наведени (givens) при пъзел с уникално решение е 17.

Кратка история

Идеята за настоящата форма на пъзела идва от Хауърд Гарнс, който през 1979 г. публикува варианта под името "Number Place" в американски списания. През 1980-те японските издатели (най-известно издателство е Nikoli) преоткриват и кръщават пъзела "Sudoku" — съкращение от японската фраза, означаваща "едно число", под популяризирането на Мaки Каджи и други. Световната слава идва в началото на XXI век, когато судоку започва да се появява в ежедневни вестници в Европа и Америка, а по-късно и в онлайн платформи и приложения.

Видове и варианти

Освен класическото 9×9 съществуват много варианти, които добавят разнообразие и нови логически предизвикателства:

  • 4×4, 6×6, 12×12, 16×16 — по-малки или по-големи решетки с числа/символи.
  • Диагонално судоку — всички числа 1–9 трябва да присъстват и по основните диагонали.
  • Killer (Килър) судоку — сумите в някои области са зададени и клетките нямат начални числа.
  • Hyper/Extra-region Sudoku — добавени са допълнителни области с изискване за уникални числа.
  • Samurai, Multi-Sudoku — свързани решетки, които споделят общи полета.
  • Irregular/Геометрично судоку — полетата не са стандартни 3×3, а неправилни форми.

Основни стратегии за решаване

Тук ще опишем техники от най-простите до по-напредналите. Започнете винаги със сканиране и маркиране, след това използвайте последователни логически стъпки.

  • Сканиране (cross-hatching) — прегледайте редове/колони/кутийки за очевидни липсващи числа.
  • Единични кандидати (naked single) — клетка има само една възможна цифра според текущите бележки.
  • Скрити единични (hidden single) — в ред/колона/кутийка едно число може да отиде само в една клетка, макар клетката да има други кандидати.
  • Naked pair/triple/quad — две (или три и т.н.) клетки в една единица споделят същите два (три и т.н.) кандидати; тези кандидати могат да бъдат премахнати от останалите клетки в единицата.
  • Pointing pair/box-line reduction — кандидат в рамките на кутия е ограничен в един ред/колона и може да бъде елиминиран от същия ред/колона в други кутии.
  • X-Wing, Swordfish, Jellyfish — техники, базирани на модели в две или повече реда/колони, които позволяват елиминиране на кандидати.
  • XY-Wing, XYZ-Wing — локални верижни логики, които водят до елиминиране на кандидати в зависими клетки.
  • Цветиране и вериги (coloring, chains) — използват графи и паритет, за да открият противоречия и да елиминират кандидати.
  • Уникалност и предположения — при особено трудни пъзели се прави структурирано предположение (т.нар. trial-and-error) с връщане назад; при качествени пъзели това рядко е необходимо, тъй като има логична последователност.

Съвети за начинаещи

  • Започнете със сканиране на всички редове, колони и кутии за очевидни единични решения.
  • Използвайте малки бележки (pencil marks) за потенциалните кандидати и ги обновявайте често.
  • Не прескача секи техники: научете и упражнявайте naked/hidden pairs, box-line reductions и X-Wing; те решават много "трудни, но не крайни" пъзели.
  • Бъдете търпеливи — при сложни пъзели разделете проблема на по-малки стъпки и проверявайте всяка промяна логически.

Компютърни методи и алгоритми

Судоку е интересен и за информатиците: генерация, решаване и проверка на уникалност се правят с различни алгоритми — обратно търсене (backtracking), Dancing Links (DLX, алгоритъм на Доналд Кнут за покриване на множества), и логически решаващи двигатели. Общата задача на Sudoku при произволни размери е NP-пълна, което я прави трудна от теоретична гледна точка.

Къде да играете и допълнителни ресурси

Освен в печатни издания и книги, судоку се намира в изобилие онлайн и в мобилни приложения. Много сайтове предлагат интерактивни решаващи инструменти, обяснения на техники и колекции по трудност. Има и международни състезания и клубове, сред които Световно първенство по судоку и други турнири, организирани от пъзел и логически общности.

Судоку е лесен за започване, но предлага богато поле за развитие — от ежедневна закуска за ума до сериозни логически предизвикателства за ентусиасти и състезатели.