首页 > 代码库 > 骑士周游问题 --- 递归解法 --- java代码

骑士周游问题 --- 递归解法 --- java代码

骑士游历:

定义了向量的数组M,行数组X,列数组Y, 棋盘plane,计数器count,走动步数step

需要注意的是,递归函数的进入前的验证,原先的想法是传入来时的方向参数,可是这样的想法被实践否定了,

从理论上看,一个棋子走向哪里是不受它的过去制约的,最近的过去也不例外,

 

详情请见:http://en.wikipedia.org/wiki/Knights_tour

代码如下:

 

 

/**
 * Created by kodoyang on 2014/5/3.
 */
public class KnightTour {

    private static final int[][] M= {
            {2, 1}, {1, 2}, {-1, 2}, {-2, 1}, {-2, -1}, {-1, -2}, {1, -2}, {2, -1}
    };

    private static final int[] X = {0, 1, 2, 3, 4, 5, 6, 7}, Y = {0, 1, 2, 3, 4, 5, 6, 7};

    private static final int[][] plane = new int[X.length][Y.length];

    public final static void main(String[] args){

        int[] O = {0, 0};
        next(X[0], Y[0], 1);
    }

    private static int count = 0;
    private final static void next(final int x, final int y, final int step){

        plane[x][y] = step;
        if(step == 64)
            print( ++count );
        else {
            for(int i = 0; i < M.length; i++){
                int[] v = M[i];
                int _x = x + v[0], _y = y + v[1];

                if (valid(_x, _y))
                    next(_x, _y, step + 1);

            }
        }

        plane[x][y] = 0;
    }

    private static final boolean valid(final int x, final int y){
        boolean result = false;

        if(x >= X[0] && x <= X[7] && y >= Y[0] && y <= Y[7]){
            result = plane[x][y] == 0;
        }

        return result;
    }

    private static final void print(int step){
        System.out.println("----------------------------------   " + step + "   ------");
        for(int i = X[0]; i <= X[7]; ++i) {
            for (int j = Y[0]; j <= Y[7]; ++j) {
                System.out.print("\t" + plane[i][j]);
            }
            System.out.println();
        }
        System.out.println("---------------------------------------------------");
    }

}

 

 

这里一共有26,534,728,821,064种结果,程序被我提前停掉了,运行结果如下:


----------------------------------   1   ------
    1    60    39    34    31    18    9    64
    38    35    32    61    10    63    30    17
    59    2    37    40    33    28    19    8
    36    49    42    27    62    11    16    29
    43    58    3    50    41    24    7    20
    48    51    46    55    26    21    12    15
    57    44    53    4    23    14    25    6
    52    47    56    45    54    5    22    13
---------------------------------------------------
----------------------------------   2   ------
    1    50    45    62    31    18    9    64
    46    61    32    49    10    63    30    17
    51    2    47    44    33    28    19    8
    60    35    42    27    48    11    16    29
    41    52    3    34    43    24    7    20
    36    59    38    55    26    21    12    15
    53    40    57    4    23    14    25    6
    58    37    54    39    56    5    22    13
---------------------------------------------------
----------------------------------   3   ------
    1    60    45    48    31    18    9    64
    46    49    32    61    10    63    30    17
    59    2    47    44    33    28    19    8
    50    35    42    27    62    11    16    29
    41    58    3    34    43    24    7    20
    36    51    38    55    26    21    12    15
    57    40    53    4    23    14    25    6
    52    37    56    39    54    5    22    13
---------------------------------------------------
----------------------------------   4   ------
    1    60    57    44    31    18    9    64
    58    43    32    61    10    63    30    17
    33    2    59    56    45    28    19    8
    42    47    54    27    62    11    16    29
    53    34    3    46    55    24    7    20
    48    41    50    37    26    21    12    15
    35    52    39    4    23    14    25    6
    40    49    36    51    38    5    22    13
