Algoritmo del Checker della soluzione per un gioco

0

Per il momento sto parlando in senso stretto in Pseudocode. Mi piacerebbe solo vedere se sono sulla strada giusta. Il gioco di cui sto parlando è simile a un'applicazione chiamata FLOW.
In questo gioco, ti viene assegnata una scheda nxn (sempre un quadrato) e devi compilare ogni slot nel tabellone. Allo stesso modo, quando un gioco da tavolo viene inizializzato, avrà oggetti come l'impostazione sotto ...

Board - 1 2 3 1
        0 0 0 0
        0 2 3 0
        0 0 0 0

In questo esempio: gli oggetti sono 1 2 e 3.

Una soluzione sarebbe la seguente ...

Board - 1 2 3 1
        1 2 3 1
        1 2 3 1 
        1 1 1 1

L'intero scopo è compilare il gioco da tavolo collegando l'oggetto iniziale all'oggetto finale. Quello che ho in mente è il seguente ...

CheckSolution(1d representation of the boards state, int totalcolors) {

  // I would loop through the colors, a 0 is not a color - empty. 
  // If the board has a 0 in the array, I would automatically return a false solution. 
  // Then, I would call DepthFirstSearch on the color. 
       // -- I would set a counter on this to count the # of colors, if this isn't equal to the total # of that particular color, I would return false.   
  // Else, the solution is valid.
}

Suona ragionevole? O è il modo migliore per implementare un correttore di soluzione.

    
posta user2908101 17.03.2014 - 19:14
fonte

2 risposte

1

In base al flusso , le regole dicevano:

Simple, but fun HTML5 puzzle game. Connect the dots by drawing a line with the mouse between the two dots with matching colors. Lines can not cross and you must fill in every square to completely solve the puzzle. Game features fun audio and 150 different levels. Not to difficulty to beat, but fun to play through once or twice.

L'approccio di riempimento non tiene conto del fatto che esiste una singola linea che deve collegare gli spot e può accettare soluzioni non valide.

Considera il puzzle:

1 . . .
2 3 . .
. 3 . .
. . 2 1

L'approccio di riempimento pieno accetterà tutto:

1 1 1 1    1 1 1 1    1 1 1 1
2 3 1 1    2 3 3 1    2 3 2 1
2 3 1 1    2 3 3 1    2 3 2 1
2 2 2 1    2 2 2 1    2 2 2 1

come valido. Tuttavia, solo il mezzo è una soluzione valida per il puzzle perché non è stata disegnata alcuna linea per connettere i 3 attraverso altre celle negli altri due. Inoltre, i 2 non sono finiti nel punto giusto su quello a destra.

In quanto tale, il cercatore di soluzioni non è corretto. Ha bisogno dello stato iniziale del puzzle, la soluzione, e idealmente il percorso è stata tracciata la linea per determinare se una determinata soluzione è valida o meno.

    
risposta data 17.03.2014 - 19:55
fonte
1

Il tuo algoritmo è sostanzialmente OK (anche se potresti averlo espresso molto meglio ...), se contrassegni tutte le celle visitate (ad es. impostandole su 0).

Puoi avviare la ricerca (equivalente a un riempimento pieno) durante la scansione della matrice, non è necessario effettuare due passaggi.

Non penso che ci sia un modo per evitare il "riempimento dell'inondazione".

Modifica

Per quanto riguarda il "conteggio", dovrai piuttosto controllare che ogni colore sia riempito solo una volta. Quindi, sarebbe meglio allocare una matrice di booleani che ti dice se un colore è stato "riempito" o meno, inizializzato in falso. Quindi, ogni volta che trovi un nuovo inizio per un riempimento, per prima cosa controlla se quel colore non è già stato visto - se lo ha, non è una soluzione. L'unica cosa che vale la pena di contare è il numero di riempimenti. Invece di controllare se l'array è "tutti i trues" alla fine, puoi verificare di aver completato totalcolors fills.

    
risposta data 17.03.2014 - 19:23
fonte

Leggi altre domande sui tag