Program til løsning af IQ block puslespil (en udfordring)

[nivS]

Jeg sidder og bikser med et program som skal forsøge at finde alle de
mulige løsnings metoder til en IQ block. Kort fortalt er der 10
brikker af forskellig form som skal lægges i en 8x8 ramme. Se et foto
her: Loading Image...
Hvis computeren skal forsøge alle kombination så siger mine
beregninger at det er 8*8 = 64 mulige placeringer af en brik og der er
10 brikker så det er vel 64^10 kombinationer? Værre er at en brik jo
både kan vendes om og roteres. Så det giver endnu flere. Det virker
som en total uoverkommelige opgave at få en computer til at løse sådan
en. Men jeg tænkte der der måske sidder nogle matematiske genier der
ude som kan komme på nogle optimeringer eller andet så der ikke skal
forsøges så mange kombinationer.
Jeg har bygget et simpelt C# program op, det minder jo meget om C/C++,
Java, JavaScript eller hvad man nu helst vil programmere i så de
fleste burde kunne være med. Programmet er meget simpelt opbygget, så
ikke noget fancy. Jeg har selv optimeret ved at en brik som er 3x3
ikke bliver placeret så den rager ud over kanten af spille pladen (25
mulige placeringer i stedet for 64), Men det hjælper ikke meget i det
samlede antal iterationer.
Download source koden her: http://nivs.dk/iqsolve.zip (Visual Studio
2008), Når programmet starter viser den først en mulig løsning (så man
kan se de brikker der er til spillet) og ved klik på start knappen går
den i gang med at finde løsninger. Men det tager jo år at komme alle
kombinationer igennem. Så er der nogen der har nogle gode forslag,
eller er det en helt umulig opgave for en almindelig computer at gøre?
Jeg tænkte på noget med flere tråde således at man kan udnytte min
quad core processor eller noget andet?

Mvh. Hans Milling...

[Andreas Andersen]

Post by nivS
Jeg sidder og bikser med et program som skal forsøge at finde alle de
mulige løsnings metoder til en IQ block. Kort fortalt er der 10
brikker af forskellig form som skal lægges i en 8x8 ramme. Se et foto
her: http://nivs.dk/iqblock.jpg
Hvis computeren skal forsøge alle kombination så siger mine
beregninger at det er 8*8 = 64 mulige placeringer af en brik og der er
10 brikker så det er vel 64^10 kombinationer? Værre er at en brik jo
både kan vendes om og roteres. Så det giver endnu flere. Det virker
som en total uoverkommelige opgave at få en computer til at løse sådan
en. Men jeg tænkte der der måske sidder nogle matematiske genier der
ude som kan komme på nogle optimeringer eller andet så der ikke skal
forsøges så mange kombinationer.
Jeg har bygget et simpelt C# program op, det minder jo meget om C/C++,
Java, JavaScript eller hvad man nu helst vil programmere i så de
fleste burde kunne være med. Programmet er meget simpelt opbygget, så
ikke noget fancy. Jeg har selv optimeret ved at en brik som er 3x3
ikke bliver placeret så den rager ud over kanten af spille pladen (25
mulige placeringer i stedet for 64), Men det hjælper ikke meget i det
samlede antal iterationer.
Download source koden her: http://nivs.dk/iqsolve.zip (Visual Studio
2008), Når programmet starter viser den først en mulig løsning (så man
kan se de brikker der er til spillet) og ved klik på start knappen går
den i gang med at finde løsninger. Men det tager jo år at komme alle
kombinationer igennem. Så er der nogen der har nogle gode forslag,
eller er det en helt umulig opgave for en almindelig computer at gøre?
Jeg tænkte på noget med flere tråde således at man kan udnytte min
quad core processor eller noget andet?

Hvis man nu forestiller sig 10 brikker fordelt som:

3 brikker på 4x4
3 brikker på 2x2
4 brikker på 1x1

så får jeg ved lidt hurtig regning, at der er mindst 2^34 (ca. 17
milliarder) løsninger, og selv om det måske ikke er så stort et tal, at
man ikke kan finde dem, kan man bruge ret lang tid på at skrive dem ud
og læse dem igennem. Så generelt er det nok ikke meningsfyldt at finde
samtlige løsninger til en vilkårlig instans af sådan et problem. Til et
specifikt problem kan der selvfølgelig være mange færre løsninger, men
det ved man ikke, før man har prøvet dem alle sammen, og der er nok
mange flere blindgyder, end der er løsninger. Kort sagt: Det er vist,
som du selv gætter på, håbløst.

Hvis man bare vil finde en eller anden løsning, er det selvfølgelig en
helt anden sag.

[nivS]

Post by Andreas Andersen

Post by nivS
Jeg sidder og bikser med et program som skal forsøge at finde alle de
mulige løsnings metoder til en IQ block. Kort fortalt er der 10
brikker af forskellig form som skal lægges i en 8x8 ramme. Se et foto
her:http://nivs.dk/iqblock.jpg
Hvis computeren skal forsøge alle kombination så siger mine
beregninger at det er 8*8 = 64 mulige placeringer af en brik og der er
10 brikker så det er vel 64^10 kombinationer? Værre er at en brik jo
både kan vendes om og roteres. Så det giver endnu flere. Det virker
som en total uoverkommelige opgave at få en computer til at løse sådan
en. Men jeg tænkte der der måske sidder nogle matematiske genier der
ude som kan komme på nogle optimeringer eller andet så der ikke skal
forsøges så mange kombinationer.
Jeg har bygget et simpelt C# program op, det minder jo meget om C/C++,
Java, JavaScript eller hvad man nu helst vil programmere i så de
fleste burde kunne være med. Programmet er meget simpelt opbygget, så
ikke noget fancy. Jeg har selv optimeret ved at en brik som er 3x3
ikke bliver placeret så den rager ud over kanten af spille pladen (25
mulige placeringer i stedet for 64), Men det hjælper ikke meget i det
samlede antal iterationer.
Download source koden her:http://nivs.dk/iqsolve.zip(Visual Studio
2008), Når programmet starter viser den først en mulig løsning (så man
kan se de brikker der er til spillet) og ved klik på start knappen går
den i gang med at finde løsninger. Men det tager jo år at komme alle
kombinationer igennem. Så er der nogen der har nogle gode forslag,
eller er det en helt umulig opgave for en almindelig computer at gøre?
Jeg tænkte på noget med flere tråde således at man kan udnytte min
quad core processor eller noget andet?

