Сложные судоки

← →
Димка На (2011-11-25 20:48) [0]

Для общего развития пишу программу для решения сложных классических судок. Причем на основе логических выводов, а не перебора (хотя там и перебирать особо нечего).
Предлагаю вашему вниманию сложную судоку
http://argi.ru/sudoku.png
Черным обозначены изначально установленные цифры, серым - те, что программа рассчитала сама. Мелкими - возможные варианты в этой ячейке (программа также определяет автоматически).
Вопрос: что в этой судоке можно определить не перебирая? Какие цифры можно проставить, какие исключить?

← →
Димка На (2011-11-25 21:01) [1]

Я нашел, предлагаю форумчанам так же найти:)

← →
SQLEX © (2011-11-25 21:01) [2]

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

← →
Rouse_ © (2011-11-25 21:06) [3]

Логику на графе пишешь или что-то свое, типа генетики?

← →
Омлет © (2011-11-25 21:15) [4]

Почему в желтой клетки нет серой двоечки? Там же тоже возможна.

← →
Димка На (2011-11-25 21:20) [5]

> SQLEX © (25.11.11 21:01) [2]

Вот именно такой момент я хочу исключить.

> Rouse_ © (25.11.11 21:06) [3]

Могу ошибаться в терминах, поэтому просто расскажу как есть.

Имеется несколько правил упрощения (пока 5), выполняются по порядку до тех пор, пока вносят какие-либо изменения.
Пусть ряды, столбцы и квадраты называются множествами, тогда пока правила такие:
1. Если во множестве S в ячейке P стоит цифра, то это цифра не может стоять в какой либо другой ячейке этого множества.
2. Если во множестве S какая то цифра может стоять только в одной ячейке - то никакие другие цифры в этой ячейке быть не могут.
3. (Наиболее сложное для понимания) Пусть даны два разных множества S1 и S2, и их пересечение InterS, то если какая либо цифра может быть установлена в ячейках пересечения InterS и не может быть установлена в остальных ячейках S1, то она не может быть установлена и в остальных ячейках S2.
4. Если какие либо две цифры могут быть установлены только в две ячейки какого либо множества, то в этих ячейках не может других цифр.
5. Тоже самое что и 4, только для трех цифр.

Нового ничего в голову пока не идет.

← →
Димка На (2011-11-25 21:21) [6]

> Омлет © (25.11.11 21:15) [4]

Исключена по правилу 4. Если какие либо две цифры (в этом примере 3 и 5) могут быть установлены только в две ячейки какого либо множества (центральный квадрат), то в этих ячейках не может других цифр.

← →
SQLEX © (2011-11-25 21:23) [7]

http://delphimaster.net/view/9-1139901269/
посты Vlad Oshin ©
с единственным предположением в первой строке третьей колонки при выборе между 69, что там 6, далее все разрешилось само собой

http://zalil.ru/32134220

← →
Димка На (2011-11-25 21:35) [8]

> SQLEX © (25.11.11 21:23) [7]

Я так тоже могу. Мне не решить ее надо, на написать алгоритм, если хотите, без подобных предположений, а основанный на каких либо логических выводов.
Точнее не надо, а хочется. Тот что я описал в [5] уже справляется с судокой из [0].

← →
Димка На (2011-11-25 22:02) [9]

Вот еще более сложное.

http://argi.ru/sudoku2.png

Вопросы из [0] остаются

← →
SQLEX © (2011-11-25 22:04) [10]

> Димка На

> Я нашел, предлагаю форумчанам так же найти:)

ну собственно вот
а теперь

> Я так тоже могу.

:)

А если серьезно, алгоритм из [5] не доказан. Хотя, видится правильным.

Не удалось мне доказать также и такое предположение, что:
после упрощение по правилам (у тебя они 1,2)
1. Обязательно получится место(возможно, не одно), где будет возможны максимум 2 числа.
2. Всегда надо выбирать только такие места для предположения.
3. Предполагать из 2х следует то число, которое меньше всего встречается по вертикали, горизонтали и в квадрате по сравнению со своим визави.
Из этих правил собственно 0 и решил с первого раза.

Но это не алгоритм(как и твой), а теория. (хотя и не подводившая пока еще)

> http://argi.ru/sudoku2.png

ячейка 2,2 по теории из [10] советует предположить 8.
Предполагаем, проверяем, правильно.

← →
Димка На (2011-11-25 22:18) [12]

> Не удалось мне доказать также и такое предположение, что:
> после упрощение по правилам (у тебя они 1,2)

Правила выполняются снова и снова, пока применимы.

> ячейка 2,2 по теории из [10] советует предположить 8.
> Предполагаем, проверяем, правильно.

Там и 8 и 1 встречаются одинаковое количество раз:) Но не суть важно.

> Там и 8 и 1 встречаются одинаковое количество раз:) Но не
> суть важно.

нет
6:4 в пользу 8
http://zalil.ru/32134636

← →
Димка На (2011-11-25 22:59) [14]

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

У меня эта ссылка не пашет
http://argi.ru/sudoku.png

Димка а ты как решал судоку?В 3х3 я решал так: выбирал какую нибудь цифру(количество этой цифры было скажем 4-5)и смотрел на квадраты где их не было и в этих квадратах просматривал где цифра не могла стоять.Вот пример:

9?5|???|??8
4??|57?|1?6
?27|6??|?4?
-----------
?96|??3|512
7?4|?1?|3??
21?|98?|??4
-----------
?81|??4|?9?
3??|8??|?51
??2|??7|?6?

Здесь я выбрал первую цифру 1.Начал с верхнего левого квадрата.В этом кв. уже есть 5 цифр и 4 пустых ячейки.С нижнего кв. Число 1 простреливает две ячейки а с правого углового кв. число 1 простреливает одну ячейку.Считаем 5 цифр уже вписанные + 3 простреленные(извините за мою терминологию:))получается 8.Значит в последнюю ячейку вписываем 1.Под четверкой вписываем число 1.С одним квадратом и одним числом разобрались.

9?5|???|??8
4??|57?|1?6
127|6??|?4?
-----------
?96|??3|512
7?4|?1?|3??
21?|98?|??4
-----------
?81|??4|?9?
3??|8??|?51
??2|??7|?6?

Теперь нижний центральный квадрат.Там 8,4 и 7.Слева,справа и с центра три 1 простреливают пять ячеек из шести пустых.Остается под 8 написать 1.

9?5|???|??8
4??|57?|1?6
127|6??|?4?
-----------
?96|??3|512
7?4|?1?|3??
21?|98?|??4
-----------
?81|??4|?9?
3??|8??|?51
??2|1?7|?6?

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

9?5|???|??8
4??|57?|1?6
127|6?1|?4?
-----------
?96|??3|512
7?4|?1?|3??
21?|98?|??4
-----------
?81|??4|?9?
3??|8??|?51
??2|1?7|?6?

Затем берем другое число и считаем дальше.Есть еще несколько приемов расчета(где то и в уме надо запомнить 1-2 числа)но это в зависимости как расположены цифры.Здесь конечно во всех квадратах вписались числа 1.Так обычно не бывает.
Кто нибудь скиньте задачку по судоку и порешаем вместе:)

Сложные судоки Найти похожие ветки