马踏棋盘算法（Java代码实现）

ゝ一纸荒年。 2023-02-14 07:47 81阅读 0赞

#### 马踏棋盘算法介绍和游戏演示 ####

1.  马踏棋盘算法也被称为骑士周游问题
2.  将马随机放在国际象棋的 8X8 棋盘Board\[0~7\] \[0~7\]的某个方格中，马按走棋规则(马走日字)进行移动。要求每个方格只进入一次，走遍棋盘上全部64个方格

[马踏棋盘的游戏地址：进行测试][Link 1]

#### 马踏棋盘游戏代码实现 ####

1.  马踏棋盘问题(骑士周游问题)实际上是图的深度优先搜索(DFS)的应用。
2.  如果使用回溯(就是深度优先搜索)来解决，假如马儿踏了53个点，走到了第53个，坐标(1,0) ，发现已经走到尽头，没办法，那就只能回退了，查看其他的路径，就在棋盘上不停的回退…
3.  分析第一种方式的问题，并使用贪心算法(greedyalgorithm)进行优化。解决马踏棋盘问题.
4.  使用前面的游戏来验证算法是否正确。

使用回溯实现：

解决步骤和思路

1.  创建棋盘chessBoard，是一个二维数组
2.  将当前位置设置为已经访问，然后根据当前位置，计算马儿还能走哪些位置，并放入到一个集合中(ArrayList),最多有8个位置，每走-步,就使用step+1
3.  遍历ArrayList中存放的所有位置，看看哪个可以走通,如果走通，就继续，走.不通，就回溯.
4.  判断马儿是否完成了任务，使用step 和应该走的步数比较，如果没有达到数量，则表示没有完成任务，将整个棋盘置0 ;

注意:马儿不同的走法(策略)，会得到不同的结果，效率也会有影响(优化)

代码实现：

package Horse;
    
    import java.awt.Point;
    import java.util.ArrayList;
    
    public class HorsechessBoard { 
    	private static int X; // 表示列
    	private static int Y; // 表示行
    	private static boolean visited[]; // 是否被访问
    	private static boolean finished; // 是否全部完成
    
    	// 进行行走
    	public static void traversal(int[][] arr, int row, int col, int step) { 
    		arr[row][col] = step;
    		visited[row * X + col] = true;// 初始位置标记为已访问
    		// 获取下一步集合
    		ArrayList<Point> ps = next(new Point(col, row));
    		// 遍历集合
    		while (!ps.isEmpty()) { 
    			Point p = ps.remove(0);
    			// 判断该点是否访问过
    			if (!visited[p.y * X + p.x]) {  // 没有访问过
    				traversal(arr, p.y, p.x, step+1);
    			}
    		}
    		if (step < X * Y && !finished) { 
    			arr[row][col] = 0;
    			visited[row * X + col] = false;
    		} else { 
    			finished = true;
    		}
    	}
    
    	// 根据当前位置计算还有哪些位置可以走
    	public static ArrayList<Point> next(Point cutPoint) { 
    		ArrayList<Point> ps = new ArrayList<Point>();
    		Point p1 = new Point();
    		// 判断是否可以走下一个位置
    		if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y - 1) >= 0) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y - 2) >= 0) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y - 2) >= 0) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y - 1) >= 0) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x + 2) < X && (p1.y = cutPoint.y + 1) < Y) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x + 1) < X && (p1.y = cutPoint.y + 2) < Y) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x - 1) >= 0 && (p1.y = cutPoint.y + 2) < Y) { 
    			ps.add(new Point(p1));
    		}
    		if ((p1.x = cutPoint.x - 2) >= 0 && (p1.y = cutPoint.y + 1) < Y) { 
    			ps.add(new Point(p1));
    		}
    		return ps;
    	}
    
    	public static void main(String[] args) { 
    		X = 8;
    		Y = 8;
    		int row = 1;
    		int col = 1;
    		int[][] arr = new int[X][Y];
    		visited = new boolean[X * Y];
    		System.out.println("开始");
    		long start = System.currentTimeMillis();
    		traversal(arr, row-1, col-1,1);
    		long end = System.currentTimeMillis();
    		System.out.println("耗时 = "+ (end-start)+" 毫秒");
    		for(int[] rows:arr) { 
    			for(int step :rows) { 
    				System.out.print(step+"\t");
    			}
    			System.out.println();
    		}
    		System.out.println("结束");
    	}
    }

查看输出：用时基本在30到40秒之间：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]  
在游戏当中进行测试：切换成6X6的棋盘：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]  
 使用贪心算法进行优化：

我们需要对ps中所有的Point的下一步的所有集合的数目, 进行非递减排序就ok,

代码实现：

在前面的基础上，添加方法

// 进行非递减排序
    	public static void sort(ArrayList<Point> ps) { 
    		ps.sort(new Comparator<Point>() { 
    			@Override
    			public int compare(Point o1, Point o2) { 
    				int count1 = next(o1).size();
    				int count2 = next(o2).size();
    				if (count1 < count2) { 
    					return -1;
    				} else if (count1 == count2) { 
    					return 0;
    				} else { 
    					return 1;
    				}
    			}
    
    		});
    	}

然后在traversal方法当中的ps进行排序：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]  
测试代码不变，进行测试：很显然这样进行优化之后，在很短的时间当中就会得到结果：  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]

总结：在学习了这一门[数据结构（Java版）][Java]大概花费一个半月的时间（4-17到6-1号），在先前也学习了数据结构，只不过是学时太短，知识点太多，外加自己本身的原因，不过经过再一次的对数据结构这一门课进行过滤一遍，还是学到了很多，教程也不错。

[Link 1]: http://h.4399.com/play/146267.htm
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70]: https://img-blog.csdnimg.cn/20200601221817997.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 1]: https://img-blog.csdnimg.cn/20200601222207296.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 2]: https://img-blog.csdnimg.cn/20200601223548460.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5_size_16_color_FFFFFF_t_70 3]: https://img-blog.csdnimg.cn/20200601223650352.png?x-oss-process=image/watermark,type_ZmFuZ3poZW5naGVpdGk,shadow_10,text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3FxXzQ0OTczMTU5,size_16,color_FFFFFF,t_70
[Java]: https://www.bilibili.com/video/BV1n4411U7BD