Mahjong: disponi le tessere per garantire almeno un percorso verso la vittoria, indipendentemente dal layout

Question

Indipendentemente dal layout utilizzato per le tessere, c'è un buon modo per dividere le tessere in modo da poter garantire all'utente che, all'inizio del gioco, esiste almeno un percorso per completare il puzzle e vincere la partita?

Ovviamente, a seconda delle mosse dell'utente, possono impedirsi di vincere. Voglio solo essere in grado di dire sempre all'utente che il puzzle è vincibile se giocano bene.

Se posizioni casualmente le tessere all'inizio del gioco, è possibile che l'utente possa fare alcune mosse e non essere più in grado di farlo. La consapevolezza che un puzzle è almeno risolvibile dovrebbe renderlo più divertente da giocare.

Answer 1

Metti tutte le tessere al rovescio (es. layout fuori dal tabellone a partire dal centro, lavorando)

Per stuzzicare ulteriormente il giocatore, potresti farlo visibilmente ma ad altissima velocità.

Answer 2

Gioca al contrario.

Disporre casualmente i pezzi coppia per coppia, in punti in cui è possibile farli scorrere nell'heap. Avrai bisogno di un modo per sapere dove ti è permesso posizionare i pezzi per finire con un mucchio che corrisponde ad un modello predefinito, ma ti servirà comunque.

Answer 3

So che questa è una vecchia domanda, ma mi sono imbattuto in questo quando ho risolto il problema da solo. Nessuna delle risposte qui è del tutto perfetta, e molte di esse presentano avvertimenti complicati o si rompono su schemi patologici. Ecco la mia soluzione:

Risolvi la scheda (avanti, non indietro) con tessere non contrassegnate. Rimuovi due tessere gratuite alla volta. Spingi ogni coppia che rimuovi su una "coppia abbinata" " pila. Spesso, questo è tutto ciò che devi fare.

Se ti imbatti in un vicolo cieco (numFreeTiles == 1), resetta il tuo generatore :) Ho scoperto che di solito non raggiungo i vicoli ciechi e finora ho un numero massimo di tentativi di 3 per il 10- o così layout che ho provato. Dopo aver fatto 8 tentativi, mi arrendo e assegno casualmente il resto delle tessere. Ciò mi consente di utilizzare lo stesso generatore sia per l'impostazione della scheda, sia per la funzione shuffle, anche se il giocatore ha sbagliato e ha fatto uno stato irrisolvibile al 100%.

Un'altra soluzione quando si raggiunge un vicolo cieco è tornare indietro (espellere la pila, sostituendo le tessere sul tabellone) fino a quando non si può prendere una strada diversa. Prendi un percorso diverso assicurandoti di abbinare le coppie che rimuoveranno la tessera di blocco originale.

Sfortunatamente, a seconda della scheda, questo può essere ripetuto per sempre. Se finisci per rimuovere una coppia che assomiglia a un "nessun outlet" strada, dove tutte le successive "strade" sono un vicolo cieco e ci sono più vicoli ciechi, il tuo algoritmo non verrà mai completato. Non so se è possibile progettare una scheda in cui questo sarebbe il caso, ma in tal caso, c'è ancora una soluzione.

Per risolvere quel problema più grande, considera ogni possibile stato della scheda come un nodo in un DAG, con ogni coppia selezionata che è un bordo su quel grafico. Esegui un attraversamento casuale, fino a quando non trovi un nodo foglia a profondità 72. Tieni traccia della cronologia degli attraversamenti in modo da non ripetere mai una discesa.

Poiché i vicoli ciechi sono più rari delle soluzioni di prima prova nei layout che ho usato, quello che mi viene subito in mente è una soluzione ibrida. Prima prova a risolverlo con memoria minima (archivia le coppie selezionate sul tuo stack). Una volta che hai raggiunto il primo vicolo cieco, degrada a fare marcatura completa / generazione di spigoli quando visiti ciascun nodo (valutazione pigra ove possibile).

Tuttavia, ho fatto pochissimi studi sulla teoria dei grafi, quindi forse c'è una soluzione migliore al problema di attraversamento / ricerca casuale DAG :)

Modifica: potresti effettivamente utilizzare una qualsiasi delle mie soluzioni con la generazione della scheda al contrario, post del 13 ottobre 2008. Hai ancora gli stessi avvertimenti, perché puoi ancora finire con vicoli ciechi. Generare una tavola al contrario ha regole più complicate, però. Ad esempio, si è certi di non riuscire a eseguire l'installazione se non si avvia almeno ALCUNE delle righe con il primo pezzo nel mezzo, come in un layout con 1 riga lunga. Scegliere una prima mossa completamente casuale (legale) in un generatore di soluzioni avanzate è più probabile che porti a un consiglio risolvibile.

Answer 4

