ACM · UVA

103 – 167 – Sultan’s Successors

Link to Problem : http://goo.gl/RI5mF0

Solution :

The problem is obviously a mutation of the famous Eight Queens’ problem. However, it assigns a certain value to each cell. Then, you are asked to sum the values of the cells occupied by the Queens and return the maximum sum that occurs.

Hence, a valid solution for the problem will test all the possible combinations to compare their sum to the maximum sum.

A backtracking technique did well to give the solution below;

For all cells in a row
1 – mark the cell as visited
2 – place the queen in the cell
3 – unmark the cell & try next cell

The code was written in smaller functions to allow the reader to notice the algorithm more clearly. The validation step which requires validating the cell horizontally, vertically, diagonally and anti diagonally was delegated to four smaller functions for readability and making it easier to unit test the solution.

Finally, the maximum sum returned in each test case was stored in an array and then the array was output in reverse order.

The solution was submitted to UVA Online Judge and was Accepted with submission id #14243417.

#include <iostream>
#include <iomanip>

using namespace std;

const int W = 8;
int board[W][W];
bool vis[W][W];
bool visRows[W];
int max_sum;

void init()
{
	for(int i = 0; i < W; i++)
	{
		visRows[i] = false;
		for(int j = 0; j < W; j++)
		{
			vis[i][j] = false;
		} // end for j -> W
	} // end for i -> W
} // end init

bool isValidRow(int r)
{
	for(int i = 0; i < W; i++)
	{
		if(vis[r][i])
			return false;
	} // end for i -> W
	return true;
} // end is valid row

bool isValidCol(int c)
{
        for(int i = 0; i < W; i++)
        {
                if(vis[i][c])
                        return false;
        } // end for i -> W
        return true;
} // end is valid col

bool isValidDiagonal(int r, int c)
{
        int i = r, j = c;
        while( i < W && j < W )
        {
                if(vis[i][j])
                        return false;
		i++; j++;
        } // end while

        i = r, j = c;
        while( i >= 0 && j >= 0 )
        {
                if(vis[i][j])
                        return false;
		i--; j--;
        } // end while

        return true;
} // end is valid diagonal

bool isValidRDiagonal(int r, int c)
{
        int i = r, j = c;
	while( i < W && j >= 0 )
	{
		if(vis[i][j])
			return false;
		i++; j--;
	} // end while
	i = r, j = c;
	while( i >= 0 && j < W )
	{
		if(vis[i][j])
			return false;
		i--; j++;
	} // end while
        return true;
} // end is valid reverse diagonal

bool validate(int r, int c)
{
	// is valid row
	if(!isValidRow(r)) return false;
 	// is valid col
	if(!isValidCol(c)) return false;;
	// is valid diagonal
	if(!isValidDiagonal(r,c)) return false;
	// is valid inverse diagonal
	if(!isValidRDiagonal(r,c)) return false;

	return true;
} // end validate

bool bt(int r, int counter, int sum)
{
	if(counter == W)
	{
		if( sum > max_sum )
		{
			max_sum = sum;
		} // end if max sum
		return true;
	} // end if counter

	// loop all columns
	for(int i = 0; i < W; i++)
	{
		if(vis[r][i])
			continue;
		if(!isValidRow(r))
		{
			i = 0;
			r++;
		} // end if !valid row
		if(validate(r, i))
		{
			// mark
			vis[r][i] = true;
			// process
			bt(r + 1, counter + 1, sum + board[r][i]);
			// unmark
			vis[r][i] = false;
		} // end if valid
	} // end for i -> W
	return false;
} // end bt

int main()
{
	int k; // number of boards
	cin >> k;
	int* res = new int[k];
	int s = k;
	while(k--)
	{
		for(int i = 0; i < W; i++)
		{
			for(int j = 0; j < W; j++)
			{
				cin >> board[i][j];
			} // end for j -> W
		} // end for i -> W
		max_sum = 0;
		init();
		visRows[0] = true;
		bt(0,0,0);
		res[k] = max_sum;
        } // end while k
	for(int i = s-1; i >= 0; i--)
	{
		cout << setw(5) << res[i] << endl;
	} // end for i -> s
	return(0);
} // end main

Screen-shot:
2014-09-21-222656_1366x768_scrot

White-board and paper drafts:
IMAG0541IMAG0542

* 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