修改这个8难题代码来打印中间状态以达到解决方案 [英] Modifying this 8-puzzle code to print the intermediate states to reach the solution

问题描述

关于8难题问题

  import java.util。*; 
 
 class EightPuzzle {
 
 Queue< String> q = new LinkedList< String>（）; //使用LinkedList实现的队列用于存储BFS中的所有节点。 
 Map< String，Integer> map = new HashMap< String，Integer>（）; // HashMap用于忽略重复节点
 
 public static void main（String args []）{
 
 
 String str =087465132; //以0作为空格输入棋盘状态
 
 EightPuzzle e = new EightPuzzle（）; // EightPuzzle的新实例
 e.add（str，0）; //添加初始状态
 
 while（e.q.peek（）！= null）{
 
 e.up（e.q.peek（））; //向上移动空格并添加新的状态以排队
 e.down（e.q.peek（））; //将空格向下移动
 e.left（e.q.peek（））; //向左移动
 e.right（e.q.remove（））; //向右移动并从队列中移除当前节点
 
 System.out.println（Solution does not exist）; 
} 
 
 //添加方法将新字符串添加到地图和队列
 void add（String str，int n）{
 if（！map。 containsKey（str））{
 map.put（str，n）; 
 q.add（str）; 
} 
} 
 
 / *以下每种方法都将当前董事会状态视为字符串。如果可能的话，完成移动空白的操作。 
之后，新的字符串被添加到地图和队列中。如果它是目标状态，则程序终止。 
 * / 
 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（解决方案存在于层+ map.get（s）+的树）; 
 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（解决方案存在于层+ map.get（s）+的树）; 
 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（解决方案存在于层+ map.get（s）+的树）; 
 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（解决方案存在于层+ map.get（s）+的树）; 
 System.exit（0）; 
} 
} 
} 
} 
  

I想要修改代码，以便打印出用于达到解决方案的中间状态，而不是仅仅说明达到解决方案的级别。例如，给定这块板子

  1 4 2 
 3 0 5 
 6 7 8 
  
 
 $ b 
（as String 142305678）
 
 
 
我想要打印：
 p> 
 
 
  1 4 2 
 3 0 5 
 6 7 8 
  
  
 
 2 
 3 4 5 
 6 7 8 
  
（如字符串102345678）  
 
 
  0 1 2 
 3 4 5 
 6 7 8 
  
（作为字符串012345678）
 
 
通过查看代码，我相信这个中间字符串通过add方法存储到Queue中： 
 
 
  void add（String str，int n）{
如果（！地图。 containsKey（str））{
 map.put（str，n）; 
 q.add（str）; 
 
 
 
 
 $ b 
我没有使用HashMap的经验，看看存储在那里的中间状态？ 
解决方案
以下是我如何处理您的请求，以便将足迹链接开始到目标： 
 
 
 
 
组织导入以明确正在使用哪些实用程序类。
 
 
重命名变量以阐明各自的含义/作用。
 
 
添加了 stateHistory 映射关系，以便将每个状态与其前任关联。
 
 
重构重复的完成检查代码将每个移动方法移出到单独的 checkCompletion 方法中。
 
 
修改 add 方法来获取新旧状态（将深度查找内化到该方法）并维护 stateHistory 映射以及 stateDepth  map和 agenda  queue。
 
 
修改 checkCompletion 方法将 stateHistory 从目标状态（一旦到达）移回到原始状态（没有前导状态的状态）。
 
 
 
 
 
 
 
 
运行修改后的代码会产生以下输出： 
 
 
 解决方案存在于树的第28层
 123456780在28 
 123450786在27 
 120453786在26 
 102453786在25 
 152403786在24 
 152043786 at 23 
 152743086 at 22 
 152743806 at 21 
 152743860 at 20 
 152740863 at 19 
 150742863 at 18 
 105742863 at 17 
 145702863在16 
 145072863在15 
 045172863在14 
 405172863在13 
 475102863在12 
 475162803在11 
 475162083在10 
 475062183在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 
  
进一步修改以打印序列前进顺序（开始到目标，而不是从目标开始向后）作为练习留给学生。 
 
 
 
 
 
  import java.util.HashMa磷; 
 import java.util.LinkedList; 
 import java.util.Map; 
 import java.util.Queue; 
 
 class EightPuzzle {
 
 Queue< String> agenda = new LinkedList< String>（）; //使用LinkedList实现的队列用于存储BFS中的所有节点。 
 Map< String，Integer> stateDepth = new HashMap< String，Integer>（）; // HashMap用于忽略重复节点
 Map< String，String> stateHistory = new HashMap< String，String>（）; //将每个位置关联到它的前一个元素
 
 public static void main（String args []）{
 
 String str =087465132; //以0作为空格输入棋盘状态
 
 EightPuzzle e = new EightPuzzle（）; // EightPuzzle的新实例
 e.add（str，null）; //添加初始状态
 
 while（！e.agenda.isEmpty（））{
 String currentState = e.agenda.remove（）; 
 e.up（currentState）; //将空格向上移动并将新状态添加到队列
 e.down（currentState）; //向下移动空白
 e.left（currentState）; //向左移动
 e.right（currentState）; //向右移动并从队列中移除当前节点
 
 
 System.out.println（解决方案不存在）; 
} 
 
 //添加方法将新字符串添加到映射和队列
 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）; 
} 
} 
 
 / *以下每种方法都将当前董事会状态视为字符串。如果可能的话，完成移动空白的操作。 
之后，新的字符串被添加到地图和队列中。如果它是目标状态，则程序终止。 
 * / 
 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（解决方案存在于等级+ stateDepth.get（newState）+的树）; 
字符串traceState = newState; （traceState！= null）{
 System.out.println（traceState +at+ stateDepth.get（traceState））; 
 while 
 traceState = stateHistory.get（traceState）; 
} 
 System.exit（0）; 
} 
} 
 
} 
  
 
About the 8 Puzzle Problem

// 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)

I want it to print:
1 4 2
3 0 5
6 7 8
(as the String 142305678)
1 0 2
3 4 5
6 7 8
(as the String 102345678)
0 1 2
3 4 5
6 7 8
(as the String 012345678)

By looking at the code, I believe this intermediate strings are getting stored via the add method into the Queue:
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? 
解决方案
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 stateHistory map to relate each state to its predecessor.
Refactored the duplicated completion-check code out of each movement method into a separate checkCompletion method.
Modified the add method to take new and old states (internalized the depth lookup to that method) and to maintain the stateHistory map as well as the stateDepth map and agenda queue.
Modified the checkCompletion method to walk the stateHistory back from the goal state (once reached) to the original state (the one with no predecessor).




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);
        }
    }

}


                        
这篇关于修改这个8难题代码来打印中间状态以达到解决方案的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！