#define WIN32_LEAN_AND_MEAN
#include <Windows.h>
#include <stdio.h>

static int N = 5;
static int** Board = NULL;

#define Abs(a) (a < 0 ? -a : a)

bool BeenThere()
{
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            if (Board[i][j] == 0)
                return false;
        }
    }

    return true;
}

bool CanDo_Knight(int Row, int Column, int Count)
{
    if ((Row >= 0 && Row < N) && (Column >= 0 && Column < N))
    {
        if (Board[Row][Column] == 1) //Been there, done that...
        {
            return false;
        }
        else
        {
            Board[Row][Column] = 1;

            if (Count == N * N)
                return true;

            for (int r = -2; r <= 2; r++)
            {
                if (r != 0)
                {
                    for (int c = -2; c <= 2; c++)
                    {
                        if (c != 0)
                        {
                            if (Abs(r) != Abs(c))
                            {
                                if (CanDo_Knight(Row + r, Column + c, Count + 1))
                                {
                                    printf("{ %d, %d", Row + r + 1, Column + c + 1);
                                    if (Count > 1)
                                        printf(" }, ");
                                    else
                                        printf(" }\n");

                                    return true;
                                }
                            }
                        }
                    }
                }
            }

            Board[Row][Column] = 0;
            return false;
        }
    }
    else
    {
        return false;
    }
}

void PrintStartingPoint_Knight()
{
    int TotalTime = GetTickCount();

    int i = 0;
    int j = 0;
    for (int i = 0; i < N; i++)
    {
        for (int j = 0; j < N; j++)
        {
            for (int k = 0; k < N; k++)
                ZeroMemory(Board[k], N * sizeof(Board[i]));

            int StartingTime = GetTickCount();

            printf("%d, %d:\n", i, j);

            if (CanDo_Knight(i, j, 1))
                printf("Success!!!");
            else
                printf("Failure\t");
            printf("\t(%f seconds)\n\n\n", (GetTickCount() - StartingTime) / 1000.0f);
        }
    }

    printf("Done!\nTotal Time: %f seconds.\n", (GetTickCount() - TotalTime) / 1000.0f);
}

void PrintBoard()
{
    const char Outputs[2][4][6] = { { "%d", "%c", "  " }, { "%02d", "% 2c", "   " } };

    for (int row = -1; row < N; row++)
    {
        if (row != -1)
        {
            printf(Outputs[N >= 10][0], row + 1);

            putchar('|');
        }
        else
        {
            printf(Outputs[N >= 10][2]);
        }

        for (int col = 0; col < N - 1; col++)
        {
            if (row == -1)
                printf(Outputs[N >= 10][0], col + 1);
            else
                printf(Outputs[N >= 10][1], Board[row][col]);

            putchar('|');
        }

        if (row == -1)
            printf(Outputs[N >= 10][0], N);
        else
            printf(Outputs[N >= 10][1], Board[row][N - 1]);

        putchar('\n');
    }
}

void SetQueen(int Row, int Column, int bSet)
{
    for (int distance = 1; distance < N; distance++)
    {
        for (int row = -1; row <= 1; row++)
        {
            for (int col = -1; col <= 1; col++)
            {
                int r = Row + row * distance;
                int c = Column + col * distance;

                if ((r >= 0 && r < N) && (c >= 0 && c < N))
                    Board[r][c] += (bSet ? 1 : -1);
            }
        }
    }

    if (bSet)
        Board[Row][Column]++;
    else
        Board[Row][Column] = 0;
}

bool CanDo_Queen(int Row = 0)
{
    if (Row >= N)
        return (Row == N);

    for (int Column = 0; Column < N; Column++)
    {
        if (Board[Row][Column] == 0)
        {
            SetQueen(Row, Column, 1);
            bool bRet = CanDo_Queen(Row + 1);
            SetQueen(Row, Column, 0);

            if (bRet)
            {
                Board[Row][Column] = 'Q';

                printf("{ %d, %d }", Row + 1, Column + 1);

                if (Row)
                    printf(", ");
                else
                    printf("\n");

                return true;
            }
        }
    }

    return false;
}

void PrintStartingPoint_Queen()
{
    int StartingTime = GetTickCount();

    if (CanDo_Queen())
    {
        printf("Success!!!!!!!!!!!\n--------------------\n");
        PrintBoard();
    }
    else
    {
        printf("Failure");
    }

    printf("\nDone!\nTime: %f seconds.\n", (GetTickCount() - StartingTime) / 1000.0f);
}

int main()
{
    int bLoop = 1;
    int Choice;

    do
    {
        printf( "1. Knight's Tour\n"
                "2. Queens Puzzle\n"
                "3. Exit\nEnter your choice: ");
        do
        {
            bLoop = scanf_s("%d", &Choice);

            if (Choice == 3)
                return 1;

            if (!bLoop)
                printf("Invalid option!\n");
        }
        while (!bLoop);

        if (Board)
        {
            for (int i = 0; i < N; i++)
                delete Board[i];

            delete[] Board;
        }

        do
        {
            printf("Enter size: ");
            bLoop = scanf_s("%d", &N);

            if (!bLoop)
                printf("Enter a valid integer!\n");
            else if (N < 4 || N >= 100)
                printf("Size must be at least 4 and less than 100!\n");

        } while (N < 4 || N >= 100);

        Board = (int**)new int[N];
        for (int i = 0; i < N; i++)
        {
            Board[i] = new int[N];
            ZeroMemory(Board[i], N * sizeof(Board[i]));
        }

        if (Choice == 1)
        {
            printf( "\n---------------------------------------------\n"
                    "\n\t\tKnight's Tour\n"
                    "\n---------------------------------------------\n");

            PrintStartingPoint_Knight();
        }
        else if (Choice == 2)
        {
            printf( "\n---------------------------------------------\n"
                    "\n\t\tQueens Puzzle\n"
                    "\n---------------------------------------------\n");

            PrintStartingPoint_Queen();
        }
    } while (bLoop);

    return 0;
}