Ребята здраствуйте!
Тут есть одна интересна игра называется Судоку(Sudoku).
Информация о игре здесь

Предлогаю на форуме обсудить алгоритмы её решения, не просто тупой перебо, а какие-нибудь алгоритмы связаные с KI


Зарания всем благодарен.

ну подобные задачи чаще всего решаются перебором с какими-нибудь модификациями
самая частая модификация - отсечение какого-нибудь множества вариантов
еще один вариант - перебор в каком-то определенном порядке

тут сразу же добавляется отсечение - проверка корректности после каждой поставленной цифры
дальше, как мне кажется, нелишним будет упорядочвание перебора: сначала искать те клетки, где количество вариантов наименьшее
если оно - 0, сразу ясно, что надо делать откат
если 1 - и перебора никакого нету
2 - перебрать два варианта

это немного замедлит рост количества вариантов по мере углубления...

Я тут в интернете почитал многие к этой проблемме подходят с матиматической точке зрения, некотыре испльзуют какой-то Sword Fish
Кто что про эти методы знает.

писал пару дней назад перебор на эту задачу, но для поля 5*5 он загибался. 4*4моментально работает.

А скажите лучьше, как генерить это самое поле 9х9?

По-моему более разумно не заниматься перебором, а строить трехмерный массив вариантов расположения с удалением невозможных.

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

Пара реализаций решателя sudoku на Erlang:
http://www.erlang-consulting.com/obfuscatederlang.html
http://www.mail-archive.com/[email protected]/msg00274.html

Генерил рекурсией.
Есть даче код на Jave, отрабатывает за доли секунды.

Есть еще dancing links algorithm Кнута, смотри линк, там есть пример для судоку

boevik, на ВБ можешь сделать исходники?

В принципе, не должно быть проблемным.
Можешь и сам попробовать, код не сложный.

boevik, я пытался сам, но у меня нифига не вышло. Даже на сайте посвященному чисто программированию судоку исходники рабоают неправильно. Т.е. лбо по вертикали, либо по горизонтал, либо в блоках цифры повторяются.Так что, если не жалко, помоги?

Выкладываю исходники на Java, будут затруднения пиши:



Всё начинается с запуска 
результатом является заполненое поле table.
Если надо получить поля для отгадывания, то есть другая функция которая рандомально затирает цифры в заполненом поле.

Удачи

Спасибо. Попытаюсь разобраться. Хотя я в Яве не шарю, я васче кроме вб и паскаля нде ни шарю, но это дело поправимое.

Переложил на VB, ни фига не работает. Переменная digit принимает значения большее 9. Почему так?

Выкладывай кодна VB, с VB я немного знаком.

digit%10 -> digit mod 10  - это выполнил?

самый разумный алгоритм...сначало заполнить матрицу...потом сохранить ее в вирт массиве.

и в зависимости от сложности отчистить ее, оставив нужное количество цифер

http://ru.wikipedia.org/wiki/Судоку
http://ru.wikipedia.org/wiki/Обобщённое_судоку

http://en.wikipedia.org/wiki/Sudoku
http://en.wikipedia.org/wiki/Mathematics_of_Sudoku

http://fr.wikipedia.org/wiki/Sudoku

Да, и не забывайте, что задача обобщённого судоку NP-полна => полиномиального решения не существует (по крайней мере, до тех пор, пока мы глобально не пересмотрим существующую теорию вычислений). Лучший здесь вариант -- это, имхо, оптимизированный «умный» перебор.


Это сообщение отредактировал(а) V_A_KeRneL - 29.12.2006, 09:42

http://markbyers.com/moinmoin/moin.cgi/ShortestSudokuSolver

Ох. С Си плохо знаком, а еще и написано нечитабельно 
Кто нибудь в Алгол может перевести?

Вот алгоритм boevik переписанный на Delphi:

Помоему прога от "boevik" много лишнего делает.
Алгоритм можно упростить.




Пусть есть матрица  ,удовлетворяющая правилам судоку . Например А = 
-------------------------------
| 0  3  6 | 1  4  7 | 2  5  8 |
|            |            |            |
| 1  4  7 | 2  5  8 | 0  3  6 |
|            |            |            |
| 2  5  8 | 0  3  6 | 1  4  7 |
+---------|---------|---------|
| 3  6  0 | 4  7  1 | 5  8  2 |
|            |            |            |
| 4  7  1 | 5  8  2 | 3  6  0 |
|            |            |            |
| 5  8  2 | 3  6  0 | 4  7  1 |
+---------|---------|---------|
| 6  0  3 | 7  1  4 | 8  2  5 |
|            |            |            |
| 7  1  4 | 8  2  5 | 6  0  3 |
|            |            |            |
| 8  2  5 | 6  0  3 | 7  1  4 |
+---------|---------|---------|


что бы получить новую, достаточно в этой поменять две строчки (или столбца) местами,
при уловии что они обе принадлежат [ 0 , 2 ] [ 3 , 5 ] [ 6 , 8 ] .

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

так например меняем первую(нулевую) строку со второй(первой), 4(3) столбец с 6(5) 

---------------------------------
| 1  4  7 | 8  5  2 | 0  3  6 |
|            |            |            |
| 0  3  6 | 7  4  1 | 2  5  8 |
|            |            |            |
| 2  5  8 | 6  3  0 | 1  4  7 |
+---------|----------|---------|
| 3  6  0 | 1  7  4 | 5  8  2 |
|            |            |            |
| 4  7  1 | 2  8  5 | 3  6  0 |
|            |            |            |
| 5  8  2 | 0  6  3 | 4  7  1 |
+---------|---------|---------|
| 6  0  3 | 4  1  7 | 8  2  5 |
|            |            |            |
| 7  1  4 | 5  2  8 | 6  0  3 |
|            |            |            |
| 8  2  5 | 3  0  6 | 7  1  4 |
+---------|---------|---------|



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



ПыСы : математика это хАрАшо, тока за неё не платят...  


Это сообщение отредактировал(а) Vsts - 10.1.2007, 22:17

Совершенно врно, прога делает много лишнего - в нее уже заложены инструменты для других решений.
К примеру, 1) можно задать начальную мартицу и найти все возможные решения решения; 
2) производить проверку ввода юзером
и т.д и т.п.