Когато заседнете в някое дяволско трудно судоку е странно да не се зачудите дали пъзела наистина има решение. В някои моменти, може да сте имали съмнения, че има някакъв по-прост и систематичен начин за решаване на судоку решетката. Може да са ви идвали на ум въпросите:
- Колко различни пъзела може да има в стандартния 9x9 формат?
- Може ли пъзел с по-малко начални числа да е по-лесен от някой с повече?
- Колко е минималния брой на числата които са нужни за да се гарантира че пъзела има само едно решение?
Въпреки, че се смята, че пъзелите не изискват математика за решаване, някои от въпросите, които повдигат, изискват математически анализ за намиране на отговорите. Статия от Юни месец написана от Американската Математическа Общност създава рамка за решаването на някои основни въпроси свързани със Судоку.
Всяка 9 на 9 судоку решетка се състои от 3 на 3 под-решетки. Първоначално, някои от тези 81 квадрата съдържат числа от 1 до 9, но други не. Целта е да се попълнят празните квадратчета, така че всеки ред, колона и под-решетка да съдържат числата от 1 до 9 в произволен ред. Всеки пъзел има само едно решение.
Агнес М. Херцберг и М. Рам Мърти от Кралския университет в Кингстън, Онтарио са превели проблема за решаване на судоку пъзела на езика на теорията на графите. 81-те квадрати в решетката съответстват на върховете в математическата графика. Линия свързва върховете които се появяват във всеки ред, колона или под-решетка. Това математическо преобразуване се ползва от математиците за да се разработи теорията на графите и да се разбере Судокуто.
Въпреки че судоку пъзелите почти винаги ползват числата от 1 до 9, каквито и да е 9 различни символа ще свършат същата работа. Например, един пъзел може да се състои от 9 букви, фигури или цвята вместо числа. Когато теоретиците слагат етикети на върховете, те го наричат "оцветяване". Един судоку пъзел започва с частично оцветяване, понеже само няколко места имат въведени числа. Веднъж когато всеки връх е оцветен и няма два свързани върха с един и същи цвят, оцветяването се нарича "правилно".
По този начин, на езика на теорията на графите, решаването на судоку означава преминаването от частично оцветяване на графиката до правилното и оцветяване.
Ферцберг и Мърти използват техники от теорията на графите за да покажат че съществува проста математическа формула за намирането на броя на решенията на даден судоку пъзел. Ако пъзела е проектиран правилно, той има само едно възможно решение. Такава формула може да помогне на алгоритъм за решаване на судоку, да разбере, дали наистина судокуто има само едно решение.
За съжаление, обаче, въпреки че математиците доказаха, че съществува формула, те не успяха да разберат каква е точно тя.
Херцберг и Мърти обаче установиха, че за да може един пъзел да има точно едно решение, първоначално зададените числа трябва да включват най-малко осем от девет цифри. Тяхната логика е проста. Да предположим, че нито 1, нито 2 се появяват в началните вписвания. Тогава при всяко решение, всички 1-ници могат да бъдат разменени със всички 2-ки, така че ще има най-малко две валидни решения.
Судоку пъзелите са пример за тип графика позната като Латински квадрат, който математиците са изучавали в продължение на векове. Латинския квадрат е проста мрежа от числа от 1 до N, подредени така, че всеки ред и всяка колона съдържат всяко число само по веднъж. Ако Латинския квадрат съдържа под-квадрати които също съдържат N на брой числа, тогава това е Судоку.
Колко Латински квадрата са валидни Судоку пъзели? Преброяването на всички възможни латински квадрати които са 9 на 9 се оказва доста трудно, а определянето на валидните Судоку квадрати между тях е още по-трудно. През 1975 година изследователите установили, че има 5,524,751,496,156,892,842,531,225,600 (около 5,5 х 1027) Латински квадрата които са 9 на 9. Преди две години Бертрам Фелгенхауер от Дрезденския Технически Университет в Германия и Фразер Джарвис от Университета Шефилд в Англия са установели че има 3,546,146,300,288 (около 3,5 х 1012) различни 9 на 9 судоку пъзела. Това е огромен брой, но не може да се мери с броя на Латинските квадрати.
Но пред Херцберг и Мърти има по-голям въпрос. Стандартната 9 на 9 судоку решетка има 3 на 3 под-решетки, но судоку може да бъде по-малко или по-голямо. Примерно 4 на 4 судоку има четири 2 на 2 под-решетки. 16 на 16 судоку има шестнадесет 4 на 4 под-решетки, и като цяло N2 на N2 судоку ще има N на квадрат N на N под-решетки. Колко латински решетки от тези размери са валидни Судоку пъзели?
Този въпрос изглежда невъзможен за отговаряне, при положение, че никой не знае колко Латински квадрата съществуват за размери по-големи от 11 на 11. Освен това никой не знае колко Судоку пъзела съществуват за размер по-голям от 9 на 9. Независимо от това, Херцберг и Мърти успяват да изчислят, че за произволно избран квадрат с размери N2 на N2, колкото по-голям е N, толкова пада вероятността това да е Судоку. В действителност, вероятността клони към нула, когато N нараства.
Защо изразходвате тази математическа енергия за този малък пъзел? "Забавно е", казва Мърти.
Но той посочва и няколко сериозни причини. Забележително е че Судоку може да има практическо приложение, ако се гледа като проблем на теорията на графите. Примерно, насрочването на комитет за срещите на различни групи, в различни времеви интервали, може да е подобно математическо предизвикателство. Всеки връх представлява различна комисия, а две комисии се свързват с линия ако са с общо членство. Ако някой от комитетите вече имат възложени времеви интервали, графика на заседанията на останалите трябва да е частично оцветен до правилно оцветен, така че всички срещи и техните времена да нямат конфликт помежду си. Мърти обръща внимание и на приложение за проектирането на опитни полета за селскостопански изследвания и за избягване на смущения при възлагането на честотни сигнали за телевизионни станции.
Мърти казва, че той е очарован от судоку пъзелите, защото представляват един прост проблем, който се свързва с усъвършенстването на математиката. Например, същите инструменти които той използва за разбиране на Судоку, са приложими и за "проблема на четирите цвята". Това е класическо предположение, че за всяка дадена карта са необходими само четири различни цвята, за да се оцвети всяка страна (или държава), така че всеки две държави които имат обща граница да не са с един и същи цвят. Отне повече от век за да се разреши този проблем.
"Тези въпроси, които изглеждат невинни, може да имат дълбока математика в себе си", казва той.
"Судоку е един от тях"