Логика для Кроссвордов Судоку.

[С.М.С]

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

[Sasha_Smirnov]

Не может быть! Точнее, не должно. Попробуйте в квадрате 3 на 3.

[С.М.С]

то, что квадрат 3 на 3 это так, и их там 9, плюс в некоторых случаях числа недолжны повторяться и по диагоналям. Дело не в этом, есть случаи, когда в одну ячейку подходит одна цифра на нескольких последовательных этапах обработки, тогда программа всё отлично и быстро расчитывает. А вот если создается ситуация, когда в ячейку подходит два, три и более значений, вот тогда и проблема. Сделал, чтобы в такой ситуаци программа брала число подставляла и производила проверку на совпадение, если числа не повторяются, то это число сохраняется и расчёт продолжается. При таком алгоритме может возникнуть ошибка вначале расчёта, что и происходит( к примеру если число взято неправельное для конечного результата, но в данный момен работы оно проходит все проверки). Так вот можно сделать полное заполнение нескольких квадратов, а дальше производить расчёт, если расчёт не верен изменять значение в последней ячейки, по достижению в ней числа 9, производить сброс в этой ячейки и увеличивать значение на еденицу больше в предыдущей в результате для одного квадрата получаем 9^9 комбинаций или 387 милин 420тыс 489 комбинации, а если брать несколько квадратов, при этом необходимо после каждого изменения значения проводить проверку на совпадение.!!!!

[С.М.С]

работает! восьмой уровень сложности в среднем 8 минут.

[wall66]

думаю легче было бы просчитать все возможные варианты расположения цифр вообще, и искать среди них подходящий для конкретного случая (с совпадающими клетками)

занимать будет много места, но производительность станет гораздо выше

[Levsha100]

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

думаю легче было бы просчитать все возможные варианты расположения цифр вообще, и искать среди них подходящий для конкретного случая (с совпадающими клетками)

занимать будет много места, но производительность станет гораздо выше

Типа представить все состояния поля как вершины графа, а ходы как ребра, и искать выигравшую комбинацию!

[С.М.С]

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

[wall66]

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