|
|
|
|
|
Sudoku is a logic puzzle, usually consisting of a 9 by 9 grid subdivided into 3 by 3 squares, some of which are marked with numerals from 1 to 9 (the givens). The goal of the puzzle is to mark the rest of the grid so that the result is a Latin square, that is, so that each row, column, and subgrid has all of the numerals 1 to 9 with no duplicates.
Given a partially filled $n \times n$ Latin square, the problem of testing if it extends to a complete Latin square is NP-complete.
Thus, a sudoku usually has 81 squares with about 30 givens. A sudoku can have a unique solution with as few as 17 givens (or 18 if symmetry of givens is required), but it's also possible for it to have as many as 77 givens (just four squares short of solving) and still lack a unique solution.
|
"sudoku" is owned by Mravinci.
|
|
(view preamble | get metadata)
Cross-references: symmetry, solution, NP-complete, complete, column, row, Latin square, squares, grid, logic
There are 2 references to this entry.
This is version 5 of sudoku, born on 2006-09-16, modified 2007-01-26.
Object id is 8364, canonical name is Sudoku.
Accessed 1424 times total.
Classification:
| AMS MSC: | 91A24 (Game theory, economics, social and behavioral sciences :: Game theory :: Positional games ) | | | 00A08 (General :: General and miscellaneous specific topics :: Recreational mathematics) |
|
|
|
|
|
|
Pending Errata and Addenda
|
|
|
|
|
|
|
|
|
|
|
