2020/2, стр. 202 - 217

ON SOME RANDOMIZED ALGORITHMS AND THEIR EVALUATION

Резюме: The paper considers implementations of some randomized algorithms in connection with a random \(n^{2} \times n^{2}\) Sudoku matrix with the programming language \(\mathrm{C}++\). For this purpose we describe the set \(\Pi_{n}\) of all \((2 n) \times n\) matrices, consisting of elements of the set \(\mathbb{Z}_{n}=\{1,2, \ldots, n\}\), such that every row is a permutation. We emphasize the relationship between \(\Pi_{n}\)-matrices and the \(n^{2} \times n^{2}\) Sudoku matrices. An algorithm to obtain random \(\Pi_{n}\) matrices is presented. Several auxiliary algorithms that are related to the underlying problem have been described. We evaluated all algorithms according to two criteria - probability evaluation, and time for the generation of random objects and checking a belonging to a specific set. These evaluations are interesting from both theoretical and practical points of view because they are particularly useful in the analysis of computer programs.

Ключови думи: randomized algorithm; random object; permutation; binary matrix; algorithm evaluation; Sudoku matrix

1. Introduction

This article is intended for anyone who studies programming, as well as for teachers. The work is a continuation and addition of (Yordzhev, 2012). Here, along with the basic definitions and ideas for constructing randomized algorithms outlined in the cited publication, we will also describe specific implementations of these algorithms in the C++ programming language.

To demonstrate the ideas outlined in the article, we have chosen the \(\mathrm{C}++\) programming language (Todorova, 2002), (Todorova, 2011a), (Todorova, 2011b), but they can be implemented in any other algorithmic language. We hope that students who prefer to write in Java (Hadzhikolev & Hadzhikoleva, 2016) or any other modern programming language will have no problems with the implementation of the algorithms we have proposed.

The presented in the article source codes have been repeatedly tested with various input data and they work correctly.

Let \(\mathfrak{M}\) be a finite set. A Random objects generator of \(\mathfrak{M}\) is every algorithm \(\mathcal{A}_{\mathfrak{M}}\) randomly generating any element of \(\mathfrak{M}\), while elements generated by a random objects generator will be called random elements of \(\mathfrak{M}\), for example random numbers, random matrices, random permutations, etc. We take for granted that probabilities to obtain different random elements of \(\mathfrak{M}\) by means of \(\mathcal{A}_{\mathfrak{M}}\) are equal, and are also equal to \(\tfrac{1}{|m|}\). We denote the time that the random objects generator needs to obtain a random element of \(\mathfrak{M}\) with \(T\left(\mathcal{A}_{\mathfrak{M}}\right)\).

By randomized algorithm we will mean any algorithm which essentially uses a random object generator in its work.

The randomized algorithms are very often used to solve problems, which are proved to be NP-complete. For detailed information about NP-complete problems and their application see (Garey & Jonson, 1979) or (Hopcroft et al., 2001). A proof that a popular Sudoku puzzle is NP-complete is given in (Yato, 2003) and (Yato & Seta, 2003).

In this study, we will solve some particular cases from the following class of problems:

Let \(n\) and \(m=m(n)\) be natural numbers. Let us consider the set \(\mathcal{U}\), consisting of objects every of which dependent on \(m\) parameters, and every parameter belongs to the finite set \(\mathfrak{M}\). We assume that there is a rule that uniquely describes object \(u \in \mathcal{U}\), if all \(m\) parameters are specified. Let \(\mathcal{V} \subset \mathcal{U}\). The problem is to obtain (at least one) object, which belongs to the set \(\mathcal{V}\). The number of the elements of the sets \(\mathcal{U}\) and \(\mathcal{V}\) depends only on the parameter \(m\), which is an integer function of the argument \(n\).

The standard algorithm that solves the above problem is briefly described as follows:

Algorithm 1

1) We obtain consequently \(m=m(n)\) random elements of \(\mathfrak{M}\) using random objects generator \(\mathcal{A}_{\mathbb{m}}\) and so we get the object \(u \in \mathcal{U}\);

2) We check if \(u \in \mathcal{V}\). If the answer is no, everything is repeated.

In other words, if we already have a random objects generator, a randomized algorithm can be used as a generator of more complex random objects. The efficiency of Algorithm 1 depends on the particular case in which it is used and can be evaluated according to the following criteria:

Probability evaluation: If \(p(n)\) denotes the probability after generating \(m=m(n)\) random elements of \(\mathfrak{M}\) of obtaining an object of \(\mathcal{V}\), then according to the classical probability formula:

