Algoritmo di set nascosti Sudoku

Modifica: l'ho tagliato troppo qui. Lascerò l'originale intatto e poi indicherò il difetto.

Prima di rifiutare la soluzione della forza bruta, guarda la dimensione del problema.

Sudoku ha solo 9 elementi di seguito. Quindi la forza bruta naive è solo 512 combinazioni da controllare.

In pratica non ci può essere un insieme nascosto di 9 in 9 voci, questo significa che il set più grande che devi controllare è 8 - per un massimo di 256 combinazioni.

Tuttavia, supponiamo di avere un set nascosto di 8 voci su 9 - cosa dice del nono valore? Può avere solo un potenziale cliente, quindi lo avresti già scelto e stai trovando un set nascosto di 8 su 8, ma ancora una volta ciò non può avvenire.

Quindi sei giù a 7, per un totale di 128 casi.

Tuttavia, supponi di averlo? Quali sono i valori delle ultime due voci? Se qualche voce avesse un solo potenziale cliente, l'avresti già scelto. Ciò lascia solo un caso possibile: entrambe le restanti due celle hanno esattamente due prospettive. Due celle, due prospettive, hai un set: avresti dovuto trovarlo prima di cercare set nascosti.

Ora siamo giù a 6, per un totale di 64 casi.

Forza brutale 64 casi? Orribile!

Aggiornamento: la mia logica relativa alla dimensione massima che è possibile trovare è corretta ma il numero di casi è superiore a quello che stavo immaginando. Non è 6 su 6, è 6 su 9. Pertanto ci sono 465 combinazioni da controllare.

In pratica, tuttavia, raramente trovi un'intera riga senza valori noti e quindi raramente dovrai fare qualcosa come tutti i casi.

La conclusione è la stessa: la forza bruta è abbastanza ragionevole.

Se costruisci un grafico come di seguito, non è troppo difficile da risolvere. Devi ancora testare molte combinazioni, ma puoi fare molta potatura. Ho preso il suggerimento di Doc Brown di aggiungere 1 a C per renderlo un po 'più interessante.

Inizia guardando i numeri con un solo margine. Questi sono i set di 1. Puoi rimuoverli dal grafico.

Quindi troviamo serie di due. Possiamo temporaneamente eliminare 2 , 3 e 5 dalla considerazione in questo set, poiché sono tutti presenti in almeno tre celle. Questo lascia 1 , 4 e 8 .

Passa attraverso di loro e segui i bordi verso l'alto. Se inizi con 1 , allora A e C devono essere nel set. Segui i bordi di A e C indietro, il che ti dà 4 e 8 come candidati per il set. Per fare in modo che sia un set di due, non è necessario introdurre una nuova cella, ma 4 introduce D e 8 introduce B , quindi sappiamo che non ci sono set di due contenenti 1 , quindi può essere temporaneamente potato.

Backtrack e ripeti con 4 e 8 e possiamo determinare che non ci sono serie di due. Se avessimo trovato set di due, potremmo rimuovere quelli dal grafico.

Gli insiemi di tre funzionano allo stesso modo. Recidiamo solo un livello più in profondità.