---------------------------------------------------
----------------------------------   5   ------
    1    60    43    48    31    18    9    64
    44    49    32    61    10    63    30    17
    59    2    45    42    47    28    19    8
    50    33    40    27    62    11    16    29
    39    58    3    46    41    24    7    20
    34    51    36    55    26    21    12    15
    57    38    53    4    23    14    25    6
    52    35    56    37    54    5    22    13
---------------------------------------------------
----------------------------------   6   ------
    1    60    43    48    31    18    9    64
    44    47    32    61    10    63    30    17
    59    2    45    42    49    28    19    8
    46    33    40    27    62    11    16    29
    39    58    3    50    41    24    7    20
    34    51    36    55    26    21    12    15
    57    38    53    4    23    14    25    6
    52    35    56    37    54    5    22    13
---------------------------------------------------
----------------------------------   7   ------
    1    60    35    30    37    18    9    64
    34    31    28    61    10    63    38    17
    59    2    33    36    29    40    19    8
    32    49    42    27    62    11    16    39
    43    58    3    50    41    24    7    20
    48    51    46    55    26    21    12    15
    57    44    53    4    23    14    25    6
    52    47    56    45    54    5    22    13
---------------------------------------------------
----------------------------------   8   ------
    1    50    45    62    43    18    9    64
    46    61    28    49    10    63    42    17
    51    2    47    44    29    40    19    8
    60    31    38    27    48    11    16    41
    37    52    3    30    39    24    7    20
    32    59    34    55    26    21    12    15
    53    36    57    4    23    14    25    6
    58    33    54    35    56    5    22    13
---------------------------------------------------
----------------------------------   9   ------
    1    60    45    48    43    18    9    64
    46    49    28    61    10    63    42    17
    59    2    47    44    29    40    19    8
    50    31    38    27    62    11    16    41
    37    58    3    30    39    24    7    20
    32    51    34    55    26    21    12    15
    57    36    53    4    23    14    25    6
    52    33    56    35    54    5    22    13
---------------------------------------------------
----------------------------------   10   ------
    1    60    39    34    29    18    9    64
    38    35    28    61    10    63    32    17
    59    2    37    40    33    30    19    8
    36    49    42    27    62    11    16    31
    43    58    3    50    41    24    7    20
    48    51    46    55    26    21    12    15
    57    44    53    4    23    14    25    6
    52    47    56    45    54    5    22    13
---------------------------------------------------
----------------------------------   11   ------
    1    50    45    62    29    18    9    64
    46    61    28    49    10    63    32    17
    51    2    47    44    33    30    19    8
    60    35    42    27    48    11    16    31
    41    52    3    34    43    24    7    20
    36    59    38    55    26    21    12    15
    53    40    57    4    23    14    25    6
    58    37    54    39    56    5    22    13
---------------------------------------------------
----------------------------------   12   ------
    1    60    45    48    29    18    9    64
    46    49    28    61    10    63    32    17
    59    2    47    44    33    30    19    8
    50    35    42    27    62    11    16    31
    41    58    3    34    43    24    7    20
    36    51    38    55    26    21    12    15
    57    40    53    4    23    14    25    6
    52    37    56    39    54    5    22    13
---------------------------------------------------
----------------------------------   13   ------
    1    34    59    46    29    18    9    64
    60    45    28    33    10    63    30    17
    35    2    61    58    47    32    19    8
    44    49    56    27    62    11    16    31
    55    36    3    48    57    24    7    20
    50    43    52    39    26    21    12    15
    37    54    41    4    23    14    25    6
    42    51    38    53    40    5    22    13
---------------------------------------------------
----------------------------------   14   ------
    1    60    35    46    29    18    9    64
    36    47    28    61    10    63    30    17
    59    2    49    34    45    32    19    8
    48    37    44    27    62    11    16    31
    43    58    3    50    33    24    7    20
    38    51    40    55    26    21    12    15
    57    42    53    4    23    14    25    6
    52    39    56    41    54    5    22    13
