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

[Dr4k0n]

Итак, сделал графический интерфейс к игре Судоку.
Исходники и бинарник тут: 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

[Flex Ferrum]

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

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

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

[Dr4k0n]

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

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

[Dr4k0n]

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

[ArdI]

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

[tserega]

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

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

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

[kopilov]

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

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

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

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

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

ну или более.

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

[ArdI]

Цитата

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

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

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

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

[Dr4k0n]

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

[Sazabis]

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

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

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

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

[ArdI]

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

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

[tserega]

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

[Sazabis]

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

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

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

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

по этому ?

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

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

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

[ArdI]

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

[Sazabis]

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

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

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

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


Перебор ?