java 修改这个 8-puzzle 代码以打印中间状态以达到解决方案
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/1884624/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Modifying this 8-puzzle code to print the intermediate states to reach the solution
提问by andandandand
// Breadth First Search Usage in the common Eight Puzzle Problem.
// 广度优先搜索在常见八拼问题中的用法。
import java.util.*;
class EightPuzzle {
Queue<String> q = new LinkedList<String>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> map = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
public static void main(String args[]){
String str="087465132"; // Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(str,0); // Add the Initial State
while(e.q.peek()!=null){
e.up(e.q.peek()); // Move the blank space up and add new state to queue
e.down(e.q.peek()); // Move the blank space down
e.left(e.q.peek()); // Move left
e.right(e.q.remove()); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String str){
int a = str.indexOf("0");
if(a>2){
String s = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void down(String str){
int a = str.indexOf("0");
if(a<6){
String s = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void left(String str){
int a = str.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String s = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void right(String str){
int a = str.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String s = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
}
I want to modify the code so that it prints the intermediate states used to reach the solution, instead of just saying the level on which the solution was reached.
我想修改代码，以便它打印用于达到解决方案的中间状态，而不是仅仅说明达到解决方案的级别。
For example, given this board
例如，给定这个板
1 4 2
3 0 5
6 7 8
(as String 142305678)
（如字符串 142305678）
I want it to print:
我希望它打印：
1 4 2
3 0 5
6 7 8
(as the String 142305678)
（如字符串 142305678）
1 0 2
3 4 5
6 7 8
(as the String 102345678)
（作为字符串 102345678）
0 1 2
3 4 5
6 7 8
(as the String 012345678)
（作为字符串 012345678）
By looking at the code, I believe this intermediate strings are getting stored via the add method into the Queue:
通过查看代码，我相信这个中间字符串是通过 add 方法存储到队列中的：
void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
}
}
I have no experience working with HashMap, how would I look into the intermediate states stored there?
我没有使用 HashMap 的经验，我将如何查看存储在那里的中间状态？
回答by joel.neely
Here's how I addressed your request to get the trail linking start to goal:
以下是我如何解决您的请求，让路径链接开始到目标：
- Organized the imports to make explicit which utility classes are being used.
- Renamed variables to clarify meaning/role of each.
- Added the
stateHistorymap to relate each state to its predecessor. - Refactored the duplicated completion-check code out of each movement method into a separate
checkCompletionmethod. - Modified the
addmethod to take new and old states (internalized the depth lookup to that method) and to maintain thestateHistorymap as well as thestateDepthmap andagendaqueue. - Modified the
checkCompletionmethod to walk thestateHistoryback from the goal state (once reached) to the original state (the one with no predecessor).
- 组织导入以明确使用哪些实用程序类。
- 重命名变量以阐明每个变量的含义/作用。
- 添加了
stateHistory地图以将每个状态与其前身相关联。 - 将每个移动方法中重复的完成检查代码重构为一个单独的
checkCompletion方法。 - 修改了
add方法以获取新旧状态（将深度查找内stateHistory化为该方法）并维护地图以及stateDepth地图和agenda队列。 - 改装后的
checkCompletion走法stateHistory从目标状态（一度达到）到原来的状态恢复（带有无前身）。
Running the modified code produces this output:
运行修改后的代码会产生以下输出：
Solution Exists at Level 28 of the tree
123456780 at 28
123450786 at 27
120453786 at 26
102453786 at 25
152403786 at 24
152043786 at 23
152743086 at 22
152743806 at 21
152743860 at 20
152740863 at 19
150742863 at 18
105742863 at 17
145702863 at 16
145072863 at 15
045172863 at 14
405172863 at 13
475102863 at 12
475162803 at 11
475162083 at 10
475062183 at 9
475602183 at 8
475682103 at 7
475682130 at 6
475680132 at 5
470685132 at 4
407685132 at 3
487605132 at 2
487065132 at 1
087465132 at 0
Further modification to print the sequence in forward order (start-to-goal, rather than backwards from goal-to-start) is left as an exercise to the student.
进一步修改以向前顺序打印序列（从开始到目标，而不是从目标到开始向后）作为练习留给学生。
import java.util.HashMap;
import java.util.LinkedList;
import java.util.Map;
import java.util.Queue;
class EightPuzzle {
Queue<String> agenda = new LinkedList<String>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> stateDepth = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
Map<String,String> stateHistory = new HashMap<String,String>(); // relates each position to its predecessor
public static void main(String args[]){
String str="087465132"; // Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(str, null); // Add the Initial State
while(!e.agenda.isEmpty()){
String currentState = e.agenda.remove();
e.up(currentState); // Move the blank space up and add new state to queue
e.down(currentState); // Move the blank space down
e.left(currentState); // Move left
e.right(currentState); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String newState, String oldState){
if(!stateDepth.containsKey(newState)){
int newValue = oldState == null ? 0 : stateDepth.get(oldState) + 1;
stateDepth.put(newState, newValue);
agenda.add(newState);
stateHistory.put(newState, oldState);
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String currentState){
int a = currentState.indexOf("0");
if(a>2){
String nextState = currentState.substring(0,a-3)+"0"+currentState.substring(a-2,a)+currentState.charAt(a-3)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void down(String currentState){
int a = currentState.indexOf("0");
if(a<6){
String nextState = currentState.substring(0,a)+currentState.substring(a+3,a+4)+currentState.substring(a+1,a+3)+"0"+currentState.substring(a+4);
checkCompletion(currentState, nextState);
}
}
void left(String currentState){
int a = currentState.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String nextState = currentState.substring(0,a-1)+"0"+currentState.charAt(a-1)+currentState.substring(a+1);
checkCompletion(currentState, nextState);
}
}
void right(String currentState){
int a = currentState.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String nextState = currentState.substring(0,a)+currentState.charAt(a+1)+"0"+currentState.substring(a+2);
checkCompletion(currentState, nextState);
}
}
private void checkCompletion(String oldState, String newState) {
add(newState, oldState);
if(newState.equals("123456780")) {
System.out.println("Solution Exists at Level "+stateDepth.get(newState)+" of the tree");
String traceState = newState;
while (traceState != null) {
System.out.println(traceState + " at " + stateDepth.get(traceState));
traceState = stateHistory.get(traceState);
}
System.exit(0);
}
}
}
回答by trashgod
A small enhancement to Joel Neely's version: initializing e.stateDepth.put(null, -1);simplifies the logic in the add method, int newValue = stateDepth.get(oldState) + 1;.
对 Joel Neely 版本的一个小改进：初始化e.stateDepth.put(null, -1);简化了 add 方法中的逻辑，int newValue = stateDepth.get(oldState) + 1;.
回答by Rajshree Rai
You just need to add one line of code to print the intermediate states. In the add function, insert the code
您只需要添加一行代码来打印中间状态。在add函数中，插入代码
System.out.println(str+" "+ "level"+map.get(str));
The entire code will look like this.
整个代码看起来像这样。
import java.util.*;
class EightPuzzle {
Queue<String> q = new LinkedList<String>(); // Use of Queue Implemented using LinkedList for Storing All the Nodes in BFS.
Map<String,Integer> map = new HashMap<String, Integer>(); // HashMap is used to ignore repeated nodes
public static void main(String args[]){
String str="087465132"; // Input the Board State as a String with 0 as the Blank Space
EightPuzzle e = new EightPuzzle(); // New Instance of the EightPuzzle
e.add(str,0); // Add the Initial State
while(e.q.peek()!=null){
e.up(e.q.peek()); // Move the blank space up and add new state to queue
e.down(e.q.peek()); // Move the blank space down
e.left(e.q.peek()); // Move left
e.right(e.q.remove()); // Move right and remove the current node from Queue
}
System.out.println("Solution doesn't exist");
}
//Add method to add the new string to the Map and Queue
void add(String str,int n){
if(!map.containsKey(str)){
map.put(str,n);
q.add(str);
System.out.println(str+" "+ "level"+map.get(str));
}
}
/* Each of the Methods below Takes the Current State of Board as String. Then the operation to move the blank space is done if possible.
After that the new string is added to the map and queue.If it is the Goal State then the Program Terminates.
*/
void up(String str){
int a = str.indexOf("0");
if(a>2){
String s = str.substring(0,a-3)+"0"+str.substring(a-2,a)+str.charAt(a-3)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void down(String str){
int a = str.indexOf("0");
if(a<6){
String s = str.substring(0,a)+str.substring(a+3,a+4)+str.substring(a+1,a+3)+"0"+str.substring(a+4);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void left(String str){
int a = str.indexOf("0");
if(a!=0 && a!=3 && a!=6){
String s = str.substring(0,a-1)+"0"+str.charAt(a-1)+str.substring(a+1);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
void right(String str){
int a = str.indexOf("0");
if(a!=2 && a!=5 && a!=8){
String s = str.substring(0,a)+str.charAt(a+1)+"0"+str.substring(a+2);
add(s,map.get(str)+1);
if(s.equals("123456780")) {
System.out.println("Solution Exists at Level "+map.get(s)+" of the tree");
System.exit(0);
}
}
}
}
The output will look like this.output
输出将如下所示。输出
However, it also prints states that did not contribute to reach the goal state.
但是，它还会打印对达到目标状态没有贡献的状态。
回答by Anon.
Actually, the solution appears to be stored in the queue. The map is only used to detect repeated states.
实际上，解决方案似乎存储在队列中。该地图仅用于检测重复状态。
When it's finished, pop each item off the queue and print it out.
完成后，将每个项目从队列中弹出并打印出来。