(1)\[ p(n)=\tfrac{|\mathcal{v}|}{|\mathcal{u}|} \]

Time for generating and checking: We denote by \(\tau(n)\) the time needed to execute one iteration (repetition) of Algorithm 1. Then

(2)\[ \tau(n)=m(n) T\left(\mathcal{A}_{\mathfrak{m}}\right)+\theta(n), \]

where \(\theta(n)\) is the time to examine if the obtained object belongs to the set \(\mathcal{V}\).

It is obvious that the efficiency of Algorithm 1 will be proportional to \(p(n)\) and inversely proportional to \(\tau(n)\).

Of course, time for generating and checking does not give us the total time to execute the algorithm, since the number of repetitions is not known in advance. However, the characteristic \(\tau(n)\) is essential to the effectiveness of any randomized algorithms.

The cases in which probability evaluation is equal to 1, i.e. the cases in which the algorithm is constructed directly to obtain element of the set \(\mathcal{V}\) and there is no need of belonging examination, are of great interest, as only one iteration is implemented then, i.e. there is no repetition. Let \(n\) be a positive integer. We denote by \(\mathbb{Z}_{n}\) the set of the integers

\[ \mathbb{Z}_{n}=\{1,2, \ldots, n\} \]

There are standard procedures for obtaining random numbers of the set \(\mathbb{Z}_{n}\) in most of the programming environments. We take this statement for granted and we will use it in our examinations. Let \(\mathcal{A}_{n}\) be a similar procedure. In the current study, we will consider that for \(n \neq l\)

(3)\[ T\left(\mathcal{A}_{n}\right) \approx T\left(\mathcal{A}_{l}\right)=t_{0}=\text { Const } \]

Below we show an example of a C ++ function that generates a random positive integer belonging to the set \(\mathbb{Z}_{n}=\{1,2, \ldots, n\}\) :

Algorithm 2.

In order for the function rand_Zn(int) to work so that every time we execute the program in which we will use it to obtain various random numbers, we must add the procedure

before first accessing this function, for example, at the beginning of the main() function. The functions rand() and srand(s) are from the library <cstdlib>, and the function time(t) is from the library <ctime>. For more details, see for example (Azalov & Zlatarova, 2011, p. 75).

Let \(P_{i j}, 0 \leq i, j \leq n-1\) be \(n^{2}\) in number square \(n \times n\) matrices, whose elements belong to the set \(\mathbb{Z}_{n^{2}}=\left\{1,2, \ldots, n^{2}\right\}\). Then \(n^{2} \times n^{2}\) matrix

\[ P=\left[P_{i j}\right]=\left[\begin{array}{llll} P_{00} & P_{01} & \cdots & P_{0 n-1} \\ P_{10} & P_{11} & \cdots & P_{1 n-1} \\ \vdots & \vdots & \ddots & \vdots \\ P_{n-10} & P_{n-11} & \cdots & P_{n-1 n-1} \end{array}\right] \] is called a Sudoku matrix, if every row, every column and every submatrix \(P_{i j}\), \(0 \leq i, j \leq n-1\) make permutation of the elements of set \(\mathbb{Z}_{n^{2}}\), i.e. every integer \(s \in\left\{1,2, \ldots, n^{2}\right\}\) is present only once in every row, every column and every submatrix \(P_{i j}\). Submatrices \(P_{i j}\) are called blocks of \(P\).

In this paper we will illustrate the above mentioned ideas by analyzing some randomized algorithms for obtaining an arbitrary permutation of \(n\) elements, an arbitrary \(n^{2} \times n^{2}\) Sudoku matrix and an arbitrary \((2 n) \times n\) matrix with \(2 n\) rows and \(n\) columns, every column of which is a permutation of \(n\) elements.

We will prove that the problem for obtaining ordered \(n^{2}\)- tuple of \((2 n) \times n\) matrices, every row of which is a permutation of elements of \(\mathbb{Z}_{n}\) is equivalent to the problem of generating a Sudoku matrix. We will analyze some possible algorithms for generating a random Sudoku matrix.

How to create computer program for Sudoku solving (a mathematical model of the algorithm), using the concept set combined with the trial and error method is described in (Yordzhev, 2018).

2. Random permutations

