Створення і оцінка кількості судоку

Зі шкільного віку мені подобалися судоку. Допомагало коротати час в дорозі в школу (та й зараз граю з дороги на роботу). Незабаром я і бабусю зміг підсадити на судоку, але проблема була в тому, що вона не могла грати на електронному пристрої. Тому прийшла ідея в голову зробити свій судоку, який можна буде роздруковувати.

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


Реалізовувати буду все на Pascal, так як він був ближче за всіх до мишки на момент написання статті. Проте все можна реалізувати і на інших мовах.

▍Спосіб перший. Алфавітна заміна.
Перший спосіб, який ми розглянемо, буде заміна одних цифр на інші у вихідному прикладу судоку. За вихідний варіант візьмемо наступну таблицю.

Картинка таблиці

Суть способу полягає в тому, щоб кожній цифрі зіставити іншу цифри і тим самим змінити всю судоку

Для цього скористаємося одновимірної матрицею з індексами від 1 до 9 і заповнимо в самому початку всі клітинки у відповідності з їх індексами. А далі будемо брати дві випадкові клітинки і змінювати їх значення між собою. Зауважимо, що проробивши цю операцію непарну кількість разів у нас не вийде вихідний варіант заповнення матриці (доказ надається читачеві). Для тих, хто сумнівається в кінці програми проводиться генерація одного мільйона матриць судоку та оцінка їх збігів з вихідним.

Пояснювальна картинка

Код програми на Pascaltype rec=record//алфавіт заміни
num:array [1..9] of integer;
constructor Create();
var i:integer;
begin
for i:=1 to 9 do
num[i]:=i;
end;
procedure rand();//випадковий обмін двох чисел в алфавіті
var i,j,k:integer;
begin
i:=random(1,9);
j:=i;
while(i=j) do j:=random(1,9);
k:=num[i];
num[i]:=num[j];
num[j]:=k;
end;
procedure wr();//висновок алфавіту на екран
var i:integer;
begin
for i:=1 to 9 do
write(num[i]+' ');
writeln;
end;
end;

Підрахувавши, отримаємо 9! варіантів, а це 362 880 різних комбінацій.

▍Спосіб другий. Матричні перестановки.
Це спосіб, який був ще на Хабре пару років тому. Подробиці можна почитати тут.

А тут наведу коротку витримку:

Можна поміняти рядки/стовпці в трійках, як показано на малюнках


Варто також відзначити, що непарна кількість перестановок гарантує відміну від початкового варіанта.

Тому реалізуємо спочатку обмін рядків і обмін стовпців в матриці судоку. Так само для спрощення коду вставимо туди функцію заміни цифр за алфавітом (спосіб, описаний раніше)

