Løse puslespill i .NET

[Spartakus]

Hei,

 

på jobben har vi noen små leketøy for hjernetrimmens del.

 

Et av de er et lite puslespill bestående av 6 brikker som tilsammen former en kube. Brikkene er utformet slik at de passer inn i hverandre, se vedlegg.

 

Såklart er det meningsløst å bruke maskinen til å løse slike ting, men det er interessant likevel å programmere det slik at maskinen gjør alt tankearbeidet Det var med samme innstilling jeg lagde en Sudoku-løser også, hehe

 

Jeg er usikker på hvordan man skal gå frem i det hele tatt. Jeg antar man må lage en Piece-klasse som holder på informasjon om alle de 4 sidene til en brikke, samt noen hjelpe-funksjoner for Rotate og Flip I tillegg ser jeg for meg en Cube-klasse som holder på informasjon om hvordan kuben er satt sammen av de 6 brikkene. Hver brikke må være identifiserbar med feks et nr. Her må det holdes styr på hvilke brikker som er brukt og hvordan de er satt inntil hverandre. Ved funnet løsning må programmet presentere dette til brukeren på en visuell måte slik at brukeren kan verifisere løsningen selv.

 

All logikken bør ligge i en CubeResolver-klasse som prøver å velge ut ledige brikker, snu og vende på de for å få de til å passe sammen. Når programmet finner ut at nåværende plassering av brikkene ikke mulig å løse slik de ligger, så må programmet bryte opp kuben og forsøke og legge de på en ny måte. Det er i allefall noe slik jeg ser for meg at den må jobbe. Noen som har noen tips til struktur/algoritmer evt pseudo-kode?

[GeirGrusom]

Hver brikke kan deles inn et 5x5 rutenett med fire ulike representasjoner. Deretter kan en bruke en genetisk algoritme, eller brute force for å løse det.

[torbjørn marø]

Hver brikke kan deles inn et 5x5 rutenett med fire ulike representasjoner. Deretter kan en bruke en genetisk algoritme, eller brute force for å løse det.

Ikke glem at du kan vende brikkene, så da blir det åtte ulike representasjoner.

 

Forslag (brute force):

 

• Lag en Solution-klasse som holder på seks brikker (Piece) i bestemte posisjoner. Brikkene kan selv holde på representasjoner.
  
• Lag en lazy sequence av alle permutasjoner av brikkenes ulike representasjoner og plassering i forhold til hverandre - IEnumerable<Solution> AllPossibleSolutions()
  
• Lag en bool Validate() metode på Solution som finner ut om denne er gyldig. Dette er kanskje det vanskeligste...
  
• Lag en enkel while-loop som plukker en og en solution, validerer, og returnerer om en er gyldig.
  
• Eventuelt kan du bruker Linq og si AllPossibleSolutions().Where(s => s.Validate()) for å finne alle gyldige løsninger.
  

 

Og så trenger du bare implementere visningsfunksjonaliteten for Piece og deretter Solution.

 

UPDATE:

 

AllPossibleSolutions() bør kanskje eventuelt ta inn de seks brikkene (som er tilgjengelig) som parametre, slik at den kan gjenbrukes for ulike kuber.

 

UPDATE 2 - PRO TIP:

 

Testdreven utvikling vil være til stor hjelp når man skal implementere Validate().

Endret 13. juli 2011 av torbjørn marø

[MailMan13]

Vet ikke om jeg ville enumerert alle sånn. Bør validere delløsninger underveis slik at man kan kaste deler av løsningstreet så nært roten som mulig.

 

Alle løsninger blir vel fort 5! * 8^5 = 4*10^6 mulige løsninger i den enumeratoren. Mulig det er såpass mange muligheter at man treffer en ganske raskt likevel?

 

Eller at jeg tar fullstendig feil her, holder en brikke i ro blir det 5! permutasjoner av resten, og 8^5 kombinasjoner av orientasjoner for hver av dem igjen?

 

Jeg ville sett løsningsområdet som et tre.

- Et nivå er en posisjon

- En node er en brikke i en gitt orientasjon.

- Brikken du holder i ro er roten.

- Hver n+1 branch er de posisjoner som er tillatt i kombinasjon med alle nodene over seg

- Alle noder i 6-nivå i treet lovlige løsninger.

 

Da trenger å definere

- Validate for å finne ut om et barn er gyldig,

- En metode for å finne første barn for en delløsning,

- En metode for å finne neste søsken for en delløsning

- Finne forste lovlige løsning med dybde først søk ved hjelp av "første barn" og "neste søsken"-metodene.

Endret 13. juli 2011 av MailMan13

[GeirGrusom]

Vet ikke om jeg ville enumerert alle sånn. Bør validere delløsninger underveis slik at man kan kaste deler av løsningstreet så nært roten som mulig.

 

Alle løsninger blir vel fort 5! * 8^5 = 4*10^6 mulige løsninger i den enumeratoren. Mulig det er såpass mange muligheter at man treffer en ganske raskt likevel?

 

Eller at jeg tar fullstendig feil her, holder en brikke i ro blir det 5! permutasjoner av resten, og 8^5 kombinasjoner av orientasjoner for hver av dem igjen?

 

