Теория Судоку

sudoku-theory

Судоку — это все о перестановках, перестановках с дополнительным применением логики. Чтобы изучить теорию, лежащую в основе Судоку, сначала нужно изучить перестановки.

Перестановки

Для двух символов существуют только два возможных порядка: {1;2} и {2;1}, для трех — шесть возможных порядков: {1;2;3},{1;3;2},{2;1;3},{2;3;1},{3;1;2},{3;2;1}, а для четырех символов — 24 перестановки. Количество перестановок — это факториал числа символов в группе. Таким образом, для сетки Судоку стандартного размера 9X9 мы имеем факториал дявяти (представленный в математике как 9!) или 9x8x7x6x5x4x3x2x1 возможных перестановок, которые равны 362880 возможным способам упорядочения девяти символов в строке, столбце или блоке.

Свойства перестановок

Можно создать другие перестановки, выполнив одно из следующих действий:

  • Последовательная замена символов

В перестановке вы всегда можете поменять местами все вхождения одного символа на другой, если обмен производится систематически и наоборот. Если вы поменяете 4 на 1, тогда 1 нужно поменять местами на 4 (например: 4; 2; 3; 1 станет 1; 2; 3; 4). Таким образом можно поменять местами несколько или все символы. Результат всегда будет тождественной перестановкой.

Вот головоломка 4×4 , в ней символы 1;2;3 поменялась на 3;1;2 соответственно, это две тождественные головоломки Судоку.

sudoku-theory-1sudoku-theory-2

 

 

 

 

  • Смена порядка

Вы можете поменять порядок, как хотите, и результат также является перестановкой. Например, вы можете сдвинуть символ «8» из начала в конец, чтобы последовательность (8;4;5;6;1;2;7;9;3) стала (4;5;6;1;2;7;9;3;8) или поменять местами соседние элементы попарно, тогда (8;4;5;6;1;2;7;9;3) станет (4;8;6;5;2;1;9;7;3).

Вот головоломка 4×4 с замененными нижними двумя строками, это две тождественные головоломки Судоку.

sudoku-theory-3sudoku-theory-4

 

 

 

 

Арифметический анализ

Похожая на Судоку головоломка «волшебный квадрат» обладает тем же свойством — сумма всех чисел в строках и столбцах равна одному и тому же числу.

Это также свойство перестановок, если вы прибавляете определенные числа в набор перестановок, то результат всегда будет давать ту же сумму. Это связано с тем, что сложение ассоциативно, и неважно, в каком порядке складывать числа, вы всегда получите тот же результат: ((5+1)+2) = (5+(1+2)). То же самое относится и к умножению, но это не относится ко всем простым арифметическим операциям, поскольку как вычитание, так и деление дают разные результаты в зависимости от порядка выполнения операций, например: (4/3)/2 не совпадает с 4/(3/2).

Если мы сложим все девять чисел в строке, столбце или блоке Cудоку, ответ всегда будет один и тот же: 45, а если мы их перемножим, то ответ будет равен 362880 (это факториал девяти — 9!).
Это может быть полезно в случае, если у нас в группе есть недостающее число, то можно его вычислить. Например, если отсутствует одно число, а сумма остальных чисел равна 40, недостающее число — 5, так как сумма всех чисел в группе должна быть равна 45. Это метод не работает в случае, если отсутствуют два числа, а сумма остальных равна 38, невозможно определить, какие эти два числа, это могут быть любые числа, дающие в сумме 7 (2 и 5, либо 1 и 6, либо 3 и 4).

По аналогии с умножением, одно недостающего число можно вычислить, перемножив вместе остальные числа и разделив 362880 на их произведение. Например, если произведение чисел 8,4,6,1,2,5,9,3 равно 51840, разделив 362880 на 51840, получим недостающее число 7. К сожалению, так же, как со сложением, мы не можем использовать эту схему, чтобы определить, какие из двух или более чисел отсутствует. Существует несколько вариантов чисел, которые дают один и тот же ответ.
Вот значения факториалов чисел от 1 до 9:

sudoku-theory-5

Прежде чем перейти к дальнейшему анализу, давайте использовать более простую сетку Судоку 4×4 вместо 9×9, чтобы уменьшить количество вариантов. В сетке 4×4 правила такие же, но в каждой группе есть только четыре числа (1, 2, 3 и 4) . Поэтому cумма чисел в группе должна составлять 10, а их произведение равняться 24 (факториалу 4 — 4!).

Числа Гёделя

Проблема с вычислением недостающих чисел не возникает, если мы используем форму чисел Гёделя. Здесь мы не просто перемножаем числа Судоку, а используем соответствующее простое число.

Простым числом называется натуральное число, которое делится только на 1 и само на себя. Итак, для 1 мы используем первое простое число 2, для 2 используем второе простое число 3, для 3 используем 5, для 47 и так далее.

Все четыре числа группы в сетке 4×4 теперь перемножим и получим результат: 2x3x5x7=210, а не 24. Если группа из четырех чисел содержит {2;3} и две пропущенные цифры, мы преобразуем их в соответствующие числа и перемножаем 3×5, получая 15. Теперь: 210/15=14. Следовательно произведение двух недостающих чисел должно быть равно 14, и есть только два числа, которые соответсвуют этому условию: 2 и 7.

Используя соответствующую таблицу, получаем, что 1 (для 2) и 4 (для 7) являются недостающими числами. Мы можем использовать этот метод для нахождения любого количества недостающих чисел в группе Судоку (любого размера) только с помощью умножения и деления. Почему это работает? Потому что мы не можем получить простое число, перемножив два других числа.

sudoku-theory-6

В сетке Судоку 9×9 для 5 нужно использовать простое число 11, для 6 число 13, для 7 число 17, для 819 и для 9 простое число 23. Итак, чтобы выяснить, какого числа не хватает в неполном ряду 8,4,6,1,2,5,9,3, преобразуем их в соответствующие простые числа и перемножим 19x7x13x2x3x11x23x5 = 13123110, но произведение всех простых чисел должно быть 223092870 (для сетки 9×9), получаем, что недостающее простое число равно 17, а ему соответствует число 7.

sudoku-theory-7

Теперь рассмотрим группу с недостающими тремя цифрами {9;3;6;1;2;8}. Произведение чисел Гёделя, соответствующих числам этой группы, дают 170430, разделив 223092870 на которое, получаем ответ: 1309. Существует только один способ генерации 1309 с использованием простых чисел, а именно: путем умножения 7x11x17, и поэтому соответствующие недостающие числа должны быть 4, 5 и 7.