java - Boggle 游戏板搜索程序问题

Question

我正在编写一个令人难以置信的游戏板解算器。它使用一个堆栈，一个从 .dat/.txt 文件读取的游戏板字母二维数组网格，并搜索“状态”来存储它的具体位置(点坐标、到目前为止的单词)。它的设计目的是搜索板上所有可能的字母组合，以形成长度为 3 或以上的字符串，然后检查字典文件以查看该单词是否是有效的单词解决方案。之后，它存储该单词并将参数中给出的解决方案列表返回到游戏板。

我的问题:由于某种原因，这个程序让我无法理解，就像我以前写过的任何其他程序一样。我对“状态”的概念非常陌生，因此这可能是一个潜在的问题。我相信我所拥有的已经相当接近工作了，我只是不知道它可能出什么问题。当前的问题是，它在检查相邻字母时不会存储当前字母和构建字符串。它确实正确检查邻居，但没有构建任何字符串。这是代码:

令人惊叹的搜索:包含main方法，充当驱动类。

import java.io.*;
import java.util.*;

public class BoggleSearch {

protected static int GRID_SIZE = 4;
public static String[][] grid = new String[GRID_SIZE][GRID_SIZE];

public static void main(String[] args) throws FileNotFoundException {

    if (args.length != 1) {
        System.err.println("Usage: java BoggleSearch gridFile");
        System.exit(1);

    }

    Scanner scan = new Scanner(new File(args[0]));

    String bigString = scan.next();
    bigString = bigString+scan.next();
    bigString = bigString+scan.next();
    bigString = bigString+scan.next();

    scan.close();

    int count = 0;

    for (int i = 0; i < GRID_SIZE; i++) {

        for (int j = 0; j < GRID_SIZE; j++) {


            grid[i][j] = bigString.substring(count, count);

            count++;
        }

    }

    WordSearch ws = new WordSearch(grid);

    ArrayList<BoggleSearchState> foundWords = ws.startSearch();

    System.out.println(foundWords);


   }

}

词搜索:包含所有算法，这些算法可以找到给定游戏板上可能出现的所有可能的字母组合，并与字典类进行交叉检查。

import java.awt.Point;
import java.util.*;

