Вопрос для проекта "Головоломки".
Вероятно, все знают, что такое судоку.
(На всякий случай: матрица 3 на 3 из массивов 3 на 3 (рассматриваемая также как матрица 9 на 9 из цифр 1..9) заполняется цифрами 1..9, причём:
- в каждом массиве цифра 1..9 встречается единожды
- в каждой строке матрицы цифра 1..9 встречается единожды
- аналогично для столбцов)
А вот знает ли кто-нибудь алгоритм генерации таблиц-судоку? Несомненно, метод прямого перебора работает, да только мой процессор этого не выдерживает.
Уважаемые авторы вопросов! Большая просьба сообщить о результатах решения проблемы на этой странице. Иначе, следящие за обсуждением, возможно имеющие аналогичные проблемы, не получают ясного представления об их решении. А авторы ответов не получают обратной связи. Что можно расценивать, как проявление неуважения к отвечающим от автора вопроса.
11-12-2009 05:20 | Комментарий к предыдущим ответам
странно... написал генератор в лоб. т.е. перебор, по сути
1000 судоку генерит за 3 секунды.
27-10-2009 16:03 | Комментарий к предыдущим ответам
Вот тут расписан отлично и быстро работающий алгоритм: http://malover.ucoz.ru/sudoku
Генерация происходит отдельными блоками, а не поэлементно. Читайте, короче (способ 3).
Это скрипт, "безболезненно" убирающий цифры из случайных ячеек таблицы, так чтоб решение было все еще однозначным. Зверским поиском вообще всех цифр, которые можно убрать, я не занимался.
Используется набор из восьми карт расположения цифр в таблице, а потом уже очищаются ячейки.
Карта - это строка типа 'abcdefghi', затем случайным образом буквы заменяются на цифры.
Что интересно, вариантов замены символов из строки 'abcdefghi' на цифры аж больше 350 тысяч.
(9*8*7*6*5*4*3*2*1=362880)
У меня таких карт восемь. Мог бы и восемь тысяч таких наделать, но генерация с чистого листа перспективнее. Поленился, то бишь.
14-08-2008 16:33 | Комментарий к предыдущим ответам
Кажется я придумал вполне простой в плане программирования алгоритм создания исходных таблиц судоку. Из них потом можно убирать циферки и головоломка готова. Все пока еще в процессе, обязательно отпишусь.
Будет настроение - даже исходник дам и объясню как это работает.
решалка судоку. Решает головоломку одночзначным образом. Т.е. если дальше цифры не ставятся - работа завершается и остаются пустые клетки. Дальше, мол, думайте сами.
А вообще тоже ищу алгоритм составления исходных таблиц судоку, из которых потом можно убирать цифры. Я лично голосую за удаление цифр не просто бездумным рандомом, а с проверкой, можно ли цифру удалить безболезненно - чтоб решение все еще оставалось однозначным.
26-05-2008 06:57 | Комментарий к предыдущим ответам
Как-то хотел я такую программулечку сделать, да все времени нет. Но делал бы так. Вводим следующие основные операции:
1. анализ строки
2. анализ столбца
3. анализ квадрата 3х3
Анализ заключается в переборе свободных клеток в объекте и попытке записать в клетку все недостающие числа. Как только число подбирается или все числа перебраны - переходим к следующей клетке. При проверке, может ли число находиться в клетке делаем:
1. при анализе строки - наличие числа в столбце и в квадрате
2. при анализе столбца - наличие числа в строке и в квадрате
3. при анализе квадрата - наличие числа в столбце и в строке
На каждом шаге:
1. запускаем анализ всех строк
2. запускаем анализ всех столбцов
3. запускаем анализ всех квадратов
(порядок может быть любым)
и циклим это все, пока не останется незаполненных клеток.
Примерно так сам и решаю. Берем клетку. Смотрим: 1 можно вставить? Можно - вставляем и идем к следующей. Иначе: 2 можно - да/нет. 9 можно = да/нет. Если 9 - нет, то оставляем клетку пустой. Человек, правда, подходит более интелеектуально в ряде случаев, но и эти случаи можно запрограммировать.
Однако, такой подход не пройдет для некоторых сложных вариантов, когда все возможные клетки заполнены, а оставшиеся нельзя заполнить, пока в какую-то из оставшихся не вставишь число, которое скорее всего должно там быть (я такие называю вероятностными клетками). Если угадал число правильно, то все решается нормально. Если неправильно - вставляем другое число или число в другую клетку и повторяем все заново.
Надеюсь идею описал более-менее понятно. :)
04-08-2007 11:50 | Комментарий к предыдущим ответам
По составлению программы-судоку вполне можно использовать алгоритм Андерсена (если скляроз в отлучке). Суть метода такова:
1.- для начально заданной матрицы составляем массивы степеней свободы для строк (во сколько клеточек в строке можно воткнуть данную цифру) и сттолбцов (то же самое, но для столбцов);
2.- сортируем суммы степеней свободы для каждой клетки матрицы (столбец+строка);
3.- выбираем миниммальную сумму (положительную - в идеале - 2=1+1 :) );
4.- тыкаем туда число;
5.- пересчитываем матрицу и соответственно суммы для клеток;
6.- переходим к шагу 3.
Есть небольшой ньанс: при попадании в столбец или строку цифры 0 - данная клетка не может быть заполнена. Эту проверочку нужно предусмотреть.
Данный алгоритм часто используется при решении олимпиадных задач. Так например задача "Острова" - более известная как японский сканводр - решалась именно им :) Ну и там ферзи всякие и т.п.
12-07-2007 07:23 | Комментарий к предыдущим ответам
Я в свое время написал программу для решения судоку 4х4 ( =) ), 9х9 и 16х16.
Использовал только логику ну и (там, где логика сдавалась), перебор.
В принципе работало это очень быстро.
19-05-2007 18:06 | Комментарий к предыдущим ответам
Если оставлять от rnd открытые ячейки, то игра будет иметь решения :
... 18 открытых ячеек - более 150 решений
27 более 100 решений
Пишут, что можно решать (и генерировать) судоку методом раскраски графа: http://en.wikipedia.org/wiki/Algorithmics_of_sudoku
Кстати, там же приведен пример для 17-ти открытых клеток (в головной статье написано, что 17 - это пока наименьшее известное на данный момент число открытых клеток, дающее единственное решение).
21-10-2006 01:11 | Комментарий к предыдущим ответам
А еще интересней, как открыть в сгенеренной таблице цифры так, чтобы решение было единственный.
Если оставлять от rnd открытые ячейки, то игра будет иметь решения :
... 18 открытых ячеек - более 150 решений
27 более 100 решений
36 более 30 решений
45 единицы решений
54 единственное решение
Спасибо, Panda!
Работает даже быстрее, чем я думал...
До этого генерировал ламерским способом: отражал и поворачивал две несчастные таблицы (из двух сделал 10). Удивительно, но никто не пожаловался на однообразие - наверное, из-за случайного определения известных с самого начала значений.
А если делать перебор так: сгенерировать все множество массив 3х3 - их будет 9! = 362880. Это же множество можно использовать как возможные комбинации составления этих матриц между собой. После чего в цикле прогнать проверку на валидность каждой таблицы (проверку по строкам и полям).
Если вы заметили орфографическую ошибку на этой странице, просто выделите ошибку мышью и нажмите Ctrl+Enter. Функция может не работать в некоторых версиях броузеров.
