马踏棋盘的实现

马踏棋盘是经典的程序设计问题之一，主要的解决方案有两种：一种是基于深度优先搜索的方法，另一种是基于贪婪算法的方法。第一种基于深度优先搜索的方法是比较常用的算法，深度优先搜索算法也是数据结构中的经典算法之一，主要是采用递归的思想，一级一级的寻找，最后找到合适的解。而基于贪婪的算法则是依据贪婪算法的思想设置一种标准，然后依据标准进行选择，从而得到解，但是他不一定能够得到最优解。

 

关于马踏棋盘的基本过程：国际象棋的棋盘为8*8的方格棋盘。现将"马"放在任意指定的方格中，按照"马"走棋的规则将"马"进行移动。要求每个方格只能进入一次，最终使得"马"走遍棋盘的64个方格。

 

深度优先搜索属于图算法的一种，英文缩写为DFS即Depth First Search.其过程简要来说是对每一个可能的分支路径深入到不能再深入为止，而且每个节点只能访问一次. （来自百度）

贪心算法（又称贪婪算法）是指，在对问题求解时，总是做出在当前看来是最好的选择。也就是说，不从整体最优上加以考虑，他所做出的仅是在某种意义上的局部最优解。贪心算法不是对所有问题都能得到整体最优解，但对范围相当广泛的许多问题他能产生整体最优解或者是整体最优解的近似解。（来自百度）

其中基于深度优先搜索的算法就是依据当前点找到下一个可能的点，然后对这个点进行深度优先搜索，然后依次递归，当出现条件不满足时，退回来，采用其他的路劲进行搜索，最后肯定能够得到对应的结果。实现的基本过程如下：

/*deepsearch to solve the horse chess problem*/
#include<stdio.h>
#include<stdlib.h>
#include<time.h>
#define ROWS    8
#define COLS    8

int chess[ROWS][COLS];

/*eight directions of x moved*/
const int x_move[] = {-2,-1,1,2,2,1,-1,-2};
/*eight directions of y moved*/
const int y_move[] = {1,2,2,1,-1,-2,-2,-1};

void print_matrix()
{
    int i = 0,j = 0;
    for (i = 0; i < ROWS; ++ i)
    {
        for (j = 0; j < COLS; ++ j)
        {
            printf("%d\t",chess[i][j]);
        }
        printf("\n\n\n");
    }
}