Код програми на Pascaltype sudoku=record//таблиця судоку
num:array [1..9] of array [1..9] of integer;
constructor Create();//ряд від 1 до 9 зрушений циклічно так, щоб таблиця відповідала правилам судоку
begin
num[1][1]:=1; num[1][2]:=2; num[1][3]:=3; num[1][4]:=4; num[1][5]:=5; num[1][6]:=6; num[1][7]:=7; num[1][8]:=8; num[1][9]:=9;
num[2][1]:=4; num[2][2]:=5; num[2][3]:=6; num[2][4]:=7; num[2][5]:=8; num[2][6]:=9; num[2][7]:=1; num[2][8]:=2; num[2][9]:=3;
num[3][1]:=7; num[3][2]:=8; num[3][3]:=9; num[3][4]:=1; num[3][5]:=2; num[3][6]:=3; num[3][7]:=4; num[3][8]:=5; num[3][9]:=6;
num[4][1]:=2; num[4][2]:=3; num[4][3]:=4; num[4][4]:=5; num[4][5]:=6; num[4][6]:=7; num[4][7]:=8; num[4][8]:=9; num[4][9]:=1;
num[5][1]:=5; num[5][2]:=6; num[5][3]:=7; num[5][4]:=8; num[5][5]:=9; num[5][6]:=1; num[5][7]:=2; num[5][8]:=3; num[5][9]:=4;
num[6][1]:=8; num[6][2]:=9; num[6][3]:=1; num[6][4]:=2; num[6][5]:=3; num[6][6]:=4; num[6][7]:=5; num[6][8]:=6; num[6][9]:=7;
num[7][1]:=3; num[7][2]:=4; num[7][3]:=5; num[7][4]:=6; num[7][5]:=7; num[7][6]:=8; num[7][7]:=9; num[7][8]:=1; num[7][9]:=2;
num[8][1]:=6; num[8][2]:=7; num[8][3]:=8; num[8][4]:=9; num[8][5]:=1; num[8][6]:=2; num[8][7]:=3; num[8][8]:=4; num[8][9]:=5;
num[9][1]:=9; num[9][2]:=1; num[9][3]:=2; num[9][4]:=3; num[9][5]:=4; num[9][6]:=5; num[9][7]:=6; num[9][8]:=7; num[9][9]:=8;
end;
procedure change(alf:rec);//алфавітна заміна
var i,j:integer;
begin
for i:=1 to 9 do
for j:=1 to 9 do
num[i][j]:=alf.num[(num[i][j])];
end;
procedure swip_row();//обмін рядами
var i,j,k,r:integer;
begin
i:=random(1,9);
j:=i;
while(j=i) do j:=random(3*((i-1+3)div 3-1)+1,3*((i-1+3)div 3-1)+3);
for r:=1 to 9 do
begin
k:=num[i][r];
num[i][r]:=num[j][r];
num[j][r]:=k;
end;
end;
procedure swip_line();//обмін стовпцями
var i,j,k,r:integer;
begin
i:=random(1,9);
j:=i;
while(j=i) do j:=random(3*((i-1+3)div 3-1)+1,3*((i-1+3)div 3-1)+3);
for r:=1 to 9 do
begin
k:=num[r][i];
num[r][i]:=num[r][j];
num[r][j]:=k;
end;
end;
procedure wr();//вивід на екран
var i,j:integer;
begin
for i:=1 to 9 do
begin
for j:=1 to 9 do
write(num[i][j],' ');
writeln;
end;
writeln;
end;
end;

Підрахувавши, отримаємо що при заміні тільки в одній трійці стовпців/рядів, можна збільшити кількість варіантів у 6 разів на кожну трійку (6*6*6 за стовпці і стільки ж за рядка, загальна 46 656 варіантів).

А так само напишемо окремо функцію, яка буде посимвольно порівнювати дві судоку між собою і повертати true/false якщо вони співпадають/збігаються.

Код програми на Pascalfunction compl(s1,s2:sudoku):boolean;//порівняння двох таблиць судоку
var i,j:integer; flag:boolean;
begin
flag:=true;
for i:=1 to 9 do
for j:=1 to 9 do
if(s1.num[i][j]<>s2.num[i][j])then flag:=false;
compl:=flag;
end;

var
a:rec;
nw,was:sudoku;
i:integer;
t,n:integer;
cor:integer;
begin
//Розрахунок ймовірності збігу судоку після заміни алфавіту та вихідного варіанта
cor:=0;
for t:=1 to 1000000 do
begin
nw:=new sudoku();
was:=new sudoku();
a:=new rec();

//Загальне зауваження. При непарній кількості перестановок, вихідна ситуація неможлива
//за 6 перестановок можна перемішати всі трійки стовбців/рядків
for i:=1 to 7 do nw.swip_row ();//6*3 варіантів
for i:=1 to 7 do nw.swip_line ();//6*3 варіантів
//за 8 парних перестановок можна отримати будь-яку комбінацію з 9 цифр.
for i:=1 to 9 do a.rand();//9! варіантів
//Оціночна кількість варіантів 117 573 120

nw.change(a);
if(compl(nw,was)) then cor:=cor+1;
end;
writeln((cor/1000000)*100,'%');
nw.wr();
end.

▍В ув'язненні розрахунків
Варто пояснити, чому отримані два числа можна перемножити. При заміні рядків ми не отримаємо той же варіант, що і при заміні цифр, так як інакше отримаємо, інший алфавіт замін (розглянувши останню заміну рядків, можна знайти протиріччя).

Тому даний алгоритм дозволяє створювати до 362 880 * 46 656 або 16 930 529 280 варіантів.

У статті описані не всі перетворення з таблицею судоку (заміна трійок стовбців/рядків, транспонування та інше), що доводить, що кількість варіантів судоку ще більше.

Джерело: Хабрахабр

0 коментарів

Тільки зареєстровані та авторизовані користувачі можуть залишати коментарі.