当前位置： 文江博客话题详情

修改这个 8 谜题代码以打印中间状态以得出解决方案

发布于 2024-08-14 11:55:52 字数 3976 浏览 1 评论 0原文

关于 8 谜题问题

// 常见的 8 谜题问题中的广度优先搜索用法。

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

我想修改代码，以便它打印用于达到解决方案的中间状态，而不仅仅是说出达到解决方案的级别。

例如，给定这个板

1 4 2
3 0 5
6 7 8

（作为字符串142305678），

我希望它打印：（

1 4 2
3 0 5
6 7 8

作为字符串142305678）

1 0 2
3 4 5
6 7 8

（作为字符串102345678）

0 1 2
3 4 5
6 7 8

（作为字符串012345678）

通过查看代码，我相信这个中间字符串是通过存储的添加方法到队列中：

void add(String str,int n){
        if(!map.containsKey(str)){
            map.put(str,n);
            q.add(str);
        }
    }

我没有使用 HashMap 的经验，我将如何查看存储在那里的中间状态？

原文

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?

如果你对这篇内容有疑问，欢迎到本站社区发帖提问 参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

扫码二维码加入Web技术交流群

发布评论

需要 登录 才能够评论， 你可以免费 注册 一个本站的账号。

评论（4）

半﹌身腐败 2024-08-21 11:55:52

以下是我如何满足您的请求，以获取链接开始到目标的跟踪：

  1. 组织导入以明确正在使用哪些实用程序类。
  2. 重命名变量以阐明每个变量的含义/作用。
  3. 添加了 stateHistory 映射，将每个状态与其前一个状态关联起来。
  4. 将每个移动方法中重复的完成检查代码重构为单独的 checkCompletion 方法。
  5. 修改了 add 方法以获取新旧状态（将深度查找内部化到该方法）并维护 stateHistory 映射以及 stateDepth 地图和议程队列。
  6. 修改了 checkCompletion 方法，将 stateHistory 从目标状态（一旦达到）返回到原始状态（没有前驱状态）。

运行修改后的代码会产生以下输出：

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

进一步修改以向前顺序（从开始到目标，而不是从目标到开始向后）打印序列，作为练习留给学生。

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

}

Here's how I addressed your request to get the trail linking start to goal:

  1. Organized the imports to make explicit which utility classes are being used.
  2. Renamed variables to clarify meaning/role of each.
  3. Added the stateHistory map to relate each state to its predecessor.
  4. Refactored the duplicated completion-check code out of each movement method into a separate checkCompletion method.
  5. 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.
  6. 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);
        }
    }

}
回复 原文
原来是傀儡 2024-08-21 11:55:52

对 Joel Neely 版本的一个小增强：初始化 e.stateDepth.put(null, -1); 简化了 add 方法中的逻辑，int newValue = stateDepth.get(oldState) + 1 ;。

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;.

回复 原文
小女人ら 2024-08-21 11:55:52

实际上，解决方案似乎存储在队列中。该映射仅用于检测重复状态。

完成后，将每个项目从队列中弹出并打印出来。

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.

回复 原文
薄情伤 2024-08-21 11:55:52

您只需要添加一行代码即可打印中间状态。
在add函数中，插入代码

    System.out.println(str+" "+ "level"+map.get(str));

整个代码将如下所示。

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

输出将如下所示。输出

但是，它还会打印对到达没有贡献的状态目标状态。

You just need to add one line of code to print the intermediate states.
In the add function, insert the code

    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.

回复 原文
~没有更多了~

关于作者

云归处

暂无简介

0 文章
0 评论
24 人气
发私信

相关话题

更多

热门标签

操作系统 程序设计 IT运维 Linux系统管理 JavaScript 服务器应用 solaris C/C++ PHP Shell BSD Vue.js aix Oracle Python HTML 系统管理 HTML5 CSS 前端
更多

推荐作者

1CH1MKgiKxn9p

文章 0 评论 0

ゞ记忆︶ㄣ

文章 0 评论 0

JackDx

文章 0 评论 0

信远

文章 0 评论 0

yaoduoduo1995

文章 0 评论 0

霞映澄塘

文章 0 评论 0

更多

友情链接

文江博客
    我们使用 Cookies 和其他技术来定制您的体验包括您的登录状态等。通过阅读我们的 隐私政策 了解更多相关信息。 单击 接受 或继续使用网站，即表示您同意使用 Cookies 和您的相关数据。
    原文