Судоку: алгоритм нахождения решения

Итак, сделал графический интерфейс к игре Судоку.
Исходники и бинарник тут: http://forum.sources.ru/index.php?act=Atta...post&id=2065842

Всем, кому интересно - могут свободно брать прогрмму за основу и дорабатывать.
Алгоритм поиска решения находится в sudoku_solve.h.

Чтобы заполнить поле надо нажать мышкой на нужную клетку и ввести цифру.
Такую систему подсмотрел в какой-то другой программе, с закрытым кодом +)

Основной вопрос: подскажите плз с алгоритмом. А то на некоторых комбинациях он зависает.

Сейчас он такой:
1. Ищется пустая клетка с наименьшим числом кандидатов.
2. Туда подставляются возможные варианты и рекурсивно выполняется п. 1.

int SudokuSolveRecursive(BYTE ** pData)
{
    CPointSudoku pt;
    int iRet;
 
    // ищем клетку с наименьшим числом кандидатов:
    iRet = SudokuFindMinPoint(pt, pData);
 
    if (iRet == 0) return 1; // решение найдено
    if (iRet == -1) return -1; // тупиковая комбинация
 
    BYTE ** pSaveData = SudokuCreateTempArray(pData);
    SudokuCopyArray(pData, pSaveData); // сохраняем то, что есть
 
    for (BYTE variance = 1; variance <= 9; variance++) // пытаемся ставить на найденную клетку цифры от 1 до 9
    {
        pData[pt.i][pt.j] = variance;
        if (! CheckSudoku(pData)) continue; // такую цифру поставить нельзя. берём следующую.
    
        iRet = SudokuSolveRecursive(pData); // запускаем функцию рекурсивно
 
        if (iRet == -1) // тупиковая комбинация
        {
            SudokuCopyArray(pSaveData, pData); // восстанавливаем массив и берём следующую цифру на то же место
            continue;
        }
 
        if (iRet == 1) // решение найдено
        {
            SudokuDeleteTempArray(pSaveData);
            return 1;
        }
    }
 
    SudokuDeleteTempArray(pSaveData);
    return -1;
}

Сообщение отредактировано: Dr4k0n - 15.11.08, 19:07

Цитата Dr4k0n @ 22.06.07, 16:41

А то на некоторых комбинациях он зависает.

Так и будет виснуть. Сколько раз сталкивался (в печатных судоку), когда в финале возможные два варианта расстановки чисел. Оба равновероятных.

Не очень понял... Причём тут равновераятные или нет?
Это же тупой перебор, правда немного оптимизированный:
1. Отсечение неподходящий кандидатов
2. Направление поиска от минимального числа возможных кандидатов в клетку.

Добавлено 22.06.07, 17:28
Понял, о чём хотели сказать.
Но моя прога на этом не запорится.
Она выйдет на первом попавшемся решении.

http://rus.postimees.ee/081106/glavnaja/razvlechenija/7603_foto.php - "самую сложну в миру судоку" программка решила за 10 секунд.

Судоку NP-hard. Исходник этот работает только для так называемых детерминированных судоку.

Цитата ArdI @ 26.06.07, 17:55

Исходник этот работает только для так называемых детерминированных судоку.

А что есть детерминированные и недетерминированные судоку?
В чем их разница?

Цитата tserega @ 27.06.07, 05:29

А что есть детерминированные и недетерминированные судоку?

Наверно, детерминированные ("определённые") -- имеющие одно и только одно решение; недетерминированные --

Цитата Flex Ferrum @ 22.06.07, 16:57

когда в финале возможные два варианта расстановки чисел. Оба равновероятных

ну или более.

Сообщение отредактировано: kopilov - 27.06.07, 09:52

Цитата

Наверно, детерминированные ("определённые") -- имеющие одно и только одно решение; недетерминированные --

