The Structure of Reduced Sudoku Grids and the Sudoku Symmetry Group

A Sudoku grid is a constrained Latin square. In this paper a reduced Sudoku grid is described, the properties of which differ, through necessity, from that of a reduced Latin square. The Sudoku symmetry group is presented and applied to determine a mathematical relationship between the number of reduced Sudoku grids and the total number of Sudoku grids for any size. This relationship simplifies the enumeration of Sudoku grids and an example of the use of this method is given. 1. Introduction A Sudoku grid, , is a array subdivided into minigrids of size ？？(where . consists of ？？bands, each composed of horizontally consecutive minigrids, and ？？stacks, each composed of vertically consecutive minigrids. Each minigrid possesses subrows, or tiers and subcolumns, or pillars. The values are contained within the array in such a way that each value occurs exactly once in every row, column, and minigrid. The discussion that follows requires analysis of the enumeration of Sudoku grids and therefore the following notation is required: is the number of ways of arranging the values in . A Sudoku grid is a constrained Latin square. The calculation of the number of Latin squares, of some dimension, is greatly simplified by only counting those Latin squares which are in reduced form. A Latin square, or rectangle, is reduced if the values in the first row and column are in the natural order [1]. There are far fewer reduced Latin squares than Latin squares, and there exists a mathematical relationship allowing a direct calculation of the number of the latter from the number of the former. If the first row and first column of a Sudoku grid are in the natural order there is no longer a direct mathematical relationship between the number of these and the number of Sudoku grids. Therefore reduced Sudoku grids, defined in this paper, have different properties to reduced Latin squares. In [2–5] the number of reduced Latin squares (for sizes 8 to 11) is calculated. In a recent article, Stones [6] surveys some well-known and some more recent formulae for Latin rectangles, their usefulness, and means to obtain approximate numbers. If is the number of reduced Latin rectangles of size then the total number of Latin rectangles, , [1] is as follows: A similar relationship is developed here between the total number of Sudoku grids and the number of reduced Sudoku grids. Such relationships have previously been given for “NRC-Sudoku” [7] and “2-Quasi-Magic Sudoku” [8] where the focus is the symmetry groups for these structures; symmetry groups have been defined for [9], [10], and the