Ricerca efficiente per risolvere un puzzle?

Question

Credo che risolvere un puzzle sia in generale NP-completo in base alle due domande collegate di seguito. Tuttavia, vorrei implementare un algoritmo euristico che funziona bene in pratica.

Supponiamo che i pezzi del puzzle siano codificati come 4 vettori di numeri interi che rappresentano i quattro lati. Un numero intero negativo indica un rientro che deve essere abbinato al corrispondente intero positivo che rappresenta un'estrusione. Zero rappresenta un bordo liscio (cioè un bordo.) Le rotazioni corrispondono quindi allo spostamento ciclico (supponendo che le rientranze/estrusioni siano rotazionalmente simmetriche.)

La mia euristica per una soluzione efficiente è cercare di piastrellare il puzzle in una spirale interiore che parte dai bordi. Qual è la migliore strategia per la costruzione di una catena di pezzi di adattamento che evita di provare in modo esaustivo tutte le combinazioni/rotazioni?

Ho trovato alcune domande SE correlate che sono rilevanti:

1. https://cs.stackexchange.com/questions/13849/are-zero-one-jigsaw-puzzles-np-complete
2. https://stackoverflow.com/questions/15121903/algorithm-for-solving-tiling-jigsaw-puzzle
3. Puzzle parzialmente riempito con sei tipi di piastrelle