DFS 解谜游戏 (java)
DFS puzzle game solver (java)
我正在使用 DFS 解算器开发 8 益智游戏。此代码从树中打印所有 children 直到正确状态，但我只想打印正确的解决方案。
我的输出：
120
345
678
125
340
678
102
345
678
125
348
670
125
304
678
142
305
678
012
345
678
预期输出：
120
345
678
102
345
678
012
345
678
代码：
public class puzzle {
public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
public static HashSet<String> CLOSED = new HashSet<String>();
public static boolean STATE = false;
public static void main(String args[]) {
int statesVisited = 0;
String start = "120345678";
String goal = "012345678";
String X = "";
String temp = "";
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
print(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = down(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = left(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = right(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
}
}
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
DFS returns 它找到的第一个路径。要获得最短路径，请使用 BFS。
您可以使用地图
private static Map<String, List<String>> paths = new HashMap<>();
将每个节点（状态）映射到通往它的路径：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
public class puzzle {
private static LinkedHashSet<String> OPEN = new LinkedHashSet<>();
private static HashSet<String> CLOSED = new HashSet<>();
private static Map<String, List<String>> paths = new HashMap<>();
public static boolean STATE = false;
public static void main(String args[]) {
String start = "120345678";
String goal = "012345678";
String X = "";
String temp = "";
OPEN.add(start);
paths.put(start, Arrays.asList(start));
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
print(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS" +"\n" + paths.get(X));
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = down(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = left(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = right(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
}
}
}
static void updatePaths(String s, List<String> path){
if(paths.containsKey(s)) return;
List<String> newPath = new ArrayList<>(path);
newPath.add(s);
paths.put(s, newPath);
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p - 3) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p + 3) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p - 1) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p + 1) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
我们需要以某种方式保存步骤之间的关系，以便仅从成功路径中找到步骤。
这是我的解决方案：
public class Puzzle {
public static LinkedHashSet<Step> open = new LinkedHashSet<>();
public static HashSet<Step> closed = new HashSet<>();
public static boolean problemSolved = false;
private static class Step {
final String data;
Step previous = null;
Step(String data) {
this.data = data;
}
Step(Step previous, String data) {
this.previous = previous;
this.data = data;
}
public String getData() {
return data;
}
public Step getPrevious() {
return previous;
}
@Override
public String toString() {
return new StringBuilder()
.append(data.substring(0, 3))
.append("\r\n")
.append(data.substring(3, 6))
.append("\r\n")
.append(data.substring(6, 9))
.toString();
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (!(obj instanceof Step)) {
return false;
}
if (obj == this) {
return true;
}
return this.getData().equals(((Step) obj).getData());
}
@Override
public int hashCode() {
return this.getData().hashCode();
}
}
public static void main(String args[]) {
int statesVisited = 0;
Step startStep = new Step("120345678");
Step goalStep = new Step("012345678");
Step currentStep;
open.add(startStep);
while (!open.isEmpty() && !problemSolved) {
currentStep = open.iterator().next();
open.remove(currentStep);
// print(currentStep);
if (currentStep.equals(goalStep)) {
System.out.println("SUCCESS PATH: \r\n");
printSuccessPath(
getSuccessPathFromFinishStep(currentStep) // here currentStep is finish step
);
problemSolved = true;
} else {
// generate children
closed.add(currentStep);
Step nextStep = up(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = down(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = left(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = right(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
}
}
}
/*
* MOVEMENT UP
*/
public static Step up(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT DOWN
*/
public static Step down(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT LEFT
*/
public static Step left(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT RIGHT
*/
public static Step right(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
private static void print(Step s) {
System.out.println(s);
System.out.println();
}
private static void printSuccessPath(List<Step> successPath) {
for (Step step : successPath) {
print(step);
}
}
private static List<Step> getSuccessPathFromFinishStep(Step finishStep) {
LinkedList<Step> successPath = new LinkedList<>();
Step step = finishStep;
while (step != null) {
successPath.addFirst(step);
step = step.getPrevious();
}
return successPath;
}
}
我对您的代码进行了一些重构。并引入了新的 class Step，它允许我们保存当前步骤与上一步之间的关系。
逻辑有点复杂，但如果您不清楚，请随时提出其他问题）
顺便说一句，这是结果：
SUCCESS PATH:
120
345
678
102
345
678
012
345
678
因此，一个干净（呃）的解决方案可以满足您的要求，如下所示：
package basic;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class Puzzle {
private static class Node {
private final Node previous;
private final String data;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
return result;
}
public Node getPrevious() {
return previous;
}
public String getData() {
return data;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
return true;
}
public Node(String data) {
this.data = data;
this.previous = null;
}
public Node(String data, Node previous) {
this.data = data;
this.previous = previous;
}
}
public static void main(String args[]) {
Queue<Node> open = new LinkedList<>();
Set<Node> closed = new HashSet<>();
Node start = new Node("120345678");
Node goal = new Node("012345678");
open.add(start);
boolean solving = true;
while (!open.isEmpty() && solving) {
Node current = open.poll();
int pos = current.getData().indexOf('0');
if (!closed.contains(current)) {
if (current.equals(goal)) {
printPath(current);
System.out.println("SUCCESS");
solving = false;
} else {
// generate children
up(current, pos, open, closed);
down(current, pos, open, closed);
left(current, pos, open, closed);
right(current, pos, open, closed);
closed.add(current);
}
}
}
}
/*
* MOVEMENT UP
*/
private static void up(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition >= 3) {
char substitutedChar = current.getData().charAt(zeroPosition - 3);
open.add(new Node(current.getData().substring(0, zeroPosition - 3) + '0'
+ current.getData().substring(zeroPosition - 2, zeroPosition) + substitutedChar
+ current.getData().substring(zeroPosition + 1), current));
}
}
/*
* MOVEMENT DOWN
*/
private static void down(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition <= 5) {
char substitutedChar = current.getData().charAt(zeroPosition + 3);
open.add(new Node(current.getData().substring(0, zeroPosition) + substitutedChar
+ current.getData().substring(zeroPosition + 1, zeroPosition + 3) + '0'
+ current.getData().substring(zeroPosition + 4), current));
}
}
/*
* MOVEMENT LEFT
*/
private static void left(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition % 3 != 0) {
char substitutedChar = current.getData().charAt(zeroPosition - 1);
open.add(new Node(current.getData().substring(0, zeroPosition - 1) + '0' + substitutedChar
+ current.getData().substring(zeroPosition + 1), current));
}
}
/*
* MOVEMENT RIGHT
*/
private static void right(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition % 3 != 2) {
char substitutedChar = current.getData().charAt(zeroPosition - 1);
open.add(new Node(current.getData().substring(0, zeroPosition) + substitutedChar + '0'
+ current.getData().substring(zeroPosition + 2), current));
}
}
private static void printPath(Node current) {
Stack<String> stack = new Stack<>();
for (; current != null; current = current.getPrevious()) {
stack.push(current.getData());
}
while (!stack.isEmpty()) {
print(stack.pop());
}
}
private static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
请注意，我没有更改基本的棋盘表示法（您选择使用字符串，而我建议使用二维数组，这样交换的成本要低得多，代码也更容易理解）
一些注意事项：
- 要打印整个 "path"，您必须保持解决方案 "steps" 之间的连接
- 尽可能避免使用全局变量
- 更喜欢使用接口（集合、队列）作为集合的类型（并根据您的使用方式选择它们）
- Java 8 不要求您在构造期间指定通用集合中使用的具体类型（因此使用
Set<String> set = new HashSet<>(); 而不是使用 Set<String> set = new HashSet<String>();
- 尽可能避免使用多余的（和可读性差的）条件/代码结构（
if (booleanVariable) 优于 if (booleanVariable == true)
（可能还有一些东西需要从中删除，但这是一个有用的列表）
编辑：
下面添加了一个数据是二维数组的版本
基础包；
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class Puzzle {
private static class Node {
private final Node previous;
private final char[][] data;
public Node getPrevious() {
return previous;
}
public char[][] getData() {
return data;
}
public int getZeroX() {
return zeroX;
}
public int getZeroY() {
return zeroY;
}
private final int zeroX;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.deepHashCode(data);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!Arrays.deepEquals(data, other.data))
return false;
return true;
}
private final int zeroY;
public Node(Node previous, char[][] data, int zeroX, int zeroY) {
super();
this.previous = previous;
this.data = data;
this.zeroX = zeroX;
this.zeroY = zeroY;
}
}
public static void main(String args[]) {
Queue<Node> open = new LinkedList<>(); //Stack<Node> open = new Stack<>();
Set<Node> closed = new HashSet<>();
Node start = new Node(null, new char[][] { { '1', '2', '0' }, { '3', '4', '5' }, { '6', '7', '8' } }, 2, 0);
Node goal = new Node(null, new char[][] { { '0', '1', '2' }, { '3', '4', '5' }, { '6', '7', '8' } }, 0, 0);
open.add(start); //open.push(start);
boolean solving = true;
while (!open.isEmpty() && solving) {
Node current = open.poll(); //open.pop();
if (!closed.contains(current)) {
if (current.equals(goal)) {
printPath(current);
System.out.println("SUCCESS");
solving = false;
} else {
// generate children
up(current, open, closed);
down(current, open, closed);
left(current, open, closed);
right(current, open, closed);
closed.add(current);
}
}
}
}
/*
* MOVEMENT UP
*/
private static void up(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroY() > 0) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY() - 1][current.getZeroX()];
chars[current.getZeroY() - 1][current.getZeroX()] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX(), current.getZeroY() - 1));
}
}
/*
* MOVEMENT DOWN
*/
private static void down(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroY() < 2) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY() + 1][current.getZeroX()];
chars[current.getZeroY() + 1][current.getZeroX()] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX(), current.getZeroY() + 1));
}
}
/*
* MOVEMENT LEFT
*/
private static void left(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroX() > 0) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY()][current.getZeroX() - 1];
chars[current.getZeroY()][current.getZeroX() - 1] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX() - 1, current.getZeroY()));
}
}
/*
* MOVEMENT RIGHT
*/
private static void right(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroX() < 2) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY()][current.getZeroX() + 1];
chars[current.getZeroY()][current.getZeroX() + 1] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX() + 1, current.getZeroY()));
}
}
private static char[][] copy(char[][] data) {
char[][] newData = new char[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
newData[i][j] = data[i][j];
}
}
return newData;
}
private static void printPath(Node current) {
Stack<char[][]> stack = new Stack<>();
for (; current != null; current = current.getPrevious()) {
stack.push(current.getData());
}
while (!stack.isEmpty()) {
print(stack.pop());
}
}
private static void print(char[][] chars) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(chars[i][j]);
}
System.out.println();
}
System.out.println();
}
}
EDIT2：添加了将其转换为 DFS 的更改注释
祝你好运！
我正在使用 DFS 解算器开发 8 益智游戏。此代码从树中打印所有 children 直到正确状态，但我只想打印正确的解决方案。
我的输出：
120
345
678
125
340
678
102
345
678
125
348
670
125
304
678
142
305
678
012
345
678
预期输出：
120
345
678
102
345
678
012
345
678
代码：
public class puzzle {
public static LinkedHashSet<String> OPEN = new LinkedHashSet<String>();
public static HashSet<String> CLOSED = new HashSet<String>();
public static boolean STATE = false;
public static void main(String args[]) {
int statesVisited = 0;
String start = "120345678";
String goal = "012345678";
String X = "";
String temp = "";
OPEN.add(start);
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
print(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS");
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = down(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = left(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
temp = right(X, pos);
if (!(temp.equals("-1")))
OPEN.add(temp);
}
}
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
DFS returns 它找到的第一个路径。要获得最短路径，请使用 BFS。
您可以使用地图
private static Map<String, List<String>> paths = new HashMap<>();
将每个节点（状态）映射到通往它的路径：
import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.LinkedHashSet;
import java.util.List;
import java.util.Map;
public class puzzle {
private static LinkedHashSet<String> OPEN = new LinkedHashSet<>();
private static HashSet<String> CLOSED = new HashSet<>();
private static Map<String, List<String>> paths = new HashMap<>();
public static boolean STATE = false;
public static void main(String args[]) {
String start = "120345678";
String goal = "012345678";
String X = "";
String temp = "";
OPEN.add(start);
paths.put(start, Arrays.asList(start));
while (OPEN.isEmpty() == false && STATE == false) {
X = OPEN.iterator().next();
OPEN.remove(X);
print(X);
int pos = X.indexOf('0'); // get position of ZERO or EMPTY SPACE
if (X.equals(goal)) {
System.out.println("SUCCESS" +"\n" + paths.get(X));
STATE = true;
} else {
// generate children
CLOSED.add(X);
temp = up(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = down(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = left(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
temp = right(X, pos);
if (!temp.equals("-1")) {
OPEN.add(temp);
updatePaths(temp, paths.get(X));
}
}
}
}
static void updatePaths(String s, List<String> path){
if(paths.containsKey(s)) return;
List<String> newPath = new ArrayList<>(path);
newPath.add(s);
paths.put(s, newPath);
}
/*
* MOVEMENT UP
*/
public static String up(String s, int p) {
String str = s;
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p - 3) + '0' + newS.substring(p - 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT DOWN
*/
public static String down(String s, int p) {
String str = s;
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p + 3) + '0' + newS.substring(p + 4);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT LEFT
*/
public static String left(String s, int p) {
String str = s;
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p - 1) + '0' + newS.substring(p);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
/*
* MOVEMENT RIGHT
*/
public static String right(String s, int p) {
String str = s;
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, p + 1) + '0' + newS.substring(p + 2);
}
// Eliminates child of X if its on OPEN or CLOSED
if (!OPEN.contains(str) && CLOSED.contains(str) == false)
return str;
else
return "-1";
}
public static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
我们需要以某种方式保存步骤之间的关系，以便仅从成功路径中找到步骤。
这是我的解决方案：
public class Puzzle {
public static LinkedHashSet<Step> open = new LinkedHashSet<>();
public static HashSet<Step> closed = new HashSet<>();
public static boolean problemSolved = false;
private static class Step {
final String data;
Step previous = null;
Step(String data) {
this.data = data;
}
Step(Step previous, String data) {
this.previous = previous;
this.data = data;
}
public String getData() {
return data;
}
public Step getPrevious() {
return previous;
}
@Override
public String toString() {
return new StringBuilder()
.append(data.substring(0, 3))
.append("\r\n")
.append(data.substring(3, 6))
.append("\r\n")
.append(data.substring(6, 9))
.toString();
}
@Override
public boolean equals(Object obj) {
if (obj == null) {
return false;
}
if (!(obj instanceof Step)) {
return false;
}
if (obj == this) {
return true;
}
return this.getData().equals(((Step) obj).getData());
}
@Override
public int hashCode() {
return this.getData().hashCode();
}
}
public static void main(String args[]) {
int statesVisited = 0;
Step startStep = new Step("120345678");
Step goalStep = new Step("012345678");
Step currentStep;
open.add(startStep);
while (!open.isEmpty() && !problemSolved) {
currentStep = open.iterator().next();
open.remove(currentStep);
// print(currentStep);
if (currentStep.equals(goalStep)) {
System.out.println("SUCCESS PATH: \r\n");
printSuccessPath(
getSuccessPathFromFinishStep(currentStep) // here currentStep is finish step
);
problemSolved = true;
} else {
// generate children
closed.add(currentStep);
Step nextStep = up(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = down(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = left(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
nextStep = right(currentStep);
if (nextStep != null) {
open.add(nextStep);
}
}
}
}
/*
* MOVEMENT UP
*/
public static Step up(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (!(p < 3)) {
char a = str.charAt(p - 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 3)) + '0' + newS.substring(p - 2);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT DOWN
*/
public static Step down(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (!(p > 5)) {
char a = str.charAt(p + 3);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 3)) + '0' + newS.substring(p + 4);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT LEFT
*/
public static Step left(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (p != 0 && p != 3 && p != 7) {
char a = str.charAt(p - 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p - 1)) + '0' + newS.substring(p);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
/*
* MOVEMENT RIGHT
*/
public static Step right(Step step) {
int p = step.getData().indexOf('0');
String str = step.getData();
if (p != 2 && p != 5 && p != 8) {
char a = str.charAt(p + 1);
String newS = str.substring(0, p) + a + str.substring(p + 1);
str = newS.substring(0, (p + 1)) + '0' + newS.substring(p + 2);
}
Step nexStep = new Step(step, str); // Creates new step with step as previous one
// Eliminates child of X if its on open or closed
if (!open.contains(nexStep) && !closed.contains(nexStep))
return nexStep;
else
return null;
}
private static void print(Step s) {
System.out.println(s);
System.out.println();
}
private static void printSuccessPath(List<Step> successPath) {
for (Step step : successPath) {
print(step);
}
}
private static List<Step> getSuccessPathFromFinishStep(Step finishStep) {
LinkedList<Step> successPath = new LinkedList<>();
Step step = finishStep;
while (step != null) {
successPath.addFirst(step);
step = step.getPrevious();
}
return successPath;
}
}
我对您的代码进行了一些重构。并引入了新的 class Step，它允许我们保存当前步骤与上一步之间的关系。
逻辑有点复杂，但如果您不清楚，请随时提出其他问题）
顺便说一句，这是结果：
SUCCESS PATH:
120
345
678
102
345
678
012
345
678
因此，一个干净（呃）的解决方案可以满足您的要求，如下所示：
package basic;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class Puzzle {
private static class Node {
private final Node previous;
private final String data;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + ((data == null) ? 0 : data.hashCode());
return result;
}
public Node getPrevious() {
return previous;
}
public String getData() {
return data;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (data == null) {
if (other.data != null)
return false;
} else if (!data.equals(other.data))
return false;
return true;
}
public Node(String data) {
this.data = data;
this.previous = null;
}
public Node(String data, Node previous) {
this.data = data;
this.previous = previous;
}
}
public static void main(String args[]) {
Queue<Node> open = new LinkedList<>();
Set<Node> closed = new HashSet<>();
Node start = new Node("120345678");
Node goal = new Node("012345678");
open.add(start);
boolean solving = true;
while (!open.isEmpty() && solving) {
Node current = open.poll();
int pos = current.getData().indexOf('0');
if (!closed.contains(current)) {
if (current.equals(goal)) {
printPath(current);
System.out.println("SUCCESS");
solving = false;
} else {
// generate children
up(current, pos, open, closed);
down(current, pos, open, closed);
left(current, pos, open, closed);
right(current, pos, open, closed);
closed.add(current);
}
}
}
}
/*
* MOVEMENT UP
*/
private static void up(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition >= 3) {
char substitutedChar = current.getData().charAt(zeroPosition - 3);
open.add(new Node(current.getData().substring(0, zeroPosition - 3) + '0'
+ current.getData().substring(zeroPosition - 2, zeroPosition) + substitutedChar
+ current.getData().substring(zeroPosition + 1), current));
}
}
/*
* MOVEMENT DOWN
*/
private static void down(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition <= 5) {
char substitutedChar = current.getData().charAt(zeroPosition + 3);
open.add(new Node(current.getData().substring(0, zeroPosition) + substitutedChar
+ current.getData().substring(zeroPosition + 1, zeroPosition + 3) + '0'
+ current.getData().substring(zeroPosition + 4), current));
}
}
/*
* MOVEMENT LEFT
*/
private static void left(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition % 3 != 0) {
char substitutedChar = current.getData().charAt(zeroPosition - 1);
open.add(new Node(current.getData().substring(0, zeroPosition - 1) + '0' + substitutedChar
+ current.getData().substring(zeroPosition + 1), current));
}
}
/*
* MOVEMENT RIGHT
*/
private static void right(Node current, int zeroPosition, Queue<Node> open, Set<Node> closed) {
if (zeroPosition % 3 != 2) {
char substitutedChar = current.getData().charAt(zeroPosition - 1);
open.add(new Node(current.getData().substring(0, zeroPosition) + substitutedChar + '0'
+ current.getData().substring(zeroPosition + 2), current));
}
}
private static void printPath(Node current) {
Stack<String> stack = new Stack<>();
for (; current != null; current = current.getPrevious()) {
stack.push(current.getData());
}
while (!stack.isEmpty()) {
print(stack.pop());
}
}
private static void print(String s) {
System.out.println(s.substring(0, 3));
System.out.println(s.substring(3, 6));
System.out.println(s.substring(6, 9));
System.out.println();
}
}
请注意，我没有更改基本的棋盘表示法（您选择使用字符串，而我建议使用二维数组，这样交换的成本要低得多，代码也更容易理解）
一些注意事项：
- 要打印整个 "path"，您必须保持解决方案 "steps" 之间的连接
- 尽可能避免使用全局变量
- 更喜欢使用接口（集合、队列）作为集合的类型（并根据您的使用方式选择它们）
- Java 8 不要求您在构造期间指定通用集合中使用的具体类型（因此使用
Set<String> set = new HashSet<>();而不是使用Set<String> set = new HashSet<String>(); - 尽可能避免使用多余的（和可读性差的）条件/代码结构（
if (booleanVariable)优于if (booleanVariable == true)
（可能还有一些东西需要从中删除，但这是一个有用的列表）
编辑： 下面添加了一个数据是二维数组的版本 基础包；
import java.util.Arrays;
import java.util.HashSet;
import java.util.LinkedList;
import java.util.Queue;
import java.util.Set;
import java.util.Stack;
public class Puzzle {
private static class Node {
private final Node previous;
private final char[][] data;
public Node getPrevious() {
return previous;
}
public char[][] getData() {
return data;
}
public int getZeroX() {
return zeroX;
}
public int getZeroY() {
return zeroY;
}
private final int zeroX;
@Override
public int hashCode() {
final int prime = 31;
int result = 1;
result = prime * result + Arrays.deepHashCode(data);
return result;
}
@Override
public boolean equals(Object obj) {
if (this == obj)
return true;
if (obj == null)
return false;
if (getClass() != obj.getClass())
return false;
Node other = (Node) obj;
if (!Arrays.deepEquals(data, other.data))
return false;
return true;
}
private final int zeroY;
public Node(Node previous, char[][] data, int zeroX, int zeroY) {
super();
this.previous = previous;
this.data = data;
this.zeroX = zeroX;
this.zeroY = zeroY;
}
}
public static void main(String args[]) {
Queue<Node> open = new LinkedList<>(); //Stack<Node> open = new Stack<>();
Set<Node> closed = new HashSet<>();
Node start = new Node(null, new char[][] { { '1', '2', '0' }, { '3', '4', '5' }, { '6', '7', '8' } }, 2, 0);
Node goal = new Node(null, new char[][] { { '0', '1', '2' }, { '3', '4', '5' }, { '6', '7', '8' } }, 0, 0);
open.add(start); //open.push(start);
boolean solving = true;
while (!open.isEmpty() && solving) {
Node current = open.poll(); //open.pop();
if (!closed.contains(current)) {
if (current.equals(goal)) {
printPath(current);
System.out.println("SUCCESS");
solving = false;
} else {
// generate children
up(current, open, closed);
down(current, open, closed);
left(current, open, closed);
right(current, open, closed);
closed.add(current);
}
}
}
}
/*
* MOVEMENT UP
*/
private static void up(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroY() > 0) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY() - 1][current.getZeroX()];
chars[current.getZeroY() - 1][current.getZeroX()] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX(), current.getZeroY() - 1));
}
}
/*
* MOVEMENT DOWN
*/
private static void down(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroY() < 2) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY() + 1][current.getZeroX()];
chars[current.getZeroY() + 1][current.getZeroX()] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX(), current.getZeroY() + 1));
}
}
/*
* MOVEMENT LEFT
*/
private static void left(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroX() > 0) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY()][current.getZeroX() - 1];
chars[current.getZeroY()][current.getZeroX() - 1] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX() - 1, current.getZeroY()));
}
}
/*
* MOVEMENT RIGHT
*/
private static void right(Node current, Queue<Node>/*Stack<Node>*/ open, Set<Node> closed) {
if (current.getZeroX() < 2) {
char[][] chars = copy(current.getData());
chars[current.getZeroY()][current.getZeroX()] = chars[current.getZeroY()][current.getZeroX() + 1];
chars[current.getZeroY()][current.getZeroX() + 1] = '0';
open.add/*push*/(new Node(current, chars, current.getZeroX() + 1, current.getZeroY()));
}
}
private static char[][] copy(char[][] data) {
char[][] newData = new char[3][3];
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
newData[i][j] = data[i][j];
}
}
return newData;
}
private static void printPath(Node current) {
Stack<char[][]> stack = new Stack<>();
for (; current != null; current = current.getPrevious()) {
stack.push(current.getData());
}
while (!stack.isEmpty()) {
print(stack.pop());
}
}
private static void print(char[][] chars) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
System.out.print(chars[i][j]);
}
System.out.println();
}
System.out.println();
}
}
EDIT2：添加了将其转换为 DFS 的更改注释
祝你好运！