# Programming Sudoku

**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.

## Sudoku Algorithms

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

## Testing Sudoku Programs

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

## General N^{2} by N^{2} Sudokus

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.

## Clipboard and File Formats

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.

This article is incomplete. You can help
Sudopedia by expanding it. |