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

[Lapp]

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

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

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

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

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

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

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


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

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

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

[Bokul]

По поводу тестирования: проверял на таком файле

     8   
  85   1 
71   6   
  1      
6   4   5
 54  71  
4  18   7
 6    5  
   6     

програмка сразу вылетает, хотя решение существует

Код

546 718 392
298 534 716
713 296 458

971 365 824
632 841 975
854 927 163

425 189 637
369 472 581
187 653 249

P.S Задача и решения взято с одноименной программы
если надо могу выложить программу(чуть больше двух мегов)

Сообщение отредактировано: volvo - 2.11.2006 20:18

[Lapp]

програмка сразу вылетает, хотя решение существует
.....
если надо могу выложить программу(чуть больше двух мегов)

Она не вылетает, она сообщает, что не может решить! Это тот самый случай (множественный выбор), который я описал выше, и который требует применения другого алгоритма! Так что нужно добавить алгоритм. Другие алгоритмы есть. Вот, например, один из них.

Хотим поставить определенную цифру - например, 1. Идем по подквадратам. Если в нем уже есть 1 - переходим к следующему. Если нет - смотрим, какие строки его секут и есть ли в них 1. Затем то же со столбцами. Если в результате остается только одно одно свободное место, где в этом подквадрате может стоять 1, то ставим ее туда.

Кроме того, возможен еще перебор: если выяснено, что в некоей клетке может стоять и 1, и 2, то ставим снчала 1 и пробуем решать дальше. Не получается - возвращаемся к этой точке, ставим 2 и продолжаем.

Я же сказал - это самый первый вариант, самый простой алгоритм. Для затравки .

.....
Программу можешь выложить, но заранее скажу - я брать не буду. Я видел много в Инете, но весь интерес именно в том, чтоб сделать самому, на своих мыслях.

Добавлю еще, что делать их, конечно, интереснее, чем играть. Кстати, сейчас модно цифры расставлять в виде орнамента. Да и форму поля можно варьировать.
P.S.
в том примере, что ты выложил, есть пропущенные пробелы. Для выкладывания используй тег Code=pas, а не просто Code. Code пропускает некоторые пробелы в начале строки.