[Løst] Puslespill: Utregning av vanskelighetsgrad

[oslo72]

Ok, jeg går ikke på skole, men føler at dette er nærmeste riktige sted å poste mitt problem:

 

Et puslespill på 5000 brikker er X vanskelig.

Hvor mye vanskeligere er et puslespill på 18240 brikker?

 

Vi kan ta utgangspunkt i at alle brikkene er snudd riktig vei opp.

 

Kan noen hjelpe meg med utregningen?

Det er jo ikke slik at det er 3,648 ganger vanskeligere.

[BlueEAGLE]

Etter min mening så er vanskelighetsgraden på et puslespill mer avgjort av motivet. Et pusslespill med 10000 brikker med bilde av et tivoli (mange kontraster og varierte strukturer) mye enklere enn et puslespill på 5000 brikker hvor det er tatt bilde av en kornåker (veldig ensartet).

[oslo72]

Sant nok, men ta utgangspunkt i at alle brikkene er hvite da.

Det suger motivasjonsmessig vil jeg tro - men det finnes vel en logaritme eller noe for å regne ut dette?

Grunnen til at jeg spør er at jeg vet hvor vanskelig 5000 brikker er - men klarer ikke å forestille meg helt hvor mye 18240 er...

[BlueEAGLE]

Det blir litt som å legge parkett. Når du først vet hvordan det legges så er det ikke mer vanskelig å legge 50m² enn det er å legge 30m². Det tar bare lengere tid.

[NikkaYoichi]

Et puslespill er da ikke vanskelig i det hele tatt, ren brute force løser alle puslespill. Derfor vil jeg si at vanskelighetsgraden er lik og at det vanskelige er å finne plass å legge så store puslespill på, i så måte er det største ganske mye vanskeligere.

[oslo72]

Det blir litt som å legge parkett. Når du først vet hvordan det legges så er det ikke mer vanskelig å legge 50m² enn det er å legge 30m². Det tar bare lengere tid.

Å sammenlikne puslespill med å legge parkett blir litt søkt, siden alle "brikkene" i en parkett passer sammen - noe det ikke gjør i et puslespill. Det å finne EN brikke blant 18240 er også en god del vanskeligere enn å finne den blant 5000 brikker.

 

Plass har jeg og trenger ikke å tas med i den matematiske formelen.

Endret 7. desember 2011 av oslo72

[BlueEAGLE]

Når du legger et puslespill så grupperer du først brikkene etter hjørne kant. Så etter farger. Du vil aldri i praksis prøve alle brikkene en etter en.

 

Hvis du nå mot formodning skulle prøve alle brikkene en etter en og en hvilken som helst side aldri passet til mer enn nøyaktig en annen side på nøyaktig en annen brikke så vil det være en eksponensiell funksjon

 

I tillegg så må du ta høyde for endestykker og hjørner som kun har to eller tre sider. Med andre ord så trenger du å vite antall brikker i høyde og bredde for å kunne lage en nøyaktig beregning.

[BlueEAGLE]

Hvis den er 114x160 brikker så har du (114*2+160*2)-4 = 544 sidebrikker med kun tre muligheter. Du har alltid fire hjørnebrikker med kun to muligheter.

Da har du 18240 - 4 - 544 = 17692 brikker med fire muligheter.

 

I tillegg så kan brikker være konfigurert på følgende måter

 

 __  __    __/\__    __  __      __  __     __/\__      __  __
|  \/  |  |      |  |  \/  |    |  \/  |   |      |    |  \/  |
<        >  >    <    >      >  <      <   <        >  <        >
|__/\__|  |__  __|  |__/\__|    |__/\__|   |__/\__|    |__  __|  osv osv
             \/                                           \/

så da må vi vite hvordan brikkene er fordelt mellom alle variasjonene for å finne reelle muligheter. Dette fordi man alltid vil legge rammen først og da har man to eller flere punkt som skal passe sammen og man vil ikke forsøke å sette inn en brikke som har to tapper på et sted hvor tilhørende brikker har en eller to tapper. Altså man vil samle de formlike (med tanke på plassering av tapper og hakk) og kun prøve de konfigurasjonene som passer.

 

Med andre ord: Oppgaven du har gitt er umulig å løse på noen som helst nøyaktig måte uten at vi vet hvordan den opprinnelige X er beregnet.

[oslo72]

Okey dah

Jeg ser jo poenget ditt, absolutt. Var ikke ute etter 100% korrekt svar, men var nysgjerrig på hva slags svar som eventuelt kom opp.

 

