Thursday, July 7, 2011

Sudoku Solver with GUI written in python (Part 1 of 4)

Sudoku Solver is a small graphical app for solving any given Sudoku puzzle, almost instantaneously. It also shows the steps required to solve the same.
(Have a look at one of the toughest Sudoku puzzles here. Sudoku Solver can solve it too, and it is the toughest one I have found till date!)

This is how Sudoku Solver looks like -


For what audience is this post intended?
Although I have primarily written this post for sharing my python code, this can be useful for you if -
  1. You want to learn how to solve a Sudoku puzzle by hand.
  2. You want to yourself make a Sudoku solving program/application.
  3. You want to see some large, fairly complicated, working python code.
  4. You don't care how the Sudoku Solver works, you just want to use it to solve some of your Sudoku puzzles.
OK, I am interested. Give me some background of Sudoku.
Sudoku is a logic based placement puzzle. A Sudoku puzzle consists of a 9 x 9 grid cells which are divided into 9 rows, columns and subgrids (as shown above). The task is to place the numbers from 1 to 9 in the empty cells in such a way that, in every row, column and 3 × 3 subgrid, each number appears only once.

How to solve a Sudoku puzzle?
Although the rules of Sudoku are quite simple, solving it can sometimes become a tough task.
I have posted this separately with lots of pictorial examples here - How To Solve A Sudoku puzzle?

So what can this program do? Show me some examples.
It can solve any Sudoku puzzle, almost instantaneously

Example - 
Take any Sudoku puzzle you like, from anywhere - newspapers, websites, etc. (For this example, I have taken the one from here.) Fill up the Sudoku Solver accordingly (How do I use the Sudoku Solver?).


Click on Solve. The puzzle will be solved instantly. Note that it shows the steps required to solve the puzzle in the side pane.

(Note the time taken to solve the puzzle - 0.05 seconds!)
What's different in this?
Mostly on the web, you will find either of these -
  • Lots of websites having tonnes of Sudoku puzzles to solve and their final answers (but they don't show the steps required to solve these puzzles).
  • Some Sudoku solving apps/applets/programs, but they can solve only the simpler ones. 
With my app, you can -
  • Solve any Sudoku puzzle.
  • Also see the steps required to solve the same.

OK, so where is the source code?
The project is hosted on GitHub (version 1.2 onwards).
If you simply wish to download the source code, see the next section.

How do I run/install Sudoku Solver?

  1. Make sure you have Python 2.7 installed. 
    (On Linux: sudo apt-get install python; Windows/Mac: download)
  2. Make sure you have PyQt4 installed. 
    (On Linux: sudo apt-get install python-qt4; Windows/Mac: download)
  3. Click here to download the source files. Extract it.
  4. Simply execute the module sudoku_solver.py in a terminal-
    $ python sudoku_solver.py

To learn to use the GUI, refer to the post - Sudoku Solver - The GUI.

Coming to the programming part, how is the program structured?
The program consists of 2 parts -
  • The Graphical User Interface (GUI).
  • The logic required to solve (any) Sudoku puzzle.

Tell me more about the GUI.
I have fully described the Sudoku Solver GUI with pictorial examples in this post - Sudoku Solver - The GUI.
____________________________________________________

     I started programming this in mid-May, 2011. It took around 10 days for me to complete it.  A month later I decided to document it (which took much more time). Finally, I decided to host this as a project on on PyPI. It was fun! Now it is hosted on GitHub (version 1.2 onwards).

    3 comments:

    1. Good work! keep it up!! Saw a solution providing sudoku solver for the first time!

      ReplyDelete
    2. Pretty! This was an incredibly wonderful post.

      Thanks for providing these details. payday loans
      My web site - payday loans baton rouge

      ReplyDelete
    3. Good work !! Its great work with GUI. Check out my simple code on Sudoku on http://mytechnprograms.blogspot.in/2013/03/python-code-to-solve-sudoku-puzzle.html

      ReplyDelete