Почесний професор університету Уінтропа в Південній Кароліні (США) Джеймс Крук опублікував в журналі "Замітки Американського математичного товариства" статтю, що викладає простій спосіб вирішення головоломки судоку на будь-якому рівні складності.
Для вирішення судоку за новим методом не вимагається обчислювальної техніки, достатньо ручки і паперу. Алгоритм Крука - перший математичний опис способу вирішення популярної головоломки. Він полягає в обході вершин дерева рішень до тих пір, поки не знайдене вірне.
Недоліком представленого алгоритму є його трудоємкість. У кожну порожню клітину слід вписати бракуючі цифри і почати перебір. Рішення головоломки круківським способом займає близько години. Зазвичай її вирішують за 20 хвилин.
Математики зацікавилися судоку кілька років тому. Одною з робіт, на які спирався Джеймс Крук в своєму дослідженні, була "Sudoku Squares and Chromatic Polynomials", автори якої застосували метод розфарбовування карти з теорії графів для вирішення судоку.
За матеріалом Лента.Ру
Судоку — основана на логіці головоломка-пазл з числами. В перекладі з японської мови "су" позначає слово "число", "доку" має безліч різних перекладів, але в цілому означає щось одне, одиничне, цілісне. Оригінальну назву головоломки японською дуже важко вимовити, і для англійців його довелося скоротити до "Sudoku".
Рішення головоломки не вимагає математичних розрахунків, але потребує терпіння і здатності до логічного мислення. По деяким даним рішення головоломок Судоку поліпшує пам"ять, мислення, а також перешкоджає розвитку і навіть лікує захворювання пов"язані з головним мозком (таких, як хвороба Альцгеймера).
Ігрове поле складається з квадрата, розміром 9 × 9, розділеного на менші квадрати (їх ще називають "регіони") із стороною 3 × 3 клітинки. Таким чином, все поле налічує 81 клітинку. У деяких з них вже на початку гри розташовані числа (від 1 до 9). Залежно від того, скільки клітинок вже заповнено, конкретну судоку можна віднести до легких або складних.
Мета головоломки - необхідно заповнити вільні клітинки цифрами від 1 до 9 так, щоб в кожному рядку, в кожному стовпці і в кожному малому квадраті 3×3, кожна цифра зустрічалася лише один раз. Правильна головоломка має лише одне рішення.
Математична основа
Кількість можливих комбінацій в судоку 9х9 складає за розрахунками Бертхама Фельгенхауера (англ. Bertram Felgenhauer) 6 670 903 752 021 072 936 960.
2 
1
Коментарі