Rubik's Cube - oplossing in ≤ 20 bewegingen

Dit is de plek voor onzin, off-topic gebrabbel en idiote moppen.
arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Rubik's Cube - oplossing in ≤ 20 bewegingen

Bericht door 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
;-)

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Bericht door 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.''

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - breaking news

Bericht door 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.

Gebruikersavatar
Marco
Beheerder
Beheerder
Berichten: 831
Lid geworden op: 19 feb 2005, 12:50
Locatie: Leeuwarden
Contacteer:

Re: Rubik's Cube - breaking news

Bericht door 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

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door 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)

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Bericht door 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.''

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door 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)

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - breaking news

Bericht door 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.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door 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)

Sjoerd Job
Vergevorderde
Vergevorderde
Berichten: 1144
Lid geworden op: 21 jan 2006, 15:09
Locatie: Krimpen aan den IJssel

Re: Rubik's Cube - breaking news

Bericht door 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.''

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - breaking news

Bericht door 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.

David
Moderator
Moderator
Berichten: 4927
Lid geworden op: 14 mei 2009, 16:22

Re: Rubik's Cube - breaking news

Bericht door 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)

Gebruikersavatar
op=op
Vergevorderde
Vergevorderde
Berichten: 1087
Lid geworden op: 23 apr 2010, 18:11

Re: Rubik's Cube - breaking news

Bericht door op=op » 15 aug 2010, 14:45


arie
Moderator
Moderator
Berichten: 3911
Lid geworden op: 09 mei 2008, 09:19

Re: Rubik's Cube - breaking news

Bericht door 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: Selecteer alles

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.

tsagld
Vergevorderde
Vergevorderde
Berichten: 341
Lid geworden op: 23 mar 2009, 12:07
Contacteer:

Re: Rubik's Cube - breaking news

Bericht door 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?

Plaats reactie