sudoku

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.

Title	sudoku
Canonical name	Sudoku
Date of creation	2013-03-22 16:15:27
Last modified on	2013-03-22 16:15:27
Owner	Mravinci (12996)
Last modified by	Mravinci (12996)
Numerical id	8
Author	Mravinci (12996)
Entry type	Definition
Classification	msc 91A24
Classification	msc 00A08