Click here to Skip to main content
Click here to Skip to main content
Go to top

Sudoku Solver

, 7 Feb 2007
Rate this:
Please Sign up or sign in to vote.
Sudoku solver using a backtracking algorithm
Sample Image - sud.jpg

Introduction

As the name indicates, the project is to solve a Sudoku puzzle. It also includes some special features.

Background

A knowledge of backtracking algorithms such as Solution to the N Queens problem would be helpful.

Concepts Used

Backtracking

Some problems can be solved in a certain number of steps sequentially, wherein in each step we have to choose between certain number of possibilities. We make a guess of the choice among the possibilities and proceed to the next step. After making each choice, we check whether it is feasible. If not, we make a different choice. At a certain step, if none of the possibilities turns out to be feasible, we know that anyone/some of our guesses is/are wrong. Hence, we go to the previous step and make a different choice and proceed. Hence the name backtracking.

Some Special Features

  1. Can solve partial Sudoku puzzles (Can solve Sudoku puzzles having more than one solution).
  2. Can find out the number of solutions a given puzzle has.
  3. Can check validity of a given puzzle.
  4. The digits which are part of the problem appear in a color different from the other digits in the solution.
  5. Any modification to a problem can be done after it has been solved easily by clicking "Modify input" button.
  6. Has an easy-to-use interface.

Using the Code

All important parts of the code are provided with appropriate comments and hence I feel not much explanation is needed of the code here. I would like to get the reader's reaction to this issue.

The code consists of the following classes among others:

  1. sudokugame: Contains the heart of the project (the function evaluate() to solve the puzzle). The function validsarr(bool comp) is used to find whether a given array is a completely (if comp=true)/incompletely (if comp=false) filled valid Sudoku row/column/grid.
  2. LIST: A template class containing some list operations. An object of this class is used in class sudokugame to store solutions of a given puzzle.
  3. num: A class derived from System::Windows::Forms::DomainUpDown. Includes two integers i & j. An object of this class represents a position in a Sudoku matrix. i &j represent the row & column of the position respectively.
  4. barrs: A class similar to list but more appropriate to use in function evaluate().

Points of Interest

  1. We may think of improving the backtracking procedure by using more intelligence in function evaluate().
  2. The backtracking procedure seemed to be the most appropriate procedure since:
    1. It is quite simple to apply to this problem.
    2. Any solution involving recursive calls would surely result in a stack overflow during runtime.
    3. A procedure involving guesses is the most appropriate since a procedure involving conformative evaluation in each step would be very complex, if possible.

How to Use

  1. Just run the demo project. To do this, download the file sud_demo.zip. Unzip the file. Run the file sud_demo/release/sudoku.
  2. Fill in the puzzle. The numbers can be fed using tab key and the keypad quickly or by using just the mouse leisurely.
  3. Click the Submit button.
  4. You see the solution.
  5. If the problem has many solutions, the first 10 (LIMIT defined in stdafx.h) are only evaluated.
  6. To see the next solution, click the Next Solution button.
  7. If you want to modify the problem, click the Modify input button.
  8. To enter a new problem, click Clear All.

History

  1. Initially, I did not use the barrs objects in function evaluate(), instead I'd used LIST<int> objects.
  2. Even before that, I did not even use these lists and had designed an evaluation involving only backtracking.
  3. Also, previously sudokugame was an unmanaged class.

License

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

Share

About the Author

kbsbng
Technical Lead Yahoo!
India India
I've studied info. sc. engg. from Sir MVIT, Bangalore.
 
I'm interested in programming.
 
Some of my technical blogs:
 
http://perl-blog.kbsbng.com/
http://java-blog.kbsbng.com/
 
I also enjoy writing some webpages such as http://sites.google.com/site/plantencyclopedia/
 
More about me at http://www.kbsbng.com and http://blog.kbsbng.com.
Follow on   Twitter   Google+

Comments and Discussions

 
QuestionWhere next ? Pinmemberboffin6328-Jun-07 8:58 
AnswerRe: Where next ? Pinmemberjonpetitta28-Jun-07 11:24 
GeneralRe: Where next ? Pinmemberboffin6329-Jun-07 3:36 
QuestionWhere's the source? PinmemberLee Middleotn10-Feb-07 22:24 
AnswerRe: Where's the source? Pinmemberkbsbng10-Feb-07 22:27 
AnswerRe: Where's the source? Pinmemberkbsbng10-Feb-07 22:32 
GeneralSomething misssing PinmemberBradml26-Jan-07 23:41 
GeneralRe: Something misssing Pinmemberkeshavaprasad26-Jan-07 23:52 
Sure, I am willing to give a description.
As I have already said the code uses backtracking.
I have included comments in the code.
If these are not sufficient, I would like to know particularly which area of the code u want a description for.
GeneralRe: Something misssing PinmemberBradml26-Jan-07 23:56 
GeneralRe: Something misssing Pinmemberkeshavaprasad26-Jan-07 23:59 
GeneralRe: Something misssing Pinmemberkeshavaprasad27-Jan-07 0:10 
GeneralRe: Something misssing PinmemberBradml27-Jan-07 0:20 
GeneralRe: Something misssing [modified] Pinmemberkeshavaprasad27-Jan-07 0:45 
GeneralRe: Something misssing PinmemberBradml27-Jan-07 0:50 

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

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

| Advertise | Privacy | Mobile
Web01 | 2.8.140916.1 | Last Updated 8 Feb 2007
Article Copyright 2007 by kbsbng
Everything else Copyright © CodeProject, 1999-2014
Terms of Service
Layout: fixed | fluid