# 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 $3\times 3$ box.

In an easy-to-solve Sudoku, careful observation and backtracking are 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, changing 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.

The following are the rules of the $4\times 4$ Kenken above:

- Each row contains exactly one of each digit 1 through 4.
- Each column contains exactly one of each digit 1 through 4.
- Each colored group of cells is a cage containing digits which achieve the result $(K)$ using the specified operation $(+$ or $\times)$.

First, solve the puzzle, where $K$ is a strictly positive integer.

If there is a unique value of $K$, determine whether or not $x + y + z + w = K$.

Otherwise, i.e. if you believe there are more than one solutions with different values of $K$ for the given puzzle, choose "Multiple solutions."

$$

**Note:** Unlike standard Sudoku, KenKen can have cage(s) with repeated digits.

**Hint:** Observe the structure of this puzzle carefully. What can be said about those tetrominoes and the numbers in each row and column?

Here are the rules of sum Sudoku:

- Each and every column, row, and $2\times2$ box contains distinct numbers from 1 to 4.
- The white circle marked at four adjacent cells indicate that the sum of upper-left and bottom-right cells is the sum of upper-right and bottom-left cells.

What can we conclude about the circle sums in the puzzle?

$$

**Example:**

The setup in the top-left box is valid since $2 + 3 = 1 + 4 = 5$. However, the four cell values at the center are invalid since $4 + 2 \neq 3 + 1$.

Write a single positive digit $(\leq 6)$ into each empty square in the figure below, such that every number $(1, 2, 3, 4, 5, 6)$ appears in each row and in each column. The number in a circle shows the product of the four numbers around it.

If you are finished, find the minimum value of the product of the numbers in the pink squares!

$$

**Note:** Here is a sample, with digits $1, 2, 3, 4$:

## 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.