» »

Rubik's cube - algoritem

Rubik's cube - algoritem

Boomerang ::

LP!

Zadnje čase se ukvarjam z zlaganjem kocke in nameravam še spisati programček, ki bi implementiral enega od algoritmov. Preden naredim prvi korak (priprava GUI, izbira programskega jezika itd) bi se rad prepričal kako težko je zadevo implementirati... če ima kdo izkušnje.

Vse skupaj si zamišljam nekako takole: uporabnik naklika trenutno stanje kockic oz. njihovih barv (zgoraj, spodaj itd.), potem program reši kocko in prikaže postopek: katero ploskev kdaj in kam obrniti.

Večje pa je vprašanje, kako naj bi algoritem delal oziroma kako delajo sorodni algoritmi za reševanje kocke? Prvo kar sem pomislil je 3D tabela, kjer bi shranjeval stanje ploščkov. Na primer:
KOCKA[ploskev][x_koordinata][y_koordinata] = barva;

Ali pa bi uporabil kar objekt, ki bi predstavljal eno ploske. Lastnost objekta pa je 2D tabela (koordinate). Potem bi definiral osnovne operacije/manevre t.j. kako nek plošček premakniti iz ene pozicije v drugo - gre za spreminjanje 3D tabele. Ostane mi še vprašanje kdaj izvesti kateri premik (manever).

Zanima me, kako se vam zdi moj način reševanja? Bi se dalo tako rešiti kocko v realnem času ali bi moral kako drugače pristopiti k problemu? Nekje sem tudi prebral, da algoritmi za reševanje kocke delajo z matrikami... samo meni matrike nikoli niso bile všeč in tudi ne razumem njihov pomen pri reševanju kocke.

MrBrdo ::

matrika = tabela (v programiranju)
tko da naj te ne bo strah :) poglej si kakšno že obstoječo implementacijo, v Javi jih je verjetno malo morje.
MrBrdo

urosz ::

premisliti še moraš, kateri algoritem za reševanje kocke boš uporabil. med speedcuberji je nekako najbolj priljubljena metoda "friedrich", ki pa sicer ni najbolj optimalna

AndrejS ::

Tu si lahko pogledaš kako zgleda :
http://www.wrongway.org/cube/solve.html

Boomerang ::

- AndrejS, glede GUI sem za začetek nameraval nekaj takega, kot je v tem primeru... mreža in gor postavim razporeditev barv. Mogoče bom kdaj kasneje naredil tudi 3D kocko (ki jo bo možno obračati), ampak to naj ostane za drugič.
- urosz, glede algoritma imam tudi še čas. Najprej moram sestaviti vmesnik za vnos in izpis stanja kocke ter osnovne premike... to imajo vsi algoritmi skupno, šele potem pride na vrsto algoritem.
- MrBrdo, drugače kot s tabelami niti ne gre :D V mislih sem imel tako matriko/vektor, kot se obravnava v matematiki... nekje sem namreč videl primer, kjer so v 3x3 matriki samo vrednosti -1, 0, 1. Ko sem tak program natančno pregledal, mi še zmeraj ni bilo jasno kako to reši kocko.

Hvala vsem trem za pomoč.

blackbfm ::

Jaz sem mel pred kratkim nek program, verjetno ga boš hitro našel na googlu če ga hočeš, kateri mislim da deluje po principu brute-force, torej na blef probava, in na koncu izbere najboljšo kombinacijo, ponavadi v 10-20 potezah..rešitev vrže ven skoraj instantno.

Boomerang ::

Bi se dalo dobit še link do tega algoritma, ker bi si res rad ogledal postopek programa. Meni je trenutno najbolj poznan adutov algoritem (najprej križ, potem celo zgornjo plast, sredinska plast in spodnja plast), ampak kocko za rešitev kocke rabim nad 50 potez (če za 1 potezo štejem rotacijo ene plasti za 90 stopinj). Zato me res preseneča, kako na bruteforce rešiti v 20 potezah.

BTW, a mogoče kdo ve, kateri so še ostali algoritmi za reševanje? Zelo popularen je tudi Friderickov algoritem, ampak se mi zdi enak kot adutov. Še kakšen drugi algoritem?

urosz ::

blackbfm je izjavil:

Jaz sem mel pred kratkim nek program, verjetno ga boš hitro našel na googlu če ga hočeš, kateri mislim da deluje po principu brute-force, torej na blef probava, in na koncu izbere najboljšo kombinacijo, ponavadi v 10-20 potezah..rešitev vrže ven skoraj instantno.


ne farbaj ljudi. sem se nekaj časa kar precej ukvarjal z rubikovo kocko in vem da trollaš.

Boomerang ::

Še eno vprašanje za vse kockarje na forumu:
Pregledal sem par online programčkov in vidim da omogočajo premikanje srednje ploskve, potem pa vzamem v roke svojo staro kocko in si jo dobro ogledam, tudi razstavim. Opazil sem, da je mehanizem kocke tako narejen, da se zunanje kockice premikajo okoli sredine.... torej srednja kockica se fizično ne more premakniti (tako kot to prikazujejo programčki). Lahko bi samo levo in desno ploskev obrnil naprej in dobim tak učinek, kot če bi srednjo ploskev zavrtel nazaj.... A razumete kaj mislim?

Torej zanima me, a dejansko obstaja kocka, ki bi omogočala premikanje srednje ploskve, ali je to le v programih, da je bolj poenostavljeno?

Smurf ::

urosz je izjavil:

blackbfm je izjavil:

Jaz sem mel pred kratkim nek program, verjetno ga boš hitro našel na googlu če ga hočeš, kateri mislim da deluje po principu brute-force, torej na blef probava, in na koncu izbere najboljšo kombinacijo, ponavadi v 10-20 potezah..rešitev vrže ven skoraj instantno.


ne farbaj ljudi. sem se nekaj časa kar precej ukvarjal z rubikovo kocko in vem da trollaš.

Meni se zdi valid izjava. Dokazano je, da lahko rubikovo kocko resis v maksimalno 20 potezah. klik

blackbfm ::

Ja, res se sliši neverjetno v 20 potezah, ampak da se. Program sicer izračuna malo plus minus, če daš na hitro kalkulacijo, lahko pa tut išče optimalno samo tisto potem traja. Link do programa:
http://kociemba.org/cube.htm

urosz ::

ne pravim da se ne da rešit v 20 potezah, ampak da se kocke ne rešuje z bruteforce metodo, ampak s sistematičnimi algoritmi ;)


Vredno ogleda ...

TemaSporočilaOglediZadnje sporočilo
TemaSporočilaOglediZadnje sporočilo
»

Rubikova kocka (strani: 1 2 )

Oddelek: Loža
5414263 (2761) mailer
»

Algoritem za rešitev Rubikovih kock vseh velikosti

Oddelek: Novice / Znanost in tehnologija
76797 (5152) bMozart
»

20 potez za Rubikovo kocko.

Oddelek: Znanost in tehnologija
82974 (2555) Jeronimo
»

Rubikova kocka

Oddelek: Loža
91152 (962) r5r
»

Rubikova Kocka

Oddelek: Loža
263697 (2972) Valentin

Več podobnih tem