Author: dharam

Solving Sudoku using Backtracking

Introduction This post is the continuation of the backtracking series. Sudoku can be solved using multiple algorithms based on Neural Networks and Genetic Algorithms by doing exhaustive searches in the solution space. However, here we are focusing on solving Sudoku using backtracking algorithm. For people who are unaware of the Sudoku puzzle, please check out Wikipedia for details. For a brief description read below: A Sudoku puzzle is a 9 * 9 grid. Few cells in the grid contain random numbers between 1 and 9 (both inclusive) A fully solved Sudoku must contain numbers through 1-...
Read More

Print all paths of robot through the grid

Introduction This is a supplement to the previous post where we were interested in just one path of a robot from top left corner to the bottom right corner. In this post we will print all paths of robot moving through a given grid containing few blocked cells. The algorithm for this solution remains the same, we just need few tricks to get that right. Here, I will explain the idea behind printing all paths of robot through the grid. Approach Here, let us discuss what different we need to do to print all the paths. As we can recall from the previous post, the moment we reached the destina...
Read More

Find Path through grid – constrained motion

Introduction This is another addition to the backtracking series of problems. The problem is asked in many interviews in many different forms. Here are few of them: Given a grid where few of the cells are blocked. You have a robot placed at the top left corner of the grid. Find path through grid such that the robot starts from the top left corner and moves to the bottom right corner. Another form just asks for all possible paths from one cell to another into a grid. Of course there are constraints on the movement of the robot, else you would end up going in circles and the paths wo...
Read More

Knight’s Tour Problem Simply Explained

Introduction This post is a continuation of the back tracking series. You can refer to other similar posts here. In this post we will be discussing the Knight's Tour Problem. The problem states that, given a N * M chessboard, a Knight's Tour is defined as the sequence of moves of a Knight, such that the Knight visits every square only once. Does this sound similar? Yes it is similar to finding the Hamiltonian Path as defined in this post. Approach for solving the Knight's Tour problem Here I define the backtracking approach to solve this problem. Let the Knight start from any location...
Read More

Pair of Numbers to obtain given sum

Introduction This problem is already defined in one of the previous post. You can read that to know the problem in more detail. The definition goes like this, find a pair of numbers to obtain given sum in an array. The task is to find two numbers in an array which when added will produce a desired sum. Approach to find a Pair of Numbers to obtain given sum As the theory is already mentioned in the previous post, let us directly jump to all possible solutions. Here I am defining three different solutions to this problem. And the idea is to build a basic understanding and then proposing the b...
Read More

Solution to find Interleaving of Strings

Introduction This post is an enhancement over one of the previous posts where the task was to find if a given string C is an interleaving of strings A and B. To know more about the problem description, please visit the previous post Solution The previous solution is a iterative solution which requires lot of space. Here we will discuss a recursive solution. Hopefully with small code foot print. Before we jump into the code, let us understand the idea behind the solution. Here are the example Strings A, B and C A -> abcd B -> ade C -> abadcde The recursive algorithm...
Read More

Count Word Frequency in Stream

Introduction Continuing our discussions on Tries, here is another practical problem which is used in many text processing scenarios. Counting word frequency in stream translates to a scenario where you are given a list of words (dictionary). Now, there is an infinite stream of characters coming in. Your task is to print the frequency of words appearing in the stream. To know more about the basics of building a Trie, please visit my previous post Example Problem for counting word frequency in stream Let us say we have a dictionary which contains the following words aca cat hell...
Read More