马踏棋盘C++实现与贪婪算法优化

马踏棋盘C++实现与贪婪算法优化

完整CLion下工程,见GitHub

问题描述

马踏棋盘问题即在一个8*8的棋盘上,指定一个起点,找到一个路径,让棋子按照马走日的规则将所有格子无重复的遍历一次。
这个问题是在学习数据结构与算法的时候看到的,当时看的是C语言的版本,也没记住具体的解法,事后回顾起来觉得很有意思,于是自己用C++编写了一段代码尝试一下。

分析

  • 首先进行分析:从数据结构的角度来分析,一个棋盘可以看作一个二维数组。然后是对每次落子进行分析,根据马走日的规则,假设不考虑是否会出现越界情况,则在某位置X上,下一步落子共有八种可能性,如图所示,按照顺时针顺序依次标记为0,1,2,3,4,5,6,7:

    那么显然易见,已知X的情况下,利用深度优先遍历的方式,是一定可以得到一个路径满足要求的,只不过这么做的计算复杂度非常之高。有了想法,当然是以能跑出结果为导向先写出大概的代码才行,于是我按照这个思路写出了原始版本:

实现与优化

/*
 * 马踏棋盘最原始的深度优先算法
 * 利用栈
 */
#include <iostream>
#include <chrono>
#include <stack>
#include <assert.h>
#include <cstring>
using namespace std;
const int chessX = 8;
const int chessY = 8;
static bool chess[chessX][chessY];//棋盘,遍历过的位置进行标记
struct Id{
    int x;
    int y;
    Id(int theX,int theY):x(theX),y(theY) {};
    ~Id() = default;
};
stack<Id> step;//栈,依次存放每次遍历的坐标,回溯的时候出栈
bool run(int,int);
int judge(int,int,int &);//判断路径,返回0-7表示选择的路径,返回则需要回溯
bool isInChess(int,int,int);//判断某个方向的落子是否在棋盘内
bool isNeverRun(int,int,int);//判断落子是否被遍历过
Id next(int,int,int);//返回cnt方向的落子位置
int main()
{
    memset(chess,0x00,sizeof(chess));
    auto start = chrono::system_clock::now();
    run(0,7);
    auto end = chrono::system_clock::now();
    auto duration = chrono::duration_cast<chrono::microseconds>(end-start);
    /*
    for(int i=0;i<chessX;++i)
    {
        for(int j = 0;j<chessY;++j)
            cout << chess[i][j];
        cout << endl;
    }*/
    if(step.size()==0)
    {
        cout << "can not complete!" << endl;
        return 0;
    }
    int res[chessX][chessY] = {0};
    for(int i=0;i<chessX*chessY;++i)
    {
        res[step.top().x][step.top().y] = chessX*chessY-i;
        step.pop();
    }
    for(int i=0;i<chessX;++i)
    {
        for(int j = 0;j<chessY;++j)
            cout << res[i][j] << '\t';
        cout << endl;
    }

    cout << double(duration.count())* chrono::microseconds::period::num/
         chrono::microseconds::period::den
         << "秒" << endl;
    return 0;
}

bool run(int x,int y)
{
    int cnt = 0;
    bool finish;
    step.push(Id(x,y));
    chess[x][y] = true;
    if(step.size()>=chessX*chessY)
        return true;
    while(judge(x,y,cnt)<8)
    {
        Id nextId = next(x,y,cnt);
        finish = run(nextId.x,nextId.y);
        if(finish)
            return true;
        else
            ++cnt;
    }
    //finish==false
    step.pop();
    chess[x][y] = false;
    return false;
}

int judge(int x,int y,int &cnt)
{
    while(cnt<8)
    {
        if(isInChess(x,y,cnt)&&isNeverRun(x,y,cnt))
            return cnt;
        else
            ++cnt;
    }
    return cnt;
}

bool isInChess(int x,int y,int cnt)
{
    assert(cnt<8&&x>=0&&x<chessX&&y>=0&&y<chessY);
    switch(cnt)
    {
        case 0:
            return (x+1<chessX)&&(y+2<chessY);
        case 1:
            return (x+2<chessX)&&(y+1<chessY);
        case 2:
            return (x+2<chessX)&&(y-1>=0);
        case 3:
            return (x+1<chessX)&&(y-2>=0);
        case 4:
            return (x-1>=0)&&(y-2>=0);
        case 5:
            return (x-2>=0)&&(y-1>=0);
        case 6:
            return (x-2>=0)&&(y+1<chessY);
        case 7:
            return (x-1>=0)&&(y+2<chessY);
        default:
            cerr << "error:isInChess" << endl;
            return 0;
    }
}

bool isNeverRun(int x, int y, int cnt)
{
    switch (cnt)
    {
        case 0:
            return !chess[x+1][y+2];
        case 1:
            return !chess[x+2][y+1];
        case 2:
            return !chess[x+2][y-1];
        case 3:
            return !chess[x+1][y-2];
        case 4:
            return !chess[x-1][y-2];
        case 5:
            return !chess[x-2][y-1];
        case 6:
            return !chess[x-2][y+1];
        case 7:
            return !chess[x-1][y+2];
        default:
            return false;
    }
}