Let \(n\) be an positive integer. We denote by \(\mathcal{S}_{n}\) the set of all permutations \(\left\langle a_{0}, a_{1}, \ldots, a_{n-1}\right\rangle\), where \(a_{i} \in \mathbb{Z}_{n}\) and \(a_{i} \neq a_{j}\) when \(i \neq j, 0 \leq i, j \leq n-1\).

If \(\sigma=\left\langle a_{0}, a_{2}, \ldots, a_{n-1}\right\rangle \in \mathcal{S}_{n}\) is a permutation of all elements of the set \(\mathbb{Z}_{n}=\{1,2, \ldots, n\}\) then obviously \(\sigma\) depends of \(m(n)=n\) parameters \(a_{0}, a_{1}\), … \(a_{n-1}\).

As it is well known, the number of all \(n\)-tuples of integers \(\left\langle x_{1}, x_{2}, \ldots, x_{n}\right\rangle\), \(x_{i} \in \mathbb{Z}_{n}\) is equal to

(4)\[ |\underbrace{\mathbb{Z}_{n} \times \mathbb{Z}_{n} \times \cdots \times \mathbb{Z}_{n}}_{n}|=n^{n} \]

and the number of all permutations of \(n\) elements is equal to

(5)\[ \left|\mathcal{S}_{n}\right|=n!=1 \cdot 2 \cdot 3 \cdots n \]

We denote by \(p_{1}(n)\) the probability to obtain a random permutation of \(S_{n}\) with the help of Algorithm 1. Then according to equations (1), (4) and (5) we obtain:

(6)\[ p_{1}(n)=\tfrac{n!}{n^{n}} \]

The next algorithm works in time \(O(n)\) and checks if ordered \(n\)-tuple \(\left\langle a_{0}, a_{1}, \ldots a_{n-1}\right\rangle, a_{i} \in \mathbb{Z}_{n}, i=0,1, \ldots, n-1\) is a permutation.

Algorithm 3. Check if given integer array a[n] is a permutation of the elements from the set \(\mathbb{Z}_{n}=\{1,2, \ldots, n\}\).

there is an element that does not belong to the set .*/ v[a[i]]++; if (v[a[i]] > 1) return false; /* Since the number a[i] occurs more than once in the n-tuple. */

Let \(\tau_{1}(n)\) denote the time for implementing one iteration of Algorithm 1 when a random permutation of elements of \(\mathbb{Z}_{n}\) is obtained, and let \(\theta_{1}(n)\) denote the time for checking whether an arbitrary \(n\)-tuples of numbers of \(\mathbb{Z}_{n}\) belongs to \(\mathcal{S}_{n}\). Analyzing Algorithm 3, it is easy to see that

(7)\[ \theta_{1}(n) \in O(n) . \]

Then, having in mind the equations (2), (3) and (7) we obtain the following time for generating and checking:

(8)\[ \tau_{1}(n)=n T\left(\mathcal{A}_{n}\right)+\theta_{1}(n) \in n t_{0}+O(n)=O(n) \]

The following algorithm is also randomized (random integers are generated), but its probability evaluation is equal to 1, i.e. in Algorithm 1 step 2 is not implemented, because when the first random \(n\) numbers are generated the obtained ordered \(n\)-tuple is a permutation.

Algorithm 4л Obtaining random permutation \(\sigma=\left\langle a_{0}, a_{1}, \ldots, a_{n-1}\right\rangle \in \mathcal{S}_{n},\) \(\sigma=\left\langle a_{0}, a_{1}, \ldots, a_{n-1}\right\rangle \in \mathcal{S}_{n}\), where \(a_{i} \in \mathbb{Z}_{n}, i=1,2, \ldots, n, a_{i} \neq a_{j}\) when \(i \neq j\).

of the elements of the array with 1. */

Analyzing the work of Algorithm 4, we see that in the end, \(n\) different elements of the set \(\mathbb{Z}_{n}=\{1,2, \ldots, n\}\) are filled in the array \(\mathrm{a}[\mathrm{n}]\). We consistently randomly take these elements from the array v with length \(n\) where all integers \(1,2, \ldots, n\) are filled, such that \(\mathrm{v}[\mathrm{i}]=\mathrm{i}+1, i=0,1, \ldots, n-1\). After each choice we remove the selected integer from the array v, i.e. from the integers which we will randomly take in the next steps of the algorithm. Therefore Algorithm 4 which obtains random permutation has probability evaluation:

(9)\[ p_{2}(n)=1 \]

