ułożenie tych samych liczb w kwadracie 3x3 - algorytm

Mamy kwadrat 3x3, w każdym jedna cyfra od 1 do 8

1 | 3 | 1
3 | 9 | 5
4 | 3 | 7

W jednym ruchu możemy dodać lub odjąć od dwóch cyfr koło siebie (w rzędzie lub kolumnie) jakąś liczbę z tym że wartości zmieniają się cyklicznie tzn. 1-1=8, 6+3=1. Znaleźć najmniejszą liczbę ruchów aby doprowadzić kwadrat do postaci z jedną tą samą, dowolną cyfrą.
Prośba o wskazówki lub algorytm.

W przykładzie jest literówka-zamiast 9 miało być 8

Algorytm rozumiem w pseudokodzie, czy masz jakiś określony język ?

Potrzebuję to zakodzić w javie ale to nie jest istotne. Prośba o jakąkolwiek formę pomocy: pseudokod, słowne wytłumaczenie kroków algorytmu itp. Z góry dzięki

Prysznic ożywia ciało i umysł, przed chwilą pod prysznicem przyszedł mi do głowy algorytm, który prowadzi do celu w co najwyżej 11 ruchach.
1 2 3 1 1 2 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1
2 1 3 2 1 3 2 1 2 2 8 1 3 1 1 1 1 1 1 1 1 1 1 1
1 4 5 1 4 5 1 4 5 1 4 5 1 4 5 7 4 5 1 6 5 1 1 8
Na koniec cztery oczywiste ruchy i masz same ósemki,

bo - Twój algorytm nie da najmniejszej liczby ruchów chociażby dla takiego kwadratu:

2 2 4
1 3 4
1 6 3

Ten kwadrat da się rozwiązać w 5 ruchach.

Ja nie twierdziłem, że on jest najszybszy. Starczyło mi że działa.
Podejrzewam, że znalezienie najszybszego, to brute force.

Jak przeczytasz dokładnie temat to zobaczysz, że w zadaniu chodzi o najmniejszą liczbę ruchów.
Brute force chyba daje trochę za dużo ilość kombinacji: jest 12*8 sposobów na wykonanie jednego ruchu (na 12 sposobów można wybrać 2 przyległe kwadraty i można odjąc 8 różnych liczb). Żeby rozwiązać Twój kwadrat trzeba 12 ruchów czyli 96^12 a to trochę za dużo do brute forcowania. Trzeba by jakieś sensowne przycięcia wymyśleć.

Czytałem dokładnie temat, wiedziałem że chodzi o najmniejszą ilość ruchów, i wiedziałem, że mój algorytm nie rozwiązuje zadania. Ale chciałem się pochwalić.;-)

Wymyśliłem innego brutforsa, który ma chyba szansę działać w rozsądnym czasie:

const int N=134217728; //tyle istnieje mozliwych kwadratow
int liczbaRuchow[N];

int main()
        {
        for (int i=0;i<N;i++)
                liczbaRuchow=-1;
        for (int i=1;i<=8;i++)
                {
                int kod=getKodKwadratu(i); //bierzemy kod kwadratu, ktory jest wypelniony tylko cyframi i
                liczbaRuchow[kod]=0;
                }
        int liczbaPustych=N-8;
	int r=0; //liczba ruchów ktorą powinny mieć aktualnie badane kwadraty. w kazdym przebiegu petli badamy coraz bardziej "oddalone" kwadraty.
        while (liczbaPustych>0)
                {
                for (int i=0;i<N;i++)
                        if (liczbaRuchow[i]==r)
                                {
                                vector<int> mozliweRuchy=getRuchy(i); //zwraca wszystkie kody kwadratow, ktore moga powstac z kwadratu i po wykonaniu jednego ruchu
                                for (int j=0;j<mozliweRuchy.size();j++)
                                        if (liczbaRuchow[mozliweRuchy[j]]==-1) //jesli ten kwadrat jeszcze nie byl badany
						{
						liczbaRuchow[i]=r+1;
						liczbaPustych--;
						}
                                }
		r++;
                }
        //wyniki dla wszystkich mozliwych kwadratow sa w tablicy liczbaRuchow;
        }

Ogólnie pomysł opiera się na tym, że wszystkich możliwych kwadratów mamy 8^9=134217728. Każdy kwadrat możemy sobie łatwo zakodować przy pomocy liczby odwrotnie. Tworzymy sobie wielką tablicę kwadratów (indeks tablicy to kod kwadratu), której każdy element oznacza najmniejszą możliwą liczbę ruchów potrzebną do osiągnięcia w kwadracie takich samych cyfr. Tablicę wypełniamy "od tyłu". Na początku wiemy, że dla ośmiu kwadratów, które musimy osiągnąć liczba ruchów wynosi oczywiście 0. Potem w pętli wykonujemy ruchy dla już policzonych kwadratów