C++解决经典的马踏棋盘问题：回溯算法实现

马踏棋盘问题是一个经典的数学问题，目标是找到一个序列，使马在棋盘上移动，每个格子恰好访问一次。这篇文章将分析一个使用C++和回溯算法解决马踏棋盘问题的代码示例。

代码分析

#include <stdio.h>
#include <stdbool.h>
#include <windows.h>
#include <iostream>
#pragma comment(lib,"winmm.lib")
using namespace std;

#define SIZE 8

int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1};
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2};

bool isSafe(int x, int y, int sol[SIZE][SIZE]) {
    return (x >= 0 && x < SIZE && y >= 0 && y < SIZE && sol[x][y] == -1);
}

void printSolution(int sol[SIZE][SIZE]) {
    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            printf("%2d ", sol[i][j]);
        }
        printf("\n");
    }
}

bool solveKTUtil(int x, int y, int movei, int sol[SIZE][SIZE]) {
    if (movei == SIZE * SIZE) {
        printSolution(sol);
        printf("\n");
        return true;
    }

    for (int k = 0; k < 8; k++) {
        int nextX = x + dx[k];
        int nextY = y + dy[k];
        if (isSafe(nextX, nextY, sol)) {
            sol[nextX][nextY] = movei;
            if (solveKTUtil(nextX, nextY, movei + 1, sol))
                return true;
            else
                sol[nextX][nextY] = -1;
        }
    }

    return false;
}

void solveKT() {
    int sol[SIZE][SIZE];

    for (int i = 0; i < SIZE; i++) {
        for (int j = 0; j < SIZE; j++) {
            sol[i][j] = -1;
        }
    }

    int startX, startY;
    printf("请输入初始坐标 (0-7): ");
    scanf("%d %d", &startX, &startY);

    if (startX < 0 || startX >= SIZE || startY < 0 || startY >= SIZE) {
        printf("Invalid starting position!\n");
        return;
    }

    sol[startX][startY] = 0;

    if (!solveKTUtil(startX, startY, 1, sol)) {
        printf("No solution found!\n");
    }
}

void menu()
{
    cout<<"\t\t\t马踏棋盘问题的解决："<<endl;
    cout<<"\t\t\t1.开始"<<endl;
    cout<<"\t\t\t2.退出"<<endl;
    cout<<"\t\t\t请输入选择：";
    int sel;
    cin>>sel;
    if (sel == 2)
        exit(0);
    while(sel >2 ||sel <1)
    {
        cout <<"\t\t\t输入格式错误，请重新输入：";
        cin>>sel;
    }
    int m,n;
    int found = 0;
    int edge;
    if (sel == 1)
    {
    system("cls");
    solveKT();
    }
}
 
int main() {
    system("color E5");
    menu();
    system("pause");
    return 0;
}

代码解释

数据结构: 使用一个二维数组 sol[SIZE][SIZE] 表示棋盘，其中 SIZE 为棋盘的大小 (8)。
马的移动: dx 和 dy 数组存储马的八个方向的移动偏移量。
安全性检查: isSafe 函数检查马的下一个位置是否在棋盘范围内，并且该位置之前未被访问过。
打印解决方案: printSolution 函数打印最终的棋盘，显示马访问每个格子的顺序。
回溯算法: solveKTUtil 函数是解决问题的核心，它使用递归和回溯算法来探索所有可能的路径。
- 如果找到解决方案 (访问了所有格子), 函数返回 true。
- 否则，尝试所有可能的移动方向。
- 如果一个移动方向有效, 标记该位置并递归调用 solveKTUtil。
- 如果递归调用返回 true, 则找到解决方案。
- 否则，回溯：将该位置标记为未访问并尝试其他方向。
主函数: solveKT 函数初始化棋盘，获取用户输入的初始位置，并调用 solveKTUtil 函数解决问题。
菜单: menu 函数提供一个简单的用户界面，让用户选择开始解决问题或退出程序。

总结

这段代码展示了如何使用 C++ 和回溯算法解决经典的马踏棋盘问题。回溯算法是一种强大的技术，可以用来解决许多类似的问题，其中需要探索所有可能的解决方案。