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