/* Quiz 2. Solutions. */

// Question 1.
// 8 Queens Problem.

// The big observation in solving the question is that it
// is enough to consider only all permutations of the numbers
// 1,2, ... 8. Here is why.

// No two queens can share a column. Given that there are 8
// queens and 8 coloumns on a chess board, this clearly
// implies that each column must contain one, and only
// one, queen. Using this first observation, we realize that
// we need to keep track only of which row each queen is on.
// To be more percise, let Q1 be the queen on column1,
// Q2 be the queen on column2, and so on. We need only
// to look at numbers <r1, r2, ..., r8> which represent
// which row each queen is sitting on. That is to say,
// Q1 sits on column1, and row r1; Q2 sits on column2 and
// row r2 and so on until Q8 sits on column8 and row r8.
//
// Finally, no two queens can share a row. In addition,
// there are exactly 8 queens and 8 rows, so that there must
// be, on each row, exactly one queen. This implies that
// exactly one of numbers r1,r2,...,r8 is 1, exactly one
// of them is 2, ... and so on. So <r1,r2,...,r8> is
// simply some arrangement of the numbers <1,2,...,8>
//
// This all implies that any acceptable configuration of
// queens can been written as some permutation of numbers
// <1,2,...,8>. For instance, <4,5,6,7,2,1,8,3> is a configuration
// saying that Q1 sits on column1, row 4; Q2 sits on column2 row 5;
// Q3 sits on column3 row 6, ... until Q8 sits on column8
// row 3. Note that not all such configurations are
// acceptable.
//
// (after all that ... ) Here is how to solve the problem
// efficiently. Generate all possible permutations of
// the numbers <1,2,3,...,8>. After generating each
// permutation check it for validity and if it is valid
// print it out. What does checking for validity mean here?
// Our setup (i.e. considering only the permutation of
// these numbers) already ensures that there are no
// two queens sitting on the same column or row. So it
// only remains to check wheather or not two
// queens sit on the same diagonal.
//
// So, how do we check for diagonals?
// There are many ways, including marking all the
// diagonals in some way. Here is a simple idea:
//
// The diagonals on a chess board all have
// slope 1 or -1. Look at small diagram below:
//
// BWBW-WBW    Two diagonals have been marked. One
// WBW-WBWB    with slope -1 is marked with '*'s and
// BW-WBWBW    another with slope 1 is marked with '-'s
// *-WBWBWB
// -*BWBWBW
// WB*BWBWB
// BWB*BWBW
// WBWB*BWB
//
// So, to check if queens Qi and Qj fall into the same
// diagonal, we need only check to see if the slope they
// make is equal to 1 or -1. That is to say, if
// ri - rj = +/- (i - j)
// Explanation: ri is the row where the queen on
// ith column sits. Similarly, rj is the row where
// the queen on the jth column sits. So the difference
// between their rows is ri - rj and between their
// columns is i - j.

PSEUDO CODE:

   proc CheckTheDiagonals
     // given the numbers <r1, r2, ..., r8> as above
     for any pair of (ri, rj)
         if ((ri - rj = i - j) or (ri - rj = -(i - j))
            return false // meaning there was a conflict

     // We survived all the testing, so
     return true         // meaning there was no problem.

   For every possible permutation P of <1,2,3,4,5,6,7,8>
       if (CheckTheDiagonals (P))
          DisplayBoard(P)

// For how to generate all possible permutations of
// <1,2,3,4,5,6,7,8> very easily, check out the STL
// documentation for the 'next_permutation' function.
// if not, you could easily use 8 nested for-loops to
// do the job for you.