基于C语言用递归算法实现马踏棋盘解法的计算

基于C语言用递归算法实现马踏棋盘解法的计算
如有不懂欢迎提问

#include<stdio.h>

#define X 7//棋盘x
#define Y 7//棋盘y
#define A 1//起始横坐标
#define B 1//起始纵坐标

void house (int , int);//递归求解，依次传入横纵坐标
void printboard();//打印具体解法
void initialization();//棋盘初始化

int board[X + 4][Y + 4];//其中下标2至X+1或Y+1为棋盘
int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标

int main() {
    if (X <= 2 || Y <= 2 || X * Y > 10000) {
        //经测试，个人计算机计算10*10已经有些吃力
        printf("棋盘不合法!");
        return 0;
    }
    if (A > X || B > Y || A <= 0 || B <= 0) {
        printf("初始坐标不合法!");
        return 0;
    }
    printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
    initialization();
    board[A + 1][B + 1] = ++step;
    house(A, B);
    printf("\n\n计算完毕!\n");
    printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", X, Y, A, B);
    printf("共找到%d组解\n",sum);
    return 0;
}

void initialization() {
    int i, j;
    //给棋盘赋值0，周围赋值-1即不可走
    for (i = 0; i <= X + 3; i++) {
        for (j = 0; j <= Y + 3; j++) {
            if (i == 0 || i == 1 || i == X + 3 || i == X + 2 || j == 0 || j == 1 || j == Y + 3 || j == Y + 2)
                board[i][j] = -1;
            else
                board[i][j] = 0;
        }
    }
    return;
}

void house(int a , int b) {
    if (step == X*Y) {
        sum++;
        printboard();
        return;
    }
    for (int i = 0; i <= 7; i++) {
        if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
            step++;
            board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
            house(a+move[i][0], b+move[i][1]);
            board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
            step--;
        }
    }
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard() {
    int i, j, k;
    printf("\n第%d种解法：\n",sum);
    printf("┌───");
    for (i = 1; i <= Y- 1; i++) 
        printf("┬───");
    printf("┐\n");
    for ( i = 2; i <= X + 1; i++) {
        for ( j = 2; j <= Y + 1; j++) 
            printf("│%3.2d", board[i][j]);
        printf("│\n");
        if (i <= X) {
            printf("├───");
            for(k=1;k<=Y-1;k++)
                printf("┼───");
            printf("┤\n");
        }
    }
    printf("└───");
    for (i = 1; i <= Y - 1; i++)
        printf("┴───");
    printf("┘\n");
    return;
}

上文为了方便使用define来确定棋盘尺寸X、Y。如果想用scanf来确定，需要用到动态数组，并且需要向函数传递地址

#include<stdio.h>
#include<stdlib.h>//包含malloc

void house(int, int, int**);//递归求解，依次传入横纵坐标ab，二维数组指针
void printboard(int**);//传入二维数组指针，打印具体解法
void initialization(int**);//棋盘初始化，依次传入二维数组指针

int sum = 0;//解法总数
int step = 0;//已走步数
int move[8][2] = { { 1,2 },{ 2,1 },{ 1,-2 },{ 2,-1 },{ -1,2 },{ -2,1 },{ -1,-2 },{ -2,-1 } };//八种走法，依次为x坐标，y坐标
int x, y;//定义全局变量

int main() {
    printf("马踏棋盘v2.0\n");
    printf("请输入棋盘大小x*y：\n");
    printf("x=");
    scanf("%d", &x);
    printf("y=");
    scanf("%d", &y);
    int a, b;//无需全局变量
    printf("请输入起始位置(a, b)，其中最小为(1, 1)：\n");
    printf("a=");
    scanf("%d", &a);
    printf("b=");
    scanf("%d", &b);
    int **board;
    board = (int**)malloc(sizeof(int *) * (x + 4));
    for (int i = 0; i < x + 4; i++) {
        board[i] = (int*)malloc(sizeof(int *) * (y + 4));
    }
    //相当于声明了动态数组board[x + 4][y + 4];其中下标2至X+1或Y+1为棋盘
    if (x <= 2 || x <= 2 || x * y > 10000) {
        //经测试，由于递归算法，计算10*10已经极为吃力
        printf("棋盘不合法!");
        return 0;
    }
    if (a > x || a > y || a <= 0 || a <= 0) {
        printf("初始坐标不合法!");
        return 0;
    }
    printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
    initialization(board);
    board[a + 1][a + 1] = ++step;
    house(a, b, board);
    printf("\n\n计算完毕!\n");
    printf("当前为%d*%d棋盘，起始坐标(%d,%d)\n", x, y, a, b);
    printf("共找到%d组解\n", sum);
    return 0;
}

void initialization(int** board) {
    int i, j;
    //给棋盘赋值0，周围赋值-1即不可走
    for (i = 0; i <= x + 3; i++) {
        for (j = 0; j <= y + 3; j++) {
            if (i == 0 || i == 1 || i == x + 3 || i == x + 2 || j == 0 || j == 1 || j == y + 3 || j == y + 2)
                board[i][j] = -1;
            else
                board[i][j] = 0;
        }
    }
    return;
}

void house(int a, int b, int** board) {
    if (step == x*y) {
        sum++;
        printboard(board);
        return;
    }
    for (int i = 0; i <= 7; i++) {
        if (board[a + 1 + move[i][0]][b + 1 + move[i][1]] == 0) {
            step++;
            board[a + 1 + move[i][0]][b + 1 + move[i][1]] = step;
            house(a + move[i][0], b + move[i][1], board);
            board[a + 1 + move[i][0]][b + 1 + move[i][1]] = 0;
            step--;
        }
    }
}

//制表符： ┌ ┬ ┐ ├ ┼ ┤ └ ┴ ┘ ─ │
void printboard(int **board) {
    int i, j, k;
    printf("\n第%d种解法：\n", sum);
    printf("┌───");
    for (i = 1; i <= y - 1; i++)
        printf("┬───");
    printf("┐\n");
    for (i = 2; i <= x + 1; i++) {
        for (j = 2; j <= y + 1; j++)
            printf("│%3.2d", board[i][j]);
        printf("│\n");
        if (i <= x) {
            printf("├───");
            for (k = 1; k <= y - 1; k++)
                printf("┼───");
            printf("┤\n");
        }
    }
    printf("└───");
    for (i = 1; i <= y - 1; i++)
        printf("┴───");
    printf("┘\n");
    return;
}