Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[18.189.180.244] |
|
Страницы: (3) [1] 2 3 все ( Перейти к последнему сообщению ) |
Сообщ.
#1
,
|
|
|
Итак, сделал графический интерфейс к игре Судоку.
Исходники и бинарник тут: 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; } |
Сообщ.
#2
,
|
|
|
Цитата Dr4k0n @ А то на некоторых комбинациях он зависает. Так и будет виснуть. Сколько раз сталкивался (в печатных судоку), когда в финале возможные два варианта расстановки чисел. Оба равновероятных. |
Сообщ.
#3
,
|
|
|
Не очень понял... Причём тут равновераятные или нет?
Это же тупой перебор, правда немного оптимизированный: 1. Отсечение неподходящий кандидатов 2. Направление поиска от минимального числа возможных кандидатов в клетку. Добавлено Понял, о чём хотели сказать. Но моя прога на этом не запорится. Она выйдет на первом попавшемся решении. |
Сообщ.
#4
,
|
|
|
http://rus.postimees.ee/081106/glavnaja/razvlechenija/7603_foto.php - "самую сложну в миру судоку" программка решила за 10 секунд.
|
Сообщ.
#5
,
|
|
|
Судоку NP-hard. Исходник этот работает только для так называемых детерминированных судоку.
|
Сообщ.
#6
,
|
|
|
Цитата ArdI @ Исходник этот работает только для так называемых детерминированных судоку. А что есть детерминированные и недетерминированные судоку? В чем их разница? |
Сообщ.
#7
,
|
|
|
Цитата tserega @ А что есть детерминированные и недетерминированные судоку? Наверно, детерминированные ("определённые") -- имеющие одно и только одно решение; недетерминированные -- Цитата Flex Ferrum @ ну или более. когда в финале возможные два варианта расстановки чисел. Оба равновероятных |
Сообщ.
#8
,
|
|
|
Цитата Наверно, детерминированные ("определённые") -- имеющие одно и только одно решение; недетерминированные -- детерминированные это те, в которых на каждом шаге можно однозначно определить цифру в какой либо клетке. Однозначно, в плане используя детерминированный алгоритм. Вообще: все детерминированные точно однозначные, а вот верно ли обратное? Т.е. есть какой-то судоку, а определить что туда поставить нельзя, но решение одно. Может кто умеет это доказывать/опровергать ? |
Сообщ.
#9
,
|
|
|
Я попробовал визуализировать процесс поиска...
Получился какой-то странный результат. Алгоритм зависает (т. е. поле периодически то заполняется полностью, то делается откат до 10 клеток) на глубине рекурсии около 60-75 уровней. А на поле остаётся около 10 незакрытых клеток... И вот он их мусолит +)) В итоге так и не разобрался. |
Сообщ.
#10
,
|
|
|
Цитата Dr4k0n @ В итоге так и не разобрался. Да все нормально, не смотря исходника. Если ты используешь поиск в глубину, то если на какой либо ветке сделаешь неправильный выбор, то тебе придется перебрать все ветви которые идут дальше. Видишь ты по 10, потому что эта такая скорость твоего алгоритма+визуализации, он их заполняет и откатывает. Если оставишь на сутки может и дождешься В общем скорость решения твоего алгоритма зависит от удачи. Могу посоветовать почитать кнута DancingLiks или DLX скорость решения судоку всегда константна(вроде) |
Сообщ.
#11
,
|
|
|
Sazabis
Разумеется, не более чем k*10^81 Откат в алгоритме из-за его жадности. Вообще жадность не гарантирует правильный выбор, это вероятнотностный( имеется в виду эвристический) алгоритм. Кто-нибудь по сабжу мне что-нить скажет ? (см. пост выше). |
Сообщ.
#12
,
|
|
|
Dr4k0n, приведи плз примеры расстановок, в которых зависает!
|
Сообщ.
#13
,
|
|
|
Цитата ArdI @ Кто-нибудь по сабжу мне что-нить скажет ? Цитата ArdI @ Т.е. есть какой-то судоку, а определить что туда поставить нельзя, но решение одно. Может кто умеет это доказывать/опровергать ? по этому ? есть техника перебора, с которой машина справяется на порядки быстрее, а есть логика, которая дает, как бы это сказать..., удовлетворение, чтоли. Так вот если тебе надо быстро решить, тоесть составить, скажем, судоку используешь DLX Кнута, а если нужна логика... то добро пожаловать в сообщество судокистов Могу сказать сразу, что в сложном судоку, полно комбинаций в которых нельзя точно сказать где стоит цифра. Но! используя логику, можно сказать, где она не стоит. Так как логических алгоритмов много, и действенный может оказаться только один, то логическое решение судоку машиной, занимает больше времени. тебе нужны примеры логики ? |
Сообщ.
#14
,
|
|
|
Sazabis
Не по теме вы мне ответили. Логика эта , которая говорит где что не стоит - это и есть детерминированный алгоритм. Речь то не об этом. Речь идёт о том, верно ли, что есть такой судоку, который однозначен, но взять его нельзя каким либо непереборным алгоритмом. В том чисе логикой. Т.е. не будет дерева вариантов никакого. |
Сообщ.
#15
,
|
|
|
Смотря что считать перебором, если искать пары чисел, скажем в двух ячейках в линию есть воможность поставить только 1 и 2, не нарушая правила, следовательно, мы можем из всех остальных ячеек в этой линии, где есть возможность поставить 1 и/или 2 убрать эти варианты. Логично ? да. Перебор есть ? вроде как надо перебрать все пары 1,2 1,3 1,4 ... 8,9 ? если принять что для логического хода можно пользоваться перебором, то любой судоку "взять".
Есть например такая стратегия Nishio для выбранной цифры, помещаем ее в спорную ячейку, потом расставляем остальные цифры на доску, если получим противоречие, то можем удалить кандидата из спорной ячейки. Перебор ? сложно сказать. Есть другая достаточная версия решения Trial & Error, ставим цифру в ячейку, решаем дальше, если получаем противоречие, раскручиваем назад и помечаем, что эту цифру в эту ячеку ставить нельзя. Это не совсем перебор, так как цель найти противоречие, раскрутить назад и удалить кандидата. Перебор ? вполне можно так считать. Есть техники которые основаны на просмотре цепочек Перебор ? |