Analysis of Algorithms

Backtracking Revisted

My friend’s 11-year-old son named Ahmed gave me an interesting puzzle this afternoon. He wanted to fill a 2D matrix with distinct numbers from one to nine such that the sum of each column equals the sum of each row equals fifteen.

I started thinking by drawing the matrices and trying to fill them accordingly. I also started thinking from bottom up by writing down the number of ways fifteen can be obtained from the sum of distinct first nine numbers;

1 + 5 + 9thinking draft

1 + 6 + 8

2 + 4 + 9

2 + 5 + 8

2 + 6 + 7

3 + 4 + 8

3 + 5 + 7

4 + 5 + 6

. . .

 

I noted the repetition pattern of the numbers. When I tried to do the same thing to achieve a different number seventeen for example. I noted that number one appeared only once in the set.

Ahmed then asked me whether it is possible to write a computer program to solve the puzzle. He actually wanted to know the numbers which will work, so that he avoids being tricked into a puzzle with no solution.

Ahmed and Puzzle

I just recalled an algorithm to solve a Sudoku puzzle using backtracking technique from Wikipedia. It simply attempts filing each cell with one digit without repeating it in next calls. This attempts 9P9 = 362,880 different combinations and outputs only the set which follows the constrains given.

Sudoku_solved_by_bactracking

Even though this approach is too expensive in terms of memory and processing, it could be pruned to short cut the attempts. Hence, I added a validation function to return early from a certain attempt if it violates the rules of the game .i.e. the sum of each col equals the sum of each row.

#include <iostream>
#include <cstring>

using namespace std;

const int WIDTH = 3;
const int HEIGHT = 3;
const int BOUND = 9;

int matrix[WIDTH][HEIGHT];
bool vis[BOUND+1];

int n;
int nWays;
int nPerms; // number of permutations

int nextRow(int r, int c)
{
	if( c == WIDTH - 1)
		return r + 1;
	return r;
}

int nextCol(int r, int c)
{
	if( c == WIDTH - 1)
		return 0;
	return c + 1;
}

void print()
{
	cout << endl;
	for(int i = 0; i < HEIGHT; i++)
	{
		for(int j = 0; j < WIDTH; j++)
		{
			cout << matrix[i][j];

			if( j != WIDTH - 1)
				cout << " ";
		}
		cout << endl;
	}
	cout << endl;
}

bool sumrows()
{
	for(int i = 0; i < HEIGHT; i++)
	{
		int sum = 0;
		for(int j = 0; j < WIDTH; j++)
		{
			sum += matrix[i][j];
		}
		if( sum != n)
			return false;
	}
	return true;
}

bool sumcols()
{
	for(int j = 0; j < WIDTH; j++)
	{
		int sum = 0;
		for(int i = 0; i < HEIGHT; i++)
		{
			sum += matrix[i][j];
		}
		if( sum != n)
			return false;
	}
	return true;
}

bool validate()
{
	if(!sumrows())
		return false;
	if(!sumcols())
		return false;
	return true;
}

bool preValidate(int newR, int newC)
{
	// if other cells in row is filled and sum > n // return false
	int sum = 0;int cnt = 0;
	for(int j = 0; j < WIDTH; j++)
	{
		if(matrix[newR][j] != -1)
		{
			sum += matrix[newR][j];
			cnt++;
		}
		if(sum > n)
			return false;
	}
	// if all filled, but not equal n // return false
	if(cnt == WIDTH && sum != n)
		return false;
	// if other cells in col is filled and sum > n // return false
	sum = 0; cnt = 0;
	for(int i = 0; i < HEIGHT; i++)
	{
		if(matrix[i][newC] != -1)
		{
			sum += matrix[i][newC];
			cnt++;
		}
		if(sum > n)
			return false;
	}
	// if all filled, but not equal n // return false
	if(cnt == WIDTH && sum != n)
		return false;
	// else return true
	return true;
}

bool bt(int r, int c)
{
	// base case
	if( r == HEIGHT )
	{
		nPerms++;
		if(validate())
		{
			nWays++;
			print();
			return true;
		}
		return false;
	}

	// permutate
	for(int i = 1; i <= BOUND; i++)
	{
		// taken
		if( vis[i])
			continue;
		// mark
		vis[i] = true;
		matrix[r][c] = i;

		// try
		int nr = nextRow(r,c);
		int nc = nextCol(r,c);
		if(preValidate(r,c))
			bt( nr, nc );

		// unmark
		vis[i] = false;
		matrix[r][c] = -1;

	} // end for i -> BOUND
	return false;
}

int main()
{
	while( cin >> n )
	{
		nWays = 0;
		nPerms = 0;
		memset(vis, false, sizeof(vis));
		memset(matrix, -1, sizeof(matrix));
		bt(0, 0);
		cout << "For N=" << n << " ,there are " << nWays << endl;
		cout << "#Permutations= " << nPerms << endl;
	}
	return(0);
}

C++ Puzzle Solution
* I am looking forward to reading all your comments below.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s