Проблема подсчета: возможные таблицы Sudoko?

Question

Я работаю над Sudoko Solver (Python). Мой метод использует игру и исследовать возможные перестановки для каждого набора цифр по алгоритму DFS.

Для анализа проблемы, я хочу знать, что является подсчетом возможного действительный и недействительный Судоко столы?

-> Таблица 9 * 9, которые имеют 9 один, 9 два, ..., 9 девять.

(Это не точный дубликат по этот вопрос)

Мое решение:

1- Первый выберите 9 ячеек для 1s: (*)

2- и, как (1) для других цифр (каждый раз, 9 ячеек будут удалены из оставшихся доступных ячеек): C (81-9,9), C (81-9 * 2,9) .... =

3- Наконец умножьте результат на 9! (Перестановка 1S-2S-3S ...- 9S в (*))

Это не равно принятому ответу этот вопрос Но проблемы эквивалентны. что я сделал не так?

Answer 1

Количество действительных решеток Sudoku Solution для стандартной сетевой сети 9 × 9 была рассчитана Бертром Фельгенхауэром и Фразером Джарвисом в 2005 году, составила 6 670 903,752 021072 936 960.

Математика Судоку | источник

Я думаю, что проблема с вашим решением заключается в том, что удаление 9 ячеек каждый раз из доступных ячеек не обязательно создает действительную сетку. То, что я имею в виду, просто удаление 9 клеток не хватает.

Вот почему 81! / (9!) ^ 9 намного больше числа, чем фактические допустимые решения.

РЕДАКТИРОВАТЬ:

Перестановки с повторными элементами

Ваши решения практически правильны, если вы хотите все таблицы не только действительные таблицы судоку.

Есть формула:

(A + B + C + ...)! / [А! B! C! ....

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

(5+3)! / (5! 3!)

Ваша проблема аналогична этому.

Есть 9 1, 9 2 ... 9 9 с. и 81 места

Так что ответ должен быть (9 + 9 + ...)! / (9!) ^ 9

Теперь, если вы умножаетесь снова на 9! Тогда это добавит дублирующиеся мероприятия к числу, проводя их.

Answer 2

Согласно с Эта статья Википедии (или Эта последовательность OEIS.), есть примерно 6,6 * 10 ^ 21 разных квадратов судоку.

Answer 3

То, что вы сделали неправильно, был последний шаг: вы не должны умножить ответ 9!. Отказ Вы уже подсчитали все возможные квадраты.

Это не помогает вам больше при подсчетах возможных судоку-таблиц. Еще одна вещь, которую вы могли бы сделать, это сосчитать таблицы, где проводится «Состояние строки»: это просто (9!)^9, потому что вы просто выбираете одну перестановку 1..9 для каждой строки.

Все еще ближе к судоку-проблемы считается Латинские квадраты. Отказ Латинская площадь должна удовлетворять как «Состояние строки» и «Состояние столбца». Это уже сложная проблема, и не известна никакая формула закрытого формы. Судоку - это латинская площадь с дополнительным «подкупом-условием».