藍色情懷

[趣味]騎士問題

在 n x n 的棋盤上，最多可以放置多少個西洋棋的「騎士」，使得每隻棋子都恰可攻擊其它二個「騎士」 (請繪出其配置圖，在符合題目所給條件下，試證：不可能放置更多的「騎士」) ？(註：騎士在棋盤上可攻擊的位置為橫二縱一或橫一縱二的位置。)

壹.   問題來源 :

    跳棋遊戲 : 騎士問題 (Knight Question) 遊戲中,騎士在 N 5 N格棋

    盤上走過的路徑,找出路徑圖形的特性,各階走法並求出其快速解 ·

貳.   內容:

1.下棋規則:騎士在 N 5 N 格棋盤上,將每一個格子都要走完,且走過的格子不可重複,其中騎士的走法與西洋棋中騎士的走法相同既:騎士在( a , b )的位置,則下一步只能到 ( a-2 , n-1 ) , ( a-1 , b-2 ) , ( a+1 , b-2 ) , ( a+2 , b-1 ) , ( a+2 ,b+1 ) , ( a+1 , b+2 ) , ( a-1 , b+2) , ( a-2 , b+1 ) ·

如圖示      n :現在位置                g 下一步

2.  以5 5 5 階棋盤為例:

                             -1-

這是其中一種走法, 5 5 5階共有122種走法(作者利用電腦排列算出)

3.圖形依對稱形態分成三類 :

a:點對稱圖形:以一點為中心旋轉180度後新圖形與原圖形重合者

b:四面對稱圖形:以一點為中心旋轉90度後新圖形與原圖形重合者

c:線對稱圖形:沿一直線將圖形對折直線兩側圖形重合者

4. 圖形型態歸納如下( N 5 N 階) :

(1)    n為奇數

a 圖形不能封閉

b沒有四面對稱圖形

c 沒有線對稱圖形

d有點對稱圖形

(2)    n為偶數且圖形不能封閉

a.沒有四面對稱圖形

b.沒有線對稱圖形

c.沒有點對稱圖形

(3)    n為偶數且圖形封閉

a.沒有線對稱圖形

b.有點對稱圖形

c.當n=4k+2 有四面對稱圖形

當n=4k 沒有四面對稱圖形

5.  N 5 N 階  圖形型態分類表(n=4k  n=4k+1  n=4k+2  n=4k+3)

// C version

/*
* 在國際棋盤格的隨意一個位置
* 放一個騎士(馬), 採用象棋中的馬走日字規則
* 要求這騎士(馬)能不重複的走完25個格子.
*/
 
#include <stdio.h>
 
// 定義一個矩陣來模擬棋盤
int chessboard[11][11];
// 標誌矩陣,即對於上述棋盤，一次進行編號1~121(行優先)
// 可以從一個棋盤格子跳到棋盤格子J時 adjm[i][j] = 1
int adjm[121][121];
// 宣告矩陣大小和標誌矩陣的大小
int n, m;
 
// 建立標誌矩陣函數宣告
void CreateAdjm(void);
// 將標誌矩陣相應位置置1
void SetMark(int, int, int, int);
// 遍巡函數宣告
void Travel(int, int);
 
int main()
{
    int i, j, k, z;
    // 輸入矩陣的大小值
    printf( "Input chessboard : " );
    scanf( "%d", &n );
    m = n*n;
    // 建立標誌矩陣
    CreateAdjm();
    // 打印輸出標誌矩陣
    for (i=1; i<=m; ++i)
    {
        for (j=1; j<=m; ++j)
            printf( "%2d", adjm[i][j] );
        printf( "\n" );
    }
 
    // 輸入騎士的初始位置
    printf( "Input i, j: " );
    scanf( "%d %d", &i, &j );
 
    // 騎士當前對應標誌矩陣的橫坐標
    z = (i-1)*n + j;
    // 對騎士位置的判斷
    while ((i>0) || (j>0))
    {
        for (i=0; i<=n; ++i)
            for (j=0; j<=n; ++j)
                chessboard[i][j] = 0;
        // 所跳步數計數
        k = 0;
        // 從I, J 出發開始遍巡
        Travel(z, k);
        // 遍巡完後輸出遍巡過程
        for (i=1; i<=n; ++i)
        {
            for (j=1; j<=n; ++j)
                printf( "%4d", chessboard[i][j]);
            printf( "\n" );
        }
 
        // 為下一次遍巡輸入起始位置
        printf( "Input i, j: " );
        scanf ( "%d %d", &i, &j );
        z = (i-1)*n + j;
    }
 
    return 0;
}
 
// 初始化矩陣
void CreateAdjm()
{
    int i, j;
    // 初始化遍巡矩陣
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            chessboard[i][j] = 0;
    // 初始化標誌矩陣
    for (i=1; i<=m; ++i)
        for (j=1; j<=m; ++j)
            adjm[i][j] = 0;
    for (i=1; i<=n; ++i)
        for (j=1; j<=n; ++j)
            if (chessboard[i][j] == 0)
            {
                chessboard[i][j] = 1;
                if ((i+2<=n) && (j+1<=n))
                    SetMark(i, j, i+2, j+1);
                if ((i+2<=n) && (j-1>=1))
                    SetMark(i, j, i+2, j-1);
                if ((i-2>=1) && (j+1<=n))
                    SetMark(i, j, i-2, j+1);
                if ((i-2>=1) && (j-1>=1))
                    SetMark(i, j, i-2, j-1);
                if ((j+2<=n) && (i+1<=n))
                    SetMark(i, j, i+1, j+2);
                if ((j+2<=n) && (i-1>=1))
                    SetMark(i, j, i-1, j+2);
                if ((j-2>=1) && (i+1<=n))
                    SetMark(i, j, i+1, j-2);
                if ((j-2>=1) && (i-1>=1))
                    SetMark(i, j, i-1, j-2);
            }
    return;
}
 
