Posts

Showing posts from May, 2017

Developing a Sudoku solver

Image
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 …

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. Before starting off, the prerequisites for understanding this post is:
Java programming (Or at least be able to understand an algorithm)2-Dimensional arraysRecursions.N-Queens problem (What it is. click on it to open Wikipedia page if you don't know.)
Backtracking: Backtracking is a form of recursion.A Recursion is a function/method calling itself.An example of recursion is the following function: The above function would print the integers from 1 to n when n is > 0If you study carefully the above function(or any recursive function), it has three main characteristics. They are:The problem has a base case(also called terminating condition) which in this case is return when n <= 0.The problem is broken down into smaller problems of the same t…