# Sudoku

Sudoku is a logic-based puzzle. It is a type of *constraint satisfaction problem*, where the solver is given a finite number of objects (the numerals 1-9) and a set of conditions stating how the objects must be placed in relation to one another. The puzzle consists of a \(9\times 9\) grid further divided into nine \(3×3\) sub-grids (also called boxes, blocks, regions, or sub-squares).

The objective is to place the digits within the grid so that each column, row, and sub-grid contains all of the digits from \(1\) to \(9\). Each puzzle is published with some of the boxes already filled in, and those constraints help define the problem's difficulty level.

People sometimes say *there is no math required to solve sudoku*. What they really mean is, there is no *arithmetic* involved in sudoku. Mathematical thinking in the forms of deductive reasoning and algorithms are the basic tools for solving sudoku puzzles.

## Strategies for Solving Sudoku

There are numerous ways to solve a sudoku puzzle. Backtracking is the most commonly used and easy to understand, though probably not the most efficient. The constraints given at the beginning of the puzzle narrow down the available numerals that can be placed in the empty boxes. For each blank, the solver can build a *candidate bank*, a list of all the numbers that meet the known constraints. When the candidate bank has been narrowed to one for a particular space, that numeral can be added to the grid. Each (correct) answer adds further constraints for the remaining spaces in the same row, column, or box, helping to narrow the candidate banks for the remaining questions.

When backtracking, it helps to keep all the dimensions of the puzzle in mind, and to look horizontally and vertically for clues, as well as within each 3x3 box.

In an easy to solve sudoku, careful observation and backtracking is usually all it takes to solve the puzzle. In more advanced puzzles, it may be necessary to guess and check (which is why sudoku is best practiced with a pencil), or to find a more sophisticated way to process the clues.

Donald Knuth developed a backtracking algorithm called Algorithm X and a technique called Dancing Links (DLX) to utilize it. This algorithm provides a more efficient means for solving sudoku puzzles.

Solve the sudoku below:

Using the rules and goals of a Sudoku puzzle there are many thousands of possible arrangements of digits that would satisfy the conditions for a proper Sudoku solution.

Given a proper Sudoku solution. How many distinct (unique) arrangements of the digits in the grid could be presented by simply swapping the digits in individual cells?

For example, change all the 9s to 1s and 1s to 9s would produce a different arrangement in the grid, but would still be a legitimate correct solution.

## Sudoku in Research

Sudoku puzzles have several qualities that make them useful in cognition studies. Sudoku is a sustained task that requires concentration and strategizing, but the rules are relatively simple and can be learned quickly by most test subjects. Sudoku has been used as a performance measure in studies on aging [1], distractions [2], multitasking [3], and other brain-related subjects.

## Sudoku Competitions

A World Sudoku Championship has been held annually since 2006 [4]. The venue rotates among countries in Asia, Europe, and North America.

## Variations

Although the format previously discussed, the \(9\times 9\) grid with \(3\times 3\) regions, is the most common, many other variations exist. They often incorporate new shapes into the puzzle design, expand the grid, or add extra constraints to the puzzle.

## References

[1] Pieramico V, Esposito R, Sensi F, et al. Combination training in aging individuals modifies functional connectivity and cognition, and is potentially affected by dopamine-related genes. PLoS ONE. 2012;7(8):e43901.

[2] Strigo IA, Simmons AN, Matthews SC, Craig AD. The relationship between amygdala activation and passive exposure time to an aversive cue during a continuous performance task. PLoS ONE. 2010;5(11):e15093.

[3] Shih SI. A null relationship between media multitasking and well-being. PLoS ONE. 2013;8(5):e64508.

[4] World Sudoku Championships http://www.worldpuzzle.org/championships/wsc/ Accessed February 16, 2016.

[5] Image from https://commons.wikimedia.org/wiki/File:World*Sudoku*Championship*2015*Sofia*Bulgaria*02.JPG under Creative Commons licensing for reuse and modification.

[6] Image from https://commons.wikimedia.org/wiki/File:World*Sudoku*Championship*2015*Sofia*Bulgaria*05.JPG under Creative Commons licensing for reuse and modification.

[7] Image from https://commons.wikimedia.org/wiki/File:25by25sudoku.png under Creative Commons licensing for reuse and modification.

[8] Image from https://commons.wikimedia.org/wiki/File:Oceans*Hypersudoku18*Solution.svg under Creative Commons licensing for reuse and modification.

[9] Image from https://commons.wikimedia.org/wiki/File:Sudoku*3D*sol.gif under Creative Commons licensing for reuse and modification.