L'unica cosa che sono stato in grado di inventare è di posizionare le tessere in coppie corrispondenti come una specie di solitario Mahjong al contrario. Quindi, in qualsiasi momento durante il posizionamento delle tessere, il tabellone dovrebbe apparire come nel mezzo di un gioco reale (cioè nessuna tessera che galleggia 3 strati sopra le altre tessere).

Se le tessere sono posizionate in coppie corrispondenti in una partita inversa, dovrebbe sempre risultare almeno un percorso in avanti per risolvere il gioco.

Mi piacerebbe sentire altre idee.

Answer 5

Credo che la risposta migliore sia già stata spinta verso l'alto: creare un set risolvendolo " al contrario " - ovvero iniziare con una tavola vuota, quindi aggiungere una coppia da qualche parte, aggiungere un'altra coppia in una posizione risolvibile e così via ...

Se preferisci " Big Bang " approccio (generando l'intero set in modo casuale all'inizio), sono uno sviluppatore macho o semplicemente ti senti masochista oggi, potresti rappresentare tutte le coppie che puoi estrarre dal set dato e come dipendono da ciascuna altro tramite un grafico diretto.

Da lì, dovresti solo ottenere la chiusura transitiva di quel set e determinare se esiste almeno un percorso da almeno una delle coppie legali iniziali che porta all'estremità desiderata (nessuna coppia di tessere rimasta).

L'implementazione di questa soluzione è lasciata al lettore come esercizio: D

Answer 6

Ecco le regole che ho usato nella mia implementazione.

Quando si costruisce un mucchio, per ogni tasto in una coppia separatamente, trovare una cella (luoghi), che sono:

• ha già riempito tutte le celle ai livelli inferiori
• il posto per il secondo tasto non si blocca per primo, considerando se il primo tasto è già inserito a bordo
• entrambi i punti sono " ai bordi " di heap già costruito:
  • EITHER ha almeno un vicino di casa sul lato sinistro o destro
  • O è il primo tasto di seguito (tutte le celle a destra e a sinistra sono ricorsivamente libere)

Queste regole non garantiscono che una build abbia sempre successo: a volte lascia le ultime 2 celle libere autobloccanti e la build deve essere ritentata (o almeno gli ultimi tasti) In pratica, "tartaruga" incorporato in non più di 6 tentativi.

La maggior parte dei giochi esistenti sembra limitare il primo ("primo sulla riga") da qualche parte nel mezzo. Questo si presenta con configurazioni più convenienti, quando non ci sono tasti ai bordi di file molto lunghe, rimanendo in piedi fino a quando l'ultimo giocatore si muove. Tuttavia, "medio" è diverso per diverse configurazioni.

Buona fortuna :)

P.S. Se hai trovato un algoritmo che crea un mucchio risolvibile in un turno, per favore fatemelo sapere.

Answer 7

Hai 144 tessere nel gioco, ognuna delle 144 tessere ha un elenco di blocchi. (il riquadro superiore in pila ha un elenco di blocchi vuoto)

Tutte le mosse valide richiedono che il loro " current__vertical_Block_list " essere vuoto .. questa può essere una matrice 144x144, quindi 20k di memoria più un elenco di blocchi SINISTRA e DESTRA, anche 20 k ciascuno.

Genera una tabella di spostamento valida da (remaning_tiles) AND ((ELENCO BLOCCO VERTICALE CORRENTE vuoto) e ((ELENCO BLOCCO SINISTRA CORRENTE vuoto) O (vuoto ELENCO BLOCCO DESTRA CORRENTE)))

Scegli 2 tessere casuali dalla tabella delle mosse valide, registrale Aggiorna le (tabelle correnti Vert, sinistra e destra), registra le tessere rimosse in una pila

Ora abbiamo un elenco di mosse che costituiscono un gioco valido. Assegna i tipi di tessere corrispondenti a ciascuna delle 72 mosse.

per i giochi più impegnativi, traccia quando ogni tessera diventa disponibile. trova i set che sono (inizio presto inizio tardi) e (fine ritardo tardi inizio) poiché è vuoto, trovi 1 blocchi EE 1 LL e 2 LE .. del blocco 2 LE, trova un EARLY che blocca QUALSIASI altro EARLY che ( eccetto il blocco a destra di un pezzo laterale sinistro)
Una volta ottenuto un gioco valido, gioca con l'ordinazione.

Answer 8

Solitaire? Solo una supposizione, ma suppongo che il tuo computer avrebbe bisogno di battere il gioco (o vicino ad esso) per determinare questo.

Un'altra opzione potrebbe essere quella di avere diversi layout preimpostati (che consentono di vincere, mescolati con il tuo livello attuale.

In una certa misura potresti provare ad assicurarti che una delle 4 tessere non sia più di X strati sotto un'altra X.

La maggior parte dei giochi che vedo hanno il comando shuffle per quando qualcuno rimane bloccato.

Vorrei provare un mix di cose e vedere cosa funziona meglio.