Chess

using System;
using System.Collections.Generic;

namespace KnightMoves
{
    class Program
    {
        //You need to move the knight through the whole board following these additional rules:
        //1.You start from the top left cell of the board 1.At each turn, from all 8 possible moves,
        //move the knight to the topmost, leftmost cell of the board that hasn't been visited
        //1. If all the 8 positions have been already visited, restart moves from the leftmost,
        //topmost unvisited cell 1. At each turn leave a number on the cell, to indicate that the
        //position has been visited and on which turn was visited
        //By given the size of the board, print the board with the knight's moves on it.
        static void Main(string[] args)
        {
            List<int> moves = new List<int>();
            int n = int.Parse(Console.ReadLine());
            int[,] matrix = new int[n, n];
            InitializeMatrix(n, matrix);
            int[] KnightIndex = new int[2] { 0, 0 };
            int counter = 2;
            matrix[0, 0] = 1;
            while (!Finished(n, matrix))
            {
                MovesAvailable(KnightIndex, matrix, moves);
                KnightIndex = TopmostLeftmost(KnightIndex, matrix, moves);
                matrix[KnightIndex[0] - 1, KnightIndex[1] - 1] = counter;
                counter++;
                moves.Clear();
            }
            Print(n, matrix);
        }
        static bool Finished(int n, int[,] matrix)
        {
            bool finish = true; ;
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    if (matrix[i, j] == 0)
                    {
                        finish = false;
                        break;
                    }
                }
            }
            return finish;
        }
        static void MovesAvailable(int[] KnightIndex, int[,] matrix, List<int> moves)
        {
            bool noMoves = true;
            if (UpRight(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }
            if (UpLeft(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }

            if(LeftUp(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }
            if (LeftDown(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }


            if (RightUp(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }

            if (RightDown(matrix, KnightIndex).Item1)

            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }
            if (DownLeft(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }

            if (DownRight(matrix, KnightIndex).Item1)
            {
                moves.Add(KnightIndex[0]);
                moves.Add(KnightIndex[1]);
                noMoves = false;
            }

            if (noMoves)
            {
                for (int i = 0; i < matrix.GetLength(0); i++)
                {
                    for (int j = 0; j < matrix.GetLength(1); j++)
                    {
                        if (matrix[i, j] == 0)
                        {
                            moves.Add(i);
                            moves.Add(j);
                        }
                    }
                }
            }
        }
        static int[] TopmostLeftmost(int[] KnightIndex, int[,] matrix, List<int> moves)
        {
            int[] TopMost = new int[2];
            TopMost[0] = moves[0];
            TopMost[1] = moves[1];
            if (moves.Count == 2)
            {
                return TopMost;
            }
            for (int i = 0; i < moves.Count - 3; i++)
            {
                if (moves[i] > moves[i + 2])
                {
                    TopMost[0] = moves[i + 2];
                    TopMost[1] = moves[i + 3];
                }
                else if (moves[i] == moves[i + 2])
                {
                    if (moves[i + 1] > moves[i + 3])
                    {
                        TopMost[0] = moves[i + 2];
                        TopMost[1] = moves[i + 3];
                    }
                    else
                    {
                        TopMost[0] = moves[i];
                        TopMost[1] = moves[i + 1];
                    }
                }
                else
                {
                    TopMost[0] = moves[i];
                    TopMost[1] = moves[i + 1];
                }
            }
            return TopMost;
        }
        static void Print(int n, int[,] matrix)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("{0, 4}", matrix[i, j]);
                }
                Console.WriteLine();
            }
        }
        static void InitializeMatrix(int n, int[,] matrix)
        {
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    matrix[i, j] = 0;
                }
            }
        }
        static (bool, int[]) Check(int[,] matrix, int[] KnightIndex)
        {
            if (KnightIndex[0] >= 0 && KnightIndex[0] < matrix.GetLength(0))
            {
                if (KnightIndex[1] >= 0 && KnightIndex[1] < matrix.GetLength(1))
                {
                    if (matrix[KnightIndex[0], KnightIndex[1]] == 0)
                    {
                        return (true, KnightIndex);
                    }
                    return (false, KnightIndex);
                }
                return (false, KnightIndex);
            }
            return (false, KnightIndex);
        }
        static (bool, int[]) UpRight(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] -= 2;
            KnightIndex[1]++;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) UpLeft(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] -= 2;
            KnightIndex[1]--;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) LeftUp(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] -= 1;
            KnightIndex[1] -= 2;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) LeftDown(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] += 1;
            KnightIndex[1] -= 2;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) RightUp(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] -= 1;
            KnightIndex[1] += 2;
            return Check(matrix, KnightIndex);

        }
        static (bool, int[]) RightDown(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] += 1;
            KnightIndex[1] += 2;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) DownLeft(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] += 2;
            KnightIndex[1] -= 1;
            return Check(matrix, KnightIndex);
        }
        static (bool, int[]) DownRight(int[,] matrix, int[] KnightIndex)
        {
            KnightIndex[0] = KnightIndex[0] + 2;
            KnightIndex[1] = KnightIndex[1] + 1;
            return Check(matrix, KnightIndex);

        }
    }
}