Задачи на программирование

[German Stimban]

Сообщение от Shamil Eshbekov

Коллега изучает Visual basıc. В качестве задачи, поставил решение судоку. Т.е. Хочет написать прогу, которая будет решать судоку любой сложности. Проблема в том, что навыков программирования нет, поэтому подходит к решению проблемы методом тыка. Что ни есть гуд. Умные люди посоветовали ему для начала составить алгоритм решения и набросать блок схему. С чем, в принципе, он согласился. Но опять проблема - не получается это у него. Усилиями коллектива мы тоже не смогли составить правильный алгоритм решения задачи. Какие будут мнения?

DarkUser прав:

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

а) Решать полным перебором

Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.

[JH]

Сообщение от German Stimban

Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.

Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки

[Shamil Eshbekov]

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

ЗЫ Басик - зло в чистом виде

У каждого свои тараканы.

[DarkUser]

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

Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки

На второй строчке будет уже намного меньше. Плюс уже стоящие цифры, отсеют большое количество вариантов.

[Shamil Eshbekov]

Сообщение от German Stimban

Поле размером 81 клетки, каждая клетка может быть любой из 9 цифр - итого 729 вариантов, решается мгновенно. Если вариантов решения более одного, отмечать, что судоку не имеет решения.

В том-то и дело, что не получается у него этот полный перебор организовать.

[JH]

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

На второй строчке будет уже намного меньше. Плюс уже стоящие цифры, отсеют большое количество вариантов.

Это все так. Но не 729 же...

[JH]

К автору задачи.
Для начала надо попробовать решить задачу без полного перебора. Пройдемся по всем 81 клеточкам (естественно, незанятым). Для каждой быстренько заводим массив из 9 целых чисел, заполняем его единичками. Потом проходим по всем остальным клеткам квадрата 3х3, в котором находится рассматриваемая клетка, если она не пустая и равна n, то заменяем n-й элемент массива ноликом. Потом то же самое делаем с той строкой, в которой находится текущая клетка, и со столбцом, соответственно. После этой операции суммируем массив, если его сумма равна единице, то вариантов заполнения этой клетки ровно 1, ищем единственный не равный нулю элемент массива и проставляем значение в клетку. Если сумма массива оказалась больше единицы, пропускаем эту клетку. И так проходим по всем 81 клеткам много раз до тех пор, пока алгоритм работает.
После того, как "очевидных" клеток не осталось, придется включать алгоритмы перебора, я в них никогда не был силен.

[German Stimban]

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

Точно 729 вариантов? Мне казалось, 362 тысячи с лишним вариантов заполнения только одной строки

Криво посчитал.

[Nadir Zaitov]

Сообщение от German Stimban

Криво посчитал.

Кстати из Википедии

Количество возможных комбинаций в судоку 9×9 составляет, по расчётам Бертхама Фельгенхауэра,
6 670 903 752 021 072 936 960 = (9!)^3

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

[Nadir Zaitov]

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

Для начала надо попробовать решить задачу без полного перебора. Пройдемся по всем 81 клеточкам (естественно, незанятым). Для каждой быстренько заводим массив из 9 целых чисел, заполняем его единичками. Потом проходим по всем остальным клеткам квадрата 3х3, в котором находится рассматриваемая клетка, если она не пустая и равна n, то заменяем n-й элемент массива ноликом. Потом то же самое делаем с той строкой, в которой находится текущая клетка, и со столбцом, соответственно. После этой операции суммируем массив, если его сумма равна единице, то вариантов заполнения этой клетки ровно 1, ищем единственный не равный нулю элемент массива и проставляем значение в клетку. Если сумма массива оказалась больше единицы, пропускаем эту клетку. И так проходим по всем 81 клеткам много раз до тех пор, пока алгоритм работает.

Как ни странно, но этот алгоритм при нормальном количестве данных чисел (обычно около 23 на разрешимую таблицу) с вероятностью близкой к 1 ни разу не даст ни одной "очевидной" циферки. Кто-нибудь попробует?