Søg
Avatar billede dr1zz Nybegynder
29. december 2007 - 01:37 Der er 11 kommentarer og
1 løsning

Advanceret Pentominoes solver

Hej,

Jeg arbejder for tiden på en løser til et spil, der på mange måder minder om det gamle spil Pentominoes, den letteste måde at  forklare det på er nok at henvise til en video der demonstrerer der: http://www.youtube.com/watch?v=4dErhPEqkyw

Formålet med spillet er at udfylde en række huller, med de brikker man får tildelt. Formen på disse brikker bliver bestemt udfra et procent system (Der er f.eks. større chance for at få en "P" brik end en "X" brik). Disse brikker skal roteres og spejlvendes, så de fylder hullerne ud, uden at overlappe hinanden og gå over hullernes kanter.

Jeg har de seneste par dage siddet og læst op på Pentominoes løsere, men uden at være i stand til at implementere en ordentlig, effektiv løser (en løsning skal gerne være fundet indenfor 2 sec, mit nuværende forsøg tager over 30+ sec hvis der skal bruges mere end 3 brikker til et hul).

Mit nuværende løsningforsøg fungerer ved at jeg opretter en arraylist over brikker, først de tre jeg har til rådighed, herefter 2 af alle slags brikker, med dem der har størst chance for at komme først. Herefter ligger jeg rekursivt brikkerne i hullet, for hver brik laver jeg en arrayliste over alle mulige huller med denne brik uden overlap, og disse huller bliver herefter testet med den næste brik, og så videre.

Dette er selvsagt ikke særlig effektivt, på et stort hul (10+ brikker) tager den længere tid end jeg gider lade den køre om at løse det.

Derfor beder jeg nu jer om hjælp, hvis i har en smart måde at gøre det på, eller gode tips til hvordan jeg ellers kan gøre det, vil jeg hjerteligt gerne høre fra jer.

Med venlig hilsen,
Dr1ZZ
Avatar billede md_craig Nybegynder
02. januar 2008 - 14:15 #1
Yderst spændende...

Et lille link til folket: http://en.wikipedia.org/wiki/Pentomino

Jeg er ikke helt sikker på jeg har gennemskuet din fremgangsmåde i forhold til det spil du viser hvor brikker udtrækkes løbende og man ikke har alle til rådighed fra starten (som man har i nogle af disse spil, rimelig logisk når de fås i små håndudgaver)...

Sider lige på arbejde nu, ved ikke om du ønsker at dele din løsning som den er nu, og evt. lidt mere dubdegående hvor dine kilder er samt hvorfor du har valgt at gå frem som du har... altså udybe:

"Mit nuværende løsningforsøg fungerer ved at jeg opretter en arraylist over brikker, først de tre jeg har til rådighed, herefter 2 af alle slags brikker, med dem der har størst chance for at komme først. Herefter ligger jeg rekursivt brikkerne i hullet, for hver brik laver jeg en arrayliste over alle mulige huller med denne brik uden overlap, og disse huller bliver herefter testet med den næste brik, og så videre."

Mere specielt med hvorfor sådan?...
Avatar billede dr1zz Nybegynder
02. januar 2008 - 16:02 #2
Spillet er ikke et Pentomino spil, men derimod et spil, baseret på Pentomino, undskyld hvis overskriften er misledende.

Den største forskel er, at I dette spil (der forøvrigt hedder Carpentry) har man kun 3 brikker til rådighed af gangen, når man bruger en får man en ny, formen på den nye bliver som sagt valgt ud fra nogle procentsatser. Dette gør også at i stedet for at absolut være tvunget til at bruge en af hver slags brik, kan man her sagtens bruge flere af den samme form.

Min nuværende løsningsmåde er yderst ineffektiv og langsom, jeg kan godt poste en detaljeret gennemgang og dens kode hvis du ønsker det, men jeg er selv overbevist om at der skal findes en anden måde at gøre det på.
Avatar billede md_craig Nybegynder
02. januar 2008 - 16:21 #3
Ja jeg tror egentlig den første den af mit spørgsmål var om det var sigtet at din løser skulle gå efter det linkede spil, eller hvad er strategien. der er jo mange Pentomino inspirerede spil (som tetris desuden er et af selv om det bruger 4 bloks tetrominoes)...

Men kigger du på de små "hånd-spil" som man kan købe som igen er inspireret fra samme koncept, så er alle tilgængelige brikker jo her tilgængelige på forhånd, desuden passer det med at alle brikker skal bruges for at danne typisk et kvadrat.

men umiddelbart som jeg læser dit går du jo efter at løse et problem hvor du i samme stil hele tiden får nye brikker?, eller hvertfald måske har flere brikker end du skal bruge?... (som med spillet)...

Typisk vil man jo bryde problemet ned i mindre problemer som en første indgangsvinkel, som det lyder som om du gør ved at kører rekursivt, efterhånden som man fylder brikker i vil der opstå mange mindre "huller" at udfylde, det du specielt kan være opmærksom på her er at du måske mange gange vil ståde på at skulle løse samme "sub-hul", dette kan du lige så godt elemineere ved at gemme løsninger under vejs.

Men det lyder jo lidt ala det du gør...
Avatar billede dr1zz Nybegynder
02. januar 2008 - 16:39 #4
Hvis du ikke har mulighed for at se youtube vidoen, kan dette screenshot måske hjælpe med bedre at forstå spillet: http://www.puzzlepirates.com/content/images/Carpentry_board.jpg

