Du er besøkende nr.
(Teller nullstilt 23. august 2007)
Sist endra: mandag, 20. august 2007 14:55:39
-
Hans Isdahl
Rubiks kube - historikk og løsning
Er det
noen som husker denne?
Ideen med å presentere
kuben på disse matematikksidene henger sammen med tankegangen bak løsning av
kuben: Både metodikk i tankegangen, løsning av puslerier samt antall
kombinasjoner er viktige momenter i matematisk tankegang. Derfor lenkes
denne sida fra generelle matematikksider samt fra sannsynlighetsregninga -
dvs. kombinatorikken.
Antall plasseringer av
de 27 - egentlig 26 - småkubene er interessant matematikk:
Den midterste kuben,
nr. 27, fins ikke. Vi har 26 småkuber å forholde oss til.
De midterste på hver
side, 6 stykker på de 6 sideflatene, er umulig å flytte i forhold til
hverandre. De er konstruert som et tredimensjonalt kors, kryss.
De 8 hjørnebitene
som vi ser 3 sider av, kan hver plasseres på 8 ulike plasser i 3 ulike
posisjoner. Hvor mange muligheter? (Kanskje vi må redusere med 3
posisjoner: Plasserer vi dem fritt, kan kanskje ikke kuben løses...)
Og de 12
midtpåsideterningene kan plasseres på 12 ulike steder, hver av dem i 2
ulike posisjoner. (Her må vi helt sikkert redusere: Den siste - for
eksempel - kan ikke plasseres fritt, men må stå i én av de to
posisjonene.)
Hvor fort
kan det gjøres? Les i Guinness' rekordbok, eller
se på denne karen! Det ser ut til at
det bare går 18,5 sekunder...
(Verdensrekorden i hurtigløsning i Guinness' rekordbok var 22,95
sekunder. Den terningen må være innsatt med såpe for å gli godt!)
Fordi dette er en del av
matematikkundervisninga, gir jeg ingen hjelp her! Vær oppmerksom på at
6 brikker alltid ligger fast i kuben, de 6 som vi bare kan se ei side
på og som ligger midt på hver sin side. Lag f.eks. øverste side BLÅ!
Symbolbruk - Du ser alltid på ei
side med 3 x 3 ruter, 3 rader og 3 kolonner; dreininger er bare nitti
grader pr. symbol!
Venstre kolonne opp
eller ned
Midtre kolonne opp
eller ned
Høyre kolonne opp
eller ned
Øvre rad mot høyre
eller mot venstre
Midtre rad mot høyre
eller mot venstre
Nedre rad mot høyre
eller mot venstre
Fremre lag dreid nitti grader mot høyre/med klokka
Fremre lag dreid nitti grader mot venstre/mot klokka
I started to think about this problem in about August of 2000. In
Jan 2001 fellow Mindstorms forums user 'agiecco' announced his
intention to work on a robotic solution and, simultaneously, I saw
that Rubik's Cubes were on sale at www.target.com. So I bought a
couple of cubes and started getting down to business...
I produced a 'late beta' version in mid-April 2001 that was a
little clunky. The final version (presented here) is smooth and
fairly reliable.
MECHANICS
To achieve a cube solution, you must be able to rotate the whole
cube by 90° in two orthogonal axes, and be able to turn a
face by 90° relative to the rest of the cube.
I opted to use the left and right grabbers to turn the faces; the
yellow grabber can rotate the left face by an 90°; the green grabber
can rotate the right face by 90°; or they can both turn
simultaneously while the bottom grab is open to rotate the whole
cube through 90°.
The bottom gabber holds the center 'slice' of the cube when the
left or right grabber is turning a single face, and also provides a
90° turn for rotating the whole cube.
The tricky part is to re-orient the cube between moves to present
the next face to be turned by the left or right grabber.
PROBLEMS SOLVED
1. The cube faces are generally too stiff for LEGO elements to
turn
This problem was solved by a tip I found on Lars Petrus's
Speed Cubing page:
lubricate the cube with silicone spray lubricant. I got an aerosol
can of LubriMatic Heavy Duty Silicone Lubricant from my local
ACE hardware store and squirted some inside the cube. After wiping
off the excess spray you must rotate the cube faces for about 30
minutes to prevent the solvent in the spray dissolving the cube body
and sticking it solid. Once you have done this, the result is a
fairly slick cube.
However, I found that some of the faces still got stuck because
the springs inside the cube were too stiff, so I pushed some wedges
(actually, plastic knives) in between the cube slices and left them
over night to force the springs inside the cube to loosen up. After
this treatment the cubes handled very well.
2. Getting
enough torque
Even with a treated cube, getting enough torque to turn the cube
faces was going to be a problem. I remembered the system that Jin
Sato used on the thigh joints of
MIBO -- worm gear to the outer 56t ring of the large Technic
turntable. This gives torque to spare for turning the faces of a
treated cube.
3. LEGO grabbers don't grip strongly enough
My early attempts at building a cube solver were all stymied by
grips that slipped. The worm-56t gave enough torque to turn, but the
fingers couldn't hang on and the grip was simply pried apart as the
grabber rotated around the stationary cube face. I thought about
changing the device's name to ButterFingers.
I rebuilt the left and right grabbers six times (and the bottom
grabber four times) trying elastic bands, Technic shocks, and
pneumatics, before I came up with an adequate grip mechanism. In the
present version, an axle runs from a motor through the center of the
large Technic turntable to a worm screw. The worm screw turns two
24t gears mounted either side of the worm inside the body of the
grabber. Each end of the 24t axles terminates with an 8t gear
outside the body of the grabber, and these 8ts engage with 24t-s on
either end of the axles which carry the grabber's fingers. This
system can be strained quite tight without risk of gear slippage,
and also allows the large turntables to rotate 180° without any
significant loss of grip.
For the bottom grabber I had to use a slightly different
arrangement (same gear combinations) because the fingers of the
green and yellow grabs kept catching on the external 24ts of the
bottom grab. Eventually I managed to work out how to mount all the
gears internally in the 4-stud width of large Technic turntable.
4. Precision of
movement
Having solved these problems, there was still the problem of
'slop' or 'gear lash' in the left and right drive trains.
Most of this was absorbed in the beta version by putting rotation
sensors on the worm drive axles that rotate the grabs. However, the
worm screws are a *tiny* bit too short to fit snugly -- they travel
a little when the motor direction is reversed. To cure this I tried
a suggestion from
John Barnes and cut thin shims out of the plastic insert tray
from inside a LEGO box. Two shims on each drive axle fixed the worm
gear nicely in position so that the gear lash (although still
detectable) was *nearly* within the tolerance of the cube for
repeated turning.
However, the rotation sensors for the LEFT and RIGHT grabbers
occasionally lost track of their position and had to be manually
tweaked during a solution. There was also the problem that the
rotation sensors were on the same axle as the worm screw turning the
turntable. This meant that when the cube was a little stiff, even if
the worm screw had performed the correct number of rotations to turn
the cube face 90°, the LEGO pieces of the grabber had enough flex
that the grabber was slightly twisted and the face did not make it
all the way around to the 90° point.
Therefore, I abandoned rotation sensors and put two touch sensors
at the limits of the quarter turn of the turntable (similar to the
bottom grabber). I built a 'toucher' attached to the rotating part
of the large turntable, and this seemed to compensate better for the
twisting of the other LEGO elements of the grabber during stiff
turns.
The disadvantage of the touch sensor approach, of course, is that
the grabbers can no longer make a full 180° turn, so there is more
time taken repositioning the side grabbers. The robot averages one
face rotation every 30 seconds (i.e., a 20 rotation solution takes
about 10 minutes). The final problem is making sure that the faces
of the cube are kept in orthogonal alignment. A standard Rubik's
Cube has side dimensions *just* larger than 7 LEGO studs.
Fortunately there is enough flex in the joints of LEGO Technic to
absorb the tiny additional dimension. Each grabber arm is fitted
with reverse slopes that force the cube into the correct orthogonal
alignment as the grabbers close.
5. Establishing
the initial (unsolved) state of the cube
The longest part of the this project involved writing the
color-recognition software. I downloaded the Logitech Quick Cam SDK
from the Logitech
Developer's site (the LEGO Vision Cam is a repackaged Logitech
Quick Cam) and used VB5 to write a fairly decent program (click the
Code link for source). The color recognition is fairly robust (about
one error every two cubes when well-calibrated), but not perfect, so
I incorporated a feature that requires you to confirm that each face
has been correctly scanned (and, optionally, allows you to correct
the input manually) before it scans the next face.
The software
requires calibration with a solved cube under the particular
lighting conditions, and it is quite finicky about changes in
lighting conditions. I also left in the earlier manual input option
so that you can get a solved cube for calibration, or in case anyone
who doesn't have a Vision Cam wants to try this.
Briefly, the software sends a message to the top RCX asking it to
present one face of the cube to the video camera. The computer
captures a frame from the video camera, and scans a 50x50 pixel area
of each color patch to find the median red, green and blue (RGB)
color values for each color patch on the face. The RGB values are
converted to CIE X Y y coordinates, and then the CIE values are
trigonometrically compared to the calibration values to find the
closest match. The computer then asks the robot to show it the next
face, and the process is repeated until all the faces have been
scanned.
6. General
solution to the Rubik's cube
There are any many general solutions to the 3^3 Rubik's Cube on
the internet (see
here
for a partial list). However, most of these produce a sequence of
moves involving 50 or 60 face rotations. Given that CubeSolver moves
quite slowly (averages about 30 seconds between face rotations), I
wanted a relatively short sequence of moves. Fortunately, I found
some
C
source code by Mike Reid on the internet which implements
Herbert Kociemba's solution method: it provides short solutions (<
40 face rotations). I ported this code to Microsoft Visual C++ and
recompiled it as an OCX for use in Visual Basic. I must say that
Mike did a very decent job with his code -- move sequences are
generated quickly, with a length usually about 20 moves or less.
BRIEF HISTORY OF
THE CUBE
Every invention has an official birth date. For
the Cube this date is 1974 when the first working prototype came into
being and a patent application was drafted. The place was Budapest, the
capital of Hungary. The inventor's name is now a household word. At the
time, Erno Rubik was a lecturer in the Department of Interior Design at the
Academy of Applied Arts and Crafts in Budapest.
Although 1974 marks the inauguration of the Cube, the processes that led to
the invention began a few years earlier, nor was the identity of the
inventor a fortuitous accident. Erno Rubik had a passionate interest in
geometry, in the study of 3D forms, in construction and in exploring the
hidden possibilities of combinations of forms and material in theory and in
practice.
In the course of his teaching, Erno Rubik preferred to communicate his
ideas by the use of actual models, made from paper, cardboard, wood or
plastic, challenging his students to experiment by manipulating clearly
constructed and easily interpreted forms. It was the realization that even
the simplest elements, cleverly duplicated and manipulated, yield an
abundance of multiple forms that was the first step on the long road that
led finally to the Cube.
Although possibly the most original of all invented puzzles, the Cube was
not created in a vacuum. Its classical antecedents are great puzzles
in their own right. The Tangram, originating from ancient China, merely
consists of 5 triangles, a square and a parallelogram, simple elements that
yield a multitude of interesting figures. The Pentomino, invented by Solomon
W Golomb, has 12 different elements, each one made up of five squares joined
together, displaying all the possible configurations of the five combined
squares. Pentomino poses the fascinating geometric problem of constructing
various rectangles. Piet Hein's Soma Cube is, in a sense, a three
dimensional version of Pentominos. It resembles Rubik's Cube both in shape
and in the large number of ways its seven elements can be assembled into a
3x3x3 cube. Finally, there is Sam Loyd's well known 15 puzzle, with it's
numbered tiles locked together yet moving separately, so that by pushing
them about they can be set in sequential order and scrambled at will.
Viewing these puzzles places Rubik's Cube in a context and highlights just
what a breakthrough creation the Cube really is.
What Erno Rubik's set out to do was create a three dimensional object,
of high aesthetic value, which was not only richer in configuration
variations and more of a mental challenge than any puzzle in existence, but
would also continue to be ONE, SELF-CONTAINED WHOLE, throughout its
manifold transformations.
This objective seemed at first as impossible to achieve as the 3-axial
rotation of the Cube appears on first encounter. After conceiving the idea
of the 3x3x3 Cube, Erno Rubik first tried to hold together the elements of a
simpler, 2x2x2 cube, by means of an elastic rubber construction that
threaded its way through all 8 elements. Even at this simple level it soon
became clear that such a device could not work. The alternatives then
available, such as magnets and the obvious tongue and grooves system, could
not cope with the complexity of the different junctions and movements that
each element required. Erno Rubik realized that only a totally original
concept could provide a satisfactory solution.
The inspiration came on a lazy, summer day as he was watching the Danube
flow by. Rubik's eye was attracted by some pebbles, whose sharp edges have
been rubbed and smoothed away in the course of time bringing into being
rounded shapes of great but simple beauty. The interior of the Cube elements
had to have the same rounded architecture. The brilliant interior
mechanism, which is basically cylindrical, took some time to reach its
final form. For ease of manipulation, the balance between tightness and
looseness had to be just right, tolerances had to be exact. Finally, the 54
outer surfaces of the individual elements were given their colors. Lots of
different decorative patterns, with numbers and symbols as well as diverse
color combinations were tried, but none of them worked nearly as well as the
six simple but distinct colors, each one unifying and differentiating one
single face of the Cube.
When the Cube was complete, Erno Rubik demonstrated it to his students and
let some of his friends play with it. The effect was instantaneous. Once
somebody laid his hands on the Cube it was difficult to get it back!
The compulsive interest of friends and students in the Cube caught its
creator completely by surprise and it was months before any thought was
given to the possibility of producing it on an industrial scale.
Eventually a manufacturer took on the job of tooling up for mass
production and making the puzzle available to the public at large. Given the
inner complexity of the Cube, and the then prevailing economic conditions in
communist Hungary, this was by no means an easy undertaking. It is to the
credit of the two men at the helm of the toy production firm of Politechnika,
President Lehel Takacz and Chief Engineer Ferencz Manczur that they at once
perceived enough merit in the Cube to accept this task. The process of
turning the hand made object into thousands of low cost, mass manufactured
units was slow. It took the best part of three years, but at last, towards
the end of 1977 the first Cubes appeared on the shelves of the Budapest
toyshops.
During 1978, without any promotion or publicity, the Cube began very
slowly to make its way through the hands of fascinated youths into homes,
playgrounds and schools. Word of mouth spread the news and by the beginning
of 1979 there were enthusiastic circles of Cube devotees in various parts of
Hungary.
With the country being both physically and culturally behind the iron
curtain at the time, the growing popularity of the Cube did not cross over
to the West for quite some time. Not surprisingly, two men of Hungarian
origin who had established their lives in the West built the bridge, which
eventually enabled the Cube to cross the divide.
Dr Tibor Laczi, born in Budapest, educated in Vienna and employed by a major
German computer manufacturer "discovered" the Cube on one of his frequent
business trips to Hungary. He fell in love with it, and sensing its
potential consumer appeal, brought it to the Nuremberg Toy Fair in
February 1979 in the hope of finding a potential German toy distributor.
He did not meet with a great deal of success but he did stumble across an
individual who at that point of the Cube's history was destined to make a
crucial difference.
Tom Kremer, a successful toy and game inventor himself, whose mother
language was also Hungarian, ran at the time his own marketing and licensing
company. Seven Towns Ltd., based in London, was widely respected throughout
the international toy industry as a product developer working not only with
its own ideas but also representing professional inventors from all over the
world.
The two men made a pact, there and then, to translate the Hungarian success
of the Cube onto the world stage. Dr Ladzi headed back to Hungary to pave
the way with the prevailing Hungarian bureaucracy whilst Tom Kremer set off
on a world tour of toy manufacturers. He was convinced that to realize the
Cube's full commercial potential it had to have the marketing muscle, the
promotional power and distribution network of a major international company.
Unfortunately he found none of the leading players in the field shared his
enthusiasm. Although impressed by the Cube, the general view within the
industry estimated its prospects to be poor. Its "faults" were numerous: Too
difficult and expensive to manufacture, impossible to demonstrate its
fascination on TV, too abstract, too cerebral, too quiet, a challenge for
the esoteric academic mind rather than a puzzle meant for the young and the
general public.
Undeterred by this universal rejection, and spurred on by his firm belief in
the exceptional quality of the toy, Tom Kremer, now armed with a convincing
marketing plan, continued his search for a viable partner. After many
disappointments, he succeeded in persuading Stewart Sims, Vice President of
Marketing of the Ideal Toy Corporation, to come to Hungary, to see with his
own eyes the Cube in play. It was now September 1979, by which time the
Cube had gained a sufficient degree of popularity to be seen
occasionally in the street, on trams, in cafes, each time in the hands of
someone turning and twisting it, completely absorbed. After five days of
convoluted negotiations between a skeptical American capitalist and an
obstinate communist organization largely ignorant of the operation of a free
market, with Laczi and Kremer desperately holding the two sides together, an
order for one million cubes was signed amidst much handshaking and great
relief all round.
In the meanwhile, quite independently of these developments, David
Singmaster, an English mathematician, became deeply interested in the
theoretical problems and ramifications raised by the Cube in his own field.
He wrote a newspaper article in June 1979, the first one to appear
outside Hungary, which brought the Cube to the attention of academic circles
world wide and led indirectly to another milestone in its history: an
article in Scientific American, with a cover picture, by Douglas Hotstadter
an acknowledged authority in the field of Recreational Mathematics.
Apart from a small seepage across the Hungarian borders, the Cube made its
international debut at the Toy Fairs of London, Paris, Nuremberg and New
York in January/February, 1980. With Erno Rubik demonstrating his own
creation, the Cube made an immediate impact. The trade buyers were impressed,
orders rolled in. There was just one problem: there were no Cubes! Western
quality standards and packaging norms meant drastic changes in the Hungarian
manufacturing process. This, as with any change under a communist in regime,
was slow in coming. Communication between New York and Budapest, given the
linguistic and cultural differences, despite the frequent interventions of
Tom Kremer, were not easy.
The flow of products from Hungary began in May 1980. As soon as the Cube
found its way into the hands of consumers it became evident that the initial
order of one million pieces for the first year would not be anywhere near
sufficient to meet the growing demand. From the very beginning it was a
characteristic of the Cube that no matter how fast production increased,
demand grew faster. Contrary to what the leaders of the Toy Industry had
expected, for the next two and a half years the problem was not one of
selling Cubes but of supplying them. From 1 million the figures started
to grow quickly to 2, to 3, to 5 million and then, in 1981 exploded
exponentially. Production centers had to expand from Hungary to Hong
Kong, Taiwan, Costa Rica and Brazil, taking up the capacities of many
separate factories in each center.
The challenge of trying to master the Cube, to be able to restore all of its
six sides to the original colors seemed to have a mesmeric effect on an
amazing variety of individuals right across age, occupation, wealth and
social standing. Grandmothers, bank managers, baseball players, pilots,
librarians, park attendants could be seen working away at their Cubes at any
hour of the day. In restaurants the Cube would feature on tables side by
side with salt and pepper pots, handled with greater frequency than either.
But it was the young, schoolboys and students, who were in the vanguard of
what was fast becoming a massive movement that swept across the world. They
were the ones who proved most adept at solving the puzzle; they were the
ones to form special cubists clubs, to organize competitions, to suffer from
Rubik's wrist playing continuously for hours and days with an object that
simply could not be put down.
The difficulty of solving the Cube and the absolute compulsion to solve it
generated over 60 books offering desperately needed help. They in turn
generated more addicts, displaying with evident pride their newly acquired
prowess.
After winning the highest prize for outstanding inventions in Hungary, in
1980 the Cube won top toy awards in Germany, France, Britain and the
U.S. by 1981 it entered the New York Museum of Modern Art as an exhibit. The
Cube achieved such a universal presence and penetrated so deeply the fabric
of our society that "Rubik's Cube", by 1982 a household term, became part of
the Oxford English Dictionary.
It is difficult to estimate the total number of Cubes sold throughout the
world. In the period of 1980-1982, partly because demand far outstripped
supply, a huge variety of pirate, unauthorized products of inferior quality
came onto the market from opportunistic Taiwanese, Korean and Hong Kong
vendors. Although the Ideal Toy Corporation won a number of court cases in
Holland, Britain, the U.S. and other countries, it was impossible to stem
the tide. It is safe to assume that the figure exceeds 100 million, it is
certain that it was significantly greater than that.
Interestingly, the legal defense of the Cube was never based on the original
patent, this only applied in Hungary. It was the "Rubik" trademark, Erno
Rubik's copyright on the object itself and the "passing off" laws, which
secured, and continues to secure adequate protection of the Cube against
unauthorized copies in all countries throughout the world.
In effect, as the Cube was initially created as a one-off object, with an
inherent artistic merit, the Rubik copyright applies not only to the 3D
object itself but also to any graphic representation of it in print or on
screen, until 70 years after the creator's death.
Given the extraordinary volumes of sales, both legitimate and illegitimate,
it was inevitable that eventually a saturation point would be reached. The
market in Cubes collapsed, shops and factories remaindered their stocks and
for some time from 1983 onwards the Cube became unavailable. The Ideal Toy
Corp. was bought by CBS and CBS itself got out of toys in 1985.
The toy business being largely fashion oriented, the industry gave up on the
Cube, considering it a fad, albeit an unprecedented one. Not so Tom Kremer.
He had always considered the Cube to be one of the all time great classic
toys, worthy to be placed alongside such permanent fixtures as Monopoly,
Scrabble and Mr. Potato Head. So in 1985 his company, Seven Towns, acquired
all the rights to the "Rubik's Cube". Biding their time, they re-introduced
the Cube, without any hype, very gradually in selected key markets,
beginning in 1991. Compared to the giant waves of the early eighties, sales
were just a trickle in the first few years. However, in 1995, Oddzon a
dynamic Californian based company took over the distribution of the Cube
with dramatic results. In 1996 in the US alone over 300,000 Cubes were
sold with the numbers growing in 1997 and 1998. In Japan, where Tsukuda
is still the faithful original Rubik's Cube distributor, sales have exceeded
100,000 in 1997 and in Britain sales are also pushing the 100,000 mark. The
pattern is the same world over. The Cube is staging a come back.
But now, in its second incarnation, the Cube is part of a family of puzzles
and games which bear the stamp of the genius who created the greatest three
dimensional puzzle the world has ever known.
Erno Rubik has not changed much over the years. Working closely with Seven
Towns, he is still deeply engaged in creating new games and puzzles, and
remains one of the principal beneficiaries of what proved to be a
spectacularly successful invention.