In primo luogo, non sono necessariamente alla ricerca di un algoritmo completo che posso semplicemente copiare e incollare, quindi chiamarlo un giorno. Qualsiasi soluzione di "approccio generale" andrebbe bene per me!Genera un puzzle Zebra/Einstein generando algoritmo
Questo post è stato stimolato da una giornata di lavoro lento, e inciampato su this site e non essere in grado di capire come hanno implementato il loro generatore.
Il problema
Per quelli di voi che non conoscono, la "Zebra Puzzle" o "Puzzle di Einstein" è un famoso puzzle logico che probabilmente avete eseguito in prima.
L'intero articolo wiki è here, ma inserirò i bit pertinenti.
There are five houses.
The Englishman lives in the red house.
The Spaniard owns the dog.
Coffee is drunk in the green house.
The Ukrainian drinks tea.
The green house is immediately to the right of the ivory house.
The Old Gold smoker owns snails.
Kools are smoked in the yellow house.
Milk is drunk in the middle house.
The Norwegian lives in the first house.
The man who smokes Chesterfields lives in the house next to the man with the fox.
Kools are smoked in the house next to the house where the horse is kept.
The Lucky Strike smoker drinks orange juice.
The Japanese smokes Parliaments.
The Norwegian lives next to the blue house.
Now, who drinks water? Who owns the zebra? In the interest of clarity, it must be
added that each of the five houses is painted a different color, and their inhabitants
are of different national extractions, own different pets, drink different beverages
and smoke different brands of American cigarets [sic]. One other thing: in statement
6, right means your right.
Questo va tutto bene. Ho trovato diversi modi concisi e accurati online per risolvere questo problema, specialmente usando la programmazione dei vincoli. Tuttavia, ciò che mi interessa è rendere più di questi tipi di puzzle.
Fare più
Ovviamente, una rappresentazione matriciale è un modo logico pensare a questo. Con ogni colonna contenente una persona, casa, cosa bevono, che tipo di auto guidano, ecc.
Il mio pensiero iniziale era di iniziare con una griglia generata a caso che è completa (cioè risolta) quindi (in qualche modo) creare suggerimenti dalla versione risolta che lo identificano in modo univoco. Ogni volta che qualcosa può essere determinato, viene rimosso dalla griglia.
strappando il sito che ho elencato all'inizio, i seguenti "suggerimenti" che possono essere utilizzati per risolvere la griglia possono essere del seguente tipo:
La persona/animale/vegetale vive/cresce in una data casa
La persona/animale/pianta non vive/cresce in una data casa.
La persona/animale/pianta vive nella stessa casa degli altri persona/animale/pianta.
La persona/animale/pianta è un vicino diretto dell'altro persona/animale/pianta.
La persona/animale/pianta è il vicino di sinistra o destra di altri persona/animale/pianta.
C'è una casa tra la persona/animale/pianta e l'altra persona/animale/pianta.
C'è una casa tra la persona/animale/piano e l'altra persona/animale/pianta a sinistra oa destra.
Ci sono due case tra la persona/animale/pianta e l'altra persona/animale/pianta.
Ci sono due case tra la persona/animale/piano e l'altra persona/animale/pianta a sinistra oa destra.
La persona/animale/pianta vive a destra oa sinistra dell'altro persona/animale/pianta.
Si può vedere come questi potrebbero essere generalizzati, esteso, ecc;
La difficoltà è che, usando il mio approccio (partendo da una griglia completa e generando questi suggerimenti), non sono sicuro di come assicurarsi che il set di suggerimenti che creo sia assolutamente determinante nella griglia di destinazione.
Ad esempio, se si dice "L'inglese non possiede un albero di pino" non è possibile abbinare in modo decisivo due cose in un dato momento nel puzzle. Tuttavia, se ci fossero solo due alberi rimanenti da risolvere, questo potrebbe di fatto essere una prova decisiva.
Sto pensando a questo nel modo completamente sbagliato? Un approccio migliore sarebbe quello di creare una griglia con alcuni elementi noti, predefiniti e randomizzati (cioè, la casa rossa è nel mezzo) e quindi costruire la griglia usando questi suggerimenti come regole per la costruzione?
Qualsiasi consiglio, articoli da leggere, tecniche di programmazione per conoscere, ecc. Sarebbe molto apprezzato!
Post correlati: http://gamedev.stackexchange.com/questions/5909/data-structures-for-logic-games -deduction-rules-sufficienti-set-of-clues – greenoldman