树形递归算法解决一笔画问题（Java）
下面要说的一笔画问题指的并不是经典的欧拉回路或汉密尔顿路径问题 而是我前几天接触的一款小游戏 ↓
核心算法在下边，前边部分讲的是具体实现（Java）
这款游戏的玩法就是从起点（绿色点）出发，一笔画过所有的方块。部分关卡还是有一定的难度的，于是便心血来潮的想了个算法来算出正确路径。
大致的思路是比较简单的，无非就是穷举出所有的路径，找到那条经过所有格子的路径。重点在于怎么用程序实现。
如果要用程序去解决这个问题，首先要构造出数据模型。我们可以将每个格子看作一个Block类实例，每个block都有自己的位置和状态（这里的状态指的是有没有被占用）。
public class Block {
private Position position = new Position(0, 0);
private int status = 0; //0代表没占用，1代表占用
public Block() {
}
public Block(Position p) {
this.position = p;
}
public Position getPosition() {
return position;
}
public int getStatus() {
return status;
}
public void setStatus(int status) {
this.status = status;
}
}Block中只有一些最简单最基本的getter和setter方法，Position类主要是一些位置信息的处理，也比简单，具体实现就不贴出了（最后会有全部的源码）。
有了格子了，还需要一个容器来装这些格子，从而完成一些初始化、添加、删除一类的工作。
public class Map {
private Block[][] blocks;//主容器
private Block nowBlock;//指向当前的格子
private int row;//棋盘行数
private int col;//棋盘列数
private int size;//棋盘包含的block个数
private Map(){}
public Map(int r, int c){
if(r > 0 && c > 0){
this.row = r + 2;
this.col = c + 2;
this.size = r * c;
blocks = new Block[c + 2][r + 2]; //注意行列是反着的
init();
}else{
throw new IllegalArgumentException("行列数必须大于0");
}
private void init(){
//设置边界
for(int i = 0; i < col; i ++){
blocks[i][0] = null;
blocks[i][row - 1] = null;
}
for(int i = 0; i < row ; i ++){
blocks[0][i] = null;
blocks[col -1][i] = null;
}
//设置格子 这里行列数减去2
for(int i = 1; i <= row - 2; i++) {
for (int j = 1; j <= col - 2; j++) {
Block b = new Block( new Position(i, j));
blocks[j][i] = b;
}
}
}
//这个函数用来设置空白块
public void setStatus(int r, int c){
blocks[c][r].setStatus(1);
size -- ;
}
public int size(){
return size;
}
public void setStart(Position start) {
Block b = new Block(start);
b.setStatus(1);
this.nowBlock = b;
blocks[start.getCol()][start.getRow()] = b;
}
public Block getBlock(Position p){
return blocks[p.getCol()][p.getRow()];
}
public Block getBlock(int r, int c){
return blocks[c][r];
}
public Block getNowBlock(){
return nowBlock;
}
public void setNowBlock(Block nowBlock) {
this.nowBlock = nowBlock;
nowBlock.setStatus(1);
}
}所有的格子装在blocks数组中，对于空白块，使用null来表示。另外为了保证block的位置信息与数组中的位置信息一一对应，这里在初始化的时候，加入了边界。举个例子，假如棋盘是6行6列，实际初始化的二维数组为 （6+2）*（6+2）也就是8*8。 其中第0、7行和第0、7列为null。 在接下来的计算中，会假设一步一步在棋盘中走，null可以用来判断是否越界。（当然也可以通过其他方法来判断，这样做的好处是简化逻辑）。
nowBlock属性用来指向当前的方块。size属性代表棋盘中除了空白块和边界外的全部block数量（也就是所有可以走的格子的数量，接下来会用它判断一条路径是否包含了全部的方块）。
所谓空白块就是指的下图 中的方块：
核心算法部分
接下来介绍核心算法–树形递归算法，这个是我自己起的名字，因为这个算法的结构太像一棵树了。
如果要通过计算机的思维来看这个问题，我们需要把整个问题拆解成最小的单元。
从起点出发，不重复的经过所有的格子，假定起点为第一个格子，那么接下来可以行进的方向有 上、下、左、右，用伪代码写出来大概是这个样子。
//伪代码
public void run(){
if(canIGo('up')){
go('up');//实际程序中，这一步实际上是设置Map的nowBlock值
}
if(canIGo('down')){
go('down');
}
if(canIGo('left')){
go('left');
}
if(canIGo('right')){
go('right');
}
}行进到第二个格子后，接下来的选择任然是上下左右，上面的伪代码可以再拓展一下
//伪代码
private Map map;
public void run(){
if(canIGo('up')){
go('up');//实际程序中，这一步实际上是设置Map的nowBlock值
run();
}
if(canIGo('down')){
go('down');
run();
}
if(canIGo('left')){
go('left');
run();
}
if(canIGo('right')){
go('right');
run();
}
}这样就形成了最基本的递归结构。下面来详细说一下伪代码中go()函数需要做的事情。
通过一开始的分析，我们建立了一个Map类用来维护整个棋盘。我们所谓的“走”，其实就是设置Map实例中的nowBlock属性。另外，我们还需要记录下我们走过的路径，如果遇到无路可走的情况，我们需要根据这个记录回退。上面的代码并没有判断有没有走完整个棋盘，还需要做一个判断，这就需要一个变量来记录走过的步数，在go()执行时给该变量加一。
通过以上分析，go()可以拆解为如下代码:
record.push(map.getNowBlock().getPostion()); //record为一个栈，用来记录走过的位置
map.setNowBlock(block);//设置当前方块 block的值在四个分支中各不相同 注意这个函数会让block的status置为1！！
count ++;//行进步数量+1分析完go()后，我们需要加上逻辑判断
//伪代码
private Map map;
private Stack record = new Stack();
private count = 1;//起点已经算走了一步了，所以这里为1
public void run(){
if(canIGo('up')){
go('up');//实际程序中，这一步实际上是设置Map的nowBlock值
run();
}
if(canIGo('down')){
go('down');
run();
}
if(canIGo('left')){
go('left');
run();
}
if(canIGo('right')){
go('right');
run();
}
//程序如果运行到这，代表没有方块可以走了
//先判断有没有走完全部的方块
if(count == map.size()){
//此时将record中的内容倒序输出即可，代码省略
System.out.println("找到路径了！");
System.exit(0);
}
//如果没找的，则进行回退，先判断record中还有数据吗
if(record.empty()){
//无解
System.exit（0）
}
//进行回退
Postion p = record.pop();//获取上一步位置
Block b = map.getBlock(p);//通过位置获取block
map.setNowBlock(b);//设置当前块
count --; //总步数减去1
}通过以上代码，就可以穷举出所有路径了。因为是递归调用，找到路径后用只能用exit()退出程序，当然也可以设置一个共享变量来解决这个问题。通过这个图可以更好的理解这个算法。
算法具体代码如下：
public class ALU {
private Map map;
private Stack<Position> record = new Stack<>(); //用来记录步骤
private int count = 0;
public ALU(@NotNull Map map){
this.map = map;
}
public void run(){
Block nowBlock = map.getNowBlock(); //获取当前格子
Position p = nowBlock.getPosition();//获取当前格子的坐标
Block up = map.getBlock(p.getRow() - 1, p.getCol());//判断上方向可不可以走
if(null != up && up.getStatus() == 0){
record.push(map.getNowBlock().getPosition());
map.setNowBlock(up);
count ++;
run();
}
nowBlock = map.getNowBlock();
p = nowBlock.getPosition();
Block down = map.getBlock(p.getRow() + 1, p.getCol());
if(null != down && down.getStatus() == 0){
record.push(map.getNowBlock().getPosition());
map.setNowBlock(down);
count ++;
run();
}
nowBlock = map.getNowBlock();
p = nowBlock.getPosition();
Block left = map.getBlock(p.getRow(), p.getCol() - 1);
if(null != left && left.getStatus() == 0){
record.push(map.getNowBlock().getPosition());
map.setNowBlock(left);
count ++;
run();
}
nowBlock = map.getNowBlock();
p = nowBlock.getPosition();
Block right = map.getBlock(p.getRow(), p.getCol() + 1);
if(null != right && right.getStatus() == 0){
record.push(map.getNowBlock().getPosition());
map.setNowBlock(right);
count ++;
run();
}
if(count == map.size() - 1){
record.push(nowBlock.getPosition());
System.out.println("找到了");
out();
System.exit(0);
}
if(record.empty()){
System.out.println("无解");
System.exit(0);
}
nowBlock.setStatus(0);
map.setNowBlock(map.getBlock(record.pop()));
count --;
}
private void out(){
for (Position p:
record) {
System.out.println(p);
}
}
}上面的代码可以优化的地方还有很多，各位大佬可以批评指正一下，因为写的匆忙，难免有一些错误，还请大家帮忙指出。整个项目稍后会贴出github地址。
idea项目地址：https://github.com/VanMesure/auto-unicursal
源码在src目录下