Как решать сложные судоку?

Question

[Сергей]

Проблема в том, что не могу понять принципы решения головоломки без использования метода перебора, так как добиваюсь решать задачу без совершения ошибок.

На скриншотах показаны две разные головоломки которые привели к тупику:

Comments

[eegmak]

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

[theuser]

Дожили, судоку на тостере.
Хотя чему удивляться - нормальные вопросы модеры удаляют, а эти висят годами.

[xmoonlight]

theuser, была бы альтернатива - давно бы уже свалил...

Answer 1

[xmoonlight]

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

По шагам:
1. Проставляете цифру до тех пор, пока не возникнет неопределённость.
2. Переходите к другой, и т.д.
3. Повторяете п.1
Т.е., как-бы "сворачиваете расхождения в спираль".
Профит!

Answer 2

[profesor08]

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

Answer 3

[Adamos]

А кто вам сказал, что сложные судоку должны решаться без перебора?
Человек в уме может прикинуть "если тут эта цифра, то..." на несколько шагов вперед, держа каждый из них в памяти.
Машина делает то же самое перебором. Это нормально.
Другое дело, что если вы делаете программу для составления судоку, вам стоит рассчитывать на решение ее человеком - а значит, необходимости глубоких переборов все-таки избегать.

Answer 4

[mayton2019]

Поиск в глубину с мини-максом. Тоже самое в шахматах и шашках и крестиках-ноликах. Меняются только ограничители на то куда можно ставить следующую фигуру. Основное ядро поискового алгоритма - это генерик. Обобщенный алгоритм если можно так сказать.

Answer 5

[SirotaSOFT]

Схожая проблема имеется и для более простых судоку 6 на 6.
Буду рад услышать идеи относительно следующего хода.

Comments

[xmoonlight]

Я бы попробовал бы на 4-й строке, сначала:
235146

[SirotaSOFT]

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

[xmoonlight]

SirotaSOFT, я дал НЕ перебор!

Корректность позиций нельзя узнать до тех пор, пока Вы не проверите корреляцию всех веток.

Я выбрал именно такой порядок: 235146 (для 4-й строки), потому, что на 2-й и 6-й стоят 1 и 5 соответтвенно, и там и там - есть 2-ка. Т.е. перекрёстная простановка.

[SirotaSOFT]

Простите, не понял логики: а почему "5"-ка не может быть в шестом столбике четвёртой строки?

[xmoonlight]

SirotaSOFT, почему не может? может, но менее вероятнее.
Т.к. баланс двух пятёрок будет на одной стороне.
А так, две ветки 5-ки: это 3-я и 6-я позиция (на 4-й строке) и нужно сводить неопределённость (корреляцию) к истинным позициям.

[SirotaSOFT]

а можно насчё "баланса" и "сторон" поподробнее, если есть время?

[xmoonlight]

SirotaSOFT, визуальная симметрия цифр по горизонтали и вертикали относительно центра поля.

[SirotaSOFT]

Однако у нас на поле только одна "5" из шести штук. Сдаётся мне, это имперический способ, а не легический.

[xmoonlight]

SirotaSOFT, других вариантов не может быть: неопределённость восстанавливается только итеративным методом.
Или Вы хотите решать не своим мозгом, а с помощью компьютера?

[SirotaSOFT]

Совершенно верно. Хочу компьюер научить, но столкнулся с проблемой - около 10% всех судоку 6х6 не решаются логическим путём, ну или я его не понимаю, а следовательно не могу объяснить компьютеру.

[xmoonlight]

SirotaSOFT, блин! Так бы сразу и сказал))
Суммы цифр в строках/столбцах должны быть равны. Чё там думать-то?!))

[SirotaSOFT]

:)