Random Permutations, Random Sudoku Matrices and Randomized Algorithms

Abstract

Some randomized algorithms, used to obtain a random n 2 × n 2 Sudoku matrix, where n is a natural number, is reviewed in this study. Below is described the set Πn of all (2n) × n matrices, consisting of elements of the set Zn = {1, 2, . . . , n}, such that every row is a permutation. It is proved that such matrices would be particularly useful in developing efficient algorithms in generating Sudoku matrices. An algorithm to obtain random Πn matrices is presented in this paper. The algorithms are evaluated according to two criteria - probability evaluation, and time evaluation. This type of criteria is interesting from both theoretical and practical point of view because they are particularly useful in the analysis of computer programs.