using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace Backtracking_TKT
{
    class Program
    {
        static int N;

        static bool IsSafe(int[,] board, int row, int col)
        {
            if (row < 0 || col < 0 || row >= N || col >= N)
            {
                return false;
            }
            if (board[row, col] != 0)
            {
                return false;
            }
            return true;
        }

        static void PrintSolution(int[,] board)
        {
            for (int i = 0; i < N; i++)
            {
                for (int j = 0; j < N; j++)
                {
                    Console.Write("{0:00} ", board[i, j]);
                }
                Console.WriteLine();
            }
        }

        static bool SolveKnightTour(int[,] board, int x, int y, int movei, int[] xMove, int[] yMove)
        {
            if ((movei - 1) == N * N)
            {
                return true;
            }
            for (int k = 0; k < 8; k++)
            {
                int nextX = x + xMove[k];
                int nextY = y + yMove[k];
                if (IsSafe(board, nextX, nextY))
                {
                    board[nextX, nextY] = movei;
                    //PrintSolution(board);
                    //Console.WriteLine();
                    if (SolveKnightTour(board, nextX, nextY, movei + 1, xMove, yMove))
                    {
                        return true;
                    }
                    else
                    {
                        board[nextX, nextY] = 0;
                    }
                }
            }
            return false;
        }
        static void Main(string[] args)
        {
            N = 6;
            int[,] matrix = new int[N, N];
            int[] xm = { -1, -1, 1, 1, -2, -2, 2, 2 };
            int[] ym = { -2, 2, 2, -2, 1, -1, 1, -1 };
            if (!SolveKnightTour(matrix, 0, 0, 1, xm, ym))
            {
                Console.WriteLine("No solution!");
            }
            else
            {
                PrintSolution(matrix);
            }
        }
    }
}