[Караидель]

Увидела в ивритской газете головоломку и загрузилась... Объясняю суть: дана матрица 9х9, поделеная на субматрицы 3х3. Каждая строчка, каждый ряд большой матрицы и каждая субматрица содержат все числа от 1 до 9 по одному разу. Даётся она частично заполненной, надо логически рассуждая заполнить до конца так, чтоб ни одно из правил не нарушалось. В той газете было 4 такие матрицы, 3 я решила, последнюю (самую трудную) не успела. Сейчас гоняю в голове задачку, пытаясь составить общий алгоритм решения таких задач и его программное воплощение. У кого какие идеи? Может, вместе порешаем?

А ещё хочу написать прогу составления таких матриц и превращения их в головоломки... Прикольная игрушка получилась бы.

Comments

[Katriel]

Солнц,у меня этих судоку в газете - каждый день по 8 штук.Пол-армейского времени забирает )) я уже насобачилась их решать,самые сложные еще не выходят,но служба долгая,успеем ))

[thunder1]

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

рассматриваем 2 варианта-или данная цифра подходит клетке,тогда если

вызов рекурсивной функции для оставшихся выдал true,то закончили.

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

проблемму вывода правильного пути можно решить так-определить

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

при выходе в main в контейнере окажется правильно заполненая таблица или мусор при неудаче.

мы собственно просто пробуем все варианты заполнения таблицы цифрами

пока не натыкаемся на подходящий.сложность алгоритма конечно

экспоненциальна,но зато в виде кода занимает мало места и радует глаз

такие задачи очень любил маэстро Кимхи на экзамене.

у меня есть задача решенная таким способом-"been packing problemm",могу прислать ,если интересно.

[Караидель]

Katriel

А я первый раз увидела и жутко загорелась;о)



thunder

Я не хочу эффективность решения O(2^n), я хочу O(n^2) или в крайнем случае O(n^3). Краткость кода - не всегда оптимальна, а учитывая забитый CS:IP-записями стек-сегмент, программа превращается в полный кошмар. Так что меня интересует решение с минимумом рекурсий.

[Katriel]

Караидель,тебе заныкать парочку? ))

Кстати,эта фигня сейчас такая модная,что продаются тооооненькие такие брошюрки с задачами - аж 20 шекелей штука.

В принципе,там есть способ(кроме простого дедуктивного метода),он помогает не во всех случаях,но все-таки многое решает.

Составить программу по решению - неинтересно,а вот генератор новых - это рулез.Меня интересует сколько возможных комбинаций существует.

[Караидель]

Katriel

Заныкай обязательно!

Я подумаю над алгоритмом составления;о) На самом деле, он значительно легче: составляется такая матрица и решается какие числа оставить. Основная сложность алгоритма оставить числа так, чтоб задача решалась, но только единственным способом.

Всего существует 1834933472251084800000 возможных матриц. Вычисляется это по формуле 9!*8!*7!*6!*5!*4!*3!*2!*1! Так что на наш с тобой век хватит;о)))

[Караидель]

Упс, нет, всё-таки меньше, я не учла субматрицы 3х3. Но там формула получается уж больно геморойная... Короче, почти на 2 порядка меньше будет.