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

Question

vb.net에서 boggle 게임을 만들고 있습니다. 지금, 내 오지는 2 차원 어레이 (0,0 0,1) 등으로되어 있습니다 ...

내가 원하는 것은, 내가 단어를 입력 할 때 보드에서 강조 표시합니다. 그것을 강조하는 button(x,y).doclick 하위. 현재 구현은 첫 번째 문자를 찾은 다음 각 모서리 조건을 충족 할 때까지 계속 시도합니다 (즉, 마지막 모서리와 인접 해 있음). 그러나 항상 작동하지는 않습니다. 보드에 2 개의 "G"가 있다고 가정하면 하단의 것을 원한다면 작동하지 않습니다. 누군가 나에게 어떤 일이 일어날 지에 대한 사례 코드 (psuedocode)를 줄 수 있습니까? 나는 이것을 알아 내려고 거의 6 시간 동안 곤란을 겪었다. 고마워요

Answer 1

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

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

VB 코드를 작성하는 방법을 모르겠다. 당신이 의사 코드를 요구 했으므로, 대신 여기에 거친 파이썬과 같은 의사 코드가 있습니다. 나는 16 개의 아이템 목록으로 boggle grid를 코딩하고있다. 이웃 (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 

플레이어 유형은 "이동"경우, 예를 들어, 다음 (a)는 플레이어 유형 "g"는 코드 ("g") firstLetter에 호출하고 그리드 위치의 목록 "대답을"얻는다 그 안에는 "g"가 있습니다. 첫 번째 강조 표시합니다. (b) 플레이어 유형 "o", 코드는 addletter (답변, "o")를 호출하고 그리드에서 "go"라고 말한 경로 목록을 가져옵니다. 다시 한 번 강조 표시합니다.