Id next(int x, int y, int cnt)
{
    switch (cnt)
    {
        case 0:
            return Id(x+1,y+2);
        case 1:
            return Id(x+2,y+1);
        case 2:
            return Id(x+2,y-1);
        case 3:
            return Id(x+1,y-2);
        case 4:
            return Id(x-1,y-2);
        case 5:
            return Id(x-2,y-1);
        case 6:
            return Id(x-2,y+1);
        case 7:
            return Id(x-1,y+2);
        default:
            cerr << "next func error";
            return Id(x,y);
    }
}
  • 这么一个代码的框架就算是搭起来了,那么运行结果呢,在运算8*8的棋盘时,部分点算不出来,就是 那种算几个小时都出不来的情况,有的点可以在几秒内算出来,如下:
  • 当然这种效率是很捉急的,于是查阅了相关的优化方式,发现可以使用贪婪算法对其进行优化,加快其运行速度,另一方面,这个原始版本还有其他不足,本就想做些小修改,于是我就立刻写下了另一个优化版本。
  • 先简单介绍下贪婪算法,贪婪算法就是每一步都选取局部的最优解,从而最终使得最终解逼近完美解。在本问题下,贪婪算法的执行效果就是,检测下一步可能落子的下一步可落子位置数,数量越少的,优先级越高。比如现在棋子在A点,A点下一步可以落在BCD三个点上,并且B的下一步可能有2个位置,C和D可能有3个位置,那么B的优先级就比C和D要高,我们优先选择B。
    代码修改如下:
/**
 * 马踏棋盘优化:
 * 1.DFS,对原有的结构进行改进
 * 2.选择下一步的方式采取贪婪算法,即考察每一个备选落子下一步的可落子位置数,
 * 位置数少的优先落子。
 */
#include <iostream>
#include <chrono>
#include <map>
#include <assert.h>
#include <vector>

using namespace std;

const int chessX = 8;
const int chessY = 8;
int chess[chessX][chessY] = {0};
int cnt = 0;//表示深度,表示走的步数
int fx[8] = {1,2,2,1,-1,-2,-2,-1};
int fy[8] = {2,1,-1,-2,-2,-1,1,2};
typedef int Direct;//定义新的数据类型,方便表示,0-8表示8个落子方向
typedef multimap<int,Direct> nextMap;//存放每个位置下一个落子优先级的数据
typedef nextMap::iterator nIter;//定义迭代器类型
bool run(int,int);//递归主函数
nextMap judge(int,int,int&,int&);//返回下一个落子位置的优先级,并且在keyvmin里存放key值的非0最小值
bool isOk(int,int,Direct);//判断坐标是否可用:1.没遍历过2.没有超出棋盘
int main()
{
    int x,y;
    vector<int> iveco;

    cout << "请输入初始坐标x:" << "(x>=0&&x<" << chessX << ")" << endl;
    cin >> x;
    assert(x>=0&&x<chessX);
    cout << "请输入初始坐标y: " << "(y>=0&&y<" << chessY << ")" <<endl;
    cin >> y;
    assert(y>=0&&y<chessY);
    auto start = chrono::system_clock::now();
    run(x,y);
    auto end = chrono::system_clock::now();
    auto duration = chrono::
    duration_cast<chrono::microseconds>(end-start);
    for(int i = 0;i<chessX;++i)
    {
        for(int j=0;j<chessY;++j)
            cout << chess[i][j] << '\t';
        cout << endl;
    }
    cout << double(duration.count())* chrono::microseconds::period::num
            /chrono::microseconds::period::den
         << "秒" <<endl;
    return 0;
}

bool run(int x, int y)
{
    int keyMin = 8;
    int keyMax = 0;
    bool finish;
    chess[x][y] = ++cnt;
    if(cnt>=chessX*chessY)
        return true;
    nextMap next = judge(x,y,keyMin,keyMax);
    for (int i = keyMin; i <= keyMax ; ++i)
    {
        if(next.count(i)!=0)
        {
            nIter beg = next.lower_bound(i);
            nIter end = next.upper_bound(i);
            for(nIter j = beg;j!=end;++j)
            {
                finish = run(x+fx[j->second],y+fy[j->second]);
                if(finish)
                    return true;
            }
        }
    }
    chess[x][y] = 0;
    --cnt;
    return false;
}

nextMap judge(int x, int y,int &keyMin,int &keyMax)
{
    nextMap res;
    keyMin = 8;
    keyMax = 0;
    for(int i=0;i<8;++i)
    {
        if(isOk(x,y,i))
        {
            int xx = x + fx[i];
            int yy = y + fy[i];
            int cnt = 0;
            for(int j=0;j<8;++j)
            {
                if(isOk(xx,yy,j))
                    ++cnt;
            }
            res.insert(make_pair(cnt,i));
            if(keyMin>cnt)
                keyMin = cnt;
            if(keyMax<cnt)
                keyMax = cnt;
        }
    }
    return res;
}

bool isOk(int x1, int y1,Direct direct)
{
    int x = x1+fx[direct];
    int y = y1+fy[direct];
    return chess[x][y] == 0 && x >= 0 && x < chessX && y >= 0 && y < chessY;
}
Comments are closed.