![]() |
![]() |
Lapp |
![]()
Сообщение
#1
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
Кто знаком с игрой Судоку?
Она появилась не очень давно, несколько лет назад. Я не знаю, насколько она сейчас распространена в России, поэтому рассказываю подробно (извините, если это излишне). По смыслу и по виду напоминает кроссворд, но в отличие от него она не буквенная, а цифровая. Хотя, цифры там используются только как значки - никаких операций над ними (сложения и т.п.) не проводится. Говорят (и я охотно этому верю), что она прежде всего завоевала популярность в Японии, потому что бедные японцы, ввиду особенностей своей письменности, лишены возможности разгадывать кроссворды - хотя появилась она на Западе. Если сейчас зайти в любой книжный, то прямо у дверей увишь специальный стенд, на котором стоит десятка два-три как тонких так и очень толстых книг с этими головоломками.. Игра довольно тупая, но видя такой бешеный успех за короткое время, я заинтересовался ей. А тут ее стали еще публиковать в университетской газете - не попробовать я просто не мог ![]() ![]() Теперь о правилах. Поле представляет собой квадрат 9х9 клеток (поделенный еще и на подквадраты 3х3), в некоторых из которых уже стоят циферки, а в остальные их нужно вписать. В результате в каждой клетке должно стоять по цифре от 1 до 9 (ноль не участвует!), причем так, чтобы в любом столбце и в любой строчке присутствовали все девять цифр. Более того, в каждом подквадрате тоже должны быть все цифры, каждой по одной. Правила очень простые. Существуют несколько методик решения, стратегий и тактик, которые разжевываются в книжках, но суть от этого не меняется. Ниже я привожу фото из университетской газеты (Bruin Daily, Apr 18, 2006), чтобы те, кто не видел, поимели представление. ![]() Ниже идет текст программы, которая решает головоломку. Алгоритм такой - берем перекрестье каждой строки с каждым столбцом, и смотрим набор цифр, который они содержат. Если в нем не хватает ровно одной цифры - вписываем ее в пересечение. Могут быть и другие алгоритмы, это лишь один из возможных. Одним шагом считается полный проход по полю, если за шаг находятся несколько таких цифр - ставятся все. Если не будет найдено ни одной, программа выдаст сообщение "множественный выбор" и остановится. Смысл в том, что нужно пробовать несколько разных вариантов. Я предлагаю народу попробовать и, может быть, предложить свои алгоритмы. Код не вычищен, прошу извинить за огрехи. Но он работает (проверено на FPC и TP). Программа требует наличие файла sudoku.dat - он текстовый, это просто построковая запись квадрата, я прилагаю образец ниже. ![]() Вот образец содержимого файла sudoku.dat. Важно: файл позиционный, то есть цифры сдигать нельзя. Более того, в строчке должны обязательно присутствовать все девять знаков (цифры и пробелы) - закрасьте приведенный пример блоком, чтобы увидеть пробелы, присутствующие там. Цифра обозначется цифрой, пустое место - пробелом или любым знаком (не цифрой или нулем). Лишних пробелов тоже быть не должно! 8 2 ВОт и все ![]() Кому понравилось - откликайтесь. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
Bokul |
![]()
Сообщение
#2
|
![]() Гуру ![]() ![]() ![]() ![]() ![]() Группа: Пользователи Сообщений: 1 117 Пол: Мужской Реальное имя: Богдан Репутация: ![]() ![]() ![]() |
По поводу тестирования: проверял на таком файле
програмка сразу вылетает, хотя решение существует Код 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 |
![]()
Сообщение
#3
|
![]() Уникум ![]() ![]() ![]() ![]() ![]() ![]() ![]() Группа: Модераторы Сообщений: 6 823 Пол: Мужской Реальное имя: Лопáрь (Андрей) Репутация: ![]() ![]() ![]() |
програмка сразу вылетает, хотя решение существует ..... если надо могу выложить программу(чуть больше двух мегов) Она не вылетает, она сообщает, что не может решить! ![]() Хотим поставить определенную цифру - например, 1. Идем по подквадратам. Если в нем уже есть 1 - переходим к следующему. Если нет - смотрим, какие строки его секут и есть ли в них 1. Затем то же со столбцами. Если в результате остается только одно одно свободное место, где в этом подквадрате может стоять 1, то ставим ее туда. Кроме того, возможен еще перебор: если выяснено, что в некоей клетке может стоять и 1, и 2, то ставим снчала 1 и пробуем решать дальше. Не получается - возвращаемся к этой точке, ставим 2 и продолжаем. Я же сказал - это самый первый вариант, самый простой алгоритм. Для затравки ![]() ..... Программу можешь выложить, но заранее скажу - я брать не буду. Я видел много в Инете, но весь интерес именно в том, чтоб сделать самому, на своих мыслях. Добавлю еще, что делать их, конечно, интереснее, чем играть. Кстати, сейчас модно цифры расставлять в виде орнамента. Да и форму поля можно варьировать. P.S. в том примере, что ты выложил, есть пропущенные пробелы. Для выкладывания используй тег Code=pas, а не просто Code. Code пропускает некоторые пробелы в начале строки. -------------------- я - ветер, я северный холодный ветер
я час расставанья, я год возвращенья домой |
![]() ![]() |
![]() |
Текстовая версия | 22.06.2025 5:18 |