In Algorithm 4, there are two nested loops, so that the outer loop is repeated exactly \(n\) times. Internal loop in the worst case (if randomly selected integer equal to the value of the item v[0]) will be repeated as many times as is the length of the array v, which in the first iteration of the outer loop is equal to \(n\) and decreased each time by 1. Thus, we obtain the following time evaluation for generating and checking in one iteration of Algorithm 4.

(10)\[ \tau_{2}(n) \in t_{0}[O(n)+O(n-1)+\cdots+O(1)]=O\left(n^{2}\right) . \]

We see that Algorithm 1 applied for obtaining random permutations is more efficient than Algorithm 4 in terms of the time for generating and checking. But on the other hand, the probability evaluation of Algorithm 4 is equal to \(p_{2}(n)=1\). The probability evaluation of Algorithm 1 is equal to \(p_{1}(n)=\tfrac{n!}{n^{n}} \lt 1\) for \(n \geq 2\). Considering that the number of iterations is previously unknown and \(\lim _{n \rightarrow \infty} p_{1}(n)=0\), then this makes Algorithm 4 overall much more effective than the Algorithm 1 when applied to generate random permutations.

3. Random (2n) \(X n\) matrices, every row of which is a permutation of elements of \(\mathbb{Z}_{n}\)

Let \(\Pi_{n}\) denote the set of all \((2 n) \times n\) matrices, which are also called \(\Pi_{n}\) matrices, in which every row is a permutation of all elements of \(\mathbb{Z}_{n}\). In this case \(\mathfrak{M}=\mathbb{Z}_{n}\) and \(m(n)=2 n^{2}\). It is obvious that

(11)\[ \left|\Pi_{n}\right|=(n!)^{2 n} \]

It is easy to see that when we obtain random \(\Pi_{n}\) matrix with the help of Algorithm 1 the following evaluations can be observed:

Probability evaluation:

(12)\[ p_{3}(n)=\tfrac{|v|}{|u|}=\tfrac{(n!)^{2 n}}{n^{2 n^{2}}} \]

Time for generating and checking:

(13)\[ \tau_{3}(n)=m(n) T\left(\mathcal{A}_{n}\right)+2 n \tau_{1}(n) \in 2 n^{2} t_{0}+2 n O(n)=O\left(n^{2}\right), \]

where \(\tau_{1}(n)\) is obtained according to equation (8).

The next randomized algorithm will be more efficient than Algorithm 1 in obtaining random \(\Pi_{n}\) matrix according to the probability evaluation.

Algorithm 5. Obtaining a random matrix \(M=\left[\pi_{i j}\right]_{2 n \times n} \in \Pi_{n}\) with probability evaluation equal to 1. The algorithm will write the elements of the matrix \(M=\left[\pi_{i j}\right]_{2 n \times n}\) in the array p[] with size \(2 n^{2}\), such that \(\pi_{i j}=\mathrm{p}\left[\mathrm{i}^{*} \mathrm{n}+\mathrm{j}\right]\), where \(0 \leq i \lt 2 n, 0 \leq j \lt n\).

Practically, Algorithm 5 repeats \(2 n\) times Algorithm 4. As Algorithm 4 has a probability evaluation equal to 1, then Algorithm 5 which obtains random \(\Pi_{n}\) matrix also has probability evaluation

(14)\[ p_{4}(n)=1 p_{4}(n)=1 \]

It is easy to see that Algorithm 5 works in time for generating and checking

(15)\[ \tau_{4}(n)=2 n \tau_{3}(n) \in 2 n O\left(n^{2}\right)=O\left(n^{3}\right) . \]

As we can see below \(\Pi_{n}\) matrices can successfully be used to create algorithms that are efficient in developing Sudoku matrices.

4. \(S\)-permutation matrices

A binary (or boolean, or (0,1)-matrix) is called a matrix whose elements belong to the set \(\mathfrak{B}=\{0,1\}\). With \(\mathfrak{B}_{n \times m}\) we will denote the set of all \(n \times m\) binary matrices. The set of all square \(n \times n\) binary matrices we will denote with \(\mathfrak{B}_{n}=\mathfrak{B}_{n \times n}\)

Two binary matrices \(A=\left[a_{i j}\right]_{n \times m} \in \mathfrak{B}_{n \times m}\) and \(B=\left[b_{i j}\right]_{n \times m} \in \mathfrak{B}_{n \times m}\) will be called disjoint if there are not elements \(a_{i j} \in A\) and \(b_{i j} \in B\) with one and the same indices \(i\) and \(j\), such that \(a_{i j}=b_{i j}=1\), i.e. if \(a_{i j}=1\) then \(b_{i j}=0\) and if \(b_{i j}=1\) then \(a_{i j}=0,1 \leq i \leq n, 1 \leq j \leq m\).

