Судоку, новое повальное увлечение Опции

[Lapp]

Кто знаком с игрой Судоку?
Она появилась не очень давно, несколько лет назад. Я не знаю, насколько она сейчас распространена в России, поэтому рассказываю подробно (извините, если это излишне). По смыслу и по виду напоминает кроссворд, но в отличие от него она не буквенная, а цифровая. Хотя, цифры там используются только как значки - никаких операций над ними (сложения и т.п.) не проводится. Говорят (и я охотно этому верю), что она прежде всего завоевала популярность в Японии, потому что бедные японцы, ввиду особенностей своей письменности, лишены возможности разгадывать кроссворды - хотя появилась она на Западе. Если сейчас зайти в любой книжный, то прямо у дверей увишь специальный стенд, на котором стоит десятка два-три как тонких так и очень толстых книг с этими головоломками..

Игра довольно тупая, но видя такой бешеный успех за короткое время, я заинтересовался ей. А тут ее стали еще публиковать в университетской газете - не попробовать я просто не мог . Как ни странно, это оказалось затягивающим, и на протяжении пары недель я свою ежедневную чашку кофе (см. фото в моем профайле ) стал посвящать этому занятию. Конечно, наскучило довольно быстро, но за это время я успел набросать небольшую прогу (сначала на Паскале, а потом на Дельфи), которая решала эти задачи. Вот я и выкладываю тут свой первоначальный паскалевский вариант..

Теперь о правилах. Поле представляет собой квадрат 9х9 клеток (поделенный еще и на подквадраты 3х3), в некоторых из которых уже стоят циферки, а в остальные их нужно вписать. В результате в каждой клетке должно стоять по цифре от 1 до 9 (ноль не участвует!), причем так, чтобы в любом столбце и в любой строчке присутствовали все девять цифр. Более того, в каждом подквадрате тоже должны быть все цифры, каждой по одной.

Правила очень простые. Существуют несколько методик решения, стратегий и тактик, которые разжевываются в книжках, но суть от этого не меняется. Ниже я привожу фото из университетской газеты (Bruin Daily, Apr 18, 2006), чтобы те, кто не видел, поимели представление.

Ниже идет текст программы, которая решает головоломку. Алгоритм такой - берем перекрестье каждой строки с каждым столбцом, и смотрим набор цифр, который они содержат. Если в нем не хватает ровно одной цифры - вписываем ее в пересечение. Могут быть и другие алгоритмы, это лишь один из возможных. Одним шагом считается полный проход по полю, если за шаг находятся несколько таких цифр - ставятся все. Если не будет найдено ни одной, программа выдаст сообщение "множественный выбор" и остановится. Смысл в том, что нужно пробовать несколько разных вариантов.

Я предлагаю народу попробовать и, может быть, предложить свои алгоритмы. Код не вычищен, прошу извинить за огрехи. Но он работает (проверено на FPC и TP). Программа требует наличие файла sudoku.dat - он текстовый, это просто построковая запись квадрата, я прилагаю образец ниже.

 sudoku_1.pas ( 2.13 килобайт ) Кол-во скачиваний: 2283


Вот образец содержимого файла sudoku.dat. Важно: файл позиционный, то есть цифры сдигать нельзя. Более того, в строчке должны обязательно присутствовать все девять знаков (цифры и пробелы) - закрасьте приведенный пример блоком, чтобы увидеть пробелы, присутствующие там. Цифра обозначется цифрой, пустое место - пробелом или любым знаком (не цифрой или нулем). Лишних пробелов тоже быть не должно!

  8   2  
 51 3    
4  9 63  
53  7    
   8  96 
 7   9   
 6 5  1  
  3   4  
 1  8  2 

ВОт и все
Кому понравилось - откликайтесь.

[Lapp]

Я немного подправил алгоритм: добавил перебор при множественном выборе. Таким образом, программа должна теперь находить все возможные решения. По всей видимости, она это и делает, хотя проверить это я не возьмусь . Скажем, в том примере, который привел ты, Bokul, решений 58884 ! Неудивительно, что первый вариант программы отказался ее решать..
Те задачи, которые я брал из местной газеты, полностью детерминированы - они имеют одно решение. Но если (случайно ) стереть в них одну циферку, то количество решений увеличивается, и неслабо.

Выкладываю новый код.
Я убрал из него (закомментировал) вывод по шагам, теперь выдаются только решения - по нажатии любой клавиши, кроме Esc и пробела. Esc выводит из программы, а пробел включает/отключает режим выдачи решений без остановки (это я сделал, когда рука устала держать клавишу при проверке примера Bokul'а ).

Метод перебора возможных комбинаций включает в себя рекурсию. В ТР, думаю, может происходить переполнение стека.. Я пробовал только в FPC.

Вот пока и все. Следите за новыми выпусками нашей программы!! ))))

 sudoku_2.pas ( 3.04 килобайт ) Кол-во скачиваний: 1576