/*find the next point*/
int nextxy(int *x,int *y,int count)
{
    if(count > 7 && count < 0)
        return -1;
    switch(count)
    {
    case 0:
        /*check the conditions*/
        if(*x + x_move[0] < ROWS &&
         *x + x_move[0]>= 0 &&
         *y + y_move[0]< COLS &&
         *y + y_move[0]>= 0 &&
         chess[*x + x_move[0]][*y + y_move[0]] == 0)
        {
            *x += x_move[0];
            *y += y_move[0];
            break;
        }
        else/*failed*/
            return 0;
    case 1:
        if(*x + x_move[1] < ROWS &&
            *x + x_move[1]>= 0 &&
            *y + y_move[1]< COLS &&
            *y + y_move[1]>= 0 &&
         chess[*x + x_move[1]][*y + y_move[1]] == 0)
        {
            *x += x_move[1];
            *y += y_move[1];
            break;
        }
        else
            return 0;
    case 2:
        if(*x + x_move[2] < ROWS &&
            *x + x_move[2]>= 0 &&
            *y + y_move[2]< COLS &&
            *y + y_move[2]>= 0 &&
         chess[*x + x_move[2]][*y + y_move[2]] == 0)
        {
            *x += x_move[2];
            *y += y_move[2];
            break;
        }
        else
            return 0;
    case 3:
        if(*x + x_move[3] < ROWS &&
            *x + x_move[3]>= 0 &&
            *y + y_move[3]< COLS &&
            *y + y_move[3]>= 0 &&
         chess[*x + x_move[3]][*y + y_move[3]] == 0)
        {
            *x += x_move[3];
            *y += y_move[3];
            break;
        }
        else
            return 0;
    case 4:
        if(*x + x_move[4] < ROWS &&
            *x + x_move[4]>= 0 &&
            *y + y_move[4]< COLS &&
            *y + y_move[4]>= 0 &&
         chess[*x + x_move[4]][*y + y_move[4]] == 0)
        {
            *x += x_move[4];
            *y += y_move[4];
            break;
        }
        else
            return 0;
    case 5:
        if(*x + x_move[5] < ROWS &&
            *x + x_move[5]>= 0 &&
            *y + y_move[5]< COLS &&
            *y + y_move[5]>= 0 &&
         chess[*x + x_move[5]][*y + y_move[5]] == 0)
        {
            *x += x_move[5];
            *y += y_move[5];
            break;
        }
        else
            return 0;
    case 6:
        if(*x + x_move[6] < ROWS &&
            *x + x_move[6]>= 0 &&
            *y + y_move[6]< COLS &&
            *y + y_move[6]>= 0 &&
            chess[*x + x_move[6]][*y + y_move[6]] == 0)
        {
            *x += x_move[6];
            *y += y_move[6];
            break;
        }
        else
            return 0;
    case 7:
        if(*x + x_move[7] < ROWS &&
            *x + x_move[7]>= 0 &&
            *y + y_move[7]< COLS &&
            *y + y_move[7]>= 0 &&
         chess[*x + x_move[7]][*y + y_move[7]] == 0)
        {
            *x += x_move[7];
            *y += y_move[7];
            break;
        }
        else
            return 0;
    default:
        return 0;
    }
    return 1;
}
int deepsearch(int x,int y, int j)
{
    /*save the value x,y*/
    int x1 = x, y1 = y;
    int tag = 0, i = 0;
    /*save j on chess[x][y]*/
    chess[x][y] = j;

    /*recursion exit condition*/
    if(j == COLS*ROWS)
    {
        return 1;
    }
    /*find the next point in eight directions*/
    tag = nextxy(&x1,&y1,i);
    /*find the nextx,nexty */
    while (tag == 0 && i < 7)
    {
        i ++;
        tag = nextxy(&x1,&y1, i);
    }

    /*the nextxy be found*/
    while(tag)
    {
        if(deepsearch(x1,y1,j+1))
            return 1;

     /*if failed, a new finding process */
        x1 = x; y1 = y;
        i ++;
        tag = nextxy(&x1,&y1,i);
        while (tag == 0 && i < 7)
        {
            i ++;
            tag = nextxy(&x1,&y1,i);
        }
    }
    /*no direction can find next point*/
    if(tag == 0)
        chess[x][y] = 0;
    return 0;
}

void main()
{
    clock_t start = clock();
    deepsearch(2,0,1);
    print_matrix();
    int seconds = (clock()-start)/CLOCKS_PER_SEC;

    printf("\n%d\n",seconds);
    return;
}

采用贪婪算法的实现，首先应该设置一定的判断准则，然后根据设定的准则进行选择，在马踏棋盘中设定的准备是选择出路最少（至少为1）的一个方向为准则，能够实现马踏棋盘问题的解决。当然该问题为什么要选择出路最少，我暂时还不是很清楚。基本的实现如下：

#include <stdio.h>
#include <stdlib.h>
#include <math.h>

#define ROWS    8
#define COLS    8

/*axis i move matrix*/
const int iktmove[8] = {-2,-1,1,2,2,1,-1,-2};
/*axis j move matrix*/
const int jktmove[8] = {1,2,2,1,-1,-2,-2,-1};

int board[ROWS][COLS];

/*inital the matrix*/
void matrix_init(int matrix[][COLS],int rows,int cols)
{
    int i, j;
    for(i = 0; i < rows ; ++ i)
        for (j = 0; j < cols ; ++ j)
        {
            matrix[i][j] = 0;
        }
}
/*print the matrix*/
void print_matrix(int matrix[][COLS],int rows,int cols)
{
    int i,j;
    for(i = 0; i < rows; ++ i)
    {
        for(j = 0; j < cols; ++ j)
            printf("%d\t",matrix[i][j]);
        printf("\n\n\n");
    }
}
/*find the index of min non-zeros positive*/
int minindex_in_matrix(int a[],int cols)
{
    int i = 0,index = 0;
    int min = a[0];
    for(i = 0 ; i< cols; ++ i)
    {
        if(a[i] >0)
        {
            min = a[i];
            index = i;
            break;
        }
    }
    for(i = index + 1; i < cols ; ++ i)
    {
        if(a[i] > 0 && min > a[i])
        {
            min = a[i];
            index = i;
        }
    }
    if(a[index] > 0)
        return index;
    return -1;
}
int maxindex_in_matrix(int a[],int cols)
{
    int i = 0,index;
    int max ;
    for(i = 0 ; i< cols; ++ i)
    {
        if(a[i] >0)
        {
            max = a[i];
            index = i;
            break;
        }
    }
    for(i = index + 1; i < cols ; ++ i)
    {
        if(a[i] > 0 && max < a[i])
        {
            max = a[i];
            index = i;
        }
    }
    if(a[index] > 0)
        return index;
    return -1;
}

