使用深度优先搜素（DFS）实现马踏棋盘

感觉想学会DFS说到底最重要的也就是弄懂递归怎么用 #include<stdio.h> #define X 8 #define Y 8 int chess[X][Y] = { 0 };//棋盘 bool nextxy(int* x, int* y, int count) {//x，y使用指针类型是为了直接修改 switch (count) { case 0: if (*x + 2 <= X - 1 && *y - 1 >= 0 && chess[*x + 2][*y - 1] == 0) { *x += 2; *y -= 1; return true; } break; case 1: if (*x + 2 <= X - 1 && *y + 1 <= Y - 1 && chess[*x + 2][*y + 1] == 0) { *x += 2; *y += 1; return true; } break; case 2: if (*x + 1 <= X - 1 && *y - 2 >= 0 && chess[*x + 1][*y - 2] == 0) { *x += 1; *y -= 2; return true; } break; case 3: if (*x + 1 <= X - 1 && *y + 2 <= Y - 1 && chess[*x + 1][*y + 2] == 0) { *x += 1; *y += 2; return true; } break; case 4: if (*x - 2 >= 0 && *y - 1 >= 0 && chess[*x - 2][*y - 1] == 0) { *x -= 2; *y -= 1; return true; } break; case 5: if (*x - 2 >= 0 && *y + 1 <= Y - 1 && chess[*x - 2][*y + 1] == 0) { *x -= 2; *y += 1; return true; } break; case 6: if (*x - 1 >= 0 && *y + 2 <= Y - 1 && chess[*x - 1][*y + 2] == 0) { *x -= 1; *y += 2; return true; } break; case 7: if (*x - 1 >= 0 && *y - 2 >= 0 && chess[*x - 1][*y - 2] == 0) { *x -= 1; *y -= 2; return true; } break; default: break; } return false; }//检查周围是否可以落棋 void print() { for (int i = 0; i < X; i++) { for (int j = 0; j < Y; j++) { printf("%d\t", chess[i][j]); } printf("\n"); } }//输出棋盘 bool ChessBoard(int x, int y, int tag) { int x1 = x, y1 = y, count = 0; bool flag = false; chess[x][y] = tag; if (X * Y == tag) { print(); return true; } while (!flag && count < 8) { flag = nextxy(&x1, &y1, count); count++; } while (flag) { if (ChessBoard(x1, y1, tag + 1)) { return true; } x1 = x; y1 = y; count++; do { flag = nextxy(&x1, &y1, count); count++; } while (!flag && count < 8); } chess[x][y] = 0; return false; }//使用递归实现DFS int main() { if (!ChessBoard(2, 0, 1)) { printf("error!"); } return 0; }

输出结果：