Maddy 2 stvari koje trebaš napraviti:
1) posjećena stanja spremaj u neku hash strukturu, NE listu. Dakle, u pythonu je to npr. set()*, koji interno hashira objekte, dok pretpostavljam da bi u javi to bilo nes tipa HashSet. Jer kad bi posjećena stanja spremali u listu, svaki put kad bi išli provjeravati je li neki čvor već posjećen, morali bi pretraživati cijelu listu posjećenih stanja, a to traje dosta duže nego kad imaš neki hash set
2) za UCS, lista open cvorova ti treba biti sortirana po ukupnom costu do tog čvora. Sam ak ideš sortirati listu open svaki put i to onda 180000 puta, koliko je potrebno da se algoritam izvrti, čekat ćeš satima. Ono što trebaš napraviti umjesto toga je za listu open koristiti neku implementaciju prioritetnog reda, koji će ti svaki put kad hoćeš dohvatiti sljedeći element dohvatiti najmanji, i to napraviti na jako efikasan način. U pythonu je to npr. heapq, a za javu nisam siguran, al trebao bi postojati neki ekvivalent. Onda samo složiš da ti se objekti (čvorovi) koji se dodaju u heap uspoređuju prvo po totalCost, a onda abecedno, i trebalo bi sve raditi
Ja sam isto imao problema da mi se 3×3 nije htio izvrtiti u nekom normalnom vremenu, al kad sam rješio ove dvije stvari, i BFS i UCS mi se izvrte u nekih 10-15 sekundi
*ako koristiš set() u pythonu, pazi da stringove u njega dodaješ sa .add, a ne .update.
