Sudoku Solver

Sudoku Solver

What is this

It's obviously a solver for Sudoku puzzles. Since it has been written for the HP 200LX in QuickBASIC, it tries to be smart about solving the sudoku, and not simply backtrack/bruteforce the whole thing.

How it works

The source code is pretty well-documented, however in german. Here is a short overview in english:

Strategy 1

This strategy utilizes the exclusion principle: The "possible numbers" for each field are updated according to their horizontal, vertical and 3x3 neighborhood. If in a certain field, only one number is not excluded, then we can write this number into the field.

This strategy is repeated until it leads to no new results.

Strategy 2 and 3

If the first strategy fails in a pass, then we continue with checking for pairs or n-tuples of numbers: If in a row there are two fields with "either 2 or 9" in them, then we can tell for sure that in no other field there is a 2 or a 9. The possible numbers for affected fields are updated accordingly and we continue with strategy 1.

If searching for pairs did not help, we do the same thing for n-tuples, which is much more cpu intensive (and thus only chosen as a last resort).

Compilation

The sudoku solver is written for QBasic/QuickBASIC; www.qbasic.de is an excellent resource for this programming language. However, it can also be compiled with FreeBASIC, which is a modern and free (as in speech) successor to QBasic. Use the -lang qb command line switch in this case:

fbc -lang qb sudoku.bas

Screenshot

? ? ?  ? ? ?  ? ? ?
? ? ?  ? ? ?  ? ? ?   Sudoku-Knacker     Version 3.0
? ? ?  ? ? ?  ? ? ?   Copyright 2008 by Florian Jung
                      Lizenz: GPL3 oder höher
? ? ?  ? ? ?  ? ? ?   Kontakt: flo@windfisch.org
? ? ?  ? ? ?  ? ? ?   ICQ:     305-487-969
? ? ?  ? ? ?  ? ? ?

? ? ?  ? ? ?  ? ? ?
? ? ?  ? ? ?  ? ? ?
? ? ?  ? ? ?  ? ? ?


Bitte die gegebenen
Zahlen eingeben, für
ein leeres Feld 0, ?
oder [LEER], Korrek-
tur mit [BACKSPACE]

Usage

Upon startup, you can enter the sudoku line by line. For blank fields, press the spacebar.

It will then try to solve the sudoku; this takes several minutes on the HP200LX, and probably few milliseconds on a modern computer :).

Download

The sudoku solver is available for download here.

Its license can be obtained here.