arXiv:1604.02691v1 [] 10 Apr 2016

On an algorithm for receiving Sudoku matrices
Krasimir Yordzhev
Faculty of Mathematics and Natural Sciences, South-West University
Ivan Mihaylov 66, Blagoevgrad, 2700, Bulgaria
E-mail: yordzhev@swu.bg
Abstract
This work examines the problem to describe an efficient algorithm for
obtaining n2 × n2 Sudoku matrices. For this purpose, we define the concepts of n × n Πn -matrix and disjoint Πn -matrices. The article, using the
set-theoretical approach, describes an algorithm for obtaining n2 -tuples of
n × n mutually disjoint Πn matrices. We show that in input n2 mutually
disjoint Πn matrices, it is not difficult to receive a Sudoku matrix.

Keywords: Sudoku matrix; S-permutation matrix; Πn -matrix; disjoint matrices; data type set
2010 Mathematics Subject Classification: 05B20, 68Q65

1

Introduction and notation

Let n be a positive integer. Throughout [n] denotes the set
[n] = {1, 2, . . . , n} ,
Un = [n] × [n] = {ha, bi | a, b ∈ [n]}
and Vn denotes the set of all subsets of Un .
Let Pij , 1 ≤ i, j ≤ n, be n2 square n× n matrices, whose entries are elements
of the set [n2 ] = {1, 2, . . . , n2 }. The n2 × n2 matrix


P11 P12 · · · P1n
 P21 P22 · · · P2n 


P = .
..
.. 
..
 ..
.
.
. 
Pn1

Pn2

· · · Pnn

is called a Sudoku matrix, if every row, every column and every submatrix Pij ,
1 ≤ i, j ≤ n comprise a permutation of the elements of the set [n2 ], i.e., every
integer s ∈ {1, 2, . . . , n2 } is found just once in each row, column, and submatrix
Pij . Submatrices Pij are called blocks of P .
This work is dedicated to the problem of finding an algorithm for getting all
n2 × n2 Sudoku matrices for an arbitrary integer n ≥ 2. This task is solved for
1

n = 2 and n = 3 [3]. When n > 3, according to our information, this problem is
still open. Finding algorithm to obtain n2 × n2 , n ≥ 4 Sudoku matrices will lead
to solving the problem of constructing Sudoku puzzle of higher order, which will
increase the interest in this entertaining game. Here we not going to examine
and compare different algorithms for solving any Sudoku puzzle. Here we will
examine some algebraic properties of n2 × n2 Sudoku matrices, which are the
basis for obtaining various Sudoku puzzles.
A binary (or boolean, or (0,1)-matrix ) is a matrix all of whose elements
belong to the set B = {0, 1}. With Bn we will denote the set of all n × n binary
matrices.
Two n × n binary matrices A = (aij ) ∈ Bn and B = (bij ) ∈ Bn will be
called disjoint if there are not integers i, j ∈ [n] such that aij = bij = 1, i.e. if
aij = 1 then bij = 0 and if bij = 1 then aij = 0.
A matrix A ∈ Bn2 is called an S-permutation if in each row, in each column,
and in each block of A there is exactly one 1. Let the set of all n2 × n2 Spermutation matrices be denoted by Σn2 .
A formula for calculating the number of all pairs of disjoint S-permutatiom
matrices is given in [11].
S-permutation matrices and their algebraic properties have an important
part in the description of the discussed in [6] algorithm.
The concept of S-permutation matrix was introduced by Geir Dahl [2] in
relation to the popular Sudoku puzzle. It is well known that Sudoku matrices
are special cases of Latin squares. It is widespread puzzle nowadays, which
presents in the entertaining pages in most of the newspapers and magazines
and in entertaining web sites. Sudoku, or Su Doku, is a Japanese word (or
phrase) meaning something like Number Place.
Obviously a square n2 × n2 matrix M with elements of [n2 ] = {1, 2, . . . , n2 }
is a Sudoku matrix if and only if there are matrices A1 , A2 , . . . , An2 ∈ Σn2 , each
two of them are disjoint and such that P can be given in the following way:
M = 1 · A1 + 2 · A2 + · · · + n2 · An2

