SI/L/z1

From WikiZMSI

Na zajęciach

• Napisać klasę reprezentującą stan planszy sudoku. Klasa powinna być ogólna tzn. pozwalać na plansze dowolnych rozmiarów n^2 x n^2 (typowo: n = 3). Przygotować metody pozwalające na: (1) konwersję sudoku do napisu - toString(), (2) wczytanie sudoku 9 x 9 z napisu - fromString(...), (3) sprawdzenie, czy sudoku jest poprawne, (4) odświeżanie licznika niewiadomych na planszy.

• Pobrać bibliotekę SaC (w tym podręcznik użytkownika w języku angielskim).

• Podpiąć z pomocą prowadzącego bibliotekę SaC w projekcie Eclipse (wskazanie wymaganych bibliotek .jar, podpięcie dokumentacji javadoc).

• Zmienić klasę Sudoku, tak aby dziedziczyła po klasie sac.graph.GraphStateImpl - potrzebne będzie zaimplementowanie metod: generateChildren(...), isSolution(...), hashCode() oraz podpięcie funkcji heurystycznej poprzez setHFunction(...).

• Eksperymenty. Przetestować działanie algorytmu Best-first-search dla kilku przykładowych sudoku (można znaleźć w internecie). Wyświetlić różne informacje na temat pracy algorytmu w momencie stopu: liczba stanów w zbiorach Open i Closed, czas pracy, liczba rozwiązań, itp. Sprawdzić wpływ różnych nastaw konfiguracyjnych (klasa GraphSearchConfigurator). Utrudniać sudoku poprzez odejmowanie liczb z planszy początkowej (obserwować wzrost liczby odwiedzonych stanów, aż do momentu uzyskania niejednoznaczności rozwiązania). Wygenerować wszystkie sudoku 4 x 4.

Do domu

• Napisać program rozwiązujący układankę "puzzle przesuwne (n^2 - 1)". Uwaga: proszę zaimplementować stan układanki jako tablicę dwuwymiarową (dla odróżnienia od istniejącej już implementacji w bibliotece SaC, gdzie użyta jest tablica jednowymiarowa).

• W szczególności należy: odziedziczyć po klasie sac.graph.GraphStateImpl, oraz zaimplementować metody: generateChildren(...), isSolution(...), hashCode().

• Zaimplementować jako osobne klasy dwie funkcje heurystyczne: "misplaced tiles" oraz "Manhattan".

• Wykonać eksperyment porównawczy heurystyk dla 100 problemów losowo pomieszanych przy n = 3. Wskazówki: (1) "losowe" układanki generować rozpoczynając od ułożonej planszy i wykonując 1000 ruchów mieszających nie dbając o ewentualne niwelowanie się ruchów przeciwnych, natomiast dbając o nie zliczanie się ruchów pustych przy brzegach planszy; (2) dla ustalonego problemu przepinać heurystyki poprzez metodę statyczną setHFunction(...) na klasie reprezentującej układankę. W eksperymentach mierzyć (w momencie stopu): liczbę stanów w zbiorach Open i Closed, czas wykonania, długość ścieżki. Jako końcowe porównanie podać wartości średnie mierzonych wielkości przypadające na każdą z heurystyk.

• Na życzenie prowadzącego mieć możliwość szybkiego nastawienia eksperymentu analogicznego do poprzedniego dla: n = 4, 10 losowych układanek powstałych poprzez 30 ruchów mieszających.