---------------------------------------------------
----------------------------------   15   ------
    1    50    35    62    29    18    9    64
    36    61    28    49    10    63    30    17
    51    2    47    34    45    32    19    8
    60    37    44    27    48    11    16    31
    43    52    3    46    33    24    7    20
    38    59    40    55    26    21    12    15
    53    42    57    4    23    14    25    6
    58    39    54    41    56    5    22    13
---------------------------------------------------
----------------------------------   16   ------
    1    60    35    48    29    18    9    64
    36    49    28    61    10    63    30    17
    59    2    47    34    45    32    19    8
    50    37    44    27    62    11    16    31
    43    58    3    46    33    24    7    20
    38    51    40    55    26    21    12    15
    57    42    53    4    23    14    25    6
    52    39    56    41    54    5    22    13
---------------------------------------------------
----------------------------------   17   ------
    1    56    35    62    29    18    9    64
    36    61    28    57    10    63    30    17
    55    2    59    34    45    32    19    8
    60    37    44    27    58    11    16    31
    43    54    3    46    33    24    7    20
    38    47    40    51    26    21    12    15
    53    42    49    4    23    14    25    6
    48    39    52    41    50    5    22    13
---------------------------------------------------
----------------------------------   18   ------
    1    46    35    58    29    18    9    64
    36    59    28    45    10    63    30    17
    47    2    61    34    57    32    19    8
    60    37    44    27    62    11    16    31
    43    48    3    56    33    24    7    20
    38    55    40    51    26    21    12    15
    49    42    53    4    23    14    25    6
    54    39    50    41    52    5    22    13
---------------------------------------------------
----------------------------------   19   ------
    1    46    35    58    29    18    9    64
    36    57    28    45    10    63    30    17
    47    2    61    34    59    32    19    8
    56    37    44    27    62    11    16    31
    43    48    3    60    33    24    7    20
    38    55    40    51    26    21    12    15
    49    42    53    4    23    14    25    6
    54    39    50    41    52    5    22    13
---------------------------------------------------
----------------------------------   20   ------
    1    60    35    46    29    18    9    64
    36    45    28    61    10    63    30    17
    59    2    49    34    47    32    19    8
    50    37    44    27    62    11    16    31
    43    58    3    48    33    24    7    20
    38    51    40    55    26    21    12    15
    57    42    53    4    23    14    25    6
    52    39    56    41    54    5    22    13
---------------------------------------------------
----------------------------------   21   ------
    1    56    35    62    29    18    9    64
    36    45    28    57    10    63    30    17
    55    2    59    34    61    32    19    8
    46    37    44    27    58    11    16    31
    43    54    3    60    33    24    7    20
    38    47    40    51    26    21    12    15
    53    42    49    4    23    14    25    6
    48    39    52    41    50    5    22    13
---------------------------------------------------
----------------------------------   22   ------
    1    50    35    62    29    18    9    64
    36    45    28    49    10    63    30    17
    51    2    47    34    61    32    19    8
    46    37    44    27    48    11    16    31
    43    52    3    60    33    24    7    20
    38    59    40    55    26    21    12    15
    53    42    57    4    23    14    25    6
    58    39    54    41    56    5    22    13
---------------------------------------------------
----------------------------------   23   ------
    1    60    35    48    29    18    9    64
    36    45    28    61    10    63    30    17
    59    2    47    34    49    32    19    8
    46    37    44    27    62    11    16    31
    43    58    3    50    33    24    7    20
    38    51    40    55    26    21    12    15
    57    42    53    4    23    14    25    6
    52    39    56    41    54    5    22    13
---------------------------------------------------
----------------------------------   24   ------
    1    60    35    56    29    18    9    64
    36    57    28    61    10    63    30    17
    45    2    59    34    55    32    19    8
    58    37    44    27    62    11    16    31
    43    46    3    54    33    24    7    20
    38    53    40    49    26    21    12    15
    47    42    51    4    23    14    25    6
    52    39    48    41    50    5    22    13