(1)

Thus, the problem to describe an efficient algorithm for obtaining all n2 tuples of mutually disjoint S-permutation matrices naturally arises. This work
is devoted to this task. For this purpose, in the next section using the settheoretical approach, we define the concepts of Πn -matrix and disjoint Πn matrices. We will prove that so defined task can be reduced to the task of
receiving all n2 -tuples of mutually disjoint Πn -matrices.
In section 3 we will describe an algorithm for obtaining n2 -tuples of n ×
n mutually disjoint Πn matrices and we will show that in input n2 mutually
disjoint Πn matrices, it is not difficult to receive a Sudoku matrix. Described
in this article algorithm essentially differs from the algorithm described in [3].

2

2

A representation of S-permutation matrices

Let n be a positive integer. If z1 z2 . . . zn is a permutation of the elements of
the set [n] = {1, 2, . . . , n} and let us shortly denote σ this permutation. Then
in this case we will denote by σ(i) the i-th element of this permutation, i.e.
σ(i) = zi , i = 1, 2, . . . , n.
Definition 1 Let Πn denotes the set of all n × n matrices, constructed such
that π ∈ Πn if and only if the following three conditions are true:
i) the elements of π are ordered pairs of integers hi, ji, where 1 ≤ i, j ≤ n;
ii) if
[ha1 , b1 i ha2 , b2 i · · · han , bn i]
is the i-th row of π for any i ∈ [n] = {1, 2, . . . , n}, then a1 a2 . . . an in this
order is a permutation of the elements of the set [n];
iii) if


ha1 , b1 i
 ha2 , b2 i 




..


.
han , bn i

is the j-th column of π for any j ∈ [n], then b1 , b2 , . . . , bn in this order is a
permutation of the elements of the set [n].
The matrices of the set Πn we will call Πn -matrices.
From Definition 1, it follows that we can represent each row and each column
of a matrix M ∈ Πn with the help of a permutation of elements of the set [n].
Conversely for every (2n)-tuple
hhρ1 , ρ2 , . . . , ρn i, hσ1 , σ2 , . . . , σn ii,
where
ρi = ρi (1) ρi (2) . . . ρi (n),

1≤i≤n

σj = σj (1) σj (2) . . . σj (n),

1≤j≤n

are 2n permutations of elements of [n] (not necessarily different), then the matrix


hρ1 (1), σ1 (1)i hρ1 (2), σ2 (1)i · · · hρ1 (n), σn (1)i
 hρ2 (1), σ1 (2)i hρ2 (2), σ2 (2)i · · · hρ2 (n), σn (2)i 


π=

..
..
..
..


.
.
.
.
hρn (1), σ1 (n)i

hρn (2), σ2 (n)i

is matrix of Πn . Hence

· · · hρn (n), σn (n)i

|Πn | = (n!)2n
(2)




Definition 2 We say that matrices π ′ = p′ ij n×n ∈ Πn and π ′′ = p′′ ij n×n ∈
Πn are disjoint, if p′ ij 6= p′′ ij for every i, j ∈ [n].
3

 


Definition 3 Let π ′ , π ′′ ∈ Πn , π ′ = p′ ij n×n , π ′′ = p′′ ij n×n and let the
integers i, j ∈ [n] are such that p′ ij = p′′ ij . In this case we will say that p′ ij and
p′′ ij are component-wise equal elements.
Obviously two Πn -matrices are disjoint if and only if they do not have
component-wise equal elements.
Example 1 We consider the following Π3 -matrices:



h3, 1i h2, 1i h1, 2i
π ′ = p′ij =  h2, 3i h3, 2i h1, 1i 
h3, 2i h1, 3i h2, 3i


h3, 2i h1, 3i h2, 1i


π ′′ = p′′ij =  h3, 3i h1, 1i h2, 2i 
h2, 1i h1, 2i h3, 3i


h3, 1i h1, 3i h2, 2i


 h2, 2i h3, 1i h1, 1i 
π ′′′ = p′′′
ij =
h2, 3i h1, 2i h3, 3i




