Algoritmo para encontrar palavra a bordo Boggle

Question

Eu estou construindo um jogo boggle em VB.NET. Agora, meus dices são como uma matriz 2d (0,0 a 0,1) etc ...

O que eu quero fazer é, como eu estou escrevendo a palavra, que destaca que na placa usando o sub button(x,y).doclick que a destaca. Agora minha implementação encontra a primeira letra, em seguida, continua tentando cada letra até que ele atenda a condição 8 de canto (ou seja, é neighbored para a última), mas isso nem sempre funciona. Se houver dizer 2 "G" é na placa e eu quero que o fundo, isso não vai funcionar. Alguém pode me dar um exemplo de psuedocode do que precisa acontecer. Eu estive perplexo por quase 6 horas tentando descobrir isso. Graças

Answer 1

Se bem entendi, dada uma seqüência que você deseja destacar um caminho através dos dados que corresponde à cadeia. Às vezes, há várias opções possíveis, acrescentando assim uma letra pode mudar completamente o que é destacado. Pode ser uma boa abordagem aqui para manter os resultados do substring anterior, por isso não temos que começar de novo. Então uma coisa razoável a fazer seria para calcular todos os caminhos possíveis.

A resposta para uma determinada string s seria uma lista de caminhos, onde um caminho é uma lista de coordenadas de grade. Cada caminho é algo que você poderia razoavelmente destacar, então você apenas destacar o primeiro. Ao adicionar uma carta para a cadeia, você encontrar caminhos que você pode expandir e remover as que não pode expandir-se.

Eu tenho medo Eu não sei como escrever código vb. Desde que você pediu pseudocódigo, aqui está um pseudocódigo python-like áspero em seu lugar. Eu estou codificação da grade boggle como uma lista de 16 itens. Os vizinhos (x) devolve uma lista das posições vizinhos (exceto para casos de ponta que vai ser [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

Se os tipos de jogadores "go", por exemplo, em seguida, (A) tipos de jogadores "g", chamadas de código firstLetter ( "G") e recebe uma "resposta" lista de posições na grade que têm um "g" neles. Destaque, dizem, a primeira. (B) tipos de jogadores "O", código chama addletter (resposta, "o") e recebe uma lista dos caminhos na grade que dizer "ir". Mais uma vez, realce o primeiro.