## Wednesday, October 1, 2014

### UVa Problem 750 - 8 Queens Chess Problem

Problem:

Solution:

The problem is easy to solve to enumerate all permutations and then check if the diagonal constraint match. In particular, since the problem requires outputting the row number of all columns, we might as well use that as the internal representation of the configuration during the search. These row numbers can only be a permutation because no rows can have 2 queens.

Now assuming we have [1, 2, ...] this is wrong because (1, 1), (2, 2) are on the same diagonal, to check this is suffice to check abs(rows[i] - i) != abs(rows[j] - j). The abs covers both diagonals.

To optimally solve this problem, I should have use next_permutation(), but since the problem is about exercising recursive backtracking, I used recursive backtracking instead. Of course, the results are the same.

One thing to note: The presentation of solution number with more than 1 digit is not specified, it should use the space to the left of the digit. I used the right and lead to presentation error. For god sake it output presentation error so I don't waste time debugging.

Code:

#include "stdafx.h"

// http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=691

#include "UVa750.h"

#include <iostream>
#include <iomanip>
#include <cmath>

using namespace std;

// Global variable
int row_of_column[8];
int solution_count;

void queens(int workingColumn)
{
if (workingColumn == 8)
{
// We have got an answer!

// Good for debugging outputing the matrix
/*
for (int i = 0; i < 8; i++)
{
for (int j = 0; j < 8; j++)
{
if (i == row_of_column[j])
{
cout << "1 ";
}
else
{
cout << "0 ";
}
}
cout << endl;
}
cout << endl;
*/

cout << setw(2)      // : gives a minimum width for the next output operation
<< setfill(' ')  // : sets the padding character
<< setiosflags(ios::right); // : padding on left

cout << (++solution_count);
cout << "     ";
for (int i = 0; i < 8; i++)
{
cout << " " << (row_of_column[i] + 1);
}
cout << endl;

return;
}

// If the working column is not already assigned
if (row_of_column[workingColumn] == -1)
{
for (int trial = 0; trial < 8; trial++)
{
for (int test = 0; test < 8; test++)
{
// The coordinate of the testing column element is (row_of_column[test], test)
// The proposed coordiate is (trial, workingColumn)
if (row_of_column[test] != -1)
{
if (row_of_column[test] == trial || abs(test - workingColumn) == abs(row_of_column[test] - trial))
{
}
}
}

{
row_of_column[workingColumn] = trial;
queens(workingColumn + 1);
row_of_column[workingColumn] = -1;
}
}
}
else
{
queens(workingColumn + 1);
}
}

int UVa750()
{
int number_of_cases;
cin >> number_of_cases;

for (int c = 0; c < number_of_cases; c++)
{
int row_number;
int col_number;
cin >> row_number;
cin >> col_number;

// Step 2: Reset global state
for (int i = 0; i < 8; i++)
{
row_of_column[i] = -1;
}
solution_count = 0;

row_of_column[col_number - 1] = row_number - 1;

if (c != 0)
{
cout << endl;
}
cout << "SOLN       COLUMN" << endl;
cout << " #      1 2 3 4 5 6 7 8" << endl;
cout << endl;

// Step 5: Search
queens(0);
}

return 0;
}