Se per qualsiasi ragione non è possibile utilizzare una delle implementazioni del solutore esistenti, è possibile migliorare l'euristica della stima non solo contando quante celle sono posizionate in modo errato ma piuttosto sommando la distanza (qualunque cosa possa essere ) dalle loro posizioni corrette.
0. Rappresentazione dello stato
Puoi rappresentare la posizione di una cella mediante il vettore 3D (= array) di 3 valori nell'intervallo < -1,1 > cioè da -1 a sinistra / in basso, a 0 per il centro a destra / in alto per +1. Ad esempio [1,1,0] è per la cella in alto a destra della faccia anteriore. Il centro del cubo è l'origine. Nota: le celle del centro del viso sono fisse, quindi la posizione è invariante di orientamento purché si orienti sempre i centri del viso allo stesso modo.
1. Distanza di Manhattan
Una delle metriche più semplici è la cosiddetta distanza di Manhattan, in cui si aggiungono solo le differenze assolute degli elementi corrispondenti. Ad esempio la distanza di manhattan da int[] v0 = [0,1,-1] a int[] v1 = int [1,1,1] è
var manhattan = abs(v0[0]-v1[0]) + abs(v0[1]-v1[1]) + abs(v0[2]-v1[2])
la stima del livello della soluzione è semplicemente la somma della distanza di Manhattan per correggere la posizione per ogni cella. Sebbene questo sia probabilmente un grande miglioramento, non tiene ancora conto del fatto che il cubo si avvolge.
Se non sbaglio, la distanza di Manhattan è stata utilizzata come euristica per IDA *, uno dei primi risolutori ottimali (in termini di giri minimi).
2. Scambia e amp; negare
Come potresti notare, la distanza effettiva dalla soluzione corrisponde a turni di numero (quarti) anziché a distanze fisiche sul cubo. Invece, dovremmo eseguire giri stessi - Rotazione 3D dei vettori di posizione della cella attorno agli assi che porterebbero alla moltiplicazione della matrice ...
... Tuttavia, a quanto pare, il nostro caso può essere notevolmente semplificato. Grazie alla scelta di < -1,1 > invece di < 0,2 > possiamo usare il ben noto swap & negare "trucco", un modo per calcolare i vettori perpendicolari. Fissando un elemento del vettore, scambiando gli altri due e negando uno (quale controlla la direzione) di quelli eseguirà il quarto di giro sulla faccia perpendicolare all'elemento fisso. La procedura potrebbe apparire come questa.
//calculates position of cell after a quarter-turn around given axis
void Rotate3DAligned(int[] vec, int axis, bool ccw)
{
var first = vec[(i-1)%3];
var second = vec[(i+1)%3];
if(ccw) first = -first;
else second = -second;
vec[(i-1)%3] = second;
vec[(i+1)%3] = first ;
}
Prendendo la posizione corrente di ogni cella e quella corretta è necessario determinare quanti turni (rotazioni, swap e amp; negati) devi prendere per portarlo nella posizione corretta. Questo può essere banalmente risolto da bruteforce poiché il numero massimo è piuttosto basso, o meglio algoritmico - quanti segni devi scambiare e quanti valori "spostare".
2.1. Hash it
Conta solo serie di turno distinte, ad esempio, salva la serie di giri in un HashSet o simile. Ciò consentirà di rilevare molti casi di celle mobili "batch", risolvendo il problema della soluzione a una svolta.
disclaimer: algoritmo non testato dall'implementazione, codice non controllato