A square binary matrix \(A \in \mathfrak{B}_{n}\) is called permutation, if there is only one 1 in

every row and every column of the matrix \(A\). Let \(\Sigma_{n^{2}}\) denote the set of all permutation \(n^{2} \times n^{2}\) matrices of the following type

(16)\[ A=\left[\begin{array}{llll} A_{0} & 0 & A_{01} & \cdots \\ A_{10} & A_{12} & \cdots & A_{0 n-1} \\ \vdots & \vdots & \ddots & \vdots \\ A_{n-10} & A_{n-11} & \cdots & A_{n-1 n-1} \end{array}\right] \]

where for every \(s, t \in\{0,1,2, \ldots, n-1\} A_{s t}\) is a square \(n \times n\) binary submatrix (block) with only one element equal to 1, and the rest of the elements are equal to 0. The elements of \(\Sigma_{n^{2}}\) will be called \(S\)-permutation.

Geir Dahl introduces the concept of S-permutation matrix [Dahl, 2009] in relation to the popular Sudoku puzzle giving the following obvious proposition:

Proposition 4.1. (Dahl, 2009) A square \(n^{2} \times n^{2}\) matrix \(P\) with elements of \(\mathbb{Z}_{n^{2}}=\left\{1,2, \ldots, n^{2}\right\}\) is Sudoku matrix if and only if there are mutually disjoint matrices \(A_{1}, A_{2}, \ldots, A_{n^{2}} \in \Sigma_{n^{2}}\) such that \(P\) can be presented as follows:

\[ P=1 \cdot A_{1}+2 \cdot A_{2}+\cdots+n^{2} \cdot A_{n^{2}} \]

As it is proved in [Dahl, 2009] and with other methods in (Yordzhev, 2013)

(17)\[ \left|\Sigma_{n^{2}}\right|=(n!)^{2 n} \]

Therefore, if a random \(\Sigma_{n^{2}}\) matrix obtained by means of Algorithm 1 the following probability evaluation is valid:

(18)\[ p_{5}(n)=\tfrac{(n!)^{2 n}}{2^{\left(n^{2}\right)^{2}}}=\tfrac{(n!)^{2 n}}{2^{n^{4}}} \]

In order to obtain a random \(\Sigma_{n^{2}}\) matrix, we have to generate \(m(n)=\left(n^{2}\right)^{2}=n^{4}\) random integers, which belong to the set \(\mathfrak{B}=\{0,1\}\). Hence, whatever randomized algorithm is used, the result is the following time for generating and checking:

(19)\[ \tau_{5}(n)=m(n) T\left(\mathcal{A}_{2}\right)+\theta_{5}(n)=n^{4} t_{0}+\theta_{5}(n) \in O\left(n^{z}\right), \quad z \geq 4 \]

where \(\theta_{5}(n)\) is time for checking that the given binary matrix belongs to the set \(\Sigma_{n^{2}}\).

Below we will give an algorithm (Algorithm 6), which checks that the given binary matrix is \(\Sigma_{n^{2}}\) and works in time \(O\left(n^{4}\right)\), i.e. \(\theta_{5}=O\left(n^{4}\right)\) and therefore \(z=4\).

Let \(A_{s t}=\left[\left(a_{s t}\right)_{k l}\right]_{n \times n}\) be an arbitrary \(n \times n\) matrix, \(0 \leq k, l, s, t \lt n\). Let \(A=\left[\alpha_{i j}\right]_{n^{2} \times n^{2}}, 0 \leq i, j \lt n^{2}\) be an \(n^{2} \times n^{2}\) matrix such that for every \(i, j, k, l, s, t\), \(0 \leq i, j \lt n^{2}\) and \(0 \leq k, l, s, t \lt n\), the equality

\[ \alpha_{i j}=\left(a_{s t}\right)_{k l} \] is satisfied. Then, taking into account that the numbering of indexes starts from 0,

it is easily seen that

(20)\[ i=s n+k \]

and

(21)\[ j=t n+l . \]