детерминированные это те, в которых на каждом шаге можно однозначно определить цифру в какой либо клетке. Однозначно, в плане используя детерминированный алгоритм.

Вообще: все детерминированные точно однозначные, а вот верно ли обратное? Т.е. есть какой-то судоку, а определить что туда поставить нельзя, но решение одно. Может кто умеет это доказывать/опровергать ?

Сообщение отредактировано: ArdI - 28.06.07, 08:13

Я попробовал визуализировать процесс поиска...
Получился какой-то странный результат.
Алгоритм зависает (т. е. поле периодически то заполняется полностью, то делается откат до 10 клеток) на глубине рекурсии около 60-75 уровней. А на поле остаётся около 10 незакрытых клеток... И вот он их мусолит +))
В итоге так и не разобрался.

Цитата Dr4k0n @ 28.06.07, 14:59

В итоге так и не разобрался.

Да все нормально, не смотря исходника. Если ты используешь поиск в глубину, то если на какой либо ветке сделаешь неправильный выбор, то тебе придется перебрать все ветви которые идут дальше. Видишь ты по 10, потому что эта такая скорость твоего алгоритма+визуализации, он их заполняет и откатывает. Если оставишь на сутки может и дождешься

В общем скорость решения твоего алгоритма зависит от удачи. Могу посоветовать почитать кнута DancingLiks или DLX
скорость решения судоку всегда константна(вроде)

Sazabis
Разумеется, не более чем k*10^81 Откат в алгоритме из-за его жадности. Вообще жадность не гарантирует правильный выбор, это вероятнотностный( имеется в виду эвристический) алгоритм. Кто-нибудь по сабжу мне что-нить скажет ? (см. пост выше).

Сообщение отредактировано: ArdI - 29.06.07, 10:03

Dr4k0n, приведи плз примеры расстановок, в которых зависает!

Цитата ArdI @ 28.06.07, 21:09

Кто-нибудь по сабжу мне что-нить скажет ?

Цитата ArdI @ 28.06.07, 08:01

Т.е. есть какой-то судоку, а определить что туда поставить нельзя, но решение одно. Может кто умеет это доказывать/опровергать ?

по этому ?

есть техника перебора, с которой машина справяется на порядки быстрее, а есть логика, которая дает, как бы это сказать..., удовлетворение, чтоли. Так вот если тебе надо быстро решить, тоесть составить, скажем, судоку используешь DLX Кнута, а если нужна логика... то добро пожаловать в сообщество судокистов

Могу сказать сразу, что в сложном судоку, полно комбинаций в которых нельзя точно сказать где стоит цифра. Но! используя логику, можно сказать, где она не стоит. Так как логических алгоритмов много, и действенный может оказаться только один, то логическое решение судоку машиной, занимает больше времени.

тебе нужны примеры логики ?

Sazabis
Не по теме вы мне ответили. Логика эта , которая говорит где что не стоит - это и есть детерминированный алгоритм. Речь то не об этом. Речь идёт о том, верно ли, что есть такой судоку, который однозначен, но взять его нельзя каким либо непереборным алгоритмом. В том чисе логикой. Т.е. не будет дерева вариантов никакого.

Смотря что считать перебором, если искать пары чисел, скажем в двух ячейках в линию есть воможность поставить только 1 и 2, не нарушая правила, следовательно, мы можем из всех остальных ячеек в этой линии, где есть возможность поставить 1 и/или 2 убрать эти варианты. Логично ? да. Перебор есть ? вроде как надо перебрать все пары 1,2 1,3 1,4 ... 8,9 ? если принять что для логического хода можно пользоваться перебором, то любой судоку "взять".

Есть например такая стратегия Nishio для выбранной цифры, помещаем ее в спорную ячейку, потом расставляем остальные цифры на доску, если получим противоречие, то можем удалить кандидата из спорной ячейки. Перебор ? сложно сказать.

