#include <iostream>
#include <time.h>
using namespace std;

const int SIZE = 10;
const int MAX = SIZE * SIZE;
const int MID = SIZE / 2; // Restrict starting square to quandrant II; avoid rotationally-symmetical redundancy.
int board[SIZE][SIZE];
int direction = 0;
int lastDirection = 0;
int x = 0;
int y = 0;
int iCurrent = 1;
int writeNext = iCurrent + 1;
int pass = 1;

int temp_x, temp_y;

int pastMoves[MAX + 1];
int pastX[MAX + 1];
int pastY[MAX + 1];

const int DIRECTIONS = 8; //0,  1,  2  3,  4,  5, 6,  7
int x_moves[DIRECTIONS] = { 3,  0, -3, 0, -2,  2, 2, -2 };
int y_moves[DIRECTIONS] = { 0, -3,  0, 3, -2, -2, 2,  2 };

int startY = 0;
int startX = 0;

bool tryAgain = true;

int init() {
	int i, j;
	for(i = 0; i < SIZE; ++i) {
		for(j = 0; j < SIZE; ++j) {
			board[i][j] = 0;
		}	
	}
	for (i = MAX - 1; i >= 0; --i) {
		pastMoves[i] = 0;
	}
	return 0;
}


bool occupied(int x, int y) {
	if(x < 0 || x >= SIZE
	|| y < 0 || y >= SIZE) return true;
	return (board[y][x] != 0);
}

bool validDirection() {
	if(direction < DIRECTIONS) return true;
	else {
		if(iCurrent == 0) {
			tryAgain = false;
			return false;
		} else {
			board[y][x] = 0;
			pastMoves[iCurrent] = 0;
			writeNext = iCurrent;
			iCurrent--;
			pastY[writeNext] = y;
			pastX[writeNext] = x;
			y = pastY[iCurrent];
			x = pastX[iCurrent];
			
			direction = pastMoves[iCurrent];
			direction++;
		}
	}
	
	return validDirection(); // recursively validate directions
}

bool outputMatrix() {
	int i, j;
	for(i = 0; i < SIZE; ++i) {
		for(j = 0; j < SIZE; ++j) {
			if(board[i][j] < 10) {
				cout << "0" << board[i][j];
			} else {
				cout << board[i][j];
			}
			cout << " ";
		}
		cout << "\n";
	}
	return true;
}


int main() {
	init();
	time_t start_time, end_time;
	start_time = time(NULL);
	while(true) {
		board[startY][startX] = iCurrent; // move the startnode
		while(tryAgain) {
			temp_x = x;
			temp_y = y;
			x += x_moves[direction];
			y += y_moves[direction];
			if( occupied(x, y) ) {
				x = temp_x;
				y = temp_y;
				direction++;
				validDirection();
			} else {
				board[y][x] = writeNext;
				pastMoves[iCurrent] = direction;
				 
				pastY[writeNext] = y;
				pastX[writeNext] = x;
				
				if(iCurrent == 99) {
					end_time = time(NULL);
					cout << "Elapsed time was " << start_time - end_time << " seconds.";
					outputMatrix();
					return 0;
				}
				
				iCurrent++;
				writeNext++;
				direction = pastMoves[iCurrent];
			}
		}
		
		board[startY][startX] = 0;
		tryAgain = true;
		
		if(startX++ == MID) {
			startX = 0;
			startY++;
		}
		
		if(startY == MID) {
			cout << "No solution found.";
			return 0;
		}
		
		iCurrent = 1;
		writeNext = 2;
		direction = 0;
	}
	
	
	
	
	
}