Algorithmus, um Wort auf Boggle Board zu finden

Question

Ich baue ein boggle Spiel in vb .net. Gerade jetzt, meine Würfel sind als 2d-Array (0,0 0,1) etc ...

Was ich will es ist, wie ich das Wort tippe, dass es es auf dem Brett mit markieren der button(x,y).doclick Sub, der es hervorhebt. Gerade jetzt findet meine Implementierung den ersten Buchstaben, dann versucht sie jeden Buchstaben weiter, bis sie die Bedingung der 8 Ecken erfüllt (dh sie ist benachbart zu der letzten), aber das funktioniert nicht immer. Wenn es 2 "G" 's auf dem Board gibt und ich will das untere, funktioniert das nicht. Kann mir jemand ein Pseudo-Beispiel geben, was passieren muss? Ich bin seit fast 6 Stunden ratlos, um das herauszufinden. Danke

Answer 1

Wenn ich richtig verstanden habe, eine Zeichenfolge gegeben, möchten Sie einen Weg durch die Würfel markieren, die der Zeichenfolge entspricht. Manchmal gibt es mehrere mögliche Auswahlmöglichkeiten, daher kann das Hinzufügen eines Buchstabens das markierte Element komplett ändern. Es kann ein guter Ansatz sein, die Ergebnisse der vorherigen Teilzeichenfolge beizubehalten, sodass wir nicht von vorne beginnen müssen. Dann wäre es vernünftig, alle möglichen Pfade zu berechnen.

Die Antwort für eine gegebene Zeichenfolge s wäre eine Liste von Pfaden, wobei ein Pfad eine Liste von Gitterkoordinaten ist. Jeder Pfad ist etwas, das du angemessen hervorheben kannst, also markiere einfach den ersten. Wenn Sie der Zeichenfolge einen Buchstaben hinzufügen, finden Sie Pfade, die Sie erweitern können, und solche, die Sie nicht erweitern können.

Ich fürchte, ich weiß nicht, wie man Vb-Code schreibt. Da du nach Pseudocode gefragt hast, hier ist ein rauer Python-ähnlicher Pseudocode. Ich kodiere das boggle-Raster als eine Liste von 16 Elementen. Die Funktion "Nachbarn (x)" gibt eine Liste der benachbarten Positionen zurück (außer bei Randfällen, die [x-1, x + 1, x-4, x + 4] sein werden).

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 

Wenn die Spielertypen „gehen“, zum Beispiel, dann (a) Spielertypen „g“, Code rufen first („g“) und bekommt eine Liste „Antwort“ der Positionen im Netz die ein "g" in ihnen haben. Markieren Sie, sagen wir, die erste. (b) player Typen "o", code Anrufe addletter (Antwort, "o") und erhält eine Liste der Pfade im Grid, die "go" sagen. Markieren Sie die erste noch einmal.