Algorithm 6. Checking that a binary \(n^{2} \times n^{2}\) matrix \(B=\left[\beta_{i j}\right] \in \Sigma_{n^{2}}\). The algorithm gets the elements of the matrix \(B=\left[\beta_{i j}\right]\) from the array a[] with size \(n^{4}\), such that \(\beta_{i j}=\mathrm{a}\left[\mathrm{i}^{*} \mathrm{n} 2+\mathrm{j}\right]\), where \(n 2=n^{2}, 0 \leq i \lt n^{2}-1,0 \leq j \lt n^{2}-1\).

For ease, we will not check for correctness of the input data, i.e. whether the input matrix is binary, in other words whether all its elements are 0 or 1. We leave this check to the reader for an exercise.

When we compare (18) with (12) and (14), as well as (19) with (13) and (15) we may assume that algorithms which use random \(\Pi_{n}\) matrices are expected to be more efficient (regard to probability and time for generating and checking) than algorithms using random \(\Sigma_{n^{2}}\) matrices to solve similar problems. This gives grounds for further examination of the \(\Pi_{n}\) matrices' properties.

5. Random Sudoku matrices

We will give a little bit more complex definition of the term ”disjoint” regarding \(\Pi_{n}\) matrices. Let \(C=\left[c_{i j}\right]_{2 n \times n}\) and \(D=\left[d_{i j}\right]_{2 n \times n}\), be two \(\Pi_{n}\) matrices. We regard \(C\) and \(D\) as disjoint matrices, if there are no natural numbers \(s, t \in\{1,2, \ldots n\}\) such that the ordered pair \(\left(c_{s t}, c_{n+t s}\right)\) is equal to the ordered pair \(\left(d_{s t}, d_{n+t s}\right)\).

The relationship between \(\Pi_{n}\) matrices and Sudoku matrices is illustrated by the following theorem, considering Proposition 4.1.

Theorem 5.1. There is a bijective map from \(\Pi_{n}\) to \(\Sigma_{n}{ }^{2}\) and the pair of disjoint matrices of \(\Pi_{n}\) corresponds to the pair of disjoint matrices of \(\Sigma_{n}{ }^{2}\)

Proof. Let \(P=\left[\pi_{i j}\right]_{2 n \times n} \in \Pi_{n}\). We obtain an unique matrix of \(\Sigma_{n^{2}}\) from \(P\) by means of the following algorithm:

Algorithm 7.

From a given matrix \(M=\left[\pi_{i j}\right]_{2 n \times n} \in \Pi_{n}\) we obtain a unique matrix \(A=\left[\alpha_{i j}\right]_{n^{2} \times n^{2}} \in \Sigma_{n^{2}}\). The algorithm gets the elements of the matrix \(M=\left[\pi_{i j}\right]_{2 n \times n}\) from the array p[] with size \(2 n^{2}\), such that \(\mathrm{p}\left[\mathrm{i}^{*} \mathrm{n}+\mathrm{j}\right]=\pi_{i j}, 0 \leq i \lt 2 n, 0 \leq j \lt n\) and obtained using Algorithm 5. The algorithm will write the elements of the matrix \(A=\left[\alpha_{i j}\right]_{n^{2} \times n^{2}}\) in the array a[] with size \(n^{4}\), such that \(\alpha_{i j}=\mathrm{a}\left[\mathrm{i}^{*} \mathrm{n}^{*} \mathrm{n}+\mathrm{j}\right]\), \(0 \leq i, j \lt n^{2}\).

For convenience, at the beginning of Algorithm 7, we constructed an auxiliary \(2 \times n \times n\) three-dimensional array b such that,according to equation (22)

(24)\[ \mathrm{b}[0][\mathrm{i}][\mathrm{j}]=\pi_{i j} \]

and according to equation (23)

(25)\[ \mathrm{b}[1][\mathrm{j}][\mathrm{i}]=\pi_{n+i j} \]

is satisfied for each \(i, j \in\{0,1, \ldots, n-1\}\).

For example, from the matrix

(26)\[ P=\left[\begin{array}{lll} 1 & 3 & 2 \\ 2 & 3 & 1 \\ 1 & 2 & 3 \\ 3 & 1 & 2 \\ 1 & 2 & 3 \\ 1 & 2 & 3 \end{array}\right] \in \Pi_{3} \]

we get the array b. For more clearly, to the left of the comma we will write the elements of \(\mathrm{b}[0]\), and to the right of the comma-the elements of \(\mathrm{b}[1]\) :

(27)\[ b=\left[\begin{array}{lll} 1,3 & 3,1 & 2,1 \\ 2,1 & 3,2 & 1,2 \\ 1,2 & 2,3 & 3,3 \end{array}\right] \]

