//
//	test of knights tour routine
//
//	Described in Chapter 11 of
//	Data Structures in C++ using the STL
//	Published by Addison-Wesley, 1997
//	Written by Tim Budd, budd@cs.orst.edu
//	Oregon State University
//

//
//	on some systems this only works using list
//	for stack, instead of deque
//
# include <deque.h>
# include <iostream.h>
# include <stack.h>
# include "backtrack.h"

//
//	class Position
//		record a position in the knights move tour
//

class Position {	// position in chessboard
public:
	void        init         (int a, int b)
		{ x= a; y=b; visited=0;  }
	Position *  nextPosition ();

protected:
	// data fields
	// x and y are coordinate positions
	int    x, y;
	// moveNumber records the sequence of steps
	int    moveNumber;
	// visited is a bit vector marking what positions have been visited
	int    visited;

	// internal method used to find the next move
	Position * findMove(int visitedPosition);

	// friends
	friend class knightsTour;
	friend ostream & operator << (ostream & out, Position & v)
		{ out << "Position " << v.x << " " << v.y; return out; }
};

const int boardSize = 5;
Position board[boardSize][boardSize];

Position * Position::nextPosition()
{
	while (++visited < 9) {
		Position * next = findMove(visited);
		// if there is a neighbor not visited then return it
		if ((next != 0) && (next->visited == 0)) 
			return next;
		}
	// can't move to any neighbor, report failure
	visited = 0;
	return 0;
}

Position * Position::findMove(int typ)
{	int nx, ny;

	switch(typ) {
		case 1: nx = x - 1; ny = y - 2; break;
		case 2: nx = x + 1; ny = y - 2; break;
		case 3: nx = x - 2; ny = y - 1; break;
		case 4: nx = x + 2; ny = y - 1; break;
		case 5: nx = x - 2; ny = y + 1; break;
		case 6: nx = x + 2; ny = y + 1; break;
		case 7: nx = x - 1; ny = y + 2; break;
		case 8: nx = x + 1; ny = y + 2; break;
		}
	// return null value on illegal positions
	if ((nx < 0) || (ny < 0)) 
		return 0;
	if ((nx >= boardSize) || (ny >= boardSize)) 
		return 0;

	// return address of new position
	return & board[nx][ny];
}

//
//	class knightsTour 
//		solve the n by n knights tour problem
//

class knightsTour : public backtrackFramework<Position *> {
public:
		// redefine the backtracking protocol
	virtual void    initialize      ();
	virtual bool    advance         (Position *);

		// new method
	void            solve           ();
};


void knightsTour::initialize ()
{
	// initialize the parent class
	backtrackFramework<Position *>::initialize ();

	// initialize chessboard
	for (int i = 0; i < boardSize; i++)
		for (int j = 0; j < boardSize; j++)
			board[i][j].init(i, j);

	// set move number on first position
	board[0][0].moveNumber = 1;

	// push initial position
	theStack.push(& board[0][0]);
}

bool knightsTour::advance(Position * currentPosition)
	// try to advance from a given position
{
	Position * newPosition = currentPosition->nextPosition ();
	if (newPosition) {
		// move forward
		newPosition->moveNumber = currentPosition->moveNumber + 1;
		theStack.push(newPosition);
		// if we have filled all squares we are done
		if (newPosition->moveNumber ==  boardSize * boardSize)
				done = true;
		// return success
		return true;
		}
	else 
		return false;	// can't move forward
}

void knightsTour::solve ()
{
	// start framework
	if (run ()) {	// print solution
		cout << "solution is:\n";
		while (! theStack.empty ()) {
			cout << * theStack.top () << '\n';
			theStack.pop ();
			}
		}
	else
		cout << "no solution ";
}

void main () {
	knightsTour foo;
	foo.solve();
}