Risoluzione della bacheca di Scrabble?

Question

Risoluzione della bacheca di Scrabble?

#1 da (5 voti)

5

Recentemente ho visto una domanda su SO riguardo la risoluzione del gioco scramble / boggle, in cui le lettere sono in una griglia 4x4 e devi trovare più parole possibili. Ho esaminato alcune soluzioni, l'ho provato personalmente e ora mi piacerebbe passare a risolvere un gioco a scrabble.

Il codice per risolvere i boggle è piuttosto semplice; memorizza lo stato della scheda in una matrice e itera su ogni mossa da ogni posizione e controlla se le parole esistono con la catena di lettere corrente.

Con scrabble, l'idea è simile, ma sto ancora avendo problemi a capirlo. Attualmente sto pensando:

Memorizzazione della scheda in serie bidimensionale.
Iterating su ogni posizione e salta se la posizione è vuota.
Creazione di una sorta di modello regex per le lettere sul rack e la lettera nella posizione ...

Sono ancora molto incerto sul da farsi al punto 3 perché so che la tessera nella posizione potrebbe essere la fine iniziale o un punto nel mezzo di una parola. E poi c'è il problema di fare in modo che, se una parola fa in modo che faccia anche le parole con le altre tessere che tocca ...

Non sto chiedendo campioni di codice, solo il processo di pensiero da parte di programmatori più esperti.

Per chiarire, il mio obiettivo è:

Given the current state of a board and a person's tiles, calculate the legal moves and the points for that move.

Per chi segue questo e in attesa di una risposta, ho trovato questo: link

Potrei dare un'occhiata a ciò che ha scritto, ma prima voglio provare a capirlo.

methodology

posta mowwwalker 01.02.2012 - 00:28

fonte

1 risposta

Leggi altre domande sui tag methodology

Le app iOS universali hanno più "problemi" quando escono le nuove versioni di iOS? Qual è la migliore tecnica per la gestione di bug e nuove funzionalità Con il controllo della versione in CVS / SVN per un team di 6-9 persone?

score 5 · Accepted Answer

Credo che tu abbia dimenticato la domanda stessa. Qual è il tuo intento?

Data una scacchiera con tessere già riempite, trova tutte le parole disponibili?
Oppure lascia che gli utenti giochino a Scrabble aggiungendo tessere e controllando il punteggio con ogni tessera aggiunta di recente?

Se è il primo punto, allora puoi:

Trasforma la tua board in un set di 30 array unidimensionali: uno contenente righe, un altro - le colonne.
Per ogni riga, passa attraverso le tessere nella riga, circondando la riga per spazio (caselle vuote) e quindi, sostituendo spazi bianchi consecutivi (caselle vuote). Ad esempio, "····stack··meta" diventerebbe "·stack·meta" .
Dividi quelli in parole. "·stack·meta" sarebbe ("stack", "meta") .
Controlla ogni parola con un dizionario.

Se è il secondo punto, non devi "scorrere su ogni posizione" (punto 2 nella tua lista). Cerca semplicemente le parole da una data posizione C _{a, b} :

In orizzontale, a partire da C _{a, 1} e camminando verso destra fino a C _{a, 15} ,
Verticalmente, a partire da C _{1, b} e camminando verso il basso fino a C _{15, b} .

Per semplificare, puoi creare due matrici unidimensionali come:

A₁ ( a ) → C _{a, n} , 1 ≤ n ≤ 15
A₂ ( b ) → C _{n, b} , 1 ≤ n ≤ 15

Quindi dovrai creare un singolo metodo che determinerà le parole esistenti date:

Un array unidimensionale (A₁ o A₂),
Una posizione a una dimensione del riquadro corrente nell'array.

Come? Vorrei iniziare isolando la parola stessa, cioè trovare il precedente e il successivo spazio bianco (cioè una tessera vuota), se presente. Quindi una parola formata deve essere controllata contro un dizionario. Quindi conti il punteggio, tenendo conto dei colori delle tessere e dei caratteri della tessera.

Esempio (usando una sintassi di una lingua immaginaria):

var A₁ = " stack overflow".ToArray(); // Given the one-dimension array...
var b = 4; // ... and the position of the current tile...
var leftEdge = A₁.Take(b).FindLast(' '); // Find the left empty tile,
var rightEdge = A₁.Skip(b).FindFirst(' '); // Then the right empty tile,
var word = A₁.Subset(leftEdge + 1, b + rightEdge - 1); // Then extract the word itself.
Assert.AreEquals("stack", word); // Found a good one?
bool isValidWord = word.IsInDictionary("en-US"); // Search the word in the dictionary.
Assert.IsTrue(isValidWord); // "stack" is a valid word.