Направо към съдържанието

Судоку

от Уикипедия, свободната енциклопедия
Судоку (щракнете за решението)

Судо̀ку (на японски: 数独 sūdoku от ji wa dokushin ni kagiru или цифрите са ограничени да са единични[1]) е логическа[2] игра с цифри. В най-разпространения си вариант се играе върху мрежа от 81 квадратчета, представляващи игрално поле от 9 еднакви квадрата, всеки от който е с девет квадратчета. В условието на всеки ребус предварително са дадени правилните места на няколко цифри. Завършените игри винаги са вид латински квадрат с допълнително ограничение на съдържанието на отделните полета. Целта е да се запълнят останалите квадратчета, като във всяка група 3×3, всеки ред и всяка колона числата от 1 до 9 не трябва да се повтарят.

Пъзели с цифри се появяват във вестниците през късния XIX век, когато французите започват да експериментират, премахвайки цифри от магическите квадрати. Le Siècle, парижки ежедневник, публикува частично попълнен 9×9 магически квадрат с 3×3 подквадратчета на 19 ноември 1892. Това обаче не е судоку, тъй като съдържа двуцифрени числа и изисква аритметика за решаването, а не логика.

На 6 юли 1895 съперникът на Le Siecle, La France, усъвършенства пъзела така, че той е почти като съвременното судоку. Той опростява 9×9 магически квадрати, така че всеки ред, колона и диагонал да съдържа само числата 1–9, но не маркира подквадратите. Макар че са немаркирани, всеки 3×3 подквадрат съдържа числата 1–9.

Тези седмични пъзели са характерни за френските вестници като L'Echo de Paris в продължение на около десетилетие, но изчезват по времето на Първата световна война.

Правила и сложност

[редактиране | редактиране на кода]

Правилото е само едно: във всеки малък квадрат (от 3×3), колона и редица (а в някои разновидности на играта – и по диагоналите) на големия квадрат (9×9) да се попълнят цифрите от 1 до 9, без да се повтарят.

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

През 2005 г. компютърният учен Бертрам Фелгенхауер и математикът Фрейзър Джарвис изчисляват всички възможни решения за судоку 9×9 – 6 670 903 752 021 072 936 960 комбинации.[3]

Техники за решаване

[редактиране | редактиране на кода]

Решаването е резултат от комбиниране на различните техники.

Единствено възможно място на числото 5
  • Защриховане – За пример ще потърсим мястото на числото 5 в горния десен квадрат. Водейки се от правилото, че всяка цифра се среща само по веднъж в колона и редица, защриховаме колоните и редиците, където търсеното число 5 не може да бъде. Така маркираното в зелено квадратче остава единствено възможно.
Маркирани възможни цифри
  • Маркиране – При тази техника във всяко квадратче се попълват всички възможни цифри, като се следи за числата в съответните подквадрат, ред и колона. Често за едно квадратче остава само една възможна цифра.
  • Елиминиране – Основава се на логическа дедукция. Когато една цифра може да бъде само в 2 или 3 възможни квадратчета в един подквадрат и те са в една линия, т.е. образуват ред (или колона), значи по продължение на този ред (или колона) тази цифра няма да присъства повече.

Броят на квадратчетата и формата на регионите, които образуват, варират от 2×2 (судоку за деца) до 25×25 (судоку гигант). Играта съществува и под формата на куб (судоку куб), подобно на кубчето Рубик, но цветовете са заменени с цифри.

Играта е измислена от швейцарския математик Леонард Ойлер през 18 век и се разпространява с наименованието „магически квадрати“. Едва през 1970-те американецът Хауърд Гарнс преработва играта до съвременния ѝ вид и през 1979 г. я публикува в специализирано печатно издание. Истинско признание играта получава едва през 1984 г. след лансирането ѝ от компанията Nikoli в Япония, където получава името „судоку“ (от японските думи су – цифра и доку – единствен).

  1. 数独 (Sudoku) в Wiktionary
  2. Arnoldy, Ben. "Sudoku Strategies". The Home Forum. The Christian Science Monitor.
  3. https://www.businessinsider.com/number-of-possible-sudoku-puzzle-grids-2019-4 "The number of solutions you could fit into your weekend Sudoku is mind-boggling" Andy Kiersz, Apr 6, 2019