Projekt Cube Solver #01 – cel projektu, zakres, przewidywane problemy i technologie

Projekt Cube Solver #01 – cel projektu, zakres, przewidywane problemy i technologie

Dzisiaj napiszę nieco więcej na temat mojego projektu, a mianowicie programu szukającego rozwiązania pomieszanej Kostki Rubika. Sam projekt dostępny jest na githubie więc łatwo można śledzić moje postępy:
https://github.com/KonradPrzetacznik/cube-solver
Zapraszam do lektury 🙂

Cel projektu

Celem projektu jest napisanie programu pozwalającego na wyszukiwanie rozwiązań pomieszanej Kostki Rubika.

Zakres projektu

Zakres projektu jaki mnie interesuje podczas rozwijania go jest następujący:

  1. Stworzenie generatora algorytmów mieszających.
  2. Stworzenie generator tablic, które pozwolą na odcinanie słabo rokujących gałęzi drzewa przeszukiwań.
  3. Stworzenie mechanizmu szukającego rozwiązania przy pomocy co najmniej dwóch z następujących algorytmów:
    • Algorytm Kociemby,
    • Algorytm Thistlethwaite’a,
    • Algorytm Korfa,
    • Algorytm bruteforce.
  4. Systematyczne pisanie testów w metodyce TDD.
  5. Stworzenie GUI.
  6. Testy wydajnościowe.
  7. Porównanie zaimplementowanych algorytmów.

Przewidywane problemy

Największym problemem, z którym będę miał do czynienia będzie niewątpliwie wydajność samego wyszukiwania rozwiązania. Aby temu zaradzić będzie konieczne wygenerowanie tablic, które będą przechowywały liczbę ruchów potrzebną do uzyskania na kostce docelowego rozwiązania danego etapu (więcej na temat samych rozwiązań i ich etapów w przyszłych wpisach). Tablice te będą następnie służyć – jak już wcześniej wspomniałem – do odcinania słabo rokujących gałęzi dlatego powinny być one możliwie małe, a jednocześnie pozwalać na łatwe wyszukiwanie interesującego nas wpisu. I to właśnie będzie kolejnym najtrudniejszym elementem projektu, gdyż przewidywany rozmiar tablic, zależnie od głębokości generowania może sięgać nawet kilu gigabajtów.

Technologie

Projekt będzie rozwijany w języku Java. Dodatkowo będzie tworzony przy pomocy metodologii test driven development.

A więc skrótowo, podczas prac będę korzystał z następujących narzędzi:

  • Java
  • JUnit
  • Intellij Idea
  • Git
  • TDD

Aktualne postępy

Na chwilę obecną został stworzony projekt na githubie z początkową strukturą folderów. Całość zmian, które poczyniłem można podejrzeć przeglądając mojego commita.

Został utworzony pakiet eu.przetacznik.cubesolver.scramblegenerator, a w nim przykładowy test i klasa, którą sprawdza. Klasa ta będzie zmieniana już w przyszłym artykule z tej serii i będzie służyła do generowania przykładowych algorytmów mieszających. Na razie nie ma specjalnie czego tłumaczyć, sama klasa i jej test są bardzo proste i  można je zobaczyć na listingach poniżej.

 

Co dalej?

Już teraz zapraszam na kolejną część, w której skupimy się na tworzeniu generatora algorytmów mieszających i poznamy pierwszą część teorii niezbędną do prawidłowego zaimplementowania go.

Dodaj komentarz

Twój adres email nie zostanie opublikowany. Pola, których wypełnienie jest wymagane, są oznaczone symbolem *