Консультация № 55432
14.09.2006, 13:55
0.00 руб.
0 15 1
Доброго времени суток!
Задача следующая: игра Судоку (квадрат 9х9, числа от 1 до 9 не должны повторятся ни в строке ни в столбце ни в малых квадратах).
Уже есть какой-то набор цифр в квадрате (не все). Необходмимо проверить количество вариантов решения этого кроссворда.
Помогите с алгоритмом

Обсуждение

Неизвестный
14.09.2006, 14:28
общий
это ответ
Здравствуйте, Dush!

Если числа не повторяются, то решение представляет собой таблицу умножения для группы порядка 9. Таких групп всего две - C9 (циклическая) и C3xC3. Но в каждой из групп строки и столбцы могут быть переставлены в произвольном порядке, плюс, элементы группы могут обозначаться разными цифрами. Так что всего решений (в общем случае):
2*9!*9!*9!=95 569 451 679 744 000
Ваша задача - найти, сколько из этих решений совпадают с Вашим набором цифр. Ясно, что перебором здесь и не пахнет. Нужно исходить именно из теоретико-групповых методов. Как - пока незнаю (можно попытаться что-нибудь получить из предположения, что i-ый столбец и j-ая строка соответствуют единичному элементу...), если что придёт ещё в голову - напишу в минифорум.
Неизвестный
14.09.2006, 14:29
общий
В первую очередь, мне видится такое решение: Там где возникает неоднозначность, делаем ветвление с помощью рекурсивного вызова. Рекурсия обрубается по тому, что квадрат решен, и результаты работы сохраняются в массив. Далее пробегаем по массиву и находим, сколько там различных элементов.Впрочем, достаточно легко написать такой алгоритм, который не выдает одинаковых решений на терминальных вызовах рекурсии.
Неизвестный
14.09.2006, 14:38
общий
2 Сухомлин Кирилл Владимировича что такое " терминальные вызовы рекурсии"?
Неизвестный
14.09.2006, 14:50
общий
Это те вызовы, из которых больше не происходит других вызовов. терминальные ~ конечные (terminate - завершать)
Неизвестный
14.09.2006, 15:37
общий
Вообще-то с числом вариантов - это я загнул. Их максимум 81(клеток)х9(цифр)=729. Так что перебрать все варианты - не проблема.
Неизвестный
14.09.2006, 15:49
общий
Вот примерный алгоритм:massiv[i,j] - массив, заполненный введенными цифрами, если ячейка пустая - 0.FullCheck - полная проверка что нет совпадений в рядах/столбцахPreCheck - неполная (для уже заполненной части таблицы)FullCheck и PreCheck могут быть одной и той же функциейglobal massivglobal count=0check(1,1);procedure check;begin  if (posi,posj)=(9,9) then begin    if FullCheck then count=count+1  end else begin    if PreCheck then begin      (posi,posj)=next(posi,posj)      if massiv[posi,posj]=0 then begin        for i=1 to 9 do begin          massiv[posi,posj]=i;          check;        end;        massiv[posi,posj]=0;      end else check;      (posi,posj)=prev(posi,posj)    end;  end;end;
Неизвестный
14.09.2006, 15:52
общий
Что-то вас бросает из крайности в крайность =)А просто расставить случайные цифры от 1 до 9 в 81 клетку можно 9^81 (2E+77) способами. Когда придете к точно правильному решению - напишите его. Я пока тоже подумаю над числом вариантов.Более хорошая оценка сверху - (9!)^9 (1E+50)Если еще немного подумать, то можно получить след: 9!*8!*...*2! (2E+21). Еще очень много, но оценка уже близка к истине =)
Неизвестный
14.09.2006, 16:02
общий
2Сухомлин Кирилл Владимирович:Н-да, наверное исходное число правильное.
Неизвестный
14.09.2006, 16:12
общий
Можно для каждой из двух групп делать все возможные перестановки строк/столбцов и проверять, можно ли исходные данные наложить на эту таблицу. Если да, то в итоге часть элементов (N) группы будет иметь конкретные числа, а остальные могут быть выбраны (9-N)! способами.Тогда нужно перебрать "всего" 263 363 788 800 варианта. Это уже куда более лёгкая задача.
Неизвестный
14.09.2006, 16:15
общий
Плюс, можно учитывать, что если в матрице есть пустые строки/столбцы (m штук), то их тоже можно учесть множителем m! (не уверен, точно ли m!), а перестановку делать только на множестве занятых строк/столбцов.
Неизвестный
14.09.2006, 16:41
общий
Спасибо за ответы и советы! Сейчас качаю книжку посвященную програмированию Судоку (правда на аглецком ну да ничего). Ежели нужно могу дать ссылкуеще раз спасибо
Неизвестный
14.09.2006, 16:55
общий
Давайте ссылку =)
Неизвестный
14.09.2006, 16:59
общий
http://depositfiles.com/ru/files/203372/ProSud.rar.html
Неизвестный
14.09.2006, 17:11
общий
Что-то медленно качается (15Кб/с).А у меня пока "в догонку" появилась еще мысль о том, что при перестановках строк/столбцов в группе тоже можно делать PreCheck. Так что, может быть, можно сделать решение задачи за конечное время.Посмотрим, что будет в книге.
Неизвестный
14.09.2006, 17:15
общий
Там есть еще такое правило:Additionally, each minigrid must contain all the numbers 1 through 9.Думаю, это должно заметно сократить как время перебора, так и число вариантов.
Форма ответа