Rubik's Cube - oplossing in ≤ 20 bewegingen

Dit is de plek voor onzin, off-topic gebrabbel en idiote moppen.

Rubik's Cube - oplossing in ≤ 20 bewegingen

Berichtdoor arie » 12 Aug 2010, 17:08

Voor degene die het grote nieuws gemist mocht hebben:
Rubik's 3x3x3 Cube is altijd op te lossen in maximaal 20 bewegingen.
Zie ook http://www.bbc.co.uk/news/technology-10929159
en http://www.cube20.org/.

Nu op naar de 4x4x4 cube...

Of wellicht deze: http://www.youtube.com/watch?v=Rpfz3m11bsk
;-)
arie
Moderator
Moderator
 
Berichten: 2994
Geregistreerd: 09 Mei 2008, 09:19

Re: Rubik's Cube - breaking news

Berichtdoor Sjoerd Job » 12 Aug 2010, 21:30

Heel erg bedankt voor de heads-up! Ik ben blij om het nu te weten!

Ik zal zeker de tijd zoeken om alles door te nemen.
``Life is complex. It has real and imaginary parts.''
Sjoerd Job
Admin
Admin
 
Berichten: 1148
Geregistreerd: 21 Jan 2006, 15:09
Woonplaats: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Berichtdoor op=op » 13 Aug 2010, 07:28

Groot nieuws kan ik het niet noemen. Mogelijk is het enigszins interessant voor de mensen die in de hoogtijdagen van dit irritante kubusje er verslaafd aan waren. Dom rekenwerk van een computer. Bah.
Om dat getal God's getal te noemen zegt meer iets over de behoefte aan verslavingszorg dan over het getal zelf.
Het wordt ook nog de populairste puzzel aller tijden genoemd. Nou, dat ik schaken.
De grootste puzzelhype, dat zou kunnen.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

Re: Rubik's Cube - breaking news

Berichtdoor Marco » 13 Aug 2010, 07:39

Het is inderdaad niet een elegant bewijs, ik vraag me af of dat ook wel mogelijk is..!
Groeten, Marco
Gebruikers-avatar
Marco
Beheerder
Beheerder
 
Berichten: 825
Geregistreerd: 19 Feb 2005, 12:50
Woonplaats: Leeuwarden

Re: Rubik's Cube - breaking news

Berichtdoor David » 13 Aug 2010, 10:22

Dit laat wel zien wat computers kunnen. Heel veel decimalen van berekenen is daar een methode voor, nu kan je dat ook testen met het vinden van god's getal (van het maximaal aantal van het minimaal aantal zetten) om elke verdraaiing van een rubiks' cube op te lossen.

Nu ben ik heel optimistisch, maar ik werp het op:
Gods getal gaat uit van volledige draaiingen.
"Gods getal" van een rubiks' van 1*1*1=0; die klopt altijd en kan je niet verdraaien
"Gods getal" van een rubiks' van 1*1*2=1
"Gods getal" van een rubiks' van 1*1*n=n-1
"Gods getal" van een rubiks' van 2*2*2=11 Zie hier, waar wel een citaat wordt gevraagd
"Gods getal" van een rubiks' van 2*2*1=2 als ik dat goed uit dit filmpje zag.
Ik ken "gods getal" van een rubiks' van 2*2*3 en van 2*3*3 niet. Zou het helpen om die getallen te kennen, om zo de gods getal voor 4*4*4 te vinden of is dat helemaal willekeurig?

Dit zal toeval zijn: een rubikscube heeft 27 vakjes. 1 daarvan zit niet in de oplossing; het centrum. 6 zitten al op de goede plaats; de centra van de 6 vierkanten. Blijven 20 vakken over. Gods getal.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

Re: Rubik's Cube - breaking news

Berichtdoor Sjoerd Job » 13 Aug 2010, 17:50

op=op schreef:Dom rekenwerk van een computer. Bah.

Tsja, net als bij de vierkleurenstelling. Die heeft ook lang opengestaan en is uiteindelijk met de computer bewezen.

Het enige wat ik mij afvraag: Ze hebben op google servers gedraaid... is het te vertrouwen?

Over het algemene God's-number: Ik denk dat we daar geen algemene formule voor zullen vinden. Sowieso zal er meer data voor een vermoeden moeten komen.

