Questa non è una risposta, ma è troppo lunga per un commento ...
Usando la metrica della distanza rimanente, puoi certamente implementare una ricerca A * e darà il risultato corretto, ma sarà estremamente inefficiente. Il motivo è che è davvero una ricerca Dijkstra mascherata da A *. Peggio ancora, come osserva Shawn, è davvero una semplice ricerca in ampiezza.
Il motivo per cui è decaduto a Dijkstra è perché la tua metrica non fornisce indizi su quale sia la direzione migliore per passare attraverso lo spazio dello stato. Ogni passaggio da un determinato stato intermedio consiste semplicemente nel riempire una cifra in una cella - precisamente come economico / costoso come il riempimento di qualsiasi altra cifra / cella possibile in quel punto e senza alcun indizio su quale stato successore (con lo stesso numero di vuoto celle) sono più vicini a una soluzione corretta . Tutti i percorsi da quello stato intermedio alla soluzione sono della stessa lunghezza, compresi quelli che conducono attraverso stati illegali a una soluzione rotta.
Questo è legale nel senso che la metrica di distanza è un limite inferiore alla distanza rimanente da una soluzione. Ma non è solo un limite inferiore, è una distanza esatta. La tua "euristica perfetta" non sta guidando la ricerca verso la soluzione in alcun modo utile al di là di ciò che potrebbe fare Dijkstra.
Il motivo per cui è decaduto in una ricerca in ampiezza è la stessa cosa, ma in termini di pesi di spigoli già attraversati finora. Ogni percorso dall'inizio ad uno stato intermedio ha lo stesso numero di spigoli e lo stesso costo totale (lo stesso numero di celle riempite). Ogni edge ha effettivamente il peso uno e non ci sono scorciatoie da sfruttare per Dijkstra.
In pratica, i solutori di Sodoku di solito usano la ricerca di profondità a ritroso con controlli relativamente economici (se ci sono due delle stesse cifre in ogni cella, riga o blocco, questo stato è impossibile come lo sono tutti i possibili stati successivi) per evitare la ricerca parti impossibili dello spazio di ricerca. Non ci sono molte indicazioni su quali stati intermedi siano migliori senza spendere di più sull'euristica e sull'algoritmo di ricerca di quanto si ottiene potando ulteriormente l'albero di ricerca, e inoltre, il backtracking della ricerca con quella semplice potatura è molto veloce.