Есть другая достаточная версия решения Trial & Error, ставим цифру в ячейку, решаем дальше, если получаем противоречие, раскручиваем назад и помечаем, что эту цифру в эту ячеку ставить нельзя. Это не совсем перебор, так как цель найти противоречие, раскрутить назад и удалить кандидата. Перебор ? вполне можно так считать.

Есть техники которые основаны на просмотре цепочек


Перебор ?

Sazabis
Да, в терминах перебора сложно определять, согласен.

Цитата

Есть например такая стратегия Nishio для выбранной цифры, помещаем ее в спорную ячейку, потом расставляем остальные цифры на доску, если получим противоречие, то можем удалить кандидата из спорной ячейки. Перебор ? сложно сказать.

Ну вот это-то точно перебор.

Цитата

Есть другая достаточная версия решения Trial & Error, ставим цифру в ячейку, решаем дальше, если получаем противоречие, раскручиваем назад и помечаем, что эту цифру в эту ячеку ставить нельзя.

Ну-да, "раскручиваем назад"- это наверно не перебор )

будем вот какое определение использовать: Судоку называется детерминированным, если на каждом шаге существует клетка [i,j] обладающая след. свойствами:
1) поиск этой клетки полиномиален
2) существует полиномиальный алгоритм, который выдаёт число, которое должно стоять в этой клетке, чтобы ничего не испортить.он будет гарантировать единственность цифры к тому же. (самый худший случай)
(разумеется считаем что P != NP)

Что такое "однозначное судоку" мы выше поняли. Ну вот и теперь вопрос : есть ли однозначный судоку, который не явл. детерминированным ? Я думаю теперь понятно, что я имею в виду.

Сообщение отредактировано: ArdI - 30.06.07, 10:05

Цитата ArdI @ 30.06.07, 10:02

Что такое "однозначное судоку" мы выше поняли. Ну вот и теперь вопрос : есть ли однозначный судоку, который не явл. детерминированным ? Я думаю теперь понятно, что я имею в виду.

понял.

Цитата ArdI @ 30.06.07, 10:02

2) существует полиномиальный алгоритм, который выдаёт число, которое должно стоять в этой клетке, чтобы ничего не испортить.он будет гарантировать единственность цифры к тому же. (самый худший случай)
(разумеется считаем что P != NP)

если поправите своё условие, то можете считать, что все судоки детерминированы. Так как по сути это конечный автомат с набором состояний.
Поправить условие надо так, чтобы за ход принималось не нахождение цифры, а нахождение цифры или удаление кандидата.
например, если посмотреть на две пары, то они вычеркивают кандидата из ячейки( звездочка )

. . . | . . . | . . . 
. . c-----------d . . 
. a . | . . . | . . . 
--|------------------ 
. | . | . . . | . . . 
. | . | . . . | . . . 
. | . | . . . | . . . 
--|------------------ 
. b . | . . . | * . . 
. . . | . . . | . . . 
. . . | . . . | . . .

но сказать куда можно поставить цифру не могут, однако след. ходом, возможно, в ячейке со звездочкой останется только один кандидат.

насколько мне известно, а известно мне далеко не все, алгоритмов нахождения хода огромное множество, но вроде как в одной программе это все не реализовано. Поэтому часто встречаются так называемые unsolvable судоку.

В общем, твой вопрос может быть ориентирован на игрока или программу. Сама судока всегда имеет возможность перейти в следущее состояние однозначно. Такие методы решения как 3D Medusa находят ответ за полиномиальное время без гаданий, но их охват сложноват для человека...

Вот, собственно, хочу еще добавить, что реально создать судоку, пока еще(?) , чтобы компьютерный алгоритм выдал сообщение guess required например реально завалить http://www.sudokusolver.co.uk/ решатель

Sazabis
Угу. Вот это, то что вы привели - я об этом и говорил. Единственное, что данный пример ессно не явл. детерминированным согласно условию. Вот это "правило следующего хода" всё портит. Если такие судоку есть, то ответ на вопрос выше "детерм != однозначный". Из данного примера ничего толком сказать нельзя ) надо конкретный судоку посмотреть.

