runtah

UVa 167 The Sultans Successors

UVa 167 The Sultans Successors

One things for sure, Backtracking is damn fun!!! :D
I liked this one a lot. Though I had to take some help for this one. But it still increased a lot of knowledge about Backtracking.

#include <cstdio>
#include <iostream>
#include <iomanip>
using namespace std;

bool col[100], d1[100], d2[100];

class c
{
 public:
 int x, y;
};

c crd[100];

int knt=0, board[100][100];

c lst[1000];

int qplace(int n)
{
 if (n>8)
 {
 for (int i=1 ; i<=8 ; i++)
 {
 lst[knt++]=crd[i];
 }
 return 0;
 }
 for (int k=1 ; k<=8 ; k++)
 {
 if (!col[k] && !d1[n+k] && !d2[n-k+8])
 {
 col[k]=d1[n+k]=d2[n-k+8]=true;
 crd[n].x = n;
 crd[n].y = k;
 qplace(n+1);
 col[k]=d1[n+k]=d2[n-k+8]=false;
 }
 }
 return 0;
}

int main()
{
 int test, i, j, sum, max;
 knt = 0;
 for (i=0 ; i<=100 ; i++)
 col[i]=d1[i]=d2[i]=false;
 qplace(1);
 //cout << knt << endl;



 scanf("%d",&test);
 while (test--)
 {
 for (i=1 ; i<=8 ; i++)
 {
 for (j=1 ; j<=8 ; j++)
 {
 scanf("%d",&board[i][j]);
 }
 }
 max = 0;
 for (i=0 ; i<knt ; i+=8)
 {
 for (j=i, sum=0 ; (j-i)<8 ; j++)
 {
 sum += board[lst[j].x][lst[j].y];
 }
 if (sum>max)
 max = sum;
 }
 cout << setw(5) << max << endl;
 }
 return 0;
}

Go to link download