Пустая сетка судоку используется в симметрии судоку,он влечет за собой строку и столбцы размером 4 × 4,16 × 16 и более с мелкими и вариантными сетками.

Головоломки судоку можно изучить математически, чтобы ответить на такие вопросы, как “Сколько полных решеток судоку?”, “Какое минимальное количество подсказок в настоящей головоломке?” а также “Как сетки судоку могут быть симметричными?” с помощью комбинаторной и групповой теории.

Основные результаты таковы, что для классического судоку, количество завершенных сеток 6,670,903,752,021,072,936,960 (6.67× 1021), который, при сохранении действительности преобразования сводится к 5,472,730,538 существенно разные группы.

Есть 26 типы симметрии, но их можно найти только примерно в 0.005% всех заполненных сеток.

Головоломка с уникальным решением должна иметь не менее 17 решения, и на каждую решенную решетку не более 21 решения. Самая большая минимально найденная головоломка 40 подсказки.

Подобные результаты известны для вариантов и меньших сеток.. Точные результаты судоку не известны лучше, чем классическая сетка 9 × 9., хотя есть оценки, которые считаются достаточно точными.

Расчетные решения для судоку

Интересный вопрос, сколько способов может 9 от 9 Сетка судоку должна быть заполнена в соответствии с Единственным правилом?

Другими словами, сколько существует различных решений судоку? Мы описываем метод, использованный Бертрамом Фельгенгауэром и Фрейзером Джарвисом в раннем 2006 чтобы вычислить это число.

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

Мы называем количество отдельных сеток Судоку N. Первый, мы называем блоки сетки следующим образом:

Сколько существует способов заполнить B1 действительным способом? Поскольку есть 9 символы, которые могут заполнить B1, по одному в каждой ячейке, то есть 9 варианты для первой ячейки.

Для каждого из этих 9 опции, есть 8 варианты второй ячейки. Для каждого из этих 8 опции, есть 7 ушел в третью камеру.

В принципе, подсчитываем количество перестановок 9 символы: сколько способов мы можем разместить 9 персонажи в 9 места, или сколько способов мы можем заказать 9 вещи.

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

Так, первое упрощающее предположение, которое мы можем сделать, это то, что B1 заполнен числами 1, 2, 3, …, 9 Для того, чтобы, как показано ниже.

Теперь мы можем подсчитать, сколько фактических окончаний сетки имеет этот конкретный B1.: назовем это N1. Общее количество реальных сеток судоку составляет N1 × 9.!, поэтому N1 = N / 9!…

Давайте рассмотрим способы заполнения первых строк в B2 и B3.. поскольку 1, 2 а также 3 встречаются в первой строке B1, эти числа не могут встречаться в других строках.

Следовательно, только числа 4, 5, 6, 7, 8 а также 9 из второго и третьего рядов B1 могут встречаться в первом ряду B2 и B3.

Перечислите все возможные способы заполнения первых строк в B2 и B3, вплоть до перестановки чисел в каждом блоке. Кончик: Есть десять способов сделать это, чтобы обмен B2 и B3 этими десятью способами дал вам еще десять способов, всего двадцать.

Мы называем две из этих возможностей чистыми верхними линиями.: когда числа {4,5,6}, как во втором ряду B1, хранятся вместе в B2, и числа {7,8,9}, как в третьем ряду B1, хранятся вместе в B3, и измененная версия этого.

Другие возможности - смешанные верхние строчки, как они смешивают наборы {4,5,6} а также {7,8,9} при использовании для заполнения первых строк B2 и B3.

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

Подумайте, как вы можете завершить первую полосу, начиная с чистого верхнего ряда. 1,2,3;{4,5,6};{7,8,9}.

(Заметка: Мы пишем,б,c для обозначения упорядоченной тройки чисел и {a,б,с} обозначать их в любом порядке.)

Сколько всего возможностей есть, подсчет различных порядков номеров в каждой строке в B2 и B3? Это число такое же, как и для другого чистого верхнего ряда?, 1,2,3;{7,8,9};{4,5,6}?

Помните, мы хотим сохранить B1 фиксированным, потому что мы уже учли количество сеток, которые можно получить, переименовав девять цифр в нем.

Оказывается, есть (3!)⁶ способы завершить первую полосу, глядя на чистый верхний ряд 1,2,3;{4,5,6};{7,8,9}.

Это потому, что мы вынуждены поставить {7,8,9};{1,2,3} во втором ряду в B2 и B3 и {1,2,3};{4,5,6} в третьем ряду, а затем мы можем изменить порядок трех цифр в каждой из шести строк B2 и B3, чтобы получить все конфигурации.

Ответ такой же для другого чистого верхнего ряда., поскольку в этом случае все, что мы сделали, поменяли местами B2 на B3.

Случаи смешанных верхних рядов более сложны.. Рассмотрим верхнюю строку 1,2,3;{4,6,8};{5,7,9}. Это можно сделать до первой полосы, как показано на следующем рисунке., где, б, и c - числа 1, 2, 3 в любом порядке.

После выбора, b и c - два оставшихся числа в любом порядке, как они в одном ряду.

Поскольку есть три варианта, и три цифры в каждом из шести наборов в B2 и B3 можно пропустить, чтобы получить разные действительные титульные страницы, общее количество конфигураций в этом случае составляет 3 ×(3!)6.

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

