Boggle 보드에서 단어를 찾는 알고리즘

Question

VB .NET에서 Boggle 게임을 구축하고 있습니다. 지금 내 다이스는 2D 어레이 (0,0 0,1) 등입니다 ...

내가 원하는 것은 단어를 입력 할 때 그것을 사용하여 보드에서 강조하는 것입니다. button(x,y).doclick 그것을 강조하는 서브. 지금 내 구현은 첫 번째 문자를 찾은 다음 8 코너 조건을 충족 할 때까지 각 글자를 계속 시도하지만 (즉, 마지막으로 이웃) 항상 작동하지는 않습니다. 보드에 2 "G"가 말하고 바닥을 원한다면 이것이 작동하지 않습니다. 누군가 나에게 무슨 일이 필요한지에 대한 psuedocode의 예를 제시 할 수 있습니까? 나는 이것을 알아 내려고 거의 6 시간 동안 걸려 넘어졌다. 감사

Answer 1

내가 올바르게 이해하면 문자열이 주어지면 문자열과 일치하는 주사위를 통해 하나의 경로를 강조하려고합니다. 때로는 몇 가지 가능한 선택이 있으므로 문자를 추가하면 강조 표시된 내용이 완전히 변경 될 수 있습니다. 이전 서브 스트링의 결과를 유지하는 것은 여기에서 좋은 접근법 일 수 있으므로 다시 시작할 필요가 없습니다. 그러면 합리적인 일은 가능한 모든 경로를 계산하는 것입니다.

주어진 문자열에 대한 답은 경로 목록이며, 여기서 경로는 그리드 좌표 목록입니다. 각 경로는 합리적으로 강조 할 수있는 경로이므로 첫 번째 경로를 강조 표시합니다. 문자열에 문자를 추가 할 때는 확장 할 수없는 경로를 찾을 수 있습니다.

VB 코드를 작성하는 방법을 모르겠습니다. 의사 코드를 요청했기 때문에 대신 거친 파이썬과 같은 의사 코드가 있습니다. Boggle 그리드를 16 개 항목 목록으로 코딩하고 있습니다. 이웃 (x) 함수는 이웃 위치의 목록을 반환합니다 ([x-1, x+1, x-4, x+4]가 될 가장자리 케이스 제외).

def firstLetter(typed):
  answer = []
  for pos in range(16): if grid[pos]==typed: answer += [pos]
  return answer

def addletter(partialanswer, typed):
  answer2 = []
  for partial in partialanswer:
      for neighbor in neighbors(partial[-1]):
          if grid[neighbor]==typed: 
             # partial+[neighbor] is a list. answer2 is a list of such lists.
             answer2 += partial + [neighbor]
  return answer2

예를 들어 플레이어가 "go"를 입력하면 (a) 플레이어 유형 "g", 코드는 FirstLetter ( "g")를 호출하고 그리드의 위치에 "g"가있는 위치의 "답변"목록을받습니다. . 첫 번째를 강조합니다. (b) 플레이어 유형 "o", 코드는 addletter (답변, "o")를 호출하고 "go"라고하는 그리드의 경로 목록을 가져옵니다. 다시, 첫 번째를 강조하십시오.