Developing a Sudoku solver

-



I've never been great at solving Sudoku because I find it boring to sit down for an hour staring at boxes some filled and others to be filled with numbers. But I think it's an interesting game. I've always thought of developing an algorithm to solve any given Sudoku puzzle. I've had this in my mind from the very first year of my under graduation but I never gave it a serious thought. If you have seen my previous post, it's about backtracking which is a general algorithm used to solve many problems such as the classical N-Queens problem(I've solved it in that post). Yesterday I tried solving a question on the Hackerrank site which required me to use the backtracking algorithm and I was successful in devising an algorithm to solve it. I felt the question was very similar to solving a Sudoku puzzle so I thought of creating a sudoku solver and I've done it! It was simpler than what I thought it would be. All you need to know is how to use backtracking. If you don't know what backtracking is, just have a look at my previous post and I hope it'd help you.

Here's a video of me solving a Sudoku puzzle at 'Evil' mode using the Sudoku solver  I developed. Hope you enjoy it.


Now coming back to Sudoku solver, I've not taken the time to see any other algorithm so this is my own approach to the problem and I think it's pretty straight forward and easy to understand. To solve the Sudoku I'll be using these methods:
  1. canPlace(): This function is used to check whether we can place a particular value at a particular position in the Sudoku.
  2. solveSudoku(): This function uses backtracking and canPlace() method to solve the Sudoku. If the given Sudoku does not have a solution, it returns false.
  3. displayBoard(): A simple function to display the numbers of a Sudoku puzzle(a box) which is simply a 2-Dimensional  array.
  4. insertNumbers(): A function to insert numbers into the Sudoku before it gets solved. You are required to mention row number, column number and value for each entry.
  5. insertFileNumbers(): This function is used to read the Sudoku entries from a mentioned file. To fill a sudoku having N*N boxes, the text must have N*N lines. The first line denotes the number at the first row and first column. The second line represents value at the first row and second column (and) so on. For not mentioning any value, you can leave the line empty or insert any non-number string.
The main logic only depends on the first two functions mentioned which are canPlace() and solveSudoku(). Both of these functions are Boolean returning functions. here are the algorithms for these functions:
  1. canPlace() function algorithm:
  2. solveSudoku() function algorithm:
I hope the above algorithms are clear enough to help you understand the logic behind Sudoku solver. Here's the code for java implementation of Sudoku solver with all of the five methods mentioned above along with the main() function.

I know this can be further developed into a good application but my intention of developing the program wasn't that. I just wanted to devise an algorithm to solve any given valid Sudoku puzzle.

Comments

Post a Comment

Popular posts from this blog

Beginner's guide to Solving the N-Queens problem using backtracking method

-
Image
This post serves as a good introduction to the backtracking method which is used widely in various types of problems to find a possible solution. Here we'll be seeing how to solve the classical N-Queens problem using backtracking method. Backtracking : The Wikipedia page  for Backtracking defines it as "a general algorithm in which, we try to incrementally build candidates to the solutions, and discard a candidate as soon as we get to know that the candidate cannot possibly be completed to a valid solution".  If that sounds complicated and confusing, don't worry! Let us understand it by running through a small example. Consider you are trapped in a haunted house with five rooms named A, B, C, D and E. Initially, you are in room A and you need to reach room E to exit the house. Below is an image of the rooms in the house. The arrows in the image indicate the directions in which you can move. For example, you can move to rooms B and C from A but, you
Read more

PvP Chain reaction game using Python

-
Image
At last, I've taken time and ventured a little deeper into the Python language! I used the  Tkinter   package to develop a rip-off of an android game called chain-reaction . It's a simple multiplayer board game in which the first person to occupy all the blocks on the board or of the opponent(s) wins. Try downloading and playing the game with your friends, it's FUN! Here's a video of the game I've developed(I've set the number of players to 4 and board dimensions are 6*8): Coming to the coding, I actually enjoyed the process of writing code much more in Python compared to any other previous languages that I've used. Maybe it is due to the fact that it's the first high-level language that I got my hands on. I'd never worked with Tkinter package before. It was quite easy to understand and I was able to build the game in roughly in four hours. I think that just a little effort is enough for anyone to understand how to use the  tkinter  packa
Read more

Developing Minesweeper using Java

-
Image
It's been a while since I've posted anything on my blog. The reason being that lately, I've been learning new languages like Python and Java. Well anyways, I've taken the time to develop Minesweeper game using Java applets. This game also got GUI which I've created using the components provided by Java. Here are a few pictures of the game. Here's the video of my game: There are two classes in my game: Board class : This class provides the backend logic of building the board for the minesweeper game. This class has also got methods using which user can play the game on command prompt itself. I've commented out the methods required for running the game on cmd ( the * beside a method listed below denotes that the method was commented ). If you're interested in playing on cmd, fiddle around with invoking methods in the main method(create one!) and see if you can run it :). The various methods in Board class are: Board() *:  Constr
Read more