Jeg klarer jo å skjønne at 18240 brikker er MYE mer enn 3-4 ganger så vanskelig og tidkrevende som 5000 brikker - men ser jo nå at det blir litt vanskelig å beregne eksakt hvor mye (selv om man kan ta utgangspunkt i at brikkeform etc varierer like mye på 18240-versjonen som på 5000-versjonen).

 

Er det noen her som har prøvd seg på så mange brikker tidligere? Frister jo å prøve etterhvert som guttungene blir litt eldre.

[NikkaYoichi]

Det største jeg noen gang har hatt glede av å legge besto av 3000 brikker tror jeg. Allerede da begynte det å ta så stor plass at jeg ble frustrert over at jeg måtte flytte det fra bordet og ned på gulvet. Det resulterte i at lekne kattunger stakk av med halve bildet. Så lærdommen ble at man må holde husdyr unna, når man pusler puslespill. ^^

[oslo72]

Hehe... kan nok tenke meg at katter er en dårlig kombo med puslespill... det er nok en ett- og fireåring også + støvsuger.

Jeg bygde en egen bordplate til de puslespillene som var på 5000 brikker - men hvis jeg skal prøve meg på 18240 så trenger jeg jo ennå større plass... jaja - det blir ihvertfall ikke de første par årene...

[Matsemann]

Et puslespill er da ikke vanskelig i det hele tatt, ren brute force løser alle puslespill. Derfor vil jeg si at vanskelighetsgraden er lik og at det vanskelige er å finne plass å legge så store puslespill på, i så måte er det største ganske mye vanskeligere.

Jeg sitter nå og øver til algoritme-eksamen. Om man bruker brute force er din påstand om at alle puslespill er like vanskelige feil.

Prøver man blindt alle kombinasjoner og vi forenkler vil man kunne starte med en brikke, prøve de 4999 andre brikkene for å finne den som passer, så de 4998 osv. = 5000!/2 når man i snitt finner riktig brikke halvveis.

For 18000 bruker man da 18000!/2

Som gir en faktor på

3.198 x 10^52454 vanskeligere å bruteforce.

Endret 7. desember 2011 av Matsemann

[oslo72]

Skjønner at jeg ikke kommer i mål her, men tusen takk for alle forsøk og innspill

[Kubjelle]

Et puslespill er da ikke vanskelig i det hele tatt, ren brute force løser alle puslespill. Derfor vil jeg si at vanskelighetsgraden er lik og at det vanskelige er å finne plass å legge så store puslespill på, i så måte er det største ganske mye vanskeligere.

Jeg sitter nå og øver til algoritme-eksamen. Om man bruker brute force er din påstand om at alle puslespill er like vanskelige feil.

Prøver man blindt alle kombinasjoner vil man kunne starte med en brikke, prøve de 4999 andre brikkene for å finne den som passer, så de 4998 osv. = 5000!/2 når man i snitt finner riktig brikke halvveis.

For 18000 bruker man da 18000!/2

Som gir en faktor på

3.198 x 10^52454 vanskeligere å bruteforce.

Det blir litt for enkelt.

 

Husk at du har flere muligheter til hvor du kan plassere brikken. Hvis du starter med en hjørne brikke så har du 2 valgmuligheter hvor du kan legge brikken. Etter du har lagt en brikke som passer har du 3 valgmuligheter. Etter at du har 3 brikker som passer er det forskjellig hvor mange valgmuligheter du har. Alt etter hvor du legger brikken, enten 3 eller 4 muligheter.

 

Vi kan se på dette på to måter. Hvis vi regner sannsynligheten for at en tilfeldig brikke passer til din gruppe med brikker, så vil sannsynligheten være høyere, fordi du har flere brikker som kan passe til forskjellige plasser. Derimot hvis vi regner sannsynligheten for at en tilfeldig brikke passer til en tilfeldig plass så vil sannsynligheten være mye lavere.

 

Hvilken som passer best er vanskelig å si. I starten er det veldig enkelt å sjekke om en brikke passer til flere plasser, men etterhver når samlingen av brikkene dine blir større så blir det vanskeligere og vanskeligere.

 

Det er mulig at disse verdiene er proporsjonale med hverandre på de forskjellige puslespillene. Altså at hvis vi regner ut verdier for den første sannsynligheten for de to forskjellige puslespillene og gjøre det samme for for den andre sannsynligheten. Så vil forholet mellom hvis du deler de to sannsynlighetene til den første sannsynligheten være lik forholdet mellom de to andre sannsynlighetene delt på hverandre. Da spiller det ingen rolle hvilken av sannsynlighetsberegningene du velger, men jeg tror ikke at de nødvendigvis er proporsjonale.

 

