Creating and estimating Sudoku

  • Tutorial
From school age I liked Sudoku. It helped to while away the time on the way to school (and now I play along the way to work). Soon, my grandmother was able to get Sudoku, but the problem was that she could not play on an electronic device. Therefore, the idea came to my mind to make my sudoku, which can be printed.

About how to make your sudoku generator and how many evaluatively different options can be discussed under the cut.


I will implement everything on Pascal, as it was closest to the mouse at the time of writing. However, everything can be implemented in other languages.

▍ Method one. Alphabetical replacement.


The first way that we will look at is to replace some numbers with others in the original Sudoku example. For the initial version we take the following table.

Table picture


The essence of the method is to match each digit with a different digit and thereby change the entire sudoku as a whole.

To do this, we use a one-dimensional matrix with indices from 1 to 9 and fill in all the cells at the very beginning in accordance with their indices. And then we will take two random cells and change their values ​​with each other. Note that having performed this operation an odd number of times, we will not be able to get the initial version of filling the matrix (the proof is provided to the reader). For those who doubt, at the end of the program, one million Sudoku matrices are generated and their matches with the original are evaluated.

Explanatory picture


Pascal program code
type rec = record // replacement alphabet
num: array [1..9] of integer;
constructor Create ();
var i: integer;
begin
for i: = 1 to 9 do
num [i]: = i;
end;
procedure rand (); // random exchange of two numbers in the alphabet
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 (); // display the alphabet
var i: integer;
begin
for i: = 1 to 9 do
write (num [i] + '');
writeln;
end;
end;

Counting, we get 9! options, and this is 362,880 different combinations.

▍ The second way. Matrix permutations.


This is a method which was still on Habré a couple of years ago. Read the details here .

And here is a brief squeeze:

You can swap rows / columns in triples as shown in the figures



It is also worth noting that an odd number of permutations guarantees a difference from the original version.

Therefore, we first implement row exchange and column exchange in the sudoku matrix. Also, to simplify the code, we insert the function of replacing the numbers alphabetically (the method described earlier)

Pascal program code
type sudoku = record // sudoku table
num: array [1..9] of array [1..9] of integer;
constructor Create (); // a series of 1 to 9 shifted cyclically so that the table matches the sudoku rules
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); // alphabetical replacement
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 (); // row exchange
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 (); // exchange columns
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 (); // display
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;

Having calculated, we get that when replacing only one triple of columns / rows, you can increase the number of options by 6 times for each triple (6 * 6 * 6 per column and the same number per row, total 46 656 options).

And also write separately a function that will compare two Sudoku character by character and return true / false if they match / do not match.

Pascal program code
function compl (s1, s2: sudoku): boolean; // comparison of two sudoku tables
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
// Calculation of the probability of a sudoku match after replacing the alphabet and the original version
cor: = 0;
for t: = 1 to 1,000,000 do
begin
nw: = new sudoku ();
was: = new sudoku ();
a: = new rec ();

//General comment. With an odd number of permutations, the initial situation is impossible
// for 6 permutations all three triples of columns / rows can be mixed
for i: = 1 to 7 do nw.swip_row (); // 6 * 3 options
for i: = 1 to 7 do nw. swip_line (); // 6 * 3 options
// for 8 pair permutations you can get any combination of 9 digits.
for i: = 1 to 9 do a.rand (); // 9! options
// Estimated number of options 117 573 120

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

▍In the conclusion of calculations


It is worth explaining why the resulting two numbers can be multiplied. When replacing strings, we do not get the same option as when replacing numbers, since otherwise we get a different alphabet of substitutions (considering the last replacement of strings, we can find a contradiction).

Therefore, this algorithm allows you to create up to 362,880 * 46,656 or 16,930,529,280 variants.

The article does not describe all the transformations with the sudoku table (replacing triples of columns / rows, transposing, etc.), which proves that the number of variants of sudoku is even greater.

Only registered users can participate in the survey. Please come in.

And how many different variants of sudoku do you think?

  • 27% 16 930 529 280 * 4 20
  • 24.3% Over 100 Billion 18
  • 13.5% trillions 10
  • 29.7% More Over 22
  • 5.4% Custom 4

Also popular now: