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

namespace HouseMoveRecursive
{
    class Program
    {
        int count = 0;
        int solution = 0;
        static int n = 5;
        int[,] move = new int[8, 2] { { -1, -2 }, { -2, -1 }, { -2, 1 }, { -1, 2 }, { 1, 2 }, { 2, 1 }, { 2, -1 }, { 1, -2 } };
        public int[,] board=new int[n,n];
        bool IsOK(int x,int y)
        {
            if ((x <= n - 1) && (x >= 0)
                && (y <= n - 1) && (y >= 0)
                && (board[x,y] == 0))
            {
                return true;
            }
            else
            {
                return false;
            }
        }
       
      
        void Show()
        {
            Console.WriteLine("第{0}种解", solution++);
            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    Console.Write("  "+board[i, j]);
                }
                Console.WriteLine();
            }
            Console.WriteLine("-----");
        }
        void DFS(int row, int col)
        {
            int nextX;
            int nextY;
            
                for (int i = 0; i < 8; i++)
                {
                nextX = row + move[i,0];
                nextY = col + move[i, 1];
                if(IsOK(nextX,nextY))
                    
                    {
                    if (count <24)
                    {
                        count++;
                        board[nextX, nextY] = count;
                        DFS(nextX, nextY);
                        board[nextX, nextY] = 0;
                        count--;

                    }
                    else
                    {
                        Show();
                    }
                       
                    }
                }
         
        
      
            //find
            //forward
            //back
            //done
        }
        static void Main(string[] args)
        {
            Program p = new Program();

            for (int i = 0; i < n; i++)
            {
                for (int j = 0; j < n; j++)
                {
                    p.board[i, j] = 0;
                }
            }
            p.board[0,0] = 1;
            p.count = 1;
            p.DFS(0, 0);
            Console.ReadKey();
        }
    }
}