资源描述：
《算法与分析课程设计—独立钻石跳棋问题》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。
1、算法与分析课程设计报告题目：专业：班级：学号：姓名：年月日一、算法问题描述独立钻石跳棋问题。在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。下棋的规则是任意棋子可以沿着水平或着垂直方向跳过与其相邻的棋子，进入空着的顶点并吃掉被跳过的棋子。试设计一个算法并找出一种下棋的方法，使得棋盘上最终只剩下一个棋子在棋盘的正中央。二、算法问题形式化表示在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。算法解决了在32个棋子摆放在有33格的盘上(只有中心格空着)在规定当一个棋子跳过邻近的一个棋子到空格时，就将这张邻
2、近的棋子从盘上拿掉，使除了最后留在中心格一个棋子外其余的棋子均被拿掉的问题！三、期望输入与输出期望输入：显示一个棋盘，在33个方格顶点摆放着32枚棋子，仅中间的顶点空着未摆放着棋子。期望输出：使得棋盘上最终只剩下一个棋子在棋盘的正中央四、算法分析与步骤描述总体一个回溯的思想，如果两个子字间能跳，那么我们就跳了之后记录其新的位置，因为跳的前后都是一个问题，所以我们能用递归分治，跳了一次之后棋子数减1，并把被跳过的棋子和编号最后的棋子交换，这样就达到了把棋子去掉的目的。并把最优解保存。如果temp当前走的次数已经大于最优解，那么我们
3、就不用算了。五、问题实例及算法运算步骤此次问题主要用回溯算法，基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。在包含问题的所有解的解空间树中，按照深度优先的策略，从根结点出发搜索解空间树。算法搜索至解空间树的任一结点时，总是先判断该结点是否肯定不包含问题的解。如果肯定不包含，则跳过对以该结点为根的子树的系统搜索，逐层向其祖先结点回溯。否则，进入该子树，继续按深度优先的策略进行搜索。回溯法在用来求问题的所有解时，要回溯到根，且根结点的所有子树都已被搜索遍才结束。而回溯法在用来求问题的任一解时，只要搜索到问题的一
4、个解就可以结束。六、算法运行截图开始时：结束后：一、附录代码（java）packagesfdesign;importjava.awt.Color;importjava.awt.GridLayout;importjava.awt.event.MouseEvent;importjava.awt.event.MouseListener;importjavax.swing.JButton;importjavax.swing.JFrame;importjavax.swing.JLabel;importjavax.swing.JPanel;
5、publicclassDCextendsJFrame{//-----move时候用的变量们publicstaticintoldx=0;publicstaticintoldy=0;publicstaticintnewx=0;publicstaticintnewy=0;publicstaticbooleanmovingflag=false;//-----layeroutprivateGridLayoutgamepanellayer=newGridLayout(1,2);privateGridLayoutoptionlayer=new
6、GridLayout(2,1);privateGridLayoutchessboardlayer=newGridLayout(9,9);//-----左右布局的jpanelprivateJPanelleftpanel=newJPanel();privateJPanelrightpanel=newJPanel();//-----publicstaticintrestcount=32;publicstaticintsteps=0;publicstaticJLabeljl1=newJLabel("剩余子数:"+restcount);p
7、ublicstaticJLabeljl2=newJLabel("当前步数:0"+steps);//-----board点阵publicstaticboolean[][]chessboard={{false,false,false,false,false,false,false,false,false},{false,false,false,true,true,true,false,false,false},{false,false,false,true,true,true,false,false,false},{false,tr
8、ue,true,true,true,true,true,true,false},{false,true,true,true,true,true,true,true,false},{false,true,true,true,true,true,true,true,