From the array b, Algorithm 7 obtains a binary matrix \(A=\left[\alpha_{i j}\right]_{n^{2} \times n^{2}}\), \(0 \leq i, j \lt n^{2}\) of type (16) such that if \(A_{s t}=\left[\gamma_{i j}\right]_{n \times n}, 0 \leq s, t \lt n\) is a block in

(28)\(A\), then

\[ \gamma_{i j}=\left\{\begin{array}{l} i=s * n+b[0][s][t]-1 \\ j=t * n+b[1][s][t]-1 \end{array}\right. \]

From (24), (25) and (28) follows that there is a single 1 in each block \(A_{s t} \in A\).

Let \(s \in\{0,1, \ldots, n-1\}\). Since \(s\)-th row of the matrix \(P\) is a permutation, then there is only one 1 in every row of \(n \times n^{2}\) matrix

\[ R_{s}=\left[\begin{array}{llll} A_{s 0} & A_{s 1} & \cdots & A_{s n-1} \end{array}\right] \]

Similarly, since ordered \(n\)-tuple \(\left\langle p_{n+t}, p_{n+t}, \ldots, p_{n+t n}\right)\) which is \((n+t)\)-th row of \(P\) is a permutation for every \(t \in \mathbb{Z}_{n}\), then there is only one 1 in every column

of \(n^{2} \times n\) matrix \[ C_{t}=\left[\begin{array}{l} A_{1 t} \\ A_{2 t} \\ \vdots \\ A_{n t} \end{array}\right] \]

Therefore, the matrix \(A\) which is obtained with the help of Algorithm 7 is a \(\Sigma_{n^{2}}\) matrix.

For example, from the array B, which corresponds to the array (27) and using Algorithm 7, we obtain the \(\Sigma_{9}\)-matrix

\[ A=\left[\begin{array}{lllllllll} 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 \end{array}\right] \]

Since a unique matrix of \(\Sigma_{n^{2}}\) is obtained for every \(P \in \Pi_{n}\) by means ofAlgorithm 7, then this algorithm provides a description of the map \(\varphi: \Pi_{n} \rightarrow \Sigma_{n^{2}}\). It is easy to see that if there are given different elements of \(\Pi_{n}\), we can use Algorithm 7 to obtain different elements of \(\Sigma_{n^{2}}\). Hence, \(\varphi\) is an injection. But according to formulas (11) and (17) \(\left|\Sigma_{n^{2}}\right|=\left|\Pi_{n}\right|\), whereby it follows that \(\varphi\) is a bijection.

Analyzing Algorithm 7, we arrived at the conclusion that \(P\) and \(Q\) are disjoint matrices of \(\Pi_{n}\) if and only if \(\varphi(P)\) and \(\varphi(Q)\) are disjoint matrices of \(\Sigma_{n^{2}}\)

according to the above mentioned definitions. The theorem is proved.

Let \(\mathcal{M}_{n^{2}}\) be the set of all square \(n^{2} \times n^{2}\) matrices with elements of the set \(\mathbb{Z}_{n^{2}}=\left\{1,2, \ldots, n^{2}\right\}\), and let \(\sigma_{n}\) be the number of all \(n^{2} \times n^{2}\) Sudoku matrices. Obviously, \(\left|\mathcal{M}_{n^{2}}\right|=\left(n^{2}\right)^{n^{2}}=n^{2 n^{2}}\). Then if we use Algorithm 1 to obtain random Sudoku matrix. According to equation (1) there is the following probability evaluation:

(29)\[ p_{6}(n)=\tfrac{\sigma_{n}}{n^{2 n^{2}}} \]

When \(\mathrm{n}=2, \sigma_{2}=288\) [Yordzhev, 2013].

When \(n=3\), there are exactly \[ \sigma_{3}=6670903752021072936960 \approx 6.671 \times 10^{21} \] in number Sudoku matrices [Felgenhauer and Jarvis, 2006; Yordzhev, 2018]. As far as the author of this study knows, there is not a universal formula for the number \(\sigma_{n}\) of Sudoku matrices with every natural number \(n\). We consider it as an open problem in mathematics.

If we employ random methods to create the matrix \(P \in \mathcal{M}_{n^{2}}\) with elements of \(\mathbb{Z}_{n^{2}}\), then according to Algorithm 1 we need to verify if every row, every column and every block of \(P\) is a permutation of elements of \(\mathbb{Z}_{n^{2}}\). According to evaluation of Algorithm 3, every verification can be done in time \(O(n)\) (see equation (8)). Hence, when we employ Algorithm 1 to obtain a random Sudoku matrix we will obtain the following time for generating and checking:

