The Sudoku puzzle is unlike most puzzles in that it is based on mathematical structure and requires some level of logic in order to be solved. The main basis behind solving Sudoku is called “NP-complete” because it is solved on n2 x n2 grids of n x n cells. It is this concept that makes Sudoku so difficult to solve. When you put cells on grids and throw in a few “givens” it takes some determining finite power to solve the puzzle correctly.
Sudoku has what is known as a “game tree”. The game tree of this puzzle game is quite large and, when there is only one solution to be found, makes solving it fast an unfeasible plan. There are, however, tips that you can use to solve Sudoku as fast as possible.
Perhaps an easy way of describing the solution of a Sudoku puzzle is to call it a “graph coloring problem”. The basic goal of the puzzle is to build, in its standard form of 9 x 9, a coloring grid. The entirety of the graph is composed of 81 vertices, with one vertex for every cell on the grid. Each of the vertices can be named with pairs that are ordered and where “x” and “y” are integers anywhere from one to nine. This means that two separate vertices are names and are connected by an edge if, and only if the edges match. The Sukoku puzzle is eventually solved by assigning an integer, from one to nine, to each of the vertices in a way where the vertices connected by an edge don’t have the same integer assigned to them.
A Latin Square
The solution of the Sudoku grid is much like a Latin square. There are, however, less solution grids for Sudoku, than there are Latin squares. This is because Sudoku has the additional problem of multiple regions. Still, there are endless solution grids for the Sudoku puzzle. In 2005 Bertram Felgenhauer calculated the number to be about 6,670,903,752,021,072,936,960. He arrived at this number using logical computations. The analysis of the number of solution grids was further simplified by Frazer Jarvis and Ed Russell. It has not yet been calculated how many solution grids there are for the 16 x 16 Sudoku puzzle.
There are some 9 x9 grids that can be recreated into other grids. This can be done by (1) rotating or reflecting the grid, (2) permuting some columns and rows, and (3) changing around the numbers. In 2005 Frazer Jarvis and Ed Russell calculated the number of different Sudoku grids that could be created and came up with a total of 5,472,730,538.
Unique Grids
In order to keep the Sudoku grid unique it’s important not to provide too many “givens”. The maximum number of “givens” that can be included in a puzzle before the grid solution is considered too unique is four less of a full grid. When there are two instances of two numbers which are each missing, and the cells which they are supposed to fill are each the corners of an orthogonal rectangle, there will only be two ways in which the numbers may be added together.
The opposite of this is just as true. The least number of “givens” that can be used before a solution is unique, or rather is a puzzle that can’t be solved, is 17. Some Japanese puzzle experts believe that this number is 18. Regardless how the least number of “givens” are rotated, the Sudoku puzzle will be unsolvable unless there are enough “givens” to make it symmetric.
Mathematically, the Sudoku puzzle is a work of art that has only one solution. This means that you may almost complete the puzzle only to find that it is one cell that turns out to be wrong. You will have no choice but to start over so that you can accurately place the numbers in the regions.
Continue to Chapter 4...
