Click here to Skip to main content
13,898,182 members
Click here to Skip to main content
Add your own
alternative version


55 bookmarked
Posted 9 Dec 2005
Licenced CPOL

Another Sudoku Solver and Generator

, 9 Dec 2005
Rate this:
Please Sign up or sign in to vote.
A program to help you to solve Sudoku problems or check if a Sudoku problem has only one solution.

Sample Image - sudoku2.png


Yet another Sudoku solver and generator, the first one in CodeProject, in VB though. It searches all the solutions for a given Sudoku problem on the fly. The interface is simple; the search is continuous and quite fast. It is therefore useful if you want to generate your own problems.


A large part of this article is extracted from: Please refer to it for more details on Sudoku.

From Wikipedia, the free encyclopedia

Sudoku (Japanese: 数独, sūdoku), sometimes spelled Su Doku, is a logic-based placement puzzle, also known as Number Place in the United States. The aim of the canonical puzzle is to enter a numerical digit from 1 through 9 in each cell of a 9x9 grid made up of 3x3 subgrids (called "regions"), starting with various digits given in some cells (the "givens"). Each row, column, and region must contain only one instance of each numeral. Completing the puzzle requires patience and logical ability. Although first published in 1979, Sudoku initially caught on in Japan in 1986, and attained international popularity in 2005.

Solving the puzzle

The program uses a technique called 'backtracking search', according to Wikipedia.

This means it assigns a value (say, 1, or the nearest available number to 1) to the first cell (say, the top left hand corner), and then moves on to assign the next available value (say, 2) to the next available cell. This continues until a conflict occurs, in which case the next alternative value is used for the last cell changed. If a cell cannot be filled, the program backs up one level (from that cell) and tries the next value at the higher level (hence the name backtracking).

This method is very simple, and it solves most problems in less than a minute.

Speed improvement 1

To improve the speed, the program also keeps track of values played for each row, column, and and 3x3 box. Three arrays are used, horz(), vert(), and box(). horz(0) indicates which cells are already entered in the first horizontal line. horz(1) indicates which cells are already entered in the second horizontal line...

To know what values can be played in the cell in line 3 and column 2, the program must check horz(3), vert(2), and box(0).

Also, each value is encoded using a 9 bits binary mask.

  • A Sudoku value of 1 is encoded with a 1
  • A Sudoku value of 2 is encoded with a 2
  • A Sudoku value of 3 is encoded with a 4
  • A Sudoku value of 4 is encoded with an 8
  • ...
  • A Sudoku value of 9 is encoded with a 256

The binary format is very convenient; in order to check which value has been played in line 3 column 2, the program can do:

dim played as integer
played = horz(3) or vert(2) or box(0)

Speed improvement 2

The second best improvement is fairly straightforward. This problem, like most game solvers, can be seen as a tree parsing program. And again, like most problems of this type, it is always better to start with the maximum constraint first. So rather than trying to play the first cell in the top left corner, the program finds which cell has less number of values fitting, and plays that one first.

' try to find the cell with the most constraints
For i As Integer = 0 To 81 - 1
  curCell = CellsArray(i)
  With curcell
    If .played = False Then
       If .forcedVal > 0 Then
            ' found a very good one
            bestCell = curCell
            Exit For
            ' try to calculate the constraints for curCell
            Dim pos As Integer = horz(.y) Or vert(.x) Or box(.box)
            curCellConstraint = nbBits(pos)
            If curCellConstraint > constraintMax Then
                bestCell = curCell
                constraintMax = curCellConstraint
                If constraintMax = 9 Then Exit For
            End If
        End If
    End If
    End With

Generating puzzles

When creating a Sudoku, you must keep in mind that there can be only one solution for it; otherwise, it is not considered a real Sudoku. Just enter values in the demo program until it displays the number of solutions = 1.


Sudoku is not the most complicated or interesting problem to solve with a computer. If you want a more complicated problem, look at the Mac Mahon article I posted earlier this year. If you know of any puzzle or problem that you think would be interesting to solve, please write to me or in the forum below. I hope some people will find this program interesting. I have tried to make it easy to use; your comments are welcome.


  • 9 December 2005 - First submission.


This article, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)


About the Author

Pascal Ganaye
Software Developer (Senior)
France France
I am a French programmer.
These days I spend most of my time with the .NET framework, JavaScript and html.

You may also be interested in...

Comments and Discussions

GeneralDirect link Pin
Sir Mari023-Feb-13 23:45
memberSir Mari023-Feb-13 23:45 
GeneralIt's the easy way Pin
Simon Dufour26-Aug-10 8:54
memberSimon Dufour26-Aug-10 8:54 
GeneralRe: It's the easy way Pin
Pascal Ganaye26-Aug-10 10:22
memberPascal Ganaye26-Aug-10 10:22 
GeneralRe: It's the easy way Pin
Simon Dufour26-Aug-10 11:50
memberSimon Dufour26-Aug-10 11:50 
Generalgood job Pin
karakaya1329-Jun-09 21:33
memberkarakaya1329-Jun-09 21:33 
GeneralRe: good job Pin
Pascal Ganaye6-Jul-09 11:29
memberPascal Ganaye6-Jul-09 11:29 
GeneralHELP Pin
hieuphan23-Apr-08 23:30
memberhieuphan23-Apr-08 23:30 
GeneralSudoku with backtracking Pin
Shunya15-Mar-08 3:43
memberShunya15-Mar-08 3:43 
GeneralA Possible Job For You Pin
Polymorpher10-Aug-06 11:25
memberPolymorpher10-Aug-06 11:25 
Generalhello... help plz Pin
Han_headache26-Apr-06 12:06
memberHan_headache26-Apr-06 12:06 
QuestionHow about a Print feature Pin
JohnnyB321-Feb-06 16:41
memberJohnnyB321-Feb-06 16:41 
AnswerRe: How about a Print feature Pin
Pascal Ganaye22-Feb-06 8:49
memberPascal Ganaye22-Feb-06 8:49 
GeneralGriddlers Pin
JohnWillemse18-Jan-06 2:42
memberJohnWillemse18-Jan-06 2:42 
GeneralRe: Griddlers Pin
Pascal Ganaye18-Jan-06 7:30
memberPascal Ganaye18-Jan-06 7:30 
GeneralJigsaw Sudoku Solver Pin
Randy Friend16-Dec-05 9:57
memberRandy Friend16-Dec-05 9:57 
GeneralEnfin :) Pin
LaFéeClochette13-Dec-05 4:04
memberLaFéeClochette13-Dec-05 4:04 

General General    News News    Suggestion Suggestion    Question Question    Bug Bug    Answer Answer    Joke Joke    Praise Praise    Rant Rant    Admin Admin   

Use Ctrl+Left/Right to switch messages, Ctrl+Up/Down to switch threads, Ctrl+Shift+Left/Right to switch pages.

Permalink | Advertise | Privacy | Cookies | Terms of Use | Mobile
Web05 | 2.8.190306.1 | Last Updated 9 Dec 2005
Article Copyright 2005 by Pascal Ganaye
Everything else Copyright © CodeProject, 1999-2019
Layout: fixed | fluid