|
您的代码片段不完整且存在语法错误。我帮您重写了一个完整的马踏棋盘解决方案,主要问题在于回溯逻辑和边界检查:
- #include <stdio.h>
- #define N 8
- // 马跳的8个方向 (顺时针)
- const int dx[8] = { 1, 2, 2, 1,-1,-2,-2,-1};
- const int dy[8] = { 2, 1,-1,-2,-2,-1, 1, 2};
- int board[N][N] = {0}; // 棋盘
- // 检查位置是否有效
- int isValid(int x, int y) {
- return (x >= 0 && x < N && y >= 0 && y < N && board[x][y] == 0);
- }
- // 打印棋盘
- void printBoard() {
- for (int i = 0; i < N; i++) {
- for (int j = 0; j < N; j++)
- printf("%2d ", board[i][j]);
- printf("\n");
- }
- }
- // 回溯法求解
- int solve(int x, int y, int moveCount) {
- // 记录当前位置步数
- board[x][y] = moveCount;
-
- // 完成所有移动
- if (moveCount >= N*N) {
- printBoard();
- return 1;
- }
-
- // 尝试所有8个方向
- for (int i = 0; i < 8; i++) {
- int nextX = x + dx[i];
- int nextY = y + dy[i];
-
- if (isValid(nextX, nextY)) {
- if (solve(nextX, nextY, moveCount+1))
- return 1;
- }
- }
-
- // 回溯:撤销当前步
- board[x][y] = 0;
- return 0;
- }
- int main() {
- // 从(0,0)开始
- if (!solve(0, 0, 1))
- printf("No solution found!\n");
- return 0;
- }
复制代码
关键改进点:
1. 使用单独的方向数组 dx 和 dy 代替二维方向数组
2. 添加完整的回溯撤销逻辑 board[x][y] = 0
3. 边界检查函数 isValid() 包含未访问检查
4. 递归终止条件改为 moveCount >= N*N
使用说明:
1. 程序从棋盘左上角(0,0)开始
2. 找到解会打印完整棋盘路径
3. 数字表示马移动的顺序
4. 未找到解会提示"No solution"
注意:8x8棋盘存在可行解,但计算时间较长(约几秒)。若需要优化,可加入Warnsdorff启发式规则减少回溯次数。
以上回复来自 FishC AI 小助理,如未能正确解答您的问题,请继续追问。 |
|