Det er noget ala det jeg gør ja, men mængden af sub-huller bliver hurtig alt for enorm. Det største problem med denne løsning er at jeg ikke kan finde på en metode at tjekke om et hul stadig er en mulig løsning efter man har lagt brikken. Det sker nemlig ofte at når den lægger en brik i hullet, er den lagt således at hullet ikke længere kan løses med de slags brikker der findes. Hvis jeg kunne finde på en måde der kan gøre dette effektivt vil det kunne nedsætte mængden af sub-huller væsentligt, måske endda nok til at denne måde bliver effektiv.
Avatar billede md_craig Nybegynder
02. januar 2008 - 18:26 #5
Jeg kan godt se videoen... derfor jeg egentlig efterlyser en tydelig beskrivelse af hvordan du ønsker det skal kører... som spillet?... (for så forstår jeg ikke din fremgang)... eller som et rigtigt fysisk inspireret puzzle? (så forstår jeg heller ikke fremgangsmåden)

Ja, hvordan lagre du sådan er problem, for for det kan lagres så det kræver utrolig lidt plads... (64 huller kan ligges i en long, 8 bytes)
Avatar billede md_craig Nybegynder
02. januar 2008 - 18:30 #6
http://godel.hws.edu/java/pent1.html er evt kilde til inspiration... dog er det igen en anden vinkel på problemet
Avatar billede dr1zz Nybegynder
02. januar 2008 - 22:27 #7
Ah ok så er jeg med :)

Det jeg er på jagt efter, er den løsning der har størst mulighed for at
Avatar billede dr1zz Nybegynder
02. januar 2008 - 22:33 #8
Hmn ramte lige send for tidligt :p

Det jeg er på jagt efter, er den løsning der er størst mulighed for at ville lade sig gøre (ved at bruge de brikker der har størst chance for at fremkomme, men kun et par af hver slags, da chancen for 3+ ens i træk ikke er særlig høj). I sidste ende vil jeg forsøge at lave en bot til spillet, men først og fremmest vil jeg lære det selv, og ved at bruge en metode til at køre fiktive huller igennem, vil jeg lære hvordan man teoretisk bedst kan opbygge hullerne :)

Jeg har før kigget på den side du postede, og hans kode virker meget meget effektiv, men det er rodet java kode (et sprog jeg aldrig har arbejdet med), jeg har svært ved at finde hoved og hale i hvad han gør.
Avatar billede dr1zz Nybegynder
05. januar 2008 - 00:25 #9
Jeg er godt klar over dette ikke er noget let, hurtigt spørgsmål, jeg giver gerne 200 point oven i hvis der er en der kan komme med en brugbar måde at gøre det på :)
Avatar billede md_craig Nybegynder
05. januar 2008 - 16:30 #10
Nej det er ikke noget let og hurtigts spørgsmål ^^... det kommer til at tage noget tid at kigge på for hvem end der gør... så tror du må have lidt tålmodighed...

apropos Java, så er Java ~ C#... de to sprog er utrolig ens, så det burde være til at forstå for dig, den største forskel er .NET Framework vs. Java SDK når man ser på overfladen... så der skal man bare lige se i Java SDK hvad der er de bruger hvis de bruger en klasse fra SDK'et, så er der 95% garanti for man kan finde en der ligner i .NET...

Jeg kigger videre men er også en af dem der er meget klæmt på tid...
Avatar billede dr1zz Nybegynder
19. januar 2008 - 19:52 #11
Jeg opgiver projektet og lukker. Men tak for hjælpen Craig.
Avatar billede md_craig Nybegynder
19. januar 2008 - 22:15 #12
intet problem... :)
Avatar billede Ny bruger Nybegynder

Din løsning...

Tilladte BB-code-tags: [b]fed[/b] [i]kursiv[/i] [u]understreget[/u] Web- og emailadresser omdannes automatisk til links. Der sættes "nofollow" på alle links.

Loading billede Opret Preview
Kategori
Se alle it-kurser fra Computerworld Kurser
IT-kurser om Microsoft 365, sikkerhed, personlig vækst, udvikling, digital markedsføring, grafisk design, SAP og forretningsanalyse.
Se alle it-kurser

Flere spørgsmål fra C# kategorien

Titel Indlæg Oprettet Seneste aktivitet
Log i Azure Af joki i C# 1 04/12/202517:27 06/12/202520:32
Hent Virksomhed hos graphql.datafordeler.dk Af krukken i C# 13 18/11/202510:57 20/11/202508:59
Http client med X509Certificate2 Af joki i C# 6 11/09/202515:08 11/09/202518:51
pull request Af OBS i C# 1 30/08/202510:47 03/09/202518:51
Vejledning i god opbygning af program, erklæring af lister og modeller. Af Henrik_B i C# 10 10/04/202519:47 13/04/202502:40
Se alle spørgsmål i kategorien Opret spørgsmål

Log ind eller opret profil

Hov!

For at kunne deltage på Computerworld Eksperten skal du være logget ind.

Det er heldigvis nemt at oprette en bruger: Det tager to minutter og du kan vælge at bruge enten e-mail, Facebook eller Google som login.

Opret Log ind

Du kan også logge ind via nedenstående tjenester

Alle kategorier på Eksperten
Seneste spørgsmål Seneste aktivitet
I går 09:43 AI google.com Af Peter Olsen i Andre onlineløsninger
31/0310:22 Makro der gemmer vedhæftet fil fra Msg og omdøber filen Af lokesa i Excel
30/0313:45 Kablet forbindelse mellem android telefon og windows 11 pc Af 1Dorte i Android
30/0312:04 Elementtype vises - og ikke billedet? Af hkprofil i Billedbehandling
29/0312:08 Problemer med replay af købte kursusvideoer Af annam i Browsere
White papers
Flere white papers »