Mirrored from Sudopedia, the Free Sudoku Reference Guide

Programming Sudoku

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

Contents

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 N2 by N2 Sudokus

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

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


Solving an N2 by N2 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:

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 page was last modified 01:28, 9 October 2010.