/**/
void warnsdorff_role(int matrix[][COLS],int rows,int cols,int start_i,int start_j)
{
    int i,npos,m,min,j,nnpos;

    int nexti[8] = {0,0,0,0,0,0,0,0};
    int nextj[8] = {0,0,0,0,0,0,0,0};
    int exit[8] = {0,0,0,0,0,0,0,0};

    /*steps a*/
    matrix_init(matrix,rows,cols);
    /*steps b*/
    matrix[start_i][start_j] = 1;
    /*steps c*/
    for(m = 1; m < 64; ++ m)
    {
        /*steps d*/
        npos = 0;
        for(i = 0; i < 8; ++ i)
        {
            /*ignore the point which doesn't satisfy the conditions*/
            if( start_i + iktmove[i] < 0 ||
                start_i + iktmove[i] >= rows ||
                start_j + jktmove[i] < 0 ||
                start_j + jktmove[i] >= cols ||
                matrix[start_i + iktmove[i]][start_j+jktmove[i]] > 0)
            {
                continue;
            }
            /*save the point which satisfy the conditions*/
            nexti[npos] = start_i + iktmove[i];
            nextj[npos] = start_j + jktmove[i];
            /*statistics how many point satisfy conditions*/
            npos ++;
        }
        /*steps e*/
        if(npos == 0)
        {
            printf("Can not finish the game!!\n,The steps of game can be %d\n",m);
            goto print;
        }
        /*steps e*/
        if(npos == 1)
        {
            min = 0;
            goto set_nextpoint;
        }
        /*steps f*/
        if(npos > 1)
        {
            /*calculate the possible way of the next next step */
            for(i = 0; i < npos ; ++ i)
            {
                nnpos = 0;
                for(j = 0; j < 8; ++ j)
                {
                    /*statistics the point which satisfy conditions*/
                    if( nexti[i] + iktmove[j] >= 0 &&
                        nexti[i] + iktmove[j] < rows &&
                        nextj[i] + jktmove[j] >= 0 &&
                        nextj[i] + jktmove[j] < cols &&
                        matrix[nexti[i] + iktmove[j]][nextj[i] + jktmove[j]] == 0)
                    {
                        nnpos ++;
                    }
                }
                /*save the numbers of points for next step*/
                exit[i] = nnpos;
            }
            /*find the proper point*/
            if((min = minindex_in_matrix(exit,npos)) >= 0)
            {
                goto set_nextpoint;
            }
            else /*failed*/
            {
                printf("Can not finish the game!!\n,The steps of game can be %d\n",m);
                goto print;
            }
        }
set_nextpoint:
        /*step g*/
        /*set the next start point of game*/
        start_i = nexti[min];
        start_j = nextj[min];
        matrix[start_i][start_j] = m+1;
    }
print:
    /*step h*/
    print_matrix(matrix,rows,cols);
}

void main()
{
    warnsdorff_role(board,ROWS,COLS,5,1);
}

实现结果：当采用深度优先搜索算法的过程中发现当棋盘为8X8时，计算速度非常的慢，而当棋盘为5X5以后，计算速度非常的快速。说明算法存在一定的缺陷。而采用贪婪算法实现的速度非常的快，棋盘的大小对算法性能影响较小。

将矩阵改为5X5得到如下的结果：从结果中可以看见两种算法得到的结果存在一定的差异，但是都能解决马踏棋盘问题。

1、深度优先搜索算法：

2、贪婪算法：