by Roxanne Manning

Sudoku is a logic-based placement puzzle with an aim to enter a numerical digit from 1 through 9 in each cell of a 9X9 grid. Although the first sudoku puzzle was published in the U.S., it did not attain international popularity until 2005. Solving sudoku puzzles generally involves a combination of three processes. These include scanning, marking up and analyzing. Following is a brief guide to solving soduku.

1. Scanning: Scanning generally takes place not only at the outset but also throughout the solution and consists of two basic techniques. (a) cross-hatching involves scanning rows or columns to identify which line in a particular region may contain a certain numeral by a process of elimination. (b) counting 1-9 in regions, rows and columns to identify missing numerals. Counting based upon the last numeral discovered may speed up the search.

2. Marking Up: Once no further numerals can be discovered, sudoku players often find it necessary to mark potential numerals in blank cells. This can be done by actually writing in numerals or dots to represent potential numerals.

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.

by Danny Demeersseman

Originally called Number Place, the first puzzle was created by Howard Garnes, a freelance puzzle constructor, in 1979.

The puzzle was first published in New York in the late 1970s by the specialist puzzle publisher Dell Magazines in its magazine Dell Pencil Puzzles and Word Games, under the title Number Place.

The puzzle was introduced in Japan by Nikoli in the paper Monthly Nikolist in April 1984 as “Suji wa dokushin ni kagiru”, which can be translated as “the numbers must be single”. At a later date, the name was abbreviated to Sudoku (pronounced sue-do-koo; su = number, doku = single).

In 1986, Nikoli introduced two innovations: the number of givens was restricted to no more than 30 and puzzles became “symmetrical” (meaning the givens were distributed in rotationally symmetric cells). Within Japan, Nikoli still holds the trademark for the name Sudoku; other publications in Japan use alternative names.

In 1989, Loadstar/Softdisk Publishing published DigitHunt on the Commodore 64, which was apparently the first home computer version of Sudoku. At least one publisher still uses that title.