public class WordSearch {

public static Stack<BoggleSearchState> stack;

public static ArrayList<BoggleSearchState> foundWords;

private String[][] grid;

private static final int GRID_SIZE = 4;

public BoggleDictionary dictionary;

public WordSearch(String[][] inputGrid) {

    grid = new String[GRID_SIZE][GRID_SIZE];
    stack = new Stack<BoggleSearchState>();
    foundWords = new ArrayList<BoggleSearchState>();
    inputGrid = new String[GRID_SIZE][GRID_SIZE];



    try {
        dictionary = new BoggleDictionary();
    } catch (Exception e) {
        System.err.println("blew up while making dict object");
        e.printStackTrace();
    }
}

public ArrayList<BoggleSearchState> startSearch() {

    for (int i = 0; i < grid.length; i++) {

        for (int j = 0; j < grid.length; j++) {

            BoggleSearchState b = new BoggleSearchState(
                    new ArrayList<Point>(), grid[i][j]);

            Point p = new Point(i, j);

            b.path.add(p);
            stack.push(b);


            while (!stack.isEmpty()) {

                BoggleSearchState s = stack.pop();

                if (s.getWord().length() >=1  && dictionary.contains(s.getWord())) {

                    foundWords.add(s);

                }

                Point loc = s.path.get(s.path.size() - 1);

                p = new Point(loc.x,loc.y);

                // Bottom Neighbor
                if (loc.x + 1 >= 0 && loc.x + 1 < grid.length && loc.y >= 0
                        && loc.y < grid.length) {
                    if (s.getVisited(new Point(p.x+1,p.y)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(new ArrayList<Point>(),s.getWord() + grid[loc.x + 1][loc.y]);
                        neo.path.add(new Point(p.x+1,p.y));
                        stack.push(neo);

                    }
                }

                // Top Neighbor
                if (loc.x - 1 >= 0 && loc.x - 1 < grid.length && loc.y >= 0
                        && loc.y < grid.length) {
                    if (s.getVisited(new Point(p.x-1,p.y)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() + 
                                grid[loc.x - 1][loc.y]);
                        neo.path.add(new Point(p.x-1,p.y));
                        stack.push(neo);

                    }
                }
                // Right Neighbor
                if (loc.x >= 0 && loc.x < grid.length && loc.y + 1 >= 0
                        && loc.y + 1 < grid.length) {
                    if (s.getVisited(new Point(p.x,p.y+1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() + 
                                grid[loc.x][loc.y + 1]);
                        neo.path.add(new Point(p.x,p.y+1));
                        stack.push(neo);


                    }
                }
                // Left Neighbor
                if (loc.x >= 0 && loc.x < grid.length && loc.y - 1 >= 0
                        && loc.y - 1 < grid.length) {
                    if (s.getVisited(new Point(p.x,p.y-1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() + 
                                grid[loc.x][loc.y - 1]);
                        neo.path.add(new Point(p.x,p.y-1));
                        stack.push(neo);

                    }
                }
                // Bottom-Right Neighbor
                if (loc.x + 1 >= 0 && loc.x + 1 < grid.length
                        && loc.y + 1 >= 0 && loc.y + 1 < grid.length) {
                    if (s.getVisited(new Point(p.x+1,p.y+1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() + 
                                grid[loc.x + 1][loc.y + 1]);
                        neo.path.add(new Point(p.x+1,p.y+1));
                        stack.push(neo);

                    }
                }

                // Bottom-Left Neighbor
                if (loc.x + 1 >= 0 && loc.x + 1 < grid.length
                        && loc.y - 1 >= 0 && loc.y - 1 < grid.length) {
                    if (s.getVisited(new Point(p.x+1,p.y-1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() +
                                grid[loc.x + 1][loc.y - 1]);
                        neo.path.add(new Point(p.x+1,p.y-1));
                        stack.push(neo);

                    }
                }

                // Top-Right Neighbor
                if (loc.x - 1 >= 0 && loc.x - 1 < grid.length
                        && loc.y + 1 >= 0 && loc.y + 1 < grid.length) {
                    if (s.getVisited(new Point(p.x-1,p.y+1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() +
                                grid[loc.x - 1][loc.y + 1]);
                        neo.path.add(new Point(p.x-1,p.y+1));
                        stack.push(neo);

                    }
                }

                // Top-Left Neighbor
                if (loc.x - 1 >= 0 && loc.x - 1 < grid.length
                        && loc.y - 1 >= 0 && -1 < grid.length) {
                    if (s.getVisited(new Point(p.x-1,p.y-1)) != true) {

                        BoggleSearchState neo = new BoggleSearchState(
                                new ArrayList<Point>(),s.getWord() +
                                grid[loc.x - 1][loc.y - 1]);
                        neo.path.add(new Point(p.x-1,p.y-1));
                        stack.push(neo);

                    }
                }
            }
        }
    }
    return foundWords;
}
}

BoggleSearchState:创建一个状态对象，用于存储游戏板上形成路径的字符串的每个实例的必要数据。包含实现其目的所需的方法。

import java.awt.Point;
import java.util.ArrayList;

public class BoggleSearchState {

private String word="";

public ArrayList<Point> path = new ArrayList<Point>();

public BoggleSearchState(ArrayList<Point>path, String word) {

    this.path = path;
    this.word = word;


}

  public String getWord() {


    return word;
}

public ArrayList<Point> getLocation() {


    return path;
}

public boolean getVisited (Point p) {

    ArrayList<Point> newPath = new ArrayList<Point>();
    for (Point s: path) {
        newPath.add(s);

        if (p.equals(s)) {
            return true;


        }

    }

    return false;
}

public String toString() {



    return this.word;
}

}

Boggle字典:为作业提供的字典课写得很糟糕。不过，它已经过测试并且功能齐全。

//  BoggleDictionary.java

import java.io.File;
import java.io.FileInputStream;
import java.io.ObjectInputStream;
import java.io.IOException;
import java.util.Scanner;
import java.util.HashSet;
import java.util.Iterator;

/** 
A class that stores a dictionary containing words that can be used in a
Boggle game.

@author Teresa Cole
@version CS221 Fall 2013
 */
    public class BoggleDictionary
    {
private HashSet<String> dictionary;

/** Create the BoggleDictionary from the file dictionary.dat
 */
@SuppressWarnings("unchecked")
public BoggleDictionary() throws Exception {
    ObjectInputStream dictFile = new ObjectInputStream(
            new FileInputStream( new File( "dictionary.dat")));
    dictionary = (HashSet<String>)dictFile.readObject();
    dictFile.close();
}

/** Check to see if a string is in the dictionary to determine whether it
 * is a valid word.
 * @param word the string to check for
 * @return true if word is in the dictionary, false otherwise.
 */
public boolean contains( String word)
{
    return dictionary.contains( word);
}

/** Get an iterator that returns all the words in the dictionary, one at a
 * time.
 * @return an iterator that can be used to get all the words in the
 * dictionary.
 */
public Iterator<String> iterator() 
{
    return dictionary.iterator();
}

/** 
 Main entry point
 */
static public void main(String[] args)  
{
    System.out.println( "BoggleDictionary Program ");

    Scanner kbd = new Scanner( System.in);
    BoggleDictionary theDictionary=null;
    try 
    {
        theDictionary = new BoggleDictionary();
    }
    catch (Exception ioe) 
    {
        System.err.println( "error reading dictionary");
        System.exit(1);
    }
    String word;

    /*
while (kbd.hasNext())
    {
    word = kbd.next();
    if (theDictionary.contains( word))
    System.out.println( word + " is in the dictionary");
    else
    System.out.println( word + " is not in the dictionary");
    }
     */

    Iterator<String> iter = theDictionary.iterator();
    while (iter.hasNext())
        System.out.println( iter.next()); 
}

}

我将不胜感激任何帮助，因为我现在真的很挣扎。我知道有很多方法可以实现其他数据结构或组织方法，以便在更高效的运行时完成此任务。然而，作业的关注点并不是效率，而是使用这些数据结构(堆栈等)的基本原则，以及理解如何能够走错误的方向，然后安全地回溯并在没有程序的情况下走上新的方向。崩溃了。预先感谢您，任何问题我都会尽快回答。

Answer 1

据我所知，WordSearch 中有两个网格，但您将它们都设置为初始化数组。您永远不会使用看起来像是在 main 方法中构建的网格。

但这很难说。

您向我们提供了很多数据，但信息却很少。我们不需要整个程序的详细信息，即使是这样大小的程序；我们需要知道您的具体问题是什么。没有人愿意为你调试这个，事实上很少有人会像我一样阅读它。

解决了初始化问题后，尽你所能调试你的程序并找出它在哪里做了(1)不应该做的事情，以及(2)你不理解的事情。您需要花费足够的时间尝试找出自己的调试教育中的#1，这使得您更有可能解释您不理解的内容并获得特定问题的良好答案。 “这不是构建字符串”还远远不够；它不是在哪里构建的，构建字符串是什么意思等等。我希望这是因为它没有输入，但我没有分析那么远。