#include <iostream>"
#include <conio.h>
#include <iomanip>



using namespace std;

/* 
    Chuong Trình : Mã Ði Tu?n 
    Gi?i Thu?t     : Ð? Qui + Quay Lui
    Mô T?         :
    -------------------- -----------------------
    T?i m?t v? trí trên bàn c?:

                 C?t    
        -------------------------
        |    | x1|    | x2|    |    |
        -------------------------
        | x8|    |    |    | x3|    |
        -------------------------
Hàng    |    |    | M    |    |    |    |
        -------------------------
        | x7|    |    |    | x4|    |
        -------------------------
        |    | x6|    | x5|    |    |
        -------------------------

        Mã ( M( Hàng, Cot )  ) có the di duoc 8 hu?ng khác nhau .
        Các vi trí có the duoc dánh dáu là x(1->8).
        Trong dó t?a d? các v? trí ph? thu?c Hàng C?t c?a M .

        Bây gi? ta s? s? d?ng Quay Lui d? duy?t l?n lu?t các hu?ng
        có th? di c?a con mã ( M ) . Ð? d?t mã M t?i ví trí nào dó
        thì t?i v? trí dó ph?i thu?c trong bàn c? ,và T?i dó con mã
        chua t?ng di qua .
        Ta s? s? d?ng các bi?n nhu sau :
        + ChessBoard[n][n] : Ð? luu các giá tr? mã dã di qua trên bàn c?
        + Number : Ð? xem th? M dã di qua du?c bao nhiêu ô trên bàn c? (< n*n)
        + Row[n] : Ð? luu d?a ch? các hàng có th? di d?n t? M.
        + Col[n] : Tuong t? nhung là giá tr? c?t .

        Ð? gi?m thi?u dk , ta s? s? d?ng ki thu?t c?m canh nhu v?y :
        +chessBoard[n+4][n+4]
        
*/
int n;
int chessBoard[12][12];
int number;
int row[8]={-2,-1,1,2,2,1,-1,-2};
int col[8]={1,2,2,1,-1,-2,-2,-1};
/********************************
    Kh?i d?ng cho bàn c? .
    Các ô chua di qua , s? ô di qua = 0, 
    và giá tr? chi?u dài,r?ng c?a b.c? 
**********************************/
void initialize()
{
    
    n=12;
    // Kh?i t?o các giá tr? ban d?u theo kt c?m canh
    for(int i=0;i<n;i++)
        for(int j=0;j<n;j++)
        {    
            if( i>=2 && i< 10 && j>=2 && j<10 )
                chessBoard[i][j]=0;
            else
                chessBoard[i][j]=-1;

        }
}
/***********************************
    Hàm Show dùng d? in các bu?c trong
    quá trình d? qui. 
***********************************/

void Show()
{
    system("cls");
    for(int i=2;i<n-2;i++)
    {
        cout<<"|";
        for(int j=2;j<n-2;j++)
        {
            if(chessBoard[i][j] == 0)
                cout<<"   "<<"|";
            else
                cout<<chessBoard[i][j]<<"|";
        }
        cout<<endl;
        cout<<"|";
        for(int j=2;j<n-2;j++)
        {
            
                cout<<"---"<<"|";

        }
        cout<<endl;
        
    }
    getch();
 

}
/***********************************
    Thông báo k?t qu? ra ngoài .
***********************************/


void Try(int step,int i,int j)
{
    int hang,cot;
    
    for(int v=0;v<8;v++)
        {
            // Cac Buoc Nhay :
            hang=i+row[v];
            cot=j+col[v];
            if(chessBoard[hang][cot] == 0 )
            {
                if(step +1 == 64)
                {
                    chessBoard[hang][cot]= step+1;
                    Show();
                    chessBoard[hang][cot]= 0;

                }
                
                else
                {
                    chessBoard[hang][cot]= step+1;
                    Try(step+1,hang,cot);
                    chessBoard[hang][cot]= 0;
    
                }
            
            }
            
            
            
        }
}
int main()
{
    initialize();
    chessBoard[2][2]=1;
    Try(1,2,2);
    cout<<" Ket Thuc"<<endl;
    
    system ("pause");
    return 0;
}