Knight's Tour

using System;

namespace GreedyKnight
{
    class Program
    {

        private static int[,] chessboard;
        private static int counter;

        static void Main()
        {
            int N = int.Parse(Console.ReadLine());
            chessboard = new int[N, N];
            counter = 1;
            chessboard[0, 0] = counter;
            FindPath(0, 0);
        }

        private static void FindPath(int col, int row)
        {
            if (!IsInMa3x(col, row))
            {
                return;
            }
            int possibilities = 0;
            int bestPossibility = int.MaxValue;
            int nextCol = 0;
            int nextRow = 0;

            possibilities = CalcWarnsdorf(col + 2, row + 1); //RRD 1
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col + 2;
                nextRow = row + 1;
            }
            possibilities = CalcWarnsdorf(col + 2, row - 1); //RRU 8
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col + 2;
                nextRow = row - 1;
            }



            possibilities = CalcWarnsdorf(col - 2, row + 1); //LLD 4
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col - 2;
                nextRow = row + 1;
            }
            possibilities = CalcWarnsdorf(col - 2, row - 1); //LLU 5
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col - 2;
                nextRow = row - 1;
            }

            possibilities = CalcWarnsdorf(col + 1, row + 2); //DDR 2
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col + 1;
                nextRow = row + 2;
            }
            possibilities = CalcWarnsdorf(col - 1, row + 2); //DDL 3
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col - 1;
                nextRow = row + 2;
            }

            possibilities = CalcWarnsdorf(col + 1, row - 2); //RUU 7
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col + 1;
                nextRow = row - 2;
            }

            possibilities = CalcWarnsdorf(col - 1, row - 2); //LUU 6
            if (possibilities < bestPossibility)
            {
                bestPossibility = possibilities;
                nextCol = col - 1;
                nextRow = row - 2;
            }

            counter++;
            chessboard[nextCol, nextRow] = counter;
            if (counter == (chessboard.GetLength(0)*chessboard.GetLength(1)))
            {
                Print(chessboard);
                return;
            }
            FindPath(nextCol, nextRow);
        }

        private static void Print(int[,] chessboard)
        {
            for (int i = 0; i < chessboard.GetLength(0); i++)
            {
                for (int j = 0; j < chessboard.GetLength(1); j++)
                {
                    string str = string.Format("{0} ", chessboard[j, i]);
                    Console.Write(str.PadLeft(4, ' '));
                }
                Console.WriteLine();
            }
        }

        private static int CalcWarnsdorf(int col, int row)
        {
            if (!IsInMa3x(col, row))
            {
                return int.MaxValue;
            }
            else if (!IsNewPosition(col, row))
            {
                return int.MaxValue;
            }
            else
            {
                int possibilities = 0;
                possibilities += IsSolution(col + 2, row + 1); //RRD 1
                possibilities += IsSolution(col + 1, row + 2); //DDR 2
                possibilities += IsSolution(col - 1, row + 2); //DDL 3
                possibilities += IsSolution(col - 2, row + 1); //LLD 4
                possibilities += IsSolution(col - 2, row - 1); //LLU 5
                possibilities += IsSolution(col - 1, row - 2); //LUU 6
                possibilities += IsSolution(col + 1, row - 2); //RUU 7
                possibilities += IsSolution(col + 2, row - 1); //RRU 8
                return possibilities;
            }
        }

        private static int IsSolution(int col, int row)
        {
            if (!IsInMa3x(col, row))
            {
                return 0;
            }
            if (!IsNewPosition(col, row))
            {
                return 0;
            }
            else
            {
                return 1;
            }
        }

        private static bool IsNewPosition(int col, int row)
        {
            if (chessboard[col, row] == 0)
            {
                return true;
            }
            return false;
        }

        private static bool IsInMa3x(int col, int row)
        {
            if (col < 0 || row < 0)
            {
                return false;
            }
            if (col > chessboard.GetLength(0) - 1 || row > chessboard.GetLength(1) - 1)
            {
                return false;
            }
            return true;
        }
    }
}