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

Question

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

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

-> таблица 9 * 9, в которой есть 9 один, 9 два, ..., 9 девять.

(это не совсем дубликат этого вопроса )

Мое решение:

1- Сначала выберите 9 ячеек для 1 с: (*)

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

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

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

Answer 1

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

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

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

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

EDIT:

Перестановки с повторяющимися элементами

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

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

(а + Ь + с + ...)! / [а! б! с! ....]

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

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

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

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

поэтому ответ должен быть (9 + 9 + ...)! / (9!) ^ 9

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

Answer 2

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

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

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

Answer 3

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