Programming Sudoku

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² by N² Sudokus

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

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² by N² Sudoku with efficient meaning running time polynomial in N.

Solving an N² by N² 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.