De 2x2xn en de 2x3x3 zullen we misschien nog wel met computers kunnen vinden, ook nog binnen korte tijd denk ik. Alleen bij de niet-regelmatige kubussen, kan het nummer veel kleiner worden, omdat de draaingen beperkter zijn.
``Life is complex. It has real and imaginary parts.''
Sjoerd Job
Admin
Admin
 
Berichten: 1148
Geregistreerd: 21 Jan 2006, 15:09
Woonplaats: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Berichtdoor David » 13 Aug 2010, 23:17

In de link die Arie gaf http://www.cube20.org/ staat een lijst met aantal draaiingen en de frequentie dat dat minimum aantal draaiingen voorkomt. Voor 16 t/m 20 draaiingen is die frequentie een benadering. Dat lijkt me ook een punt om te kijken of de claim: God's number is 20 klopt.
Kan het zo zijn dat ze minstens 1 positie zijn vergeten? Is de conclusie op basis van de benaderingen te vertrouwen?

Kloppen deze beweringen?:
  1. Een n*n*(n+1) cube heeft meer mogelijke draaiingen dan een n*n*n cube.
  2. God's getal van een n*n*(n+1) cube is groter dan dat van een een n*n*n cube.
  3. Een n*(n+1)*(n+1) cube heeft meer mogelijke draaiingen dan een n*n*(n+1) cube.
  4. God's getal van een n*(n+1)*(n+1) cube is groter dan dat van een een n*n*(n+1) cube.

Of zijn de beweringen niet (allemaal) logisch te beoordelen?

Ik had verwacht dat God's getal toenemend stijgend is voor een n*n*n-cube, maar dat blijkt, als de gegevens kloppen niet (altijd) zo te zijn.


Dat is afnemend stijgend; de eerste toename, van n=1 naar n=2, is 11, terwijl de andere toename, van n=2 naar n=3, 9 is; afnemend stijgend zover.

Als het nodig is, kan ik voor de berekening voor 2*2*n en 2*3*3 hulp (rekenkracht bijv.) vragen op een ander forum, of toch liever "intern" oplossen als dat gebeurt?
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

Re: Rubik's Cube - breaking news

Berichtdoor op=op » 14 Aug 2010, 07:03

Sjoerd Job schreef:Tsja, net als bij de vierkleurenstelling. Die heeft ook lang opengestaan en is uiteindelijk met de computer bewezen.