// 遍巡子函數
void Travel(int p, int r)
{
    int i, j, q;
    for (i=1; i<=n; ++i)
    for (j=1; j<=n; ++j)
    // 棋盤矩陣的值 > r, 則置1
    if (chessboard[i][j] > r)
        chessboard[i][j] = 0;
    // 跳步計數器加一
    r++;
    // 還原棋盤矩陣的橫坐標
    i = ((p-1)/n) + 1;
    // 還原棋盤矩陣的縱坐標
    j = ((p-1)%n) + 1;
    // 將chessboard[i][j]作為第r跳步的目的地
    chessboard[i][j] = r;
    for (q=1; q<=m; q++)
    {
        i = ((q-1)/n) + 1;
        j = ((q-1)%n) + 1;
        if ((adjm[p][q] == 1) && (chessboard[i][j] == 0))
            // 遞迴呼叫(引用)自身
            Travel(q, r);
    }
    return;
}
 
// 賦值子函數
void SetMark(int i1, int j1, int i2, int j2)
{
    adjm[(i1-1)*n+j1][(i2-1)*n+j2] = 1;
    adjm[(i2-1)*n+j2][(i1-1)*n+j1] = 1;
    return;
}

// C++ version

#include <iostream>
#include <iomanip>

using namespace std ;

// ANSI escape sequence
const char* wbc = "[34;46m" ;
const char* wrw = "[31;47m" ;
const char* wdf = "[0m" ;

const int SIZE = 5 ;

class  Knight {

  private :

    const static int NO   = 3 ;

    int  count ;
    int  knight[SIZE][SIZE] ;
    int  sol[SIZE][NO*SIZE] ;

    // print solutions in rows
    void  print_sol() const ;
    void  advance(int step , int i , int j ) ;
   
  public :

    Knight( void ) ;

    // find solutions starting from position (x,y)
    void  find( int x , int y ) ;

    // find all solutions
    void  find_all_solutions() ;
   
};


void  Knight::find( int x , int y ) {

    advance( 1 , x , y ) ;

    if ( count % NO != 0 )  print_sol() ;

}


void  Knight::find_all_solutions() {

    int i , j ;
    for ( i = 0 ; i < SIZE ; ++i ) {
        for ( j = 0 ; j < SIZE ; ++j ) {
            advance(1,i,j) ;
        }
    }
    if ( count % NO != 0 ) print_sol() ;
   
}


Knight::Knight( void ) : count(0) {

    int  i , j  ;

    for ( i = 0 ; i < SIZE ; i++ )
        for ( j = 0 ; j < SIZE ; j++ ) knight[i][j] = 0 ;
   
    for ( i = 0 ; i < SIZE ; i++ )
        for ( j = 0 ; j < NO * SIZE ; j++ ) sol[i][j] = 0 ;

}



void  Knight::print_sol (void) const {

    int i , j ;
    int r , no ;

    r = count % NO ;   
   
    if ( r == 0 ) r = NO ;

    no = count - r ;

    int  w = 0 ;
    for ( int tmp = count ; tmp != 0 ; tmp/=10 ) ++w ;
   

    for ( i = 0 ; i < SIZE ; i++ ) {
               
        if ( i == 0 ) {

            for ( j = 0 ; j < r ; ++j ) {
                cout << setw(12-w-2) << " " << wrw << setw(1) << " "
                     << setw(w) << no+j+1 << setw(1) << " " << wdf << " " ;
                if ( j < r-1 ) cout << setw(14) << " " ;
            }
            cout << endl ;

        }
                   
        for ( j = 0 ; j < SIZE*r ; j++ ) {
            cout << wbc << setw(3) << sol[i][j] << setw(1) << " " << wdf ;
            if ( (j+1)%SIZE == 0 )  cout << setw(7) << " " ;
        }

        cout << endl ;

    }

    cout << "\n\n\n" ;

} 


void  Knight::advance( int step , int i , int j ) {

    int  m , n , x , y ;

    if ( knight[i][j] == 0 ) {
  
        knight[i][j] = step ;
       
        if ( step == (SIZE*SIZE) ) {

            count++ ;
           
            n = ( ( count - 1 ) % NO )  * SIZE ;

            for ( x = 0 ; x < SIZE ; x++ )
                for ( y = n ; y < n + SIZE ; y++ )
                    sol[x][y] = knight[x][y-n] ;

            if ( count % NO == 0 )  print_sol() ;
           
            knight[i][j] = 0 ;
                           
        } else {

            for ( m = -2 ; m <= 2 ; m++ ) {
                for ( n = -2 ; n <= 2 ; n++ ) {
                    x = m + i ;  y = n + j ;
                    if ( ( m * m + n * n == 5 ) &&
                         ( x >= 0 && x <= 4 ) &&  ( y >= 0 && y <= 4 ) ) {
                        advance ( step + 1 , x , y  ) ;
                    }       
                }
            }

            knight[i][j] = 0 ;

        }
    }
}


int  main() {
    Knight  knight ;
    knight.find_all_solutions()        
    return 0 ;
}