Matrices π ′ and π ′′ are disjoint, because they do not have component-wise
equal elements.
Matrices π ′ and π ′′′ are not disjoint, because they have two component-wise
′
′′′
equal elements: p′11 = p′′′
11 = h3, 1i and p23 = p23 = h1, 1i.
Matrices π ′′ and π ′′′ are not disjoint, because they have three component′′′
′
′′′
′′
wise equal elements: p′′12 = p′′′
12 = h1, 3i, p32 = p32 = h1, 2i, and p33 = p33 =
h3, 3i.
The relationship between S-permutation matrices and the matrices from the
set Πn are given by the following theorem:
Theorem 1 Let n be an integer, n ≥ 2. Then there is one to one correspondence θ : Πn ⇆ Σn2 .
Proof. Let π = [pij ]n×n ∈ Πn , where pij = hai , bj i, i, j ∈ [n], ai , bj ∈ [n].
Then for every i, j ∈ [n] we construct a binary n × n matrices Aij with only one
1 with coordinates (ai , bj ). Then we obtain the matrix


A11 A12 · · · A1n
 A21 A22 · · · A2n 


(3)
A= .
..  .
..
..
 ..
.
. 
.
An1

An2

· · · Ann

According to the properties i), ii) and iii), it is obvious that the obtained matrix
A is n2 × n2 S-permutation matrix.
Conversely, let A ∈ Σn2 . Then A is in the form shown in (3) and for every
i, j ∈ [n] in the block Aij there is only one 1 and let this 1 has coordinates (ai , bj ).
4

For every i, j ∈ [n] we obtain ordered pairs of integers hai , bj i corresponding to
these coordinates. As in every row and every column of A there is only one
1, then the matrix π = [pij ]n×n , where pij = hai , bj i, 1 ≤ i, j ≤ n, which is
obtained by the ordered pairs of integers is matrix of Πn , i.e. matrix for which
the conditions i), ii) and iii) are true.

Corollary 1 Let π ′ , π ′′ ∈ Πn and let A′ = θ(π ′ ), A′′ = θ(π ′′ ), where θ is the
bijection defined in Theorem 1. Then A′ and A′′ are disjoint if and only if π ′
and π ′′ are disjoint.
Proof. It is easy to see that with respect of the described in Theorem 1 one
to one correspondence, every pair of disjoint matrices of Πn will correspond to
a pair of disjoint matrices of Σn2 and conversely every pair of disjoint matrices
of Σn2 will correspond to a pair of disjoint matrices of Πn .

Corollary 2 [2] The number of all n2 × n2 S-permutation matrices is equal to
|Σn2 | = (n!)

2n

Proof. It follows immediately from Theorem 1 and formula (2).

3

(4)


Description of the algorithm

Algorithm 2 Receive n2 mutually disjoint Πn -matrices.
Input: Integer n
Output: P1 , P2 , . . . , Pn2 ∈ Πn such that Pi and Pj are disjoint when i 6= j
1. Construct n × n arrays P1 , P2 , . . . Pn whose entries assume values of the
set Vn ;
2. Initialize all entries of P1 , P2 , . . . , Pn with Un ;
3. For every k = 1, 2, . . . , n2 do loop
4.

For every i = 1, 2, . . . , n do loop

5.

For every j = 1, 2, . . . , n do loop

6.

Choose ha, bi ∈ Pk [i][j];

7.

Pk [i][j] = {ha, bi};

8.

For every t = k + 1, k + 2, . . . n2 from the set Pt [i][j] remove the
element ha, bi;

9.

For every t = j + 1, j + 2, . . . n from the set Pt [i][j] remove all
elements hx, yi such that x = a;

5

10.

For every t = i + 1, i + 2, . . . n from the set Pt [i][j] remove all
elements hx, yi such that y = b;
end loop 5;
end loop 4;
end loop 3.

