# Author: dharam

## Solving the N Queen Problem

Introduction The N Queen Problem is one of the best problem used to teach backtracking and of course recursion. Backtracking is a general algorithm which finds all complete solutions to a problem by building over partial solutions. In this process, the problem might reach to a partial solution which may not result into a complete solution. Such partial solutions are effectively rejected by the backtracking algorithm. To know more about backtracking please visit the Wikipedia article. The classic case of N Queen problem In this problem, you are given an empty chess board of dimensions N *...

## Building an autocomplete system using Trie

Introduction Few days back I wrote a post about the Trie data structure. This post is a continuation to it, and intends to introduce some practical problems which Trie solves. An autocomplete system is a perfect use case. Many of the websites use this feature to help there users with suggestions & autocomplete. Also, in this post we will define a Trie interface and then work through this problem statement. An autocomplete system using Trie As we know from the previous text that a Trie is a tree like data structure which stores words such that the search for a word is proportional to ...

## Paint Fill Implementation – Image Editing

Introduction Most of the image editing software like Microsoft paint, Paint.NET, Adobe Photoshop offer features like paint fill. This post is an attempt to define a simple version of the algorithm which is used to implement paint fill. The problem definition goes like this: There is a grid with dimensions N*M such that each cell of the grid is colored. The paint fill technique allows a user to choose a color to be filled, say K and a cell C(i,j). If the cell C(i,j) has the same color as K, then do nothing. If the cell C(i,j) has a color L which is different from K then find all the...

## Fastest Reach in Snakes and Ladders

Introduction For those who are not familiar with the snakes and ladders game. Here is a link for introduction. So the fastest reach in snakes and ladders, is a modified version of the game. So, you are playing the game called snakes and ladders and you have an enchanted dice. You are the master of the dice and you can command it to get any number between 1 and 6 both inclusive. This means that when you throw the dice, the number on the upper face is totally controlled by you. If you ask for a 5, you get a 5 and so on. Problem Statement - Fastest Reach in Snakes and Ladders The problem in ha...

## Single Source Shortest Path For Undirected Graph

Introduction Single source shortest path for undirected graph is basically the breadth first traversal of the graph. Here the graph we consider is unweighted and hence the shortest path would be the number of edges it takes to go from source to destination. You can find posts on the same topic for weighted graphs, and that is solved using Dijkstra's or Bellman Ford algorithms. This post is written from the competitive programming perspective. Here I want to focus on the details of simplified implementations. Problem Statement - Shortest Path for Undirected Graph Most of the times, the probl...