汉密尔顿跳马问题c++代码

由于汉密尔顿跳马问题是一个NP问题，因此没有多项式时间算法可以解决它。以下是一种暴力穷举的算法，对于小规模问题可以得到正确的解，但对于大规模问题则会超时。

#include <iostream>
#include <cstring>
using namespace std;

const int n = 8; // 棋盘大小
int board[n][n]; // 棋盘
int dx[8] = {1, 2, 2, 1, -1, -2, -2, -1}; // x方向移动数组
int dy[8] = {2, 1, -1, -2, -2, -1, 1, 2}; // y方向移动数组

void printBoard() // 打印棋盘
{
    for(int i=0; i<n; i++)
    {
        for(int j=0; j<n; j++)
        {
            cout << board[i][j] << " ";
        }
        cout << endl;
    }
}

bool solve(int x, int y, int count) // 递归求解
{
    if(count == n*n) // 如果已经遍历完所有格子，则返回true
    {
        return true;
    }
    for(int i=0; i<8; i++) // 遍历8个方向
    {
        int nx = x + dx[i]; // 计算下一个格子的位置
        int ny = y + dy[i];
        if(nx>=0 && nx<n && ny>=0 && ny<n && board[nx][ny]==0) // 如果下一个格子在棋盘内且未被遍历过
        {
            board[nx][ny] = count+1; // 标记已遍历过
            if(solve(nx, ny, count+1)) // 递归求解
            {
                return true;
            }
            board[nx][ny] = 0; // 如果递归求解失败，则回溯
        }
    }
    return false;
}

int main()
{
    memset(board, 0, sizeof(board)); // 初始化棋盘
    board[0][0] = 1; // 起点
    if(solve(0, 0, 1)) // 从起点开始递归求解
    {
        cout << "Solution found:" << endl;
        printBoard(); // 打印解
    }
    else
    {
        cout << "Solution not found." << endl;
    }
    return 0;
}