Helaas is het vierkleurenprobleem niet bewezen. Daarvoor moet eerst nog aangetoond worden (ik bedoel: bewezen worden) dat het gebruikte algoritme correct is. Bovendien moet je ook nog het axioma accepteren dat een computer (hardware en software) geen fouten kan maken.
Er bestaat wel een theorie voor het bewijzen van algoritmen (met wp en wlp's), maar die is practisch te bewerkelijk, en bovendien wie heeft daar zin in als je honderden regels code hebt.
Door de "oplossing" m.b.v. een computer heeft het vierkleurenprobleem zijn aantrekkelijkheid verloren.
Wie is nog geinteresseerd in "het bewijs" als die deels uit computeroutput bestaat?

Als het bijvoorbeeld om decimalen van gaat wordt een resultaat pas geaccepteerd als het m.b.v. twee verschillende algoritmen is verkregen. Dit bewijst niets, het reduceert slechts de kans op fouten in het algoritme of in de hard-, middle- of software.

De berekening voor 2*2*n en 2*3*3 is volgens mij te beredeneren.
In het algemene geval denk ik dat het antwoord in de nabije toekomst bewezen wordt.
De algebra die nodig is om "Gods getal" te vinden is pas sinds enkele jaren in ontwikkeling.
Kortom, niet te ongeduldig, het antwoord komt eraan.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

Re: Rubik's Cube - breaking news

Berichtdoor David » 14 Aug 2010, 20:40

Het voordeel van zelf (ook) de berekening doen voor 2*2*n en 2*3*3 of zelfs 3*3*3 is dat je minder wantrouwend tegenover de resultaten van de onderzoekers hoeft te staan als je hetzelfde vindt. Zo ben je ook niet volledig afhankelijk van onderzoekers.

Het nadeel is dat het rekenkracht kost. Voor 3*3*3 is dat (minstens) 35 CPU-jaren. Ook: http://www.cube20.org/

In het geval van 3*3*3 vindt ik het nadeel zwaarder tellen dan het voordeel van zelf berekenen. Die overweging heb ik niet gemaakt voor 2*2*n en 2*3*3, omdat ik niet weet hoeveel CPU-tijd daarvoor nodig is. Een dergelijke overweging lijkt me nuttig om te maken.

Deze 2 uitspraken vind ik wel hoopvol:
Sjoerd Job schreef:De 2x2xn en de 2x3x3 zullen we misschien nog wel met computers kunnen vinden, ook nog binnen korte tijd denk ik. Alleen bij de niet-regelmatige kubussen, kan het nummer veel kleiner worden, omdat de draaingen beperkter zijn.

En
op=op schreef:De berekening voor 2*2*n en 2*3*3 is volgens mij te beredeneren.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

Re: Rubik's Cube - breaking news

Berichtdoor Sjoerd Job » 14 Aug 2010, 22:12

daco schreef:Kloppen deze beweringen?:
  1. Een n*n*(n+1) cube heeft meer mogelijke draaiingen dan een n*n*n cube.
  2. God's getal van een n*n*(n+1) cube is groter dan dat van een een n*n*n cube.
  3. Een n*(n+1)*(n+1) cube heeft meer mogelijke draaiingen dan een n*n*(n+1) cube.
  4. God's getal van een n*(n+1)*(n+1) cube is groter dan dat van een een n*n*(n+1) cube.

Bij de eerste, twijfel ik al.

De n*n*(n+1) heeft (n+1) kwart, halve en driekwart draaien, en n + n halve draaien: 3*(n+1) + n + n = 5n+3
De n*n*n heeft n + n + n kwart, halve en driekwart draaien: 3*(3n) = 9n.
Het aantal posities dat het genereerd kan daarentegen wel groter zijn, maar daar twijfel ik nu nog aan. Een vierkant vlak staat meer draaiingen toe dan een rechthoekig(niet vierkant) vlak. Evenzo twijfel ik ook al bij de andere uitspraken.

De vierkleurenstelling/het vierkleurenprobleem is wel of niet bewezen, afhankelijk van de persoon. Ik vind een computer-proof best wel een bewijs. Uiteraard moeten de algorithmes door verscheidene mensen bekeken zijn. Software fouten? Uiteraard kunnen die voorkomen. Laat het algorithme door drie teams implementeren op een aantal verschillende platformen. Dit verkleint de kans zeer. Voldoende om de twijfel alleen bij het algoritme te laten vallen.

Zou je het wel vertrouwen als het algoritme door duizenden mensen uitgevoerd zou zijn? Ik niet, die vertrouw ik minder.

Het komende halfjaar heb ik het heel erg druk, maar misschien kan ik wat tijd vinden om de 2*2*2 en 2*2*3 na te rekenen. (Misschien zelfs de 2*3*3). Wel daag ik jullie uit om dat ook te proberen!
``Life is complex. It has real and imaginary parts.''
Sjoerd Job
Admin
Admin
 
Berichten: 1148
Geregistreerd: 21 Jan 2006, 15:09
Woonplaats: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Berichtdoor op=op » 15 Aug 2010, 08:51

Ik denk ook dat de 4 beweringen van daco alle onjuist zijn.

Sjoerd Job schreef:Ik vind een computer-proof best wel een bewijs. Uiteraard moeten de algorithmes door verscheidene mensen bekeken zijn. Software fouten? Uiteraard kunnen die voorkomen. Laat het algorithme door drie teams implementeren op een aantal verschillende platformen. Dit verkleint de kans zeer. Voldoende om de twijfel alleen bij het algoritme te laten vallen.

Je vergeet nog enkele bronnen van fouten. De compiler van een programmeertaal kan fouten bevatten (sterker nog, die bevat vrijwel zeker fouten). Je weet niet of die fouten en wanneer die fouten en op welke wijze die fouten zich openbaren.
Het platform waarop het programma draait wemelt van de fouten. Bij windows wordt een softwaretechniek gebruikt (interfaces) die niet volledig wordt begrepen. Niet erg, is het argument, het werkt.
Alhoewel ik wel geloof dat met het algoritme voor het vierkleurenprobleem de uitkomst nu vaststaat, is er nog geen sprake van een bewijs. Een geloof is nog wat anders dan een bewijs.
Er kan pas spake zijn van een wiskundig hard bewijs als elke twijfel (hoe onwaarschijnlijk ook) is uitgesloten.
Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

Re: Rubik's Cube - breaking news

Berichtdoor David » 15 Aug 2010, 12:00

Na de uitleg van Sjoerd Job denk ik dat de 1e onjuist is. Bij de draaingen van een
n*n*(n+1). Als je een kwart- of een driekwart draai maakt over een rechthoekvlak van n*(n+1), heb je geen balkvorm meer over zoals hij was toen je begon.
Klein detail: een n*n*n kubus heeft 9(n-1) draaiingen; bijv. een 2*2*2 heeft 9 mogelijke draaiingen, niet 18; of je rekent de hele kubus mee als draaiing, maar dat hangt van de definitie af.

Evenzo voor een (n+1)*(n+1)*n kubus heb je samen 3(n-1) kwart-, halve- en driekwart draaiingen en (n) halve draaiingen en (n) halve draaiingen geeft 5n-3 draaiingen.

Een (n+1)*n*n kubus heeft 3n kwart kwart-, halve- en driekwart draaiingen en (n-1) halve draaiingen en (n-1) halve draaiingen geeft 5n-2 draaiingen. 5n-2>5n-3 zou bewering. Dus geldt het andersom:
3. Een n*n*(n+1) cube heeft meer mogelijke draaiingen dan een n*(n+1)*(n+1) cube, namelijk één meer.

Ik weet (nog) niet hoe dit bewering 2 en 4 beïnvloedt.
Stap 1 van het oplossen van een probleem is te erkennen dat je een probleem hebt.
(Raffiek Torreman)
David
Moderator
Moderator
 
Berichten: 4935
Geregistreerd: 14 Mei 2009, 16:22

Re: Rubik's Cube - breaking news

Berichtdoor op=op » 15 Aug 2010, 14:45

Gebruikers-avatar
op=op
Vergevorderde
Vergevorderde
 
Berichten: 1096
Geregistreerd: 23 Apr 2010, 18:11

Re: Rubik's Cube - breaking news

Berichtdoor arie » 15 Aug 2010, 19:53

En zie ook:
http://www.jaapsch.net/puzzles/cube223.htm

Als we net als bij 2x2x2 h-turns (=halve draaiingen = 180 graden draaiingen) als 1 turn rekenen,
is God's getal voor de Rubik 2x2x3 brick dus 14.
Rekenen we alle q-turns (=kwart draaiiingen = 90 graden draaiingen) als 1 turn (dus 1 h-turn = 2 draaiingen), dan hebben we maximaal 15 slagen nodig.

De zoekruimte voor een (gedeeltelijk) brutekracht bewijs wordt wsch snel groter.
Hieronder het aantal mogelijke configuraties van een n x n x n kubus (per regel steeds n en het aantal configuraties van de betreffende n^3 kubus).

Code: Alles selecteren
2   3.67 E6
3   4.33 E19
4   7.40 E45
5   2.83 E74
6   1.57 E116
7   1.95 E160
8   3.52 E217
9   1.42 E277
10   8.30 E349
11   1.09 E425
12   2.06 E513
13   8.76 E603
14   5.41 E707
15   7.46 E813
16   1.49 E933
17   6.69 E1054
18   4.35 E1189
19   6.33 E1326
20   1.34 E1477
21   6.31 E1629
22   4.33 E1795
23   6.63 E1963
24   1.48 E2145
25   7.34 E2328
26   5.31 E2525
27   8.57 E2724
28   2.01 E2937
29   1.05 E3152
30   8.03 E3379
31   1.37 E3610
32   3.38 E3853
33   1.87 E4099
34   1.50 E4358
35   2.69 E4619
36   7.03 E4893
37   4.09 E5170
38   3.47 E5460
39   6.56 E5752
40   1.80 E6058
41   1.11 E6366
42   9.88 E6686
43   1.97 E7010
44   5.70 E7346
45   3.69 E7685
46   3.47 E8037
47   7.30 E8391
48   2.23 E8759
49   1.52 E9129
50   1.51 E9512
51   3.34 E9897
52   1.08 E10296
53   7.74 E10696
54   8.09 E11110
55   1.89 E11527
56   6.41 E11956
57   4.86 E12388
58   5.35 E12833
59   1.32 E13281
60   4.71 E13741
61   3.76 E14204
62   4.37 E14680
63   1.13 E15159
64   4.28 E15650
65   3.60 E16144
66   4.41 E16651
67   1.21 E17161
68   4.79 E17683
69   4.26 E18208
70   5.49 E18746
71   1.58 E19287
72   6.63 E19840
73   6.21 E20396
74   8.44 E20965
75   2.57 E21537
76   1.13 E22122
77   1.12 E22709
78   1.60 E23309
79   5.13 E23911
80   2.39 E24527
81   2.48 E25145
82   3.75 E25776
83   1.27 E26410
84   6.22 E27056
85   6.82 E27705
86   1.09 E28368
87   3.86 E29032
88   2.00 E29710
89   2.31 E30390
90   3.88 E31083
91   1.45 E31779
92   7.93 E32487
93   9.66 E33198
94   1.71 E33923
95   6.76 E34649
96   3.88 E35389
97   4.99 E36131
98   9.30 E36886
99   3.88 E37644
100   2.35 E38415

De 2x2x2 kubus heeft ongeveer 3.67*10^6 configuraties, de 3x3x3 kubus zo'n 4.33*10^19.
Voor doorrekenen van de 3x3x3 kubus waren al 35 CPU jaren nodig, ik vraag me nog steeds af of we dit ook ooit voor de 4x4x4 kubus kunnen doen (ook al classificeren we alle ~ 7.40*10^45 configuraties handig).

@daco:
[1]
In het artikel geven ze voor het aantal met 16 t/m 20 draaiingen een benadering omdat ze een algoritme gebruiken dat niet alle optimale oplossingen zoekt.
Indien een configuratie is op te lossen met 20 draaiingen of minder, gaan zie niet controleren of die configuratie mogelijk met nog minder draaiingen is op te lossen.
Omdat er al een configuratie bestond waarvan bekend was dat die echt 20 draaiingen nodig had kan God's nummer niet onder de 20 liggen.
Deze methode levert een forse tijdwinst (zie artikel onder "Good vs. Optimal Solutions").
[2]
Als je een nxnxn kubus uitbreidt naar nxnx(n+1) zal die extra laag elke configuratie van een nxnxn kubus uitbreiden met een aantal nieuwe configuraties. Het aantal mogelijkheden wordt daardoor groter, God's nummer zal dan wsch groter worden (of gelijk blijven?).

@op=op:
Ik ben wat minder pessimistisch over de mogelijkheden van computers mbt bewijsvoering, zeker als de gebruikte algoritmes helder zijn. Aan de andere kant worden de mogelijkheden van computers begrensd door tijd en ruimte, terwijl zuiver wiskundige bewijzen gelden voor het hele domein en daarom toch mooier zijn.
arie
Moderator
Moderator
 
Berichten: 2994
Geregistreerd: 09 Mei 2008, 09:19

Re: Rubik's Cube - breaking news

Berichtdoor tsagld » 31 Aug 2010, 13:50

Iemand noemde 'schaken' als ingewikkelde puzzel.
Ik heb ooit gelezen dat het aantal mogelijke schaakpartijen wordt geschat op .

Zou een computer ooit de perfecte partij vinden?
tsagld
Vergevorderde
Vergevorderde
 
Berichten: 341
Geregistreerd: 23 Mrt 2009, 12:07

Volgende

Terug naar De Wiskundelounge

Wie is er online?

Gebruikers in dit forum: Geen geregistreerde gebruikers en 2 gasten

Wie is er online?

Er zijn in totaal 2 gebruikers online :: 0 geregistreerd, 0 verborgen en 2 gasten (Gebaseerd op de gebruikers die actief waren gedurende 5 minuten)
De meeste gebruikers ooit tegelijkertijd online was 649 op 31 Okt 2014, 18:45

Gebruikers in dit forum: Geen geregistreerde gebruikers en 2 gasten
Copyright © 2009 Afterburner - Free GPL Template. All Rights Reserved.