la soluzione più "bella" matematicamente è un algoritmo ricorsivo con backtrack

te la caveresti con poche righe di codice