离散数学(CS201)期末Project报告

Knight's Tour Problem

1. Introduction

Knight’s tour problem is a special case of Travelling Salesman Problem(TSP) or Hamiltonian Cycle Problem(HCP).[1]

The problem is that, on a chessboard, the knight needs to jump over the entire chessboard, only one jump per grid, and finally return to the starting point.

2. Solution

Obviously, we can use DFS and backtracking to solve the problem. For every point, there are 8 directions to search. If all 8 directions are impossible, we do the backtracking.

Based on this, we can write the Java code.

public class KnightTour {
    private static int[][] chessboard;
    private static long backCount;//backtracking times
    private static int boardSize;
    private static long startTime,endTime;
    private static int startX,startY;
    private static final int[] DIRECTIONS={{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1},{-2,1},{-1,2}};
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        System.out.print("Chessboard size:");
        boardSize = sc.nextInt();
        chessboard = new int[boardSize][boardSize];
        System.out.print("Starting point (x,y):");
        startX=sc.nextInt();
        startY=sc.nextInt();
        startTime=System.currentTimeMillis();
        dfs(startX,startY,0);
    }
    
    public static void dfs(int x,int y,int step){
        if(x<0 || x>=boardSize || y<0 || y>=boardSize){
            return;//out of the board
        }
        if(chessboard[x][y]>0){
            return;//point(x,y) has been arrived
        }
        if(step>0 && x==startX && y==startY && step<boardSize*boardSize){
            return;//arrive the start point, but don't traverse all board grids
        }
        chessboard[x][y]=step;
        if(step==boardSize*boardSize){//recursion exit
            endTime=System.currentTimeMillis();
            System.out.println("Backtracking times: "+backCount);
            System.out.printf("Time cost: %.2fs\n",(endTime-startTime)/1000.0);
            System.out.println("Result:");
            System.out.println(Arrays.deepToString(chessboard).replace("], ","]\n").substring(1).replace("]]","]"));
            System.exit(1);
        }
        //every point has 8 possible directions
        for(int i=0;i<8;i++){
            dfs(x+DIRECTIONS[i][0],y+DIRECTIONS[i][1],step+1);
            backCount++;
        }
        chessboard[x][y]=0;//all 8 directions are impossible, do the backtracking
    }
}

Then we test the algorithm, the result is below

Chessboard size:6
Starting point (x,y):0 2
Backtracking times: 1867147642 //Too many!!
Time cost: 11.26s
Result:
[8, 33, 36, 21, 24, 11]
[35, 20, 7, 10, 1, 22]
[32, 9, 34, 23, 12, 25]
[19, 6, 27, 30, 15, 2]
[28, 31, 4, 17, 26, 13]
[5, 18, 29, 14, 3, 16]

The result is correct. But obviously, the time cost is too large because every point has 8 choices, by Multiplication Principle, the time complexity is $O(8^{n^2})$, where $n$ is the chessboard size.

3. Optimize by using greedy algorithm

We can choice the direction greedily to increase the success probability. That is to say, we should first choose the most difficult point to arrive. The fewer available directions one point has, it’s more difficult to access. If we first choice the most difficult point, the remaining points are easier to access, the success probability will increase, then the backtracking times and time cost will certainly decrease.[2]

We use below method to compute the number of available directions.

static int[][] move={{-2,1},{-1,2},{1,2},{2,1},{2,-1},{1,-2},{-1,-2},{-2,-1}};//stores the direction
public static int possibleDirections(int x,int y){
    if(x<0 || x>=boardSize || y<0 || y>=boardSize){
        return 9;//out of the board
    }
    int count=0;
    for (int i = 0; i < 8; i++) {//scan all 8 directions
        int nextX=x+move[i][0];
        int nextY=x+move[i][1];
        if(nextX>=0 && nextX<boardSize && nextY>=0 && nextY<boardSize
           && chessboard[nextX][nextY]==0){
            count++;
        }
    }
    return count;
}

Based on the method, we rewrite the DFS code as below.

Direction[] directions = new Direction[8];//stores (index of move[]) and (number of available directions)
for (int i = 0; i < 8; i++) {
    int nextX=x+move[i][0];
    int nextY=y+move[i][1];
    int directionNum = possibleDirections(nextX, nextY);
    directions[i]=new Direction(i,directionNum);
}
Arrays.sort(directions);//we should first choose the most difficult point to arrive, so we sort the directions
for (int i = 0; i < 8; i++) {
    int index=directions[i].index;//the index of move[]
    dfs(x+move[index][0],y+move[index][1],step+1);
    backCount++;
}
public static class Direction implements Comparable<Direction>{
    int index;//index of move[]
    int directionNum;//the number of available directions

    public Direction(int index, int directionNum) {
        this.index = index;
        this.directionNum = directionNum;
    }

    @Override
    public int compareTo(Direction o) {
        return Integer.compare(directionNum,o.directionNum);
    }
}

Next we input the same condition as before to see the optimize result.

Chessboard size:6
Starting point (x,y):0 2
Backtracking times: 6561489
Time cost: 0.60s
Result:
[12, 31, 36, 27, 14, 29]
[35, 24, 13, 30, 1, 26]
[32, 11, 34, 25, 28, 15]
[23, 6, 9, 16, 19, 2]
[10, 33, 4, 21, 8, 17]
[5, 22, 7, 18, 3, 20]

The backtracking time decreases from $10^9$ to $10^6$. The time cost decreases from 11.26s to 0.60s.

Because of the greedy strategy, the knight tends to travel along the edge of the chessboard. Because the points on the edge have fewer directions to access.[2]

4. Other method

We can also use divide and conquer to solve the problem. We can divide the chessboard into several small blocks. As long as each small block satisfies the feature of “starting from any point and passing through all other points without repetition”, connecting the paths of each small block can form a ring that passes through all the grids.[2]

For example, we can divide a 9x10 chessboard to two 5x6 block and one 3x10 block as below

Reference

[1] Baidu Encyclopedia

[2] https://mp.weixin.qq.com/s?__biz=Mzk0NTE5MTcxNQ==&mid=2247483784&idx=1&sn=6a8d731b722c6f45f33b74d50bf6f49a&chksm=c3186fc4f46fe6d28d979799a25818867ae010e1bf7e373be7f9364e9e10376e2968b3a5d7d1&mpshare=1&scene=23&srcid=11308xJtmz42NEvcRHC1GAaf&sharer_sharetime=1642256728980&sharer_shareid=b4733ad88e1c5ed4cafc799dc34a455f#rd