(30)\[ \tau_{6}(n) \in T\left(\mathcal{A}_{n}\right)\left(n^{2}\right)^{2}+2 n O(n)+n^{2} O(n)=t_{0} n^{4}+2 n O(n)+n^{2} O(n) \in O\left(n^{4}\right) . \]

Here we will present a more efficient algorithm for obtaining random Sudoku matrix, based on the propositions and algorithms which are examined in the previous sections of this paper. The main point is to obtain \(n^{2}\) in number random \(\Pi_{n}\) matrices (Algorithm 5). For every \(\Pi_{n}\) matrix which is obtained, it has to be checked if it is disjoint with each of the above obtained matrices. The criteria, described in Theorem 5.1 and Proposition 4.1 are used in the verification. If the obtained matrix is not disjoint with at least one of the above mentioned matrices, it has to be replaced with another randomly generated \(\Pi_{n}\) matrix.

Algorithm 8. Obtaining random Sudoku matrix

\include <iostream>

With the help of Algorithm 8, we received a lot of random \(9 \times 9\) random Sudoku matrices, for example the next one:

\[ \left[\begin{array}{lllllllll} 6 & 4 & 2 & 3 & 1 & 7 & 8 & 9 & 5 \\ 5 & 3 & 1 & 8 & 2 & 9 & 4 & 7 & 6 \\ 7 & 8 & 9 & 4 & 5 & 6 & 2 & 3 & 1 \\ 9 & 6 & 7 & 2 & 4 & 5 & 1 & 8 & 3 \\ 3 & 2 & 4 & 6 & 8 & 1 & 9 & 5 & 7 \\ 1 & 5 & 8 & 9 & 7 & 3 & 6 & 2 & 4 \\ 8 & 9 & 5 & 1 & 3 & 4 & 7 & 6 & 2 \\ 2 & 1 & 3 & 7 & 6 & 8 & 5 & 4 & 9 \\ 4 & 7 & 6 & 5 & 9 & 2 & 3 & 1 & 8 \end{array}\right] \]

REFERENCES

Azalov, P. & Zlatarova, F. (2011). C++ v primeri, zadachi i prilozheniya. Sofia: Prosveta.

Dahl, G. (2009). Permutation matrices related to sudoku. Linear Algebra and its Applications, 430 (8-9): 2457 – 2463.

Felgenhauer, B.& Jarvis, F. (2006). Mathematics of sudoku. Mathematical Spectrum, 39 (1): 15 – 22.

Garey, M. R. & Jonson, D. S. (1979). Computers and Intractability. A Guide to the Theory of NP-Completeness. Bell Telephone Laboratories.

Hadzhikolev, E. & Hadzhikoleva, S. (2016). Osnovi na programiraneto s Java. Plovdiv: Paisiy Hilendarski (ISBN 978-619-202-108-5).

Hopcroft, J. E., Motwani, R. & Ullman, J. D. (2001). Introduction to Automata Theory, Languages, and Computation. AddisonWesley.

Todorova, M. (2002). Programirane na C++, volume I and II. Sofia: Ciela (ISBN 954-649-454-2(1), 954-649-480-1(2)).

Todorova, M. (2011a). Obektho-orientirano programirane na bazata na ezika C++. Sofia: Ciela (ISBN 978-954-28-0909-8).

Todorova, M. (2011b). Strukturi ot danni i programirane na \(\mathrm{C}++\) Sofia: Ciela (ISBN 978-954-28-0909-6).

Yato, T. (2003). Complexity and Completeness of Finding Another Solution and Its Application to Puzzles – Masters thesis. Univ. of Tokyo, Dept. of Information Science.

Yato, T. & Seta, T. (2003). Complexity and completeness of finding another solution and its application to puzzles. IEICE Trans. Fundamentals, E86-A(5): 1052 – 1060.

Yordzhev, K. (2012). Random permutations, random sudoku matrices and randomized algorithms. International Journal of Mathematical Sciences and Engineering Applications, 6 (VI): 291 – 302.

Yordzhev, K. (2013). On the number of disjoint pairs of s-permutation matrices. Discrete Applied Mathematics, 161 (18): 3072 – 3079.

Yordzhev, K. (2018). How does the computer solve sudoku – a mathematical model of the algorithm. Mathematics and Informatics, 61 (3): 259 – 264.