// knightstour2.cpp : Defines the entry point for the console application.
//

#include "stdafx.h"
#include <cstdio>
#include <iostream>
#include <vector>
#include <sstream>
#include <list>
#include <iterator>
#include <cmath>
using std::vector;
using std::string;
using std::list;
using std::cout;
using std::cin;
using std::endl;
#define N 5

using namespace std;

// Devining boardsize (maybe changeable by the user later)
const int boardSize = 5;

// Total moves needed to complete the knights tour = (boardSize * boardSize) - 1
const int totalNumMoves = (boardSize*boardSize) - 1;
// current move
int moveCount = 0;

// 2D array for the chessboard
// the value of the arrayposition defines if it has been visited yet
// 0 = not visited and > 0 means it has been visited
// visited places will also be chronologically numbered
// for instance if a place in the array has a value of 4 it means it is the forth place the knight has been
int chessboard[boardSize][boardSize];

//current position of the knight
int curPosX;
int curPosY;

//starting position is always the same (maybe changeable by user later)
int startPosX = 0;
int startPosY = 0;

// define a structure for a square with an x and a y coordinate
typedef struct chessMove {
    int x, y;
} chessMove;




void PrepBoard()
{
    int x = startPosX;
    int y = startPosY;

    for (int i = 0; i < boardSize; i++)
    {
        for (int j = 0; j < boardSize; j++)
        {
            chessboard[i][j] = 0;
        }
    }
    chessboard[x][y] = 1;
}

bool IsMovePossible(chessMove nextMove)
{
    int i = nextMove.x;
    int j = nextMove.y;
    if ((i >= 0 && i < N) && (j >= 0 && j < N) && (chessboard[i][j] == 0))
    {
        return true;
    }
    return false;
}

bool CalculateTour(chessMove possibleMove[], chessMove currMove, int moveCount)
{
    if (moveCount == totalNumMoves)
    {
        return true;
    }
    chessMove nextMove;

    cout << "N = " << N << endl;
    for (int i = 0; i < N; i++)
    {
        nextMove.x = currMove.x + possibleMove[i].x;
        nextMove.y = currMove.y + possibleMove[i].y;
        if (IsMovePossible(nextMove))
        {
            cout << "nextMove is possible!, nextMove = " << nextMove.x << ", " << nextMove.y << endl;
            chessboard[nextMove.x][nextMove.y] = moveCount + 1;
            if (CalculateTour(possibleMove, nextMove, moveCount) == true)
            {
                return true;
            }
            else
            {
                cout << "setting next move to 0?";
                chessboard[nextMove.x][nextMove.y] = 0;
            }
        }
    }
    return false;

}



void PrintBoard()
{
    for (int i = 0; i < N; i++)
    {
        cout << "| ";
        for (int j = 0; j < N; j++)
        {
            string extra_space = " ";
            if (chessboard[i][j] >= 10) extra_space = "";
            cout << chessboard[i][j] << extra_space << " | ";
        }
        cout << "\n";
    }
}

int main(int argc, char ** argv)
{
    chessMove currentMove = { 0,0 };
    // all possible moves the the knight could make
    chessMove possibleMove[8] =
    {
        { 2,1 },{ 1,2 },{ -1,2 },{ -2,1 },{ -2,-1 },{ -1,-2 },{ 1,-2 },{ 2,-1 }
    };
    PrepBoard();
    if (CalculateTour(possibleMove, currentMove, moveCount) == false)
    {
        cout << "\nKnightsTour does not exist";
    }
    else
    {
        cout << "\nKnightsTour does exist \n";
        PrintBoard();
    }
    return 0;
}