---------------------------------------------------
----------------------------------   25   ------
    1    60    35    56    29    18    9    64
    36    55    28    61    10    63    30    17
    45    2    59    34    57    32    19    8
    54    37    44    27    62    11    16    31
    43    46    3    58    33    24    7    20
    38    53    40    49    26    21    12    15
    47    42    51    4    23    14    25    6
    52    39    48    41    50    5    22    13
---------------------------------------------------
----------------------------------   26   ------
    1    60    35    48    29    18    9    64
    36    49    28    61    10    63    30    17
    59    2    37    34    47    32    19    8
    50    39    46    27    62    11    16    31
    45    58    3    38    33    24    7    20
    40    51    42    55    26    21    12    15
    57    44    53    4    23    14    25    6
    52    41    56    43    54    5    22    13
---------------------------------------------------
----------------------------------   27   ------
    1    40    35    62    29    18    9    64
    36    51    28    39    10    63    30    17
    41    2    37    34    61    32    19    8
    50    59    52    27    38    11    16    31
    53    42    3    60    33    24    7    20
    58    49    56    45    26    21    12    15
    43    54    47    4    23    14    25    6
    48    57    44    55    46    5    22    13
---------------------------------------------------
----------------------------------   28   ------
    1    60    35    38    29    18    9    64
    36    49    28    61    10    63    30    17
    59    2    37    34    39    32    19    8
    50    41    48    27    62    11    16    31
    47    58    3    40    33    24    7    20
    42    51    44    55    26    21    12    15
    57    46    53    4    23    14    25    6
    52    43    56    45    54    5    22    13
---------------------------------------------------
----------------------------------   29   ------
    1    38    35    50    29    18    9    64
    36    49    28    61    10    63    30    17
    39    2    37    34    51    32    19    8
    48    53    60    27    62    11    16    31
    59    40    3    52    33    24    7    20
    54    47    56    43    26    21    12    15
    41    58    45    4    23    14    25    6
    46    55    42    57    44    5    22    13
---------------------------------------------------
----------------------------------   30   ------
    1    60    35    40    29    18    9    64
    36    39    28    61    10    63    30    17
    59    2    37    34    41    32    19    8
    38    49    42    27    62    11    16    31
    43    58    3    50    33    24    7    20
    48    51    46    55    26    21    12    15
    57    44    53    4    23    14    25    6
    52    47    56    45    54    5    22    13
---------------------------------------------------
----------------------------------   31   ------
    1    60    35    40    29    18    9    64
    36    39    28    61    10    63    30    17
    59    2    37    34    41    32    19    8
    38    43    50    27    62    11    16    31
    49    58    3    42    33    24    7    20
    44    55    46    51    26    21    12    15
    57    48    53    4    23    14    25    6
    54    45    56    47    52    5    22    13
---------------------------------------------------
----------------------------------   32   ------
    1    52    35    40    29    18    9    64
    36    39    28    51    10    63    30    17
    53    2    37    34    41    32    19    8
    38    43    50    27    62    11    16    31
    49    54    3    42    33    24    7    20
    44    57    46    61    26    21    12    15
    55    48    59    4    23    14    25    6
    58    45    56    47    60    5    22    13
---------------------------------------------------
----------------------------------   33   ------
    1    60    35    40    29    18    9    64
    36    39    28    61    10    63    30    17
    59    2    37    34    41    32    19    8
    38    43    50    27    62    11    16    31
    49    58    3    42    33    24    7    20
    44    51    46    55    26    21    12    15
    57    48    53    4    23    14    25    6
    52    45    56    47    54    5    22    13
---------------------------------------------------
----------------------------------   34   ------
    1    60    35    48    29    18    9    64
    36    47    28    61    10    63    30    17
    59    2    37    34    49    32    19    8
    46    51    58    27    62    11    16    31
    57    38    3    50    33    24    7    20
    52    45    54    41    26    21    12    15
    39    56    43    4    23    14    25    6
    44    53    40    55    42    5    22    13
---------------------------------------------------

Process finished with exit code -1