Solving Sudoku Research

Sudoku was invented by Howard Garns in 1979. The puzzle was first published as "Numbers in Place." The current name, Sudoku, was introduced by a Japanese known as Maki Kaji when he published it in his puzzle company magazine (Mantere & Koljonen, 2006). The term Sudoku can be translated to mean single numbers. New Zealand's Wayne Gould played a critical role in popularizing the puzzle by writing a computer program that generated Sudokus. These Sudokus were then printed in most newspapers across the world. Sudoku is a globally enjoyed puzzle since 2005 (Mantere & Koljonen, 2007).

Is your time best spent reading someone else’s essay? Get a 100% original essay FROM A CERTIFIED WRITER!

Save 25%

The universal type of Sudoku is made up of a 99 square grid which has 81 cells. The grid is further subdivided into nine 33 blocks. Some of the 81 cells are then filled in using numbers from the set made up of 1,2,3,4,5,6,7,8,9. These filled-in cells are usually referred to as givens. The main objective of the puzzle is to fill in the entire grid with the nine digits. Eventually, each row, each column, and each block should contain each of the numbers just once. The phenomenon of constraint on the rows, columns, and blocks is referred to as the One Rule (Felgenhauer & Jarvis, 2006).

The described puzzle above is known as a Sudoku of rank 3. Normally, a Sudoku of rank n indicates an n2n2 square grid, which is subdivided into n2 blocks, each of size nn. The numbers to be used in filling in the grid are 1, 2, 3, ..., n2. Even so, the One Rule still applies.

The standards terminologies to be used in this paper include:

• A square or cell which refers to one of the 81 boxes in the sudoku grid. All of which is to be filled with a digit between 1 and 9.
• A block is the 3 3 sub-grids of the main puzzle. Here, all of the numbers between 1 and 9 are supposed to appear exactly once in a given solution. A block is made up of columns and rows which will also be used in this study.
• A candidate is any number that could probably fit into a given square in the grid. The solution is achieved gradually with the elimination of candidates from the squares/cells.
• A virtual line is applicable whereby an individual knows the values of 8 of the 9 squares in a column or row. Normally, there are 27 virtual lines in a 9 x 9 Sudoku puzzle.
• Buddies refer to the squares/cells that cannot contain a given digit because they are in the same row, column or block. There are 20 buddies for each square.

How to Solve Sudoku Mathematically

The basic method of solving the Sudoku puzzle involves the use of both logic and trial-and-error. To unravel a Sudoku conundrum, one should start by noting, in each of the empty cells, all the candidates that do not oppose the One Rule as regards the specific cells. A forced entry can result from having a single possible entry to be filled in a given cell/square. Another strategy is to choose a digit together with a row, sub-grid, or column and determining all cells that the number fits in without going against the One Rule. The digit should be filled in at the appropriate cell/square; this allows one to eliminate the number from possibly occupying another square in the surrounding squares. However, the mentioned strategies are often not adequate in completing a Sudoku puzzle. This calls for more complex methods of analysis to complete the grid (Santos-Garcia & Palomino, 2007). The methods are often coupled with occasional guessing and backtracking whenever the guesses lead to conflicts. Therefore, mathematics is also important because it is utilized in combinatorics which is important when counting the actual Sudoku grids. Group theory is also used to determine when there are two equivalent grids. Lastly, computational complexity as a part of mathematics can be attributed to solving the Sudokus (Russell & Jarvis, 2006).

A common intricate strategy entails looking at the set of cells/squares in a given block, column, or row to find a couple of cells that have only two possible candidates; but none is definite which cell it should be placed in. Based on the observation, one is certain that the two candidates cannot be placed in the remaining cells of the assesses column, row, or block. Hence, this decreases the possibility of the remaining cells and thus facilitates filling in the grid faster. In the same way, a set of three cells can have the same number of candidates between them and thus they can be eliminated as possibilities for the triple's neighborhood cells (Russell & Jarvis, 2006). In case there is no forced entry, then it is advisable to find a block remaining with the least likelihoods and choose either of the candidates. Once there is a contradiction, the player should retrace their steps and correct it. Contradictions are normally repetitions of a particular digit in the same block, row, or column.

Counting the Number of Solutions

One may be curious enough to know the number of ways a 9 x 9 Sudoku puzzle can be filled such that it does not contradict the One Rule. This can be addressed by describing the method utilized in 2006 by Felgenhauer and Jarvis to calculate the number of distinct Sudoku solutions in existence Rule (Felgenhauer & Jarvis, 2006). For purposes of making the discussion clearer, the 3 rows and columns of blocks of the entire grid will be referred to as the band and stacks respectively. Additionally, a square/cell located in the ith position of a row and jth position of a column is in position (i, j). Lastly, N will represent the number of discrete Sudoku grids.

Let us begin by labeling the grid blocks as illustrated below:

