You are here:
All Content / Reference / Tools / Sudoku Solver
Table of Contents
Subscribe to Our Newsletter
Follow us by subscribing to our newsletter and navigate to the newly added content on this website directly from your inbox!
to subscribe to this page.
Author  
manisar
Author's Display Image

"Whenever you can, share. You never know who all will be able to see far away standing upon your shoulders!"

I write mainly on topics related to science and technology.

Sometimes, I create tools and animation.

Sudoku Solver

April 19, 2020

Author - manisar

This page utilizes a service that solves a 9x9 Sudoku. The service is written in Python.


A tough Sudoku puzzle

This page opens with a default Sudoku puzzle that was posted somewhere as a very tough one. Hit the submit button in the page below to solve it and see how many recursive and non-recursive calls take place when the program finds a solution to this.

With the solved Sudoku, the service also returns some other statistics such as the counts of recursive and non-recursive calls etc.

This service solves a sudoku using backtracking and returns a JSON with the result. Provide the input in the form of numbers as route parameter placed after /sudoku-solver

For example, to resolve the sample matrix given below, use: /sudoku-solver/192000804078600030046000000000940078080103040710052000000000310060001780801000425

This service solves only 9 by 9 sudoku and hence there should be exactly 81 numbers in the parameter.

The service also returns some other information such how many recursive and non-recursive calls were made, and up to what depth recursion happened.
These elements can be extracted from the returned JSON.

 
1 9 2 8 4
7 8 6 3
4 6
9 4 7 8
8 1 3 4
7 1 5 2
3 1
6 1 7 8
8 1 4 2 5

Advertisement
Advertisement

A Bit of Background

The very next month after I started MCA (Master of Computer Applications) course in 2006, I saw this challenge posted on notice board:

  1. Make a Sudoku solving program
  2. Make a program to find a knight's tour given a starting position on a chessboard

My first thought was that these were going to be too difficult, something beyond me... so "don't even think about it".
But just as they say like a dancer cannot control his feet on hearing beats, perhaps a coder cannot control his fingers given a keyboard and a problem!

At that time, I didn't even know the rules of Sudoku, let alone trying solving one ever. By the next month, I started to think about the Sudoku challenge seriously. So I quickly acquainted myself with the rules, and hit the keyboard. Having had no previous training in solving such kind of problems through a computer program, the first obvious technique I tried was brute force (though at that time I didn't even know if there was such a thing called brute force algorithm).

Well after spending couple of days I realized that that was not going to work. But while still trying to tweak my brute force code, this clicked to me: "what if I start with just some random initial values, and go on filling the cells selecting random options out of the available ones. Then as soon as I am stuck, I'll go to the last cell and try the remaining options from that point onward. If I am stuck again, I'll go two steps back and try the remaining options".

I immediate knew that a recursive function would be needed. And some kind of memory construct to remember the options selected at any given point of time. It was around 6-7 pm in the evening when all this struck me. It was so exciting to realize this potential technique that there was no question of sleeping... well I didn't sleep the whole night and by morning the program was ready - in C. I remember the next day there was a farewell function for one of our teachers and somehow I was chosen to conduct the stage. I did it - barely managing to hide both my sleepiness and the excitement - excitement to go back to my room and maybe to run the program a few hundred times and observe its beauty! Only in the second year of my course did I come to know that this technique was called backtracking!

The next day or maybe in couple of days I wrote the program for knight's tour as well. These two C programs have seen all my journey as a coder and have incarnated into many languages - VB.Net, C#, J2ME and Python.

Fast forward two years. I was in third year when the idea of converting my C program into something that could be run on mobile phones occurred to me. It was the year 2008. Google immediately told me that J2ME would be the language if I wanted the program to run on my Nokia phone. I borrowed a J2ME book from my college library and after a fortnight I was filling the Sudokus in the newspapers in the college library everyday in two minutes (using my phone of course)! Don't worry, I stopped doing it after a week as I had already satisfied my programmer's itch and I didn't want to come in the way of habitual Sudoku solvers 🙂.

Find the link to the knight' tour tool below.

Return to Tools

Tell us what you think (select text for formatting, or click )