Maximum path sum in a triangle

Problem Statement Finding the maximum path sum in a triangle is a very common programming problem. You are given a triangle of numbers which can be represented as below. You are allowed to start from the top of the triangle and move to either of the two number below it. As we move down from the top to the bottom in multiple ways, we keep adding the numbers for each node we visit. The goal is to maximize the sum . A more formal problem statement can be found on the Project Euler website. How to approach the problem At any point you have two choices you can go to the number below the current ...
Read More

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 *...
Read More

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...
Read More