1. Backtracking

Today in class we used a recursive algorithm to solve the 8 Queens problem, which is to place 8 queens on a chessboard such that no queen attacks any other queen.  Our program is appended below.  How does it work?  It tries to place a queen in row 0, then row 1, and so on, and at each level verifies that the newly placed queen does not collide with any previous queens.  If it does, then that level fails, we pop up one level of recursion, and try another possible solution at that level.  We keep doing this until we find a solution or until we run out of choices at the root level, in which case we fail.

This approach to problem solving is called:  Backtracking.

Your task here is to modify our 8 queens code so that it demonstrates all the backtracking for us.  To do this, modify placeQueen() to print out when it is called (prefaced by a count of how many times it has been called overall, for which you may use a global), and to indent this by 3*row spaces.  Be sure to think about this number and what it means.  Anyhow, here is what your output should look like (note the backtracking, for example, where step 7 failed so we pop up to step 8):

1: placeQueen(0)
      2: placeQueen(1)
            3: placeQueen(2)
                  4: placeQueen(3)
                        5: placeQueen(4)
                              6: placeQueen(5)
                              7: placeQueen(5)
                        8: placeQueen(4)
                              9: placeQueen(5)
                                    10: placeQueen(6)
                                          11: placeQueen(7)
                              12: placeQueen(5)
                        13: placeQueen(4)
                              14: placeQueen(5)

    .....

                              111: placeQueen(5)
                                    112: placeQueen(6)
                                          113: placeQueen(7)
                                                114: placeQueen(8)
Q . . . . . . .
. . . . Q . . .
. . . . . . . Q
. . . . . Q . .
. . Q . . . . .
. . . . . . Q .
. Q . . . . . .
. . . Q . . . .

Type 'Enter' To Exit

2.  N Queens

Change the 8 Queens code to solve the N Queens problem (an NxN board, rather than 8x8).  Your program should not print out any boards nor any backtracking calls.  Rather, it should just print out a list of the N for which it finds a solution and the total number of calls to placeQueen() for each N.  Keep doing this up to some sufficiently large N (or until your program runs for some ludicrously long time).

Your task here is to adapt the 8 Queens code to solve the Knights Tour for an NxN board.  What is a Knights Tour?  Here is one of a great many web pages which explain it:
    http://www.gsat.edu.au/educate/cp/mathweb/knight/knight_tour.htm
Anyhow, your task is to write one here.  Assume that the knight starts at 0,0.  One small complication is that you must print out the actual tour, as in:  (0,0) (1,2) (2,4) (4,5)...  A simple way to handle this is to print out the tour in reverse (think about it), which still fortunately is a knight's tour.  Note that not all N have solutions, but 8 does, among others (which?).

This section is Extra Credit and is entirely optional.  Change Knights' Tour to print out the tour in the order found, not in reverse order.  Also, require that the tour conclude a legal knight's move away from where it started, so that you could keep going around infinitely through all N² positions.

// 8Queens.cpp
// By AP CS Class

// Note that this code was developed during a lecture in class,
// and is not at all properly commented.

#include <stdio.h>
#include <iostream.h>

const int ROWS = 8;
const int COLS = ROWS;

bool hasQueen[ROWS][COLS];  // you use apmatrix

bool checkPosition(int row, int col)
{
        int rc, rcdelta;

        for (rc=0; rc<ROWS; rc++)
                if ((hasQueen[rc][col]) ||
                        (hasQueen[row][rc]))
                        return false;

        for (rcdelta=-ROWS; rcdelta<ROWS;rcdelta++)
        for (int sign1=-1;sign1<2;sign1++)
        for (int sign2=-1;sign2<2;sign2++)
        if (sign1 * sign2 != 0)
        {
                int row2 = row + rcdelta * sign1;
                int col2 = col + rcdelta * sign2;
                if ((row2 >= 0) && (row2 < ROWS) &&
                        (col2 >= 0) && (col2 < COLS) &&
                        hasQueen[row2][col2])
                        return false;
        }
        return true;
}

bool placeQueen(int row)
{
        // Base case -- can always place the null queen
        // in the null row
        if (row == ROWS)
                return true;

        int col;
        for (col = 0; col < COLS; col++)
        {
                if (checkPosition(row,col))
                {
                        hasQueen[row][col] = true;
                        if (placeQueen(row+1))
                                return true;
                        // darn, there was a collision, so we
                        // must undo placing the queen and continue
                        // with the next column
                        hasQueen[row][col] = false;
                }
        }
        return false;
}

void printBoard()
{
        int row,col;

        for (row=0;row<ROWS;row++)
        {
                for (col=0;col<COLS;col++)
                        cout << (hasQueen[row][col] ? "Q " : ". ");
                cout << endl;
        }
        cout << endl;
}

void main()
{
        int r,c;
        for (r=0; r<ROWS; r++)
        for (c=0; c<COLS; c++)
                hasQueen[r][c] = false;

        if (placeQueen(0))
                printBoard();
        else
                cout << "Sorry, but no solution exists." << endl;

        cout << "Type 'Enter' To Exit" << endl;
        getchar();
}