Разминка мозгов

[swizard]

А какие бы вы предложили красивые варианты сгенерировать рандомное поле для судоку?

Мне, как инженеру неголубых кровей, помимо тупого брутфорса идей никаких не приходит =)

(defun gen-field ()
(let ((field (make-array '(9 9) :initial-element 0)))
(macrolet ((cell (r c) `(aref field ,r ,c)))
(labels ((is-valid (r c

Comments

[ext_208668]

Гы, помню писал это плюс решалку, когда начинал знакомиться с CL (и попутно читал "Искусственный интеллект. Современный подход"), но осталось где-то на старом винчестере, среди хлама...

[zevlg]

не уверен, что у тебя будут генериться uniq-solution судочьки

в пакете games под (S)XEmacs есть sudoku.el с генератором достаточно интересных судочек - http://alioth.debian.org/scm/viewvc.php/XEmacs/packages/xemacs-packages/games/sudoku.el?view=markup&root=xemacs

[zevlg]

в тему, об одной интересной судочке - http://sxemacsen.blogspot.com/2009/11/sxemacs.html

[ext_229877]

Берёшь любое валидное поле для судоку и путем набора случайных изменений, не меняющих основного свойства поля получаешь рандомное.

За пару минут придумал только два изменения:
1) поменять местами любые две строчки,
2) поменять местами любых два столбца.

Пример:
а) дано базовое поле
1 2 3
2 3 1
3 1 2

б) меняем местами два столбца
2 1 3
3 2 1
1 3 2

в) меняем местами две строчки
3 2 1
2 1 3
1 3 2

[ext_229877]

...правда для поля 9x9, в котором суммы субквадратов 3x3 должны сохранятся правило несколько ужесточается: менять местами можно только строчки и столбцы с индексами i, j, такими что floor(i / 3) = floor(j / 3). Тем не менее, мне думается что и этот способ даёт достаточную гибкость.

Теперь пара более сложных упражнений:
1) доказать или опровергнуть что этим способом можно получить все возможные судоку,
2) перенумеровать все возможные поля судоку и генерировать поле по номеру поля.

[ki11obyte]

Как то давно столкнулся с такой же проблемой, когда писал курсовую на первом курсе.

Все просто берется валидное поле 9х9 (можно сгенерировать простым смещением строк)
и несколько раз делается одно из действий

1. перестановка секторов (первая, вторая или третья тройка столбцов/строк)
2. транспонирование
(вроде что то еще было, но не помню)

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