3 brikker på 4x4
3 brikker på 2x2
4 brikker på 1x1
så får jeg ved lidt hurtig regning, at der er mindst 2^34 (ca. 17
milliarder) løsninger, og selv om det måske ikke er så stort et tal, at
man ikke kan finde dem, kan man bruge ret lang tid på at skrive dem ud
og læse dem igennem. Så generelt er det nok ikke meningsfyldt at finde
samtlige løsninger til en vilkårlig instans af sådan et problem. Til et
specifikt problem kan der selvfølgelig være mange færre løsninger, men
det ved man ikke, før man har prøvet dem alle sammen, og der er nok
mange flere blindgyder, end der er løsninger. Kort sagt: Det er vist,
som du selv gætter på, håbløst.
Hvis man bare vil finde en eller anden løsning, er det selvfølgelig en
helt anden sag.
--
Andreas

Søgte lidt på nettet og der er en fra Århus Universitet som har lavet
et Java program som på 2 sekunder kan finde alle 184 mulige løsninger
på professor spillet: http://www.cs.au.dk/~gerth/dADS1-04/professor-loesninger.html
Det er det med 16 brikker som kan drejes på 4 måder med over og under
krop. Det er 9*10^22 forskellige kombinations muligheder. Så det må
også være muligt at optimere så man ikke skal prøve alle kombinationer
i IQ Block spillet.

Hans...

[Andreas Andersen]

Post by nivS
Søgte lidt på nettet og der er en fra Århus Universitet som har lavet
et Java program som på 2 sekunder kan finde alle 184 mulige løsninger
på professor spillet: http://www.cs.au.dk/~gerth/dADS1-04/professor-loesninger.html
Det er det med 16 brikker som kan drejes på 4 måder med over og under
krop. Det er 9*10^22 forskellige kombinations muligheder. Så det må
også være muligt at optimere så man ikke skal prøve alle kombinationer
i IQ Block spillet.

Så vidt jeg husker, er der 2 overkroppe og 2 underkroppe på hver
professorspilsbrik. Det betyder jo, at når du har lagt den første brik,
er der kun 2 mulige rotationer for hver efterfølgende brik. Derudover
skal farverne passe. Det betyder, at der meget hurtigt bliver skåret en
masse muligheder fra. Det samme kan utvivlsomt gøre sig gældende for en
masse instanser af IQ-block-spillet, men i visse tilfælde vil der bare
være milliarder af korrekte løsninger.

Asymptotisk kan du ikke løse det bedre end bare at lave en rekursiv
algoritme, der forsøger fra en ende og stopper ved blindgyder, og håbe
at blindgyderne er så tilpas korte, at du når at blive færdig inden for
rimelig tid.

[nivS]

S gte lidt p nettet og der er en fra rhus Universitet som har lavet
et Java program som p 2 sekunder kan finde alle 184 mulige l sninger
p professor spillet:http://www.cs.au.dk/~gerth/dADS1-04/professor-loesninger.html
Det er det med 16 brikker som kan drejes p 4 m der med over og under
krop. Det er 9*10^22 forskellige kombinations muligheder. S det m
ogs v re muligt at optimere s man ikke skal pr ve alle kombinationer
i IQ Block spillet.

S vidt jeg husker, er der 2 overkroppe og 2 underkroppe p hver
professorspilsbrik. Det betyder jo, at n r du har lagt den f rste brik,
er der kun 2 mulige rotationer for hver efterf lgende brik. Derudover
skal farverne passe. Det betyder, at der meget hurtigt bliver sk ret en
masse muligheder fra. Det samme kan utvivlsomt g re sig g ldende for en
masse instanser af IQ-block-spillet, men i visse tilf lde vil der bare
v re milliarder af korrekte l sninger.
Asymptotisk kan du ikke l se det bedre end bare at lave en rekursiv
algoritme, der fors ger fra en ende og stopper ved blindgyder, og h be
at blindgyderne er s tilpas korte, at du n r at blive f rdig inden for
rimelig tid.
--
Andreas

Så må løsningen være at kode op til Boinc eller et af de andre
projekter hvor man kan udnytte flere tusind computere til at regne det
ud for en.

Hans...

[Andreas Andersen]

Post by nivS
Jeg sidder og bikser med et program som skal forsøge at finde alle de
mulige løsnings metoder til en IQ block. Kort fortalt er der 10
brikker af forskellig form som skal lægges i en 8x8 ramme. Se et foto
her: http://nivs.dk/iqblock.jpg

Jeg fik lige lyst til at eksperimentere med det, og har fået bikset et
program sammen til at finde alle løsningerne. I det tilfælde du angav er
der 604 løsninger (2416 med rotationer, da to af brikkerne har to ens
rotationer for hver løsning). Sig til hvis du (eller andre) stadig er
interesseret, så finder jeg lige ud af at uploade det et sted.