Algorithm 3 Receive a S-permutation matrix from a Πn -matrix.
Input: P = [hak , bl i]n×n ∈ Πn , 1 ≤ k, l ≤ n.
Output: S = [sij ]n2 ×n2 ∈ Σn2 , 1 ≤ i, j ≤ n2 .
1. Construct an n2 × n2 integer array S = [sij ], 1 ≤ i, j ≤ n2 and initialize
sij = 0 for all i, j ∈ {1, 2, . . . , n2 };
2. For every k, l ∈ {1, 2, . . . , n} do loop
3.

i = (k − 1) ∗ n + ak ;

4.

j = (l − 1) ∗ n + bl ;

5.

sij = 1
end loop.

Algorithm 4 Receive Sudoku matrices.
Input: Integer n.
Output: Sudoku matrix A.
1. Get n2 mutually disjoint Πn matrices P1 , P2 , . . . Pn2 (Algorithm 2);
2. For every k = 1, 2, . . . , n2 from Pk receive Sk ∈ Σn2 (Algorithm 3);
3. A = 1 ∗ S1 + 2 ∗ S2 + · · · + n2 ∗ Sn2 .

4

Conclusion and remarks
• Described in section 3 algorithms will work more efficiently if the programmer uses programming languages and programming environments
with integrated tools for working with data structure set [1, 4, 5, 7, 8, 9].
• If in item 6 of Algorithm 2 we choose ordered pair ha, bi ∈ Pk [i][j] randomly, then we will get a random Sudoku matrix [10]. Thus we tested the
effectiveness of the algorithm.
• If in item 6 of Algorithm 2 we choose all ordered pairs ha, bi ∈ Pk [i][j], then
finally we will get all n2 × n2 Sudoku matrices. We do not know a general
formula for finding the number θn of all n2 × n2 Sudoku matrices for each
integer n ≥ 2. We consider that this is an open mathematical problem.
Using a computer program based on described in section 3 algorithms, we
calculated that when n = 2, there are θ2 = 288 number of 4 × 4 Sudoku
6

matrices. This number coincides with our results obtained using other
methods described in [12]. In [3], it has been shown that there are exactly
θ3 = 9! · 722 · 27 · 27 704 267 971 = 6 670 903 752 021 072 936 960 number
of 9 × 9 Sudoku matrices. The next step is to calculate the number θ4 of
16 × 16 Sudoku matrices.

References
[1] Pavel Azalov. Object-oriented programming. Data structures and STL.
Ciela, Sofia, 2008.
[2] Geir Dahl. Permutation matrices related to sudoku. Linear Algebra and
its Applications, 430(8–9):2457–2463, 2009.
[3] Bertram Felgenhauer and Frazer Jarvis. Enumerating possible sudoku
grids, 2005.
[4] Ivor Horton. Beginning STL: Standard Template Library. Apress, 2015.
[5] Kathleen Jensen and Niklaus Wirth. PASCAL - User Manual and Report.
Lecture Notes in Computer Science. Springer, Berlin Heidelberg, 1985.
[6] Pallavi Mishra, D. K. Gupta, and Rakesh P. Badoni. A new algorithm for
enumerating all possible sudoku squares. Discrete Mathematics, Algorithms
and Applications, 8(2):1650026 (14 pages), 2016.
[7] Herbert Sghildt. Java: The Complete Reference, Ninth Edition. McGrawHill Education, 2014.
[8] Kiat Shi Tan, Willi-Hans Steeb, and Yorick Hardy. Symbolic C++: An
Introduction to Computer Algebra using Object-Oriented Programming.
Springer-Verlag, London, 2000.
[9] Magdalina Todorova. Data structures and programming in C ++. Ciela,
Sofia, 2011.
[10] Krasimir Yordzhev. Random permutations, random sudoku matrices and
randomized algorithms. International J. of Math. Sci. & Engg. Appls.,
6(VI):291 – 302, 2012.
[11] Krasimir Yordzhev. Calculation of the number of all pairs of disjoint spermutation matrices. Applied Mathematics and Computation, 268:1 – 11,
2015.
[12] Krasimir Yordzhev and Hristina Kostadinova. On some entertaining applications of the concept of set in computer science course. Informational
Technologies in Education, (10):24–29, 2011.

7