Dette er forresten en morsom matteoppgave. Det skader å ikke poste spørsmålet i mattetråden.

Endret 7. desember 2011 av Kubjelle

[Matsemann]

Ja, da var en veldig forenkling, bare for å illustrere at å bruteforce det ikke bare er å gange med en faktor mellom problemstørrelsene, men at det vokser veldig, veldig fort.

[BlueEAGLE]

Det finnes 52 forskjellige konfigurasjoner av firkantede brikker i et puslespill (variasjoner av tupper og hakk). Det er 4 hjørnebrikker, 8 forskjellige sidebrikker for hver av de fire sidene (32 til sammen) og 16 forskjellige brikker til å fylle inn rammen.

 

Vi tar utgangspunkt i at puslespillet er 114*160 = 18240 brikker stort og at de forskjellige konfigurasjonene av brikker er jenvt fordelt. Vi stipulerer også at vi har like mye flaks som uflaks når det kommer til sjansen for å treffe riktig brikke. Altså vil vi like ofte treffe på første som på siste brikke og i gjennomsnitt så vil vi treffe når vi er halvvegs igjennom bunken med mulige brikker.

 

De fire hjørnebrikkenes plassering er gitt.

 

Når vi skal legge neste brikke inntil rammen så har vi 112 brikker som passer på den siden, men brikken vi legger inntil har enten en tupp eller et hakk så vi kan fjerne halvparten av kandidatene med en gang. Det vil si at vi har 56 muligheter for å legge første brikke. For neste brikke så har vi 55 eller 56 muligheter og for brikken etter der har vi 54 eller 56 muligheter avhengig av konfigurasjonen på sidebrikken.

 

Uansett så vil det være mulig å utlede en formel som sier hvor mange forsøk vi trenger for å plassere ned alle 112 brikkene på kortsiden. Dette tallet ganger vi enkelt med to for å finne den andre kortsiden.

 

Når vi har denne formelen så vil det være en smal sak å endre verdiene for å finne antall forsøk man trenger for å plassere ned langsidene med 158 brikker.

 

Når rammen er lagt så er det bare å begynne i et hjørne. Her vil vi ha to tupper, en tupp og et hakk, et hakk og en tupp eller to hakk allerede. Det vil si at vi kan umiddelbart utelukke 75% av de resterende 17692 brikkene. Da har vi "bare" 4413 muligheter å forsøke.

 

Da sitter vi igjen med en variasjon av formelen over for å finne hvor mange forsøk vi igjennomsnitt vil bruke for å fullføre første linje. Når det er gjort så er det bare å begynne fra hjørnet igjen.

 

Hvis noen har lyst til å utlede formelene over så er det bare å sette i gang, men i såfall så vil dette passe bedre i mattetråden.

 

 

Når det er sagt så gjelder overstående kun for helt ensfargede puslespill. Hvis du har et puslespill med bilde på så vil du kunne gruppere brikker basert på farger og mønster og drastisk redusere mulighetene. I tillegg så vil graden av "brute force" gå ned da du vil kunne sette sammen flere deler av bildet uavhengig av hverandre og så kombinere disse.

[NikkaYoichi]

Men man legger den da ikke bare ned på ett sted i gangen, man prøver alle kantene man har tilgjengelig. Vil ikke det ha noe å si?

[BlueEAGLE]

Men man legger den da ikke bare ned på ett sted i gangen, man prøver alle kantene man har tilgjengelig. Vil ikke det ha noe å si?

Jeg forutsatte visst også at brikkene ligger med riktig vei opp.

[oslo72]

Har postet spørsmålet i mattetråden også, så får vi se

Jeg skjønner jo at det menneskelige spiller inn her også, og ser jo nå etterhvert at det blir umulig å regne ut et eksakt svar.

 

Likevel er jeg jo nysgjerrig på hvor lang tid jeg må beregne på å bli ferdig.

På 5000-spillet brukte vi ca 3 måneder (50-60 brikker om dagen i snitt) - men det er jo MYE vanskeligere å finne riktig brikke blant 18240 andre - samtidig så er det sikkert enklere å finne riktig brikke etterhvert siden jeg får flere alternative plasser å prøve brikkene på. F.eks når jeg kommer meg ned i 5000 gjenstående brikker er det enklere å finne riktig plass for gjenstående brikke 4999, 4998, 4997 etc enn når jeg startet på det minste puslespillet.

 

Tar gjerne resten av diskusjonen på:

https://www.diskusjon.no/index.php?showtopic=309688&view=getnewpost