Sudoku Math – The Mathematics Involved in Sudoku
NP_complete: The general problem of solving Sudoku puzzles on n2 x n2 boards of n x n blocks is known to be NP-complete. This gives some indication of why Sudoku is difficult to solve, although on boards of finite size the problem is finite and can be solved by a deterministic finite automaton that knows the entire game tree.
Solving Sudoku puzzles (as well as any other NP-hard problem) can be expressed as a graph colouring problem. The aim of the puzzle in its standard form is to construct a proper 9-colouring of a particular graph, given a partial 9-colouring. The graph in question has 81 vertices, one vertex for each cell of the grid. The vertices can be labelled with the ordered pairs (x,y), where x and y are integers between 1 and 9. In this case, two distinct vertices labelled by (x,y) and (x’,y’) are joined by an edge if and only if:
* x = x’, or,
* y = y’, or,
* [x/3] = [x'/3] and [y/3] = [y'/3]
The puzzle is then completed by assigning an integer between 1 and 9 to each vertex, in such a way that vertices that are joined by an edge do not have the same integer assigned to them.
Pages: 1 2