Jeg ville sett løsningsområdet som et tre.

- Et nivå er en posisjon

- En node er en brikke i en gitt orientasjon.

- Brikken du holder i ro er roten.

- Hver n+1 branch er de posisjoner som er tillatt i kombinasjon med alle nodene over seg

- Alle noder i 6-nivå i treet lovlige løsninger.

 

Da trenger å definere

- Validate for å finne ut om et barn er gyldig,

- En metode for å finne første barn for en delløsning,

- En metode for å finne neste søsken for en delløsning

- Finne forste lovlige løsning med dybde først søk ved hjelp av "første barn" og "neste søsken"-metodene.

Problemet er dog at selv om en brikke passer, betyr ikke det at den står på riktig plass, med mindre alle sider passer?

Tror kanskje en genetisk algoritme er beste fremgangsmåte dersom det er såpass mange permutasjoner.

[MailMan13]

4 mill er ikke så vanvittig svært at det ikke skulle gå fint. Den lar seg nok brute-force uten cutoffs også om man har litt tid til å vente.

 

Trenger bare cutoffs som skjærer det ned en størrelsesorden eller to, så lar seg sjekke rimelig raskt. Sett at en av fire kanter passer sammen vil man redusere løsningsrommet til en fjerdedel for det første nivået, 1/4^k, hvor k er antall naboer på plass for de neste, med forslaget mitt. Vil tro det skulle gi akseptabel løsningstid. 4 er tatt ut av luften, kanskje det er 3, eller 10, eller noe i mellom, trenden blir mye den samme.

 

Usikker på hvordan du mener en genetisk algoritme takler det bedre. Dem fine på optimeringsproblemer hvor man kan akseptere en heuristisk løsning. I dette tilfelle hvor man har et sett deterministisk riktige løsninger og alle andre er gale, hvordan lager du en genetisk algoritme som i det heletatt klarer å lande på en av de riktig løsningene innen rimelig tid?

 

Nå er det en stund siden heuristiske optimeringsmetoder på høyskolen, så det er mulig jeg er i overkant rusten på dette, men jeg ser ikke helt hvordan du mener en genetisk algoritme skal kunne løse et slikt problem spesielt godt...

Endret 13. juli 2011 av MailMan13

[MailMan13]

Ok, får ikke sove her, blir bare å gruble på hvor mange iterasjoner som trengs, jo mer jeg tenker over det, jo mindre kommer jeg frem til at det trengs. Forsåvidt, tre-prasing pleier å være logaritmisk av natur...

 

Antar et tre som beskrevet i min første post, og 6 biter, 8 orientasjoner og 1 av 4 kanter passer sammen.

 

Hvorfor 1/4? Worst case er at alle bitene er like, da vil alle av kantene gå sammen i en av orientasjonene, og bomme i den andre (1/2), best case at bitene kun passer der dem må være i løsningen (1 / 24). 1/4 virker plausibelt, lavt nok til å være problematisk uten at alle bitene trenger å være nesten like.

 

Da blir det noe sånt (tallene gir nok ikke mye mening for de 2 siste nivåene, da er dem blitt så små at det ikke gir så mye mening å regne på dem slik lenger.)

 

Nivå 1: Rot, her velger vi en fast brikke:

- 1 gren

- 0 valideringer

- 4 000 000 potensielt tillatte løsninger igjen

 

Nivå 2: Velger en nabo til første brikke: 5 brikker igjen i 8 oriantasjoner for hver gren å prøve

- 10 grener (40 mulige, 1/4 lovlige)

- 40 valideringer utført

- 1 000 000 potensielt tillatte løsninger igjen

 

Nivå 3: Velger en posisjon som er nabo til begge eksisterende posisjonene. 4 brikker igjen, 8 orientasjoner.

- 30 grener (320 mulige, 1/4^2 lovlige)

- 360 valideringer utført (40 + 160 nye)

- 62 500 tillatte løsninger igjen

 

Nivå 4: Igjen har vi en posisjon med 2 naboer. 3 brikker igjen, 8 posisjoner, 1/4^2 er lovlige.

- 45 grener (720 mulige, 1/4^2 lovlige)

- 1080 valideringer utført (360 + 720 nye)

- 4 000 potensielt tillatte løsninger igjen

 

Nivå 5: Nå har vi en posisjon med 3 naboer. 2 brikker, 8 posisjoner, 1/4^3 er lovlige

- 11 grener (720 mulige, 1/4^3 lovlige)

- 1800 valideringer

- 800-ish potensielt lovlige løsninger igjen

 

Nivå 6: Siste posisjon har 4 naboer, 1 brikke per gren igjen, kun lovlige løsninger gjenstår.

- her finner vi alle løsnigene

- 2000ish valideringer

- Kun lovlige løsninger igjen.

 

Så, ca 2000 delløsninger som skal valideres før løsningsområdet er redusert til kun tillatte løsninger. Mindre enn jeg så for meg tbh.

Endret 14. juli 2011 av MailMan13

[GeirGrusom]

Hmmm ja, da går det jo ganske radig ^^