hello大家好！ 我依然是你们熟悉的槿凉。那么最近呢由于躺平了几天，也没有来得及更新博客，没有办法啦！学校封的严严实实，闷在学校里真的是十分难受。好叭，难受归难受，也期待着早点期末考试，早点回家，早点出狱（哈哈哈哈哈哈）！ 好了，废话不多说，那么该卷还是得卷，今天呢我们就来说说这个马踏棋盘问题
定义：这里也不能说是定义叭，哈哈，其实这个算法就是一个游戏，即象棋里面的马走“日”，按照这个规则来限定我们设计的棋盘，这里我们规定我们设计的棋盘里马不能走已经走过的格子，同时要求马要走完所有的格子。来我们看一下我们要设计的棋盘：
这里我们设计一个8*8的棋盘，马儿所在的位置是第五行 第五列，马儿现在有0 1 2 3 4 5 6 7 个位置可以选择走，那么我们怎么设计这个算法来解决让马儿一次性走完所有的格子呢？
来看一段代码，我们先设计棋盘，棋盘是一个二维数组：
privatestaticintx;//棋盘的列数privatestaticinty;//棋盘的行数x=8; y=8;
然后我们来判断马儿可以走哪些位置，走的位置是有条件的，不能越界：
publicstaticArrayList<Point>next(PointcurPoint){ ArrayList<Point>ps=newArrayList<Point>(); Pointp1=newPoint(); //表示马儿可以走5这个位置if((p1.x=curPoint.x-2)>=0&& (p1.y=curPoint.y-1)>=0) { ps.add(newPoint(p1)); } //表示马儿可以走6这个位置if((p1.x=curPoint.x-1)>=0&& (p1.y=curPoint.y-2)>=0) { ps.add(newPoint(p1)); } //表示马儿可以走7这个位置if((p1.x=curPoint.x+1)<x&& (p1.y=curPoint.y-2)>=0) { ps.add(newPoint(p1)); } //表示马儿可以走0这个位置if((p1.x=curPoint.x+2)<x&& (p1.y=curPoint.y-1)>=0) { ps.add(newPoint(p1)); } //表示马儿可以走1这个位置if((p1.x=curPoint.x+2)<x&& (p1.y=curPoint.y+1)<y) { ps.add(newPoint(p1)); } //表示马儿可以走2这个位置if((p1.x=curPoint.x+1)<x&& (p1.y=curPoint.y+2)<y) { ps.add(newPoint(p1)); } //表示马儿可以走3这个位置if((p1.x=curPoint.x-1)>=0&& (p1.y=curPoint.y+2)<y) { ps.add(newPoint(p1)); } //表示马儿可以走4这个位置if((p1.x=curPoint.x-2)>=0&& (p1.y=curPoint.y+1)<y) { ps.add(newPoint(p1)); } returnps; }
我们定义一个ArrayList<point>,用来存放我们走过的格子的集合，通过if语句来判断条件，注意这里的x我们表示的是棋盘的列数，y表示的棋盘的行数，p1.curPoint.x-1表示棋盘的列数减一，减一之后不能小于零，否则会越界，同理，对于y(行数）,也要保证不能越界，越界就会导致栈溢出。
接下来我们判断马儿是否完成了任务，使用step和应该走的步数相比较
如果没有达到数量，则表示没有完成任务，将整个棋盘置0 来看具体的代码实现：
if(step<x*y&&!finished){ chessboard[row][column] =0; visited[row*x+column]=false; }else { finished=true; }
好了，那么到这里我们来定义一个函数，用来说明马儿的起始位置，以及下一个可以访问的位置，同时对集合进行遍历，最后看看能不能得到我们想要的结果：
publicstaticvoidtravelChessboard(int[][] chessboard,introw,intcolumn,intstep) { chessboard[row][column] =step; //row=4X=8,column= 4=4*8+4=36visited[row*x+column] =true;//标记改为自已经被访问//获取下一个可以访问的位置ArrayList<Point>ps=next(newPoint(column,row)); //对ps进行排序，排序的规则就是对ps的所有Point对象的下一步的位置的数目，进行非递减排序sort(ps); //遍历pswhile(!ps.isEmpty()) { Pointp=ps.remove(0);//取出下一个可以走的位置if(!visited[p.y*x+p.x]){//说明还没有被访问过travelChessboard(chessboard,p.y,p.x,step+1); } }
是不是听得有点懵呢?没有关系，多看几遍代码里面的注释就OK啦！（这里我个人感觉马踏棋盘问题还是有点难的 大家不理解的可以多看几遍哈！）
可以发现我们虽然运行了，但是耗时是非常的长，我这里也是等了估计40秒左右才看到运行结果，那么如何对这个算法进行优化呢？
这里我们使用贪心算法来优化这个问题：（贪心算法这里不做详细描述，在后面的博客里会陆续给出，可以看懂代码就可以啦）
//根据当前这一步的所有下一步的选择位置，进行非递减排序 减少回溯publicstaticvoidsort(ArrayList<Point>ps) { ps.sort(newComparator<Point>() { publicintcompare(Pointo1,Pointo2) { intcount1=next(o1).size();//获取o1的下一步所有位置的个数intcount2=next(o2).size();//获取o2的下一步所有位置的个数if(count1<count2) { return-1; } elseif(count1==count2) { return0; } else { return1; } } }); } }