The objective is to determine the valid number of ways to fill block B1. Given that we have 9 different digits that can fill the cells in B1 in the figure above, one in every 9 cells/ squares, then there are exactly 9 possibilities (candidates) for the opening cell (Taalman, 2007). This means only 8 options are remaining for the second cell/square; this applies for all the 9 available options. In the same way, there are only 7 options remaining for the subsequent cell for each of the 8 available options. Basically, this is a computation of the number of variations of 9 different digits; the number of ways the 9 digits can be arranged into the 9 cells/squares (Taalman, 2007). Therefore, there exists 9! different ways to fill up B1.

Other valid B1 blocks can be obtained, beginning with block B1 which is valid, by permuting or re-labeling the numbers. Hence, the basic simplifying assumption made is B1 above was filled up with numbers between 1 and 9 in that order as illustrated below.

Based on this, the valid grid conclusions this specific B1 has can be calculated; let it be N1. The maximum number of Sudoku grids that can be regarded as valid are N1 x 9!. Therefore, N1 = N/9! (Felgenhauer & Jarvis, 2006).

Let us consider the various ways of filling in the cells within the first rows in block B2 as well as B3. Given that digits 1, 2, and 3 appeared in the squares within the first row of block B1, then the digits cannot be used in any of the cells within the row. This means that only numbers between 4 and 9 can be utilized in the first row of the other blocks (B2 and B3). Note that these numbers are from the 2nd and 3rd rows of B1. For example, one can be required to identify all the probable ways they can fill the first-row cells both in block B2 and block B3 to the point of reordering the digits each of the blocks. Normally, there are 10 different ways of achieving this. Swapping block B2 and block B3, therefore, would lead to ten additional ways thereby translating to twenty ways in total. Of these likelihoods, two are referred to as pure top rows. In such a scenario, the numbers in the 2nd row of block B1 {4, 5, 6} are retained in block B2 and those in block B1's third row {7, 8, 9} are retained in that order in block B3, as well as the similar version that is swapped. The remaining possibilities are known as mixed top rows because the B1 set {4, 5, 6} as well as set {7, 8, 9} are mixed up when filling up block B2 and block B3's rows. The first band can, therefore, be completed given the twenty possible ways for the cells in the first row of such a grid (Felgenhauer & Jarvis, 2006). It should be noted that the twenty possibilities are limited to the rearrangement of the nine numbers in every block.

To determine the number of ways of completing the initial band, we assess the clean top row first. This can be denoted as 1, 2, 3; {4, 5, 6}; {7, 8, 9}, whereby a, b, c represents an ordered three numbers (triple numbers) while {a, b, c} denotes them in no particular order. B1 will remain fixed because we have already determined the total number of grids which is obtained through relabeling of the 9 digits within it. Evidently, it was recorded that there exists (3!)6 different ways of completing such a first band beginning with a pure top row of 1, 2, 3; {4, 5, 6}; {7, 8, 9} (Felgenhauer & Jarvis, 2006). Usually, this occurs as a result of placing {7, 8, 9}; {1, 2, 3} in block B2's second row and block B3 as well as {1, 2, 3}; {4, 5, 6} in the 3rd row. The three numbers in each of the 6 rows of block B2 and block B3 can be reordered to obtain same formations. The end result is same for all pure top row in the grid because they entail a swap of block B2 with block B3. However, the mixed top rows may prove to be more complicated. To express this, we will consider a top row containing 1, 2, 3; {4, 6, 8}; {5, 7, 9}. This row can be filled up as shown in the table below.

The moment a is selected, it means both b and c become the remaining candidates in no particular order because they are located in the specific row. There are three possible options for a. Three numbers in every six sets in block B2 and block B3 can, therefore, be calculated to obtain different first bands. For this case, the number of formations are 3 (3!) 6. This also applies to the rest of the 17 cases for the first row.

We can now obtain the number of likely first bands based on the typical block B1 as 2 (3!)6 + 18 3 (3!)6 = 2612736 (Russell & Jarvis, 2006). The total number of the first band conclusions likely from pure top rows is represented by the first part of the sum whereas the mixed top rows are represented by the second part of the sum. Jarvis and Felgenhauer (2006) indicated the first bands which shared a similar number of full grid conclusions and thus there is no need to calculate the number of full grid completions for each of the 2612736 possibilities Rule. Their analysis significantly reduces the total number of first bands expected to be well-thought-out when counting.

There are a number of operations that do not change the number of grid conclusions for the first band. These include relabeling of the digits, permuting either of the blocks within the band. Also, permuting the columns in any of the columns and 3 rows of the first band do not affect the first band. The standard form of block B1 can be restored by relabeling the digits in case of changes to block B1 resulting from any of these operations. The number of grid conclusions is preserved when permuting block B1, block B2, and block B3. This is possible because, starting with a binding Sudoku grid, the possible way of ensuring it is valid is by permuting block B4, block B5, block B6 in correspondence to blocks B7, B8, and B9 such that stacks will still remain as they were (Russell & Jarvis, 2006).

For example, the number of grid conclusions can be preserved while performing various operations on a specified first band as follows. First, the first two rows should be exchanged and relabeled such that block B1 remains in a standard form (Russell & Jarvis, 2006). Then reduce the grid lexicographically as shown below.

The main aim is to ensure the band at the start and the other band at...