Una regola del Sudoku: l'unicità di soluzione.

[Vitalluni]

Su questo invece concordo . Ti interesserà estendere il ragionamento a sudoku con celle elementari composte da altri quadrati (4, 16, 25 etc.)

[maax]

Da diversi anni ho realizzato una pagina che permette di giocare a sudoku ( http://www.secerchitrovi.com/sudoku/)

Ho dovuto studiare un metodo per determinare se la soluzione proposta è unica o meno. Ho anche verificato che non controllando tale situazione si generano quasi sempre sudoku con più soluzioni.

Dopo aver creato uno schema casuale, in base al livello di difficoltà rendo bianche più o meno caselle. Affinché la soluzione sia unica:

- per ogni quadrante guardo i 4 quadranti della stessa riga e colonna
- per i quadranti della stessa riga, confronto ogni colonna del quadrante corrente (3 colonne) con tutte le colonne degli altri 2 quadranti (6 colonne)
- in ognuna delle 3 colonne non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 colonne in cui tutti i numeri siano lasciati in bianco. Nel caso in cui la permutazione sia con 2 numeri, almeno 1 dei 4 numeri non deve essere bianco, nel caso in cui siano 3, almeno 2 numeri della stessa colonna (sui 6 numeri totali) non devono essere bianchi.
- per i quadranti della stessa colonna, confronto ogni riga del quadrante corrente (3 righe) con tutte le righe degli altri 2 quadranti (6 righe)
- in ognuna delle 3 righe non può esistere una permutazione con 2 o 3 numeri presente anche in una delle altre 6 righe in cui tutti i numeri siano lasciati in bianco.

[hamming_burst]

Piccola nota:

Ti interesserà estendere il ragionamento a sudoku con celle elementari composte da altri quadrati (4, 16, 25 etc.)

man mano si amplia il numero di riquadri più difficile sarà trovare una soluzione in tempi umani.
se il sudoku standard ha \( \displaystyle {9} \) celle in altezza e \( \displaystyle {3} \) riquadri perciò \( \displaystyle {3}{x}{3} \) celle e \( \displaystyle {{3}}^{{2}}{x}{{3}}^{{2}} \) riquadri.
Generalizzando ad \( \displaystyle {n} \), l'algoritmo che risolve il problema del sudoku \( \displaystyle {{n}}^{{2}}{x}{{n}}^{{2}} \) ci metterà tempo superpolinomiale, perciò non si troverà una soluzione nel breve termine, e che sia unica o meno non importa.