Теперь у нас есть количество возможных первых страниц, определяемое B1.: это 2 ×(3!)6+18× 3 ×(3!)6= 2612736, где первая часть суммы - это количество завершений первой страницы из чистых верхних строк, а вторая - количество завершений первой страницы из смешанных верхних строк.

Вместо того, чтобы подсчитывать, сколько раз на первой странице было завершено каждое из этих 2612736 функции, Фельгенгауэр и Джарвис определили, какие первые страницы имеют одинаковое количество завершений первой страницы из верхнего пустого..

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

Вот несколько операций, которые оставляют количество концов сетки первого диапазона неизменным.: отмечая числа, прослушивание любого из блоков в первом диапазоне, прослушивание столбцов в любом блоке и прослушивание трех строк диапазона. При любом из этих изменений B1, мы можем пометить цифры, чтобы восстановить их стандартный вид.

Организация B1, B2 и B3 сохраняют количество концов сетки, потому что если мы начнем с любой реальной сетки судоку, единственный способ сохранить реальность - это пометить B4, B5, B6 и B7, B8, B9 соответственно, чтобы стопки оставались прежними.

Другими словами, каждое фактическое завершение сетки первой страницы дает ровно одно фактическое завершение сетки первой страницы, то есть. любой B1, Би 2, B3 перестановка.
Убедитесь, что при изменении B2 на B3 в следующей сетке Судоко, единственный способ сохранить сетку действующей - изменить B5 на B6 и B7 на B8. Это сохранит стеки такими же, хотя их местоположение изменилось.

Если у вас есть действующая сетка судоку и вы пропускаете столбцы в любом из B1, B2 и B3, что бы вы сделали со столбцами остальной части сетки судоку, чтобы она оставалась действительной? Например, если вы изменили столбцы 1 а также 2 B2 в вышеприведенной сетке, как бы вы исправили полученную сетку, чтобы она удовлетворяла Единому правилу?

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

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

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

Это называется лексикографической аббревиатурой..

Поскольку каждый из двух блоков имеет 6 перестановки столбцов и два способа перестановки блоков, лексикографическая стенография говорит нам, что, учитывая первую страницу, 62 × 2 = 72 других титульных листа с таким же количеством концов сетки.

Итак, теперь у нас есть только 2612736/72 = 36288 первых страниц для рассмотрения..

Для каждой из этих возможностей давайте посмотрим на перестановки всех трех верхних блоков.: есть 6. Для каждого из них есть 63 перестановки столбцов в каждом блоке.

После выполнения этих операций, помечаем заново, чтобы вернуть B1 в стандартный вид.

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

Фельгенгауэр и Джарвис использовали компьютерную программу, чтобы определить, что эти операции уменьшают количество первых страниц, которые следует рассматривать с 36288 только 416.

Давайте рассмотрим эту первую группу.

Выполняйте с ней различные операции, сохраняя количество концов сетки.. Начать можно со следующего: Поменяйте местами первый и второй ряд. Пометьте его так, чтобы B1 был в стандартном виде.. Лексикографически уменьшить эту сетку.

Главное, чтобы группа, с которой вы начали, и другая группа, с которой вы закончили, имели одинаковое количество завершений до полной сетки судоку..

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

Есть еще шаги, которые уменьшают количество сеток для рассмотрения. Если у нас есть пара цифр {a,б} в одном столбце с a в i-й строке и b в j-й строке, и та же пара в другом столбце с b в i-й строке и a в j-й строке, каждая пара будет иметь полосу с тем же количеством концов сетки, что и исходная.

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

В качестве примера, посмотри на числа 8 а также 9 в шестом и девятом столбцах приведенного выше примера. Рассмотрим все возможные случаи этого левого Фельгенгауэра и Джарвиса с 174 из первых 416 группы, чтобы продолжить.

Они также рассмотрели другие конфигурации того же набора чисел, лежащих в двух разных столбцах или строках., которые можно опустить внутри своих столбцов или строк, оставив неизменным количество концов сетки.

Это сократило количество первых страниц до 71, и поиск каждого из них 71 дела дали им понять, что на самом деле есть только 44 первые страницы, количество завершений сетки которых необходимо найти.

Каждый из них 44 полос имеет такое же количество концовок, что и вся сетка.

Обозначим через C одно из этих 44 полосы. Затем вы можете рассчитать количество способов, которыми C может пройти до полной сетки судоку.: назовите это NC.

Нам также необходимо количество первых страниц MC, которые разделяют это количество концов сетки nC.. затем, общее количество сеток судоку просто N = ΣCmCnC, или сумма mCnC для всех 44 полосы.

Фельгенгауэр и Джарвис написали компьютерную программу для выполнения окончательных расчетов..

Они подсчитали количество допустимых завершений N1 с B1 в стандартной форме., начиная с 44 переулки. Затем они умножили это число на 9! получить ответ.

Они обнаружили, что количество возможных 9 от 9 Сетки судоку: N = 6670903752021072936960, что составляет примерно 6,671 × 1021.

Статья и кредит изображения:

HTTP://pi.math.cornell.edu/~mec/Summer2009/Mahmood/Count.html