Boggle 솔버 구현

임의의 5x5 보드에서 모든 단어를 찾는 솔루션을 구현하는 데 어려움을 겪고 있습니다. 현재는 몇 마디이지만 거의 전체 목록은 아닙니다. 나는 내 문제가 find 루프와 함께 findWords 메소드 내에 있다는 것을 확신하지만 if 문을 8 가지 방향으로 계속 이동시키기 위해 무엇을해야 하는지를 알 수 없다.Boggle 솔버 구현

import java.io.File; 
import java.util.*; 
public class RandomWordGame { 

    private static char[][] board = new char[5][5]; 
    private static Random r = new Random(); 
    private static ArrayList<String> dictionary = new ArrayList<String>(); 

    private static char[][] createBoard() 
    { 
     for (int i=0; i<board.length; i++) 
     { 
      for (int j=0; j<board.length; j++) 
      { 
       board[i][j] = (char) (r.nextInt(26) + 'a'); 
       System.out.print(board[i][j]); 
      } 
      System.out.println(""); 
     } 
     System.out.println(); 
     return board; 
    } 
    public static ArrayList<String> solver(char[][] board) 
    { 
     if(board == null) 
      System.out.println("Board cannot be empty"); 
     ArrayList<String> words = new ArrayList<String>(); 
     for(int i=0; i<board.length; i++) 
     { 
      for(int j=0; j<board[0].length; j++) 
      { 
       findWords(i, j, board[i][j] + ""); 
      } 
     } 
     return words; 
    } 
    public static void findWords(int i, int j, String currWord) 
    { 
     try 
     { 
      Scanner inputStream = new Scanner(new File("./dictionary.txt")); 
      while(inputStream.hasNext()) 
      { 
       dictionary.add(inputStream.nextLine()); 
      } 
      inputStream.close(); 
     }catch(Exception e){ 
      e.printStackTrace(); 
     } 

     for(i=0; i>=0 && i<board.length; i++) 
     { 
      for(j=0; j>=0; j++) 
      { 
       currWord += board[i][j]; 
       if(currWord.length()>5) 
        return; 
       if(dictionary.contains(currWord)) 
        System.out.println(currWord); 
      } 
     } 
    } 
    public static void main(String[] args) 
    { 
     board = createBoard(); 
     ArrayList<String> validWords = RandomWordGame.solver(board); 
     for(String word : validWords) 
      System.out.println(word); 
    } 
}

출처

2016-11-12 JakeL

사전 파일의 모양은 무엇입니까? –

_ 현재는 몇 단어 만 반환하지만 전체 목록은 거의 없습니다 ... _ 객체'ArrayList words = new ArrayList ();'이 게시 된 코드 스 니펫에 채워지지 않으므로, 항목. –

for 루프에서 i와 j를 재 초기화 할 필요가 없습니다. 그것은 모든 것을 고치는 것은 아닙니다. 선형 방식으로 2D 배열을 반복하면 찾고있는 순열의 대부분을 놓치게됩니다. 또한 사전을 한 번 작성해야합니다. 기본 방법에서이 작업을 수행 할 수 있습니다. 지금 당신의 프로그램은 똑같은 사전을 25 번 리메이크합니다. –

이 코드로 재미있는 점이 몇 가지 있습니다. 하나는 솔버 메서드에서 항상 빈 ArrayList를 반환하지만 findWords에서 각 결과를 출력하기 때문에 죽이는 것이 아닙니다.

문제는 findWords 메소드가 퍼즐의 왼쪽 상단부터 문자를 계속 추가한다는 것입니다.

//i=0 and j=0 means it will always start at the top left tile 
for(i=0; i>=0 && i<board.length; i++) 
{ 
    for(j=0; j>=0; j++) 
    { 
     //currWord is never reset, so it just keeps getting longer 
     currWord += board[i][j]; 
     if(currWord.length()>5) 
      return; 
     if(dictionary.contains(currWord)) 
      System.out.println(currWord); 
    } 
}

는 지금 만 선택한 타일로 시작하는 단어를 발견하고, 문자의 나머지 부분은 왼쪽 상단부터 퍼즐에 추가 된 동일한 순서로 선택됩니다.

필자는 연필과 종이로 시간을 보내고 2 차원 배열 인덱스와 그리드에서의 위치 사이의 관계를 자세히 이해할 것을 권장합니다.

출처

2017-01-10 14:42:13

Boggle 솔버 구현

답변

관련 문제