Figure 1.1 - A classic Sudoku puzzle and it's unique solution.

Figure 1.1 is an example of a classic Sudoku puzzle and its completed solution. In this example, the first row contains the set {1, 4, 7, 2, ∅, 8, 3, 6, 9}, which is missing the number 5. Inserting any other value besides 5 would create a repetition in the set and subsequently violate the rules. This logical deduction is based on the values already found in the row set; however, each value in the row set is also a member of two other sets – the column and region sets. For example, the fifth element from the top row (∅) also belongs to a column set containing {∅, 6, 7, 8, ∅, 1, 2, 3, 4} and a region set of {2, ∅, 8, 3, 6, 9, 4, 7, 1}. Notice that the value 5 is missing from the column set and region set, as well as the row set. If this were not the case, the puzzle would be invalid since it would be impossible to place any other value besides 5 in the row set.

Intrigue about classic 9×9 Sudoku problems found in the daily gazette stems from their ability to be solved by a human player using logic and reason. The intrigue of Sudoku as a computational problem stems from the puzzle’s classification as NP-Complete, which implies that the search time for finding solutions to Sudoku puzzles is expected to grow exponentially as the puzzle’s size increases. NP-Complete classification of the Sudoku conundrum is attributed to the rules of Sudoku, which enforces numerical constraints on valid solutions. These constraints present a particularly interesting challenge to search algorithms since the placement of any value into a partially complete puzzle will not only affect the placement of future values, but also influence the previous puzzle values as well.