Тема уже проскакивала...
Японская головоломка.
Dr4k0n, ошибка вот в чём: рекурсивная функция не возвращает 1, когда вызвана для массива со всеми заполненными клетками. Поэтому решения она не замечает! Хотя нет, вроде есть в программе такое условие.

Сообщение отредактировано: Habitus aegroti - 01.07.07, 08:09

Habitus aegroti, твоя судоку
...54.........18......38....497..5...51.9..3.37.1....4.1547.39.......6.......5...
решается чисто логически

Ну не знаю... Sudokusolver, по идее, тоже решает логически, и делает допущения, если логики недостаточно. Он посчитал это судоку сложным (правда, я потом посмотрел, со статистикой на сайте проблемы: там есть судоку и со сложностью более 80000). Может, если применять продвинутые логические методы, то можно решить и без допущений.

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

+-------+-------+
| . . . | 3 6 . |
| . . . | . . 4 |
+-------+-------+
| . . 1 | . . 6 |
| 2 . . | 5 . . |
+-------+-------+
| . 1 . | . . . |
| 3 . 4 | . . . |
+------+--------+

Я както тоже задумывался над судоку. в итоге получилась сумбурная программа которую не прочь бы и переписать. Суть в ней такая:
1. Определяем все одиночные кандидаты
2. Проставляем их
3. Снова все одиночные
4. Если одиночных нет
5. Берем двойные кандидаты в одной клетке одного квадратика и предположительно ставим одну цифру в одну позицию, вторую цифру в другу позицию
6. снова пункт 1
7. Если где то зависло. то есть цифр больше нет куда можно поставить, а пустые клетки остались. значит предположение было не верно и снова пунк 6 и теперь меняем числа местами.
....
....
Обычно после 1, или 2 подстановки Двойных кандидатов, вся раскладка решается влёт..
но когда она не решается.. в делу вступает алгоритм перебора. который случайно выбирая оставшиеся цифры из "корзины" и проставяля их в оставшиеся клетки, доводит в течение 2-10 минут решение судоку до логического завершения. Обыно до перебора доходит редко.

PS. в прикрепленной программе. алгоритм подстановки двойных кандидатов не работает. То етсь после того как исчезли все одиночки, начинается перебор. Обычно на самых простых раскладках перебор не учавствует, но на сложных как правило приходится ждать минут 10. Свёрнутая программа ускорит процесс.

Цитата

Вот я хочу ее переписать на телефон а то журнальчик с конкурсными судоку иногда раз да попадется а компьютера то и и нет чтоб рашить.

в общем кому интересно можете посмотреть.
Прикреплённый файлsudoku_mind_crash.zip (253.79 Кбайт, скачиваний: 670)

любые судоки решаются за доли секунды, читаем кнута
http://www.sudopedia.org/wiki/Dancing_Links

В помощь просящим залил исходник на форум.
Прикреплённый файлSudoku.zip (45.27 Кбайт, скачиваний: 4869)

вот еще пример решения "СУДОКУ" на Delphi ...
Прикреплённый файл_Sudoku_.rar (79.47 Кбайт, скачиваний: 746)

Цитата andrew.virus @ 10.09.08, 18:57

вот еще пример решения "СУДОКУ" на Delphi ...

А вот и контрпример:

 . . . . 8 . . 6 .
 5 . 4 3 . . 9 . .
 . 1 . . 9 . . 4 .
 . . . . . . . 8 .
 1 . 7 . . . 3 . 6
 . 4 . . . . . . .
 . 9 . . 4 . . 2 .
 . . 3 . . 6 4 . 5
 . 2 . . 5 . . . .

