/*
 * CS2S03/SE2S03, October 2011
 * Assignment 4, Question 3
 * File: PE0707.cpp
 * ----------------
 * This program solves the Knight's Tour problem,
 * which is to find a sequence of moves by a knight that will 
 * visit every square of the board exactly once.
 * This program is written primarily for clarity.
 */ 

#include <iostream>
#include <iomanip>
#include "simpio.h"
#include "genlib.h"

/*
 * Type: directionT
 * ----------------
 * This type is used to represent the knight's eight directions.
 */

enum directionT { NE, EN, ES, SE, SW, WS, WN, NW };

/*
 * Type: pointT
 * ------------
 * This type is used to encapsulate a pair of integers coordinates
 * into a single value with x and y components.
 */
 
struct pointT {
    int x, y;
};


/* Constant Declarations */

const int SIZE = 8;

/* Global Variable Declaration */

int board[SIZE][SIZE]; /* board[0][0] is the low-left corner */

/* Private function prototypes */

void InitBoard();
pointT GetStartPosition();
bool OutsideBoard(pointT pt);
void VisitSquare(pointT pt, int num);
void UnvisitSquare(pointT pt);
bool IsVisited(pointT pt);
pointT NextPoint(pointT pt, directionT dir);
bool MakeTour(pointT pt, int stepNum);
void Display();  

/* Main program */

int main() {
    InitBoard();
	pointT start = GetStartPosition();

    if (MakeTour(start, 1)) {
        Display();
    } else {
        cout << "No solution." << endl;
    }
	return 0;
}

/* Function implementations */

/*
 * Function: InitBoard
 * Usage: InitBorad();
 * -------------------
 * This function initialized the board by setting the values of
 * all squares to 0, meaning unvisited.
 */
 
void InitBoard() {
    for (int i = 0; i < SIZE; i++)
        for (int j = 0; j <  SIZE; j++)
            board[i][j] = 0;
}

/*
 * Function: GetStartPosition
 * Usage: pt = GetStartPosition();
 * -------------------------------
 * This function returns a pointT indicating the position
 * of the start square.
 */

pointT GetStartPosition() {
    pointT pt;
    cout << "Row number of the start square";
    cout << " (0-" << SIZE - 1 << "): ";
    pt.x = GetInteger();
    cout << "Column number of the start square";
    cout << " (0-" << SIZE - 1 << "): ";
    pt.y = GetInteger();
    return pt;
}

/*
 * Function: OutsideBoard
 * Usage: if (OutsideBoard(pt)) ...
 * --------------------------------
 * This function returns true if the specified point is outside
 * the boundary of the board.
 */

bool OutsideBoard(pointT pt) {
    return ((pt.x < 0) || (pt.x >= SIZE) ||
            (pt.y < 0) || (pt.y >= SIZE));
}

/*
 * Function: VisitSquare
 * Usage: VisitSquare(pt, num);
 * ----------------------------
 * This function sets the value of the specified square
 * with the specified step number.
 */
 
void VisitSquare(pointT pt, int num) {
    board[pt.x][pt.y] = num;
}

/*
 * Function UnvisitSquare
 * Usage: UnvisitSquare(pt);
 * -------------------------
 * This function resets the value of the specified square to 0,
 * meaning unvisited.
 */
 
void UnvisitSquare(pointT pt) {
    board[pt.x][pt.y] = 0;
}

/*
 * Function IsVisited
 * Usage: if (IsVisited(pt)) ...
 * -----------------------------
 * This function returns true if the specified square
 * has been visited on the tour.
 */
 
bool IsVisited(pointT pt) {
    return (board[pt.x][pt.y] > 0);
}
	
/*
 * Function NextPoint
 * Usage: nextPt = NextPoint(pt, dir);
 * -----------------------------------
 * This function returns the point next to the specified point
 * in specified direction.
 */

pointT NextPoint(pointT pt, directionT dir) {
    pointT newpt = pt;
    switch (dir) {
      case NE: newpt.x += 2; newpt.y += 1; break;
      case EN: newpt.x += 1; newpt.y += 2; break;
      case ES: newpt.x -= 1; newpt.y += 2; break;
      case SE: newpt.x -= 2; newpt.y += 1; break;
      case SW: newpt.x -= 2; newpt.y -= 1; break;
      case WS: newpt.x -= 1; newpt.y -= 2; break;
      case WN: newpt.x += 1; newpt.y -= 2; break;
      case NW: newpt.x += 2; newpt.y -= 1; break; ;
    }
    return newpt;
}

/*
 * Function: MakeTour
 * Usage: if (MakeTour(pointT pt, int stepNum)) ...
 * ------------------------------------------------
 * This function makes a Knight's Tour starting at the specified point
 * at the specified step number.
 */
 
bool MakeTour(pointT pt, int stepNum) {
    VisitSquare(pt, stepNum);
    if (stepNum == SIZE * SIZE) {
        return true;
    }
    for (int i = 0; i < 8; i++) {
        directionT dir = directionT (i);
        pointT nextpt = NextPoint(pt, dir);
        if (!OutsideBoard(nextpt) && !IsVisited(nextpt)) {
            if (MakeTour(nextpt, stepNum + 1)) {
                return true;
            }
        }
    }
    UnvisitSquare(pt);
    return false;
}

/*
 * Function: Display
 * Usage: Display();
 * -----------------
 * This function displays a solution. Each square is marked a
 * step number.
 */
 
void Display(void) {		
    cout << "A knight's tour:" << endl << endl;

    for (int i = SIZE - 1; i >= 0; i--) {
        for (int j = 0; j < SIZE; j++)
            cout << "+--";
        cout << "+" << endl;
        for (int j = 0; j < SIZE; j++)
            cout << "|" << setw(2) << board[i][j];
        cout << "|" << endl;
    }
    for (int j = 0; j < SIZE; j++)
        cout << "+--";
    cout << "+" << endl;
    cout << endl;
}