167 The Sultan’s Successors

Solution:

#include<iostream>

using namespace std;
#define CHEASEBOARD_RANGE 8


int cheaseBoard[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE];
int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE];
int MAX_SUM;

bool backTracking(int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE],int column);
bool isSafe(int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE],int row,int col);
int calculateSumOfPerfectPosition(int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE]);
void pritSpaces();

int main()
{
    int tc,T;
    freopen("167.txt","r",stdin);
    cin >> T;

    for( tc = 0; tc < T; tc++)
    {
        int i,j;
        for(i=0;i<CHEASEBOARD_RANGE;i++)
        {
            for(j=0;j<CHEASEBOARD_RANGE;j++)
            {
                cin >> cheaseBoard[i][j];
            }
        }

        MAX_SUM = -1;
        //init();
        backTracking(board,0);
        pritSpaces();
        cout << MAX_SUM << endl;
    }

    return 0;
}

bool backTracking(int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE],int column)
{
    if(column == CHEASEBOARD_RANGE)
    {
        int sum = calculateSumOfPerfectPosition(cheaseBoard);
        if(sum >MAX_SUM) MAX_SUM = sum;

        return true;
    }

    for(int i=0;i<CHEASEBOARD_RANGE;i++)
    {
        if(isSafe(board,i,column))
        {
            board[i][column] = 1;
            backTracking(board,column+1);
            board[i][column] = 0;
        }
    }
    return false;
}

bool isSafe(int board[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE],int row,int col)
{
    int i,j;

    for(i = 0; i < col ; i++)
    {
        if(board[row][i]) return false;
    }

    for(i = row, j = col; i>= 0 && j >= 0; i--, j--)
    {
        if(board[i][j]) return false;
    }

    for(i = row, j = col; i< CHEASEBOARD_RANGE && j >= 0; i++, j--)
    {
        if(board[i][j]) return false;
    }

    return true;
}

int calculateSumOfPerfectPosition(int cheaseBoard[CHEASEBOARD_RANGE][CHEASEBOARD_RANGE])
{
    int sum =0;

    int i,j;
    for(i=0;i<CHEASEBOARD_RANGE;i++)
    {
        for(j=0;j<CHEASEBOARD_RANGE;j++)
        {
            if(board[i][j])
            {
                sum+= cheaseBoard[i][j];
            }
        }
    }

    return sum;
}

void pritSpaces()
{
    if(MAX_SUM<10) cout << "    ";
    else if(MAX_SUM>=10 && MAX_SUM <100) cout << "   ";
    else if(MAX_SUM>=100 && MAX_SUM <1000) cout << "  ";
    else if(MAX_SUM>=1000 && MAX_SUM <10000) cout << " ";
}