三角跳棋，又称为Peg Solitaire Puzzle，是一种在欧洲17世纪末就开始流行的游戏。在美国，Herbert M. Smith在1891年为这个游戏的一个三角形版本申请了专利。它也被称为“Cracker Barrel”谜题。当餐厅在每张桌子上放置一个这样的谜题以娱乐等待食物的顾客时，这个游戏开始流行起来。
本篇文章将介绍如何使用Java编程语言实现这个游戏。游戏由14个棋子组成，排列成三角形，类似于保龄球瓶，但多出一行。三角形中的一个空位是空的，目标是通过跳棋的方式，每次跳过一个棋子并移除它，直到只剩下一个棋子。实际上，程序实现了一个简单的深度优先搜索（DFS）回溯算法，从当前棋盘上的棋子布局开始寻找解决方案。
程序的主要原理是展示递归函数、固有递归问题和回溯的概念。它还提供了一种面向对象的回溯实现，形式是一个包含所有回溯逻辑的可重用类。在这个任务中，将编写一个程序来解决一个经典的谜题，有时被称为“三角谜题”或“跳棋”。解决这个谜题需要使用一种称为回溯的技术，通过所有可能的移动序列进行搜索，这可以通过递归轻松实现。
“三角谜题”由15个洞组成，排列成三角形，洞中放置了棋子，至少留有一个空洞。通常，谜题开始时只有一个洞，如下所示，实心圆圈代表棋子，空心圆圈代表洞。谜题的目标是进行一系列移动，每次移动导致一个棋子被移除，直到只剩下一个棋子。只有在一个棋子被另一个棋子和洞夹在一条线上时，才能进行合法的移动。例如，下面的配置（b）是通过从配置（a）进行一次跳跃得到的，然后（c）是通过从（b）进行第二次跳跃得到的。
这里只提供一个基本的代码概述。项目的源代码注释非常详细，应该很容易通过在鼠标事件上添加一些断点来理解。
以下是用于解决跳棋谜题的算法。
Java 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
}
主要的是棋盘，它是一个Array List
Java public List possibleBoards() {
List boards = new ArrayList();
for (int i = 0; i < 5; ++i)
for (int j = 0; j <= i; ++j) {
Position start = new Position(i,j);
List possibleMoves = Moves.getMoves(start);
for (Move move : possibleMoves) {
if (validMove(move))
boards.add(jump(move));
}
}
return boards;
}
Game tree.java
Java package play;
import java.util.List;
import java.util.ArrayList;
import board.*;
public class GameTree {
GameTree level;
GameBoard gb;
List children = new ArrayList();
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
This puzzle is getting solved by three steps. You start with the empty spot on the board jump and end as you can see in this code below.
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）来创建这个游戏。首先，可以选择开始时洞的位置。已经附加了程序和输出。
当第一次创建这个程序时，程序开始时洞的位置是固定的。然后改变了程序，手动输入洞的位置。