Решение:

 7 3 9 4 8 1 5 6 2
 5 6 4 3 7 2 9 1 8
 2 1 8 6 9 5 7 4 3
 9 5 6 1 3 7 2 8 4
 1 8 7 9 2 4 3 5 6
 3 4 2 5 6 8 1 7 9
 6 9 5 7 4 3 8 2 1
 8 7 3 2 1 6 4 9 5
 4 2 1 8 5 9 6 3 7

(взято наугад из печатного Сум-до-ку №21'08, зад. 59)

выложите пожалуйста исходники на делфи, у кого есть. Очень надо, это тема курсовой, не сдам отчислят(((

zaykiy посмотри вот этот пост данной темы ...

zaykiy, а тему почтитать полностью? не? не прикалывает? пост номер 26 или не то?

Вот написал решалку :
Обновлялка
Архив с прогой

Оцените пожалуйста .

Там исходников нет только бинарник кому очень надо могу выложить исходник самого решения

Сообщение отредактировано: kilop - 05.10.09, 17:59

ЛЮДИ, надо написать программу, которая выясняет правильно ли написан судоку.
язык: С++
Среда: Borland C++ Builder 6
работа со входным (сам судоку 9*9) и выходным (CORRECT/INCORRECT) файлом.
есть код написанный в Visual Studio, но чего-то не получается ничего с ним

Тестируем алгоритм проверки судоку: sudoku-solver.awardspace.biz/

Сообщение отредактировано: Proverka - 19.06.10, 18:19

в Ubuntu Netbook Remix есть судоку, можно глянуть сорцы

Люди, помогите, пожалуйста! Приведенный код

Цитата

int SudokuSolveRecursive(BYTE ** pData)
{
CPointSudoku pt;
int iRet;

// ищем клетку с наименьшим числом кандидатов:
iRet = SudokuFindMinPoint(pt, pData);

if (iRet == 0) return 1; // решение найдено
if (iRet == -1) return -1; // тупиковая комбинация

BYTE ** pSaveData = SudokuCreateTempArray(pData);
SudokuCopyArray(pData, pSaveData); // сохраняем то, что есть

for (BYTE variance = 1; variance <= 9; variance++) // пытаемся ставить на найденную клетку цифры от 1 до 9
{
pData[pt.i][pt.j] = variance;
if (! CheckSudoku(pData)) continue; // такую цифру поставить нельзя. берём следующую.

iRet = SudokuSolveRecursive(pData); // запускаем функцию рекурсивно

if (iRet == -1) // тупиковая комбинация
{
SudokuCopyArray(pSaveData, pData); // восстанавливаем массив и берём следующую цифру на то же место
continue;
}

if (iRet == 1) // решение найдено
{
SudokuDeleteTempArray(pSaveData);
return 1;
}
}

SudokuDeleteTempArray(pSaveData);
return -1;
}

, попыталась переложить на C#. На первой же тупиковой ситуации он вылетает и токат не делает.

Вот мое решение на Java: http://sites.google.com/site/sudokujavasolution/

Всем доброго времени суток. Нужна ваша помощь, уважаемые специалисты!!! Получил задание сделать судоку, чтобы при входе в игру первоначальные данные генерировались случайным образом, а после решения пользователь мог проверить правильность своего решения. Как это можно сделать? Кто знает напишите пожалуйста. Очень надо. Заранее спасибо!!!

Sudopedia поможет ответить на многие вопросы по тому как решаются судоки, как они проверяются и какие есть вариации.
Если интересует готовое решение, то есть код на С++, от игры судоку, с разными вариациями и уровнями сложности, за вознаграждение.

я неувер что все правельно напписал но вот
пример работает
реализован на Delphi (Rad Studio 2009)

Прикреплённый файлSudoku.rar (19,93 Кбайт, скачиваний: 555)

Прикреплённый файлSudoku.rar (196,17 Кбайт, скачиваний: 509)

Сообщение отредактировано: Mishamp - 22.03.11, 15:21