Не нравятся результаты поиска? Попробуйте другой поиск!
DLE FAQ » Все вопросы » Общие вопросы » Кто сможет решить судоку?

Кто сможет решить судоку?


     30.08.2013    судоку    Все вопросы » Общие вопросы    6579

вопрос
Вопрос не стандартный, но все же мне нужна помощь профи в решении судоку :)
Написал скриптик, который решает судоку кроссворды. Средний уровень сложности и тяжелый решает в легкую, а вот с Экспертом небольшие заминки. Но суть в том, что после работы скрипта даже я не могу решить его :)
Вот я и хочу попросить помощи у посетителей сайта с целью выяснить - решаем ли кроссворд математическими способами или только посредством человеческой дедукции.

12 комментариев

pavang
Юзер

pavang - 31 августа 2013 00:18 -

Трудно так вот решить, на бумагу переписать что ли... в общем давно я этого не делал, все как-то в компьютере. Не знаю, насколько он решаем полностью, но я бы советовал подумать вот над чем. Нижний средний квадрат. Из возможных вариантов видно, что восьмерка может быть только в правом столбце - верхней или нижней ячейке. Значит в среднем квадрате в правом столбце восьмерка уже невозможна, а она есть среди возможный вариантов. Если исключить из правого столбца среднего квадрата восьмерки то мы видим, что там где среди возможных вариантов значатся 1 и 8 возможен только 1. Эта единица изменит существующие возможные варианты. Кроме того, к примеру, опять же в нижнем среднем квадрате мы видим, что шестерка возможна только в среднем столбце. Значит в среднем квадрате, что над ним, шестерка в нижней средней ячейке невозможна.

Sander
PHP-developer

Sander - 31 августа 2013 00:47 -


Что-то вы меня запутали с этими средними квадратами с правыми полосами :)
Для удобства сделал подсветку восьмерок.

Можете еще раз объяснить, но указывая номер строки и колонки.

С шестерками согласен, но это практически ничего не дает.
Да и подобный анализ будет уже на порядок сложнее...

SanDev.pro - мой блог.

Telegram: @sandev
Skype: Sander8804

pavang
Юзер

pavang - 31 августа 2013 01:10 -


Что-то не разобрался, как сюда картинку вставить =( Если, к примеру, обозначить столбцы от А до И слева направо а строки - от 1 до 9 сверху вниз, то мы видим, что в нижнем среднем квадрате восьмерка возможна только в Е7 и Е9. Если восьмерка возможна только в Е7 и Е9, то в Е6 и Е5 восьмерка уже невозможна, но она значится как возможная. Если мы уберем оттуда восьмерку то увидим, что в Е5 возможна только единица.
Вероятно такой анализ сложнее, но мне кажется других путей нет. Возможно я и ошибаюсь. Только не могу сказать, в результате всех этих действий будет ли судоку решен полностью =(

Sander
PHP-developer

Sander - 31 августа 2013 02:11 -

Согласен в обоих случаях...
По действующему алгоритму скрипта, открытие единицы ничего не дало.
Придется пожалуй вообще переделывать алгоритм работы :(
Сейчас идет простое сравнение/вычитание по вертикали/горизонтали и в своем секторе.
А вот аналаз соседей он не делает... Может в следующей версии сделаю иначе, если захочется опять с этим возиться :)

SanDev.pro - мой блог.

Telegram: @sandev
Skype: Sander8804

pavang
Юзер

pavang - 31 августа 2013 03:07 -

А если воспользоваться советом из Википедии, согласно которому сложные судоку можно решить подстановкой в клетку с двумя возможными числами одного из них и дальнейшего расчета? Если в результате случится ошибка - значит верно другое число.
Вообще загугленная решалка судоку справилась с вашим кроссвордом. Уж не знаю, вычислял ли скрипт решение или взял из базы готовое.

Sander
PHP-developer

Sander - 31 августа 2013 12:58 -


Путем подстановки одного из 2х возможных чисел в ячейку - кроссворд решается.
Ставлю в И4 - 8 и все.

Но опять же, это полуавтоматический метод...

SanDev.pro - мой блог.

Telegram: @sandev
Skype: Sander8804

pavang
Юзер

pavang - 31 августа 2013 16:03 -

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

pavang
Юзер

pavang - 31 августа 2013 16:12 -

А даже если по поводу этого расклада я и ошибаюсь, все же гарантированно существуют неподдающиеся чисто математическому расчету, поэтому думаю в любом случае нужно научить скрипт в тупиковой ситуации работать методом перебора.

Sander
PHP-developer

Sander - 31 августа 2013 16:28 -


Для упрощения мозгового штурма подсветил все не завершенные цифры.
Все же хочется избежать варианта со слепым перебором. Может все же есть решение :(

SanDev.pro - мой блог.

Telegram: @sandev
Skype: Sander8804

TheImDim
Юзер

TheImDim - 31 августа 2013 17:44 -

Глянь в исходный код этого сайта. Уверен там судоку решается с помощью js, на php только формируется код. Сам я там не копался, но думаю все делается простым перебором.

pavang
Юзер

pavang - 1 сентября 2013 00:52 -

Перебрал кажется все мне известные механизмы решения судоку, но кроме как удаления из среднего поля 6 и 8 ничуть не приблизился к результату =(

maximaf
Юзер

maximaf - 8 октября 2013 21:07 -





Долго думал...Думаю,что так?!

Чтобы комментировать - войдите или зарегистрируйтесь на сайте

Похожие вопросы

наверх