Mirrored from **Sudopedia**, the Free Sudoku Reference Guide

A good place to start when you want to write your own Sudoku program is the Sudoku Programmers forum.

## Contents |

- Dancing Links | DLX
- Binary Integer Linear Program
- Box Canonicalization of a Floor
- Box Canonicalization of a Grid

- Test Cases — a set of formal tests for Sudoku software

This wiki specializes on the standard 9 by 9 Sudoku, but we can generalize this puzzle game into a N^{2} by N^{2} one, where every row, every column, and every N by N box must contain each of the digits 1 to N^{2}.

**Creating** a generalized Sudoku puzzle is known to be NP-complete, which means that it is very unlikely to have an efficient algorithm that create a minimal puzzle in N^{2} by N^{2} Sudoku with efficient meaning running time polynomial in N.

**Solving** an N^{2} by N^{2} Sudoku by using clues and logic to uncover the unique solution through can be done by a computer program running time approaching polynomial time in N.

Essentially the difference between **creating** and **solving** a puzzle depends on whether or not *guesses* have to be made. You have to guess a lot to create a puzzle. But if the created puzzle only uses methods which are known, then solving the puzzle doesn't need any *guesses*. It would also seem that for any known puzzle that guessing would have a minimal impact. The sample space for possible solutions for the 9x9 grid of a normal Sudoku puzzle is so small that guessing at a particularly hard point in the solution has little consequence. In fact 9x9 puzzles can be solved entirely by a simple brute brute force backtracking depth first algorithm (which is NP-complete). Such a backtracking algorithm would not be feasible as as the puzzle size gets bigger. So a puzzle with a grid of 4,294,967,296 x 4,294,967,296 using 65,536 symbols would be impractical for a backtracking algorithm, but quite feasible for a program using logic.

References:

- Takayuki Yato and Takahiro Seta. Complexity and completeness of finding another solution and its application to puzzles. IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, E86-A(5):1052–1060, May 2003.

Sudoku Clipboard and File Formats documents various file and clipboard formats that have been created to share puzzles. Common formats for hardcopy printing have also been documented.