Задачи на программирование

[OmoN]

Сообщение от Nadir Zaitov

Кто-нибудь попробует?

К утру попробую что нибудь придумать. Идея уже есть.

[OmoN]

Сообщение от OmoN

К утру попробую что нибудь придумать. Идея уже есть.

Представим судоку как двумерный массив a[0..2,0..2](большой 3х3 квадрат). Каждый элемент массива содержит двумерный массив b[0..2,0..2](маленький 3х3 квадрат). У нас получается 4мерный массив. a[r,t,x,y]
r: Row number. Номер строки на большом квадрате (0..2)
t: Column number. Номер колонки на большом массиве (0..2)
x: Х координата. Номер строки на маленьком квадрате (0..2)
y: У кородината. Номер колонки на маленьком массиве (0..2).
Для каждой пустой клетки находим доступные цифры которые не встречаются на колонке, на строке и на маленьком квадрате на которым находятся текущая клетка. (в нашем примере проверяемые клетки на строке/колонке/квадрате при наведение курсора выделяется розовым цветом, не проверяемые желтым)
У меня получился вот это: http://examplecodes.narod2.ru/html/sudoku/

[German Stimban]

Простая задачка:
Есть десятичное число n, его записали в двоичном виде. Есть число m такое, что его двоичная запись зеркальна двоичной записи числа n.
Например: n=13 (1101) m=11 (1011).
Найти минимальное n, при котором m будет больше n в 1.5 раза.
1. при условии, что оба числа необязательно должны начинаться с единицы. Например n=10 (1010) m=5 (0101).
2. при условии, что оба числа обязательно должны начинаться с единицы.

[Nadir Zaitov]

Сообщение от OmoN

У меня получился вот это

См. что она выдала на заведомо решаемую задачку.

Ищите ошибку. Обычно решение не начинается сразу с заполнения 1-й клетки.

[OmoN]

Сообщение от Nadir Zaitov

Ищите ошибку. Обычно решение не начинается сразу с заполнения 1-й клетки.

Да. Это слабое место алгоритма. Для каждой клетки находить ряд доступных цифр и выбирает первый из них. Если заметили когда кликните на клетку она показывает только доступные цифры. У кого нибудь есть идея?

[Rooslan Khayrov]

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

[Nadir Zaitov]

Сообщение от OmoN

У кого нибудь есть идея?

У JH была не плохая идея, точнее не полный алгоритм, только сначала обычно проверяют совместность одинаковых цифр, а несовместность цифры в данной ячейке.
Факт, что не все Судоку решаются без перебора, однако обычно таких переборов в глубину бывает не более одного или двух шагов в глубину даже для самых сложных Судоку (например то, на которой я ваше решение тестировал). Т.е. последовательный анализ должен давать значительную часть разрешимых и однозначных Судоку.

[German Stimban]

Сообщение от OmoN

Да. Это слабое место алгоритма. Для каждой клетки находить ряд доступных цифр и выбирает первый из них. Если заметили когда кликните на клетку она показывает только доступные цифры. У кого нибудь есть идея?

Могу предложить рекурсивный метод решения в лоб:
Создаётся трёхмерный массив - координаты клетки и возможные значения для этой клетки. Сначала забиваются исходные данные, затем анализируется каждая клетка и в массив заносятся все возможные значения. Если количество возможных значений равно одному, данная клетка помечается как решённая и алгоритм начинает выполняться заново.
Таким образом можно решить простые судоку.

[Nadir Zaitov]

Сообщение от German Stimban

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

Герман. Именно такая постановка не дает ни одного решения для большинства стандартных Судоку, когда известны только 23 числа, т.е. менее 30% на строку/столбец или менее 50% известных цифр на ячейку. Скорее всего алгоритм такой ничего не даст.

Если Вы решали Судоку, то первые циферки находятся исходя из того, что в каждой строке, столбце и соотв. клетке 3×3 ровно по одной цифре из набора 1..9.

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

Например в примере сверху в двух последних строках есть пятерки. Вычеркиваем эти строки и замечаем, что в 7-й строке в третьей позиции должна быть пятерка.

[JH]

Давно я не брал в руки шашки!
Спустя 15 лет обсуждение судоку сподвигло меня написать программу На старом добром любимом QBasic (только его я и помнил, оказывается, так что извините)
Программа решает уровни сложности Easy, Medium, Hard с сайта http://websudoku.com
С уровнем "Evil" (там на каком-то этапе нужно делать перебор вариантов) не справляется.

Кстати, Надир, в вашем примере через несколько ходов тоже не остается очевидных вариантов, надо перебирать.