三角形棋

• 下载源码 - 39.59 KB

引言

15孔的三角跳棋盘游戏是17世纪末在欧洲流行的一种游戏的现代版本。在美国，赫伯特·M·史密斯在1891年获得了该游戏的三角版本的专利。 它也被称为跳棋或Cracker Barrel谜题。 当餐厅将它放在每张桌子上，供顾客在等待食物时消遣时，这个谜题开始流行起来。

这个程序让你玩跳棋游戏，也叫做三角跳棋。 游戏由14个棋子组成，以三角形排列，有15个孔，像保龄球瓶一样，但多了一排。 三角形中有一个空格是空的，目标是通过跳过棋子，移除每个跳过的棋子，直到只剩下一个棋子。 实际上，该程序实现了一个简单的回溯算法DFS，以从棋盘上棋子的当前布局开始搜索解决方案。

背景

这个程序的主要目的是展示递归函数、固有递归问题和回溯的概念。它还以可重用类的形式为回溯提供了一个面向对象的包装，该类包含所有回溯逻辑。 在这个作业中，你将编写一个程序来解决一个经典的谜题，有时被称为三角谜题或跳棋。 解决这个谜题需要使用一种称为回溯的技术来搜索所有可能的移动序列，这很容易使用递归来实现。

它是如何工作的：一个通用步骤

三角谜题是由15个孔组成的三角形，将棋子放入其中，至少留下一个空孔。 通常，谜题开始时只有一个孔，如下面的配置（a）所示，其中实心圆代表棋子，空心圆代表孔。 谜题的目的是进行一系列的移动，每次移动都会导致一个棋子被移除，从而只剩下一个棋子。 棋子只能通过另一个棋子的 "跳跃 "来移除。 因此，只有当一个棋子两侧都有另一个棋子和一个孔，并且排列成一条直线时，才能进行合法的移动。 例如，下面显示的配置（b）是从配置（a）通过一次跳跃获得的，然后（c）是通过第二次跳跃从（b）获得的。

Using the Code

我只想对代码给出一个非常基本的概述。 项目中的源代码都有很好的注释，并且通过在鼠标事件上添加一些断点，应该很容易理解。

这是此跳棋解决方案中使用的算法。

DepthFirstSearch(Board b, Peg start)
{
      If (Grandchild.isEmpty())
            Jump();
            updateBoard(); //updates empty peg, location, etc.
      else
            backtrack();  // backtrack to previous and/or try right child
}

主要的是棋盘，它是一个ArrayList<T>。 BitArray管理一个紧凑的位值数组，这些位值表示为布尔值，其中true表示该位已开启 (1)，而false表示该位已关闭 (0)。 对于游戏的目的，true表示存在棋子，而false表示一个空孔。 下面是设置新游戏板的函数InitializeBoard()

这是一些用于呈现游戏板的代码。 正如您在代码中看到的

public List<GameBoard> possibleBoards() {
            List<GameBoard> boards = new ArrayList<GameBoard>();

            for (int i = 0; i < 5; ++i)
                  for (int j = 0; j <= i; ++j) {
                        Position start = new Position(i,j);
                        List<Move> possibleMoves = Moves.getMoves(start);
                        for (Move move : possibleMoves) {
                              if (validMove(move))
                                    boards.add(jump(move));
                        }
			}
	return boards;
}

Game tree.java

 package play;
 import java.util.List;
 import java.util.ArrayList;
 import board.*;

  public class GameTree {
  GameTree level;
  GameBoard gb;
  List<GameTree> children = new ArrayList<GameTree>();

   public GameTree(GameBoard gb) {
            this.gb = gb;
      }

   public void addChild(GameTree child) {
            children.add(child);
      }

   public GameBoard getGameBoard() { return gb; }

   public boolean hasChildren() {
            return children.size() > 0;
      }

   public GameTree getFirstChild() {
            return children.get(0);
      }

   public void removeFirstChild() {
            children.remove(0);
      }

   public int numChildren() {
            return children.size();
      }
}

Move.java

这个谜题通过三个步骤解决。 你从棋盘上的空白点开始跳跃，并像你在下面的代码中看到的那样结束。

package board;
public class Move {
      private Position start;
      private Position jump;
      private Position end;

      public Move(Position start, Position jump, Position end) {
            this.start = start;
            this.jump = jump;
            this.end = end;
      }

      public Position getStart() { return start; }
      public Position getJump() { return jump; }
      public Position getEnd() { return end; }

      public String toString() {
            StringBuffer sb = new StringBuffer();

            sb.append("{"+start);
            sb.append(","+jump);
            sb.append(","+end+ "}");
            return sb.toString();
      }
}

程序是如何工作的？

我使用深度优先搜索算法（DFS）来创建游戏。 我使用了 NetBeans IDE 7.0。 首先，您可以选择开始时孔的位置。 我已经附加了程序和输出。

第一次创建程序时，程序开始时孔的位置是固定的。 然后我修改了程序，手动输入孔的位置。

结论

我创建这个游戏很有趣。 我希望这篇文章对你有所帮助，并且你能在玩游戏时玩得开心。 此外，欢迎您留下任何反馈。 在创建这款人工智能游戏之后，我对回溯算法有了清晰的认识。

历史

• 2011年10月20日：初始版本