Come risolvere un puzzle Sudoku se tutti i campi vuoti rimanenti hanno possibilità multiple? Indovinare è l'unico modo

Come risolvere un puzzle Sudoku se tutti i campi vuoti rimanenti hanno possibilità multiple? Indovinare è l'unico modo?

Scrivo di sudoku ogni giorno, su Sudoku_meta - r/Sudoku_meta Questa domanda è abbastanza comune, ed è anche abbastanza comune che le risposte siano incomplete o addirittura errate. "Indovinare" non è stato definito, e la gente usa la parola senza definirla. Stabiliamo questo dall'inizio:

Tutti i sudoku corretti hanno una sola soluzione, per definizione di "corretto". Inoltre, ci sono da tempo programmi per computer che possono risolvere rapidamente qualsiasi sudoku corretto - o, per i sudoku impropri, mostrare che non ha soluzioni, o elencare più soluzioni, SW Solver ne mostra fino a 500. Questi programmi non indovinano. In generale, i computer non indovinano, punto. Piuttosto, elaborano liste, e sono abbastanza veloci da poter iniziare con una lista di possibili soluzioni e scegliere la prima e vedere cosa succede, e possono fare ulteriori scelte, e poi tornare indietro quando trovano contraddizioni. Questo è il Filo di Arianna, ed è una tecnica logica, non è un "tirare a indovinare".

Sono stati descritti una falange di schemi logici che possono essere usati per risolvere il sudoku, ma ci sono puzzle in cui tutti gli schemi conosciuti non sono sufficienti. Questi sono chiamati "irrisolvibili", e raramente ne vedrete uno, a meno che non li cerchiate. Possono comunque essere risolti, e non è necessario indovinare, cosa che richiederebbe troppo tempo. Piuttosto il metodo che abbiamo usato è ricorsivo, lo chiamo Bivalue Ariadne's Thread (BAT). Sceglie una risoluzione proposta da una coppia. Questo è molto più efficiente che fare una scelta qualsiasi (che sarebbe più appropriato chiamare "indovinare"). E poi usa tecniche normali all'interno di quella scelta per trovare contraddizioni o risoluzioni, e se questo arriva ad un'impasse, allora fa un'ulteriore scelta BAT. E così via. Quando trova una contraddizione, fa marcia indietro. ("backtracking") Per decifrare un grande irrisolvibile in questo modo sembra richiedere circa quattro ore con fino a quattro ore in più per provare la "soluzione unica."

Guardare una coppia e provare un membro di essa è una vecchia tecnica risolutiva, chiamata Nishio. Un Nishio potrebbe anche essere suggerito da un modello di candidato. Se un candidato mostra un "ciclo di scatole", con due candidati in ogni scatola di quattro in un ciclo, e una scatola ha tre candidati, so che uno di questi può essere eliminato. Quale? Bene, provo la "cella a gomito" e vedo cosa succede, e o crea una contraddizione o risolve il ciclo. Se lo fa, posso vedere come spostare quella scelta in una delle altre tre possibilità creerà una contraddizione. Quindi questo eliminerà quel candidato. Questo può risolvere l'intero ciclo o può lasciarlo come un "ciclo perfetto" che non può essere risolto al suo interno. Sarà risolto da qualche cellula in esso che sarà trovata diversa dal candidato in esame.

C'è stata poca attenzione, in generale, all'euristica risolutiva. Ho trovato quello che non ho mai visto menzionato da nessuna parte, che quando un puzzle ha un certo numero di coppie (coppie di celle o regioni), e mettendo da parte gli "irrisolvibili", le catene di colorazione da qualsiasi coppia di semi genereranno di solito risultati, o eliminazioni reciproche o risoluzioni reciproche.

La colorazione è fatta senza scegliere o preferire un candidato. Non è indovinare. È un'analisi logica, ma spesso più complessa di quanto si possa fare a mente. Ciò che la gente chiama "logica", nel risolvere il sudoku, è spesso solo ciò che può vedere immediatamente.

Se l'analisi di una soluzione è troppo complicata per essere vista senza documentazione scritta, viene chiamata "cattiva". "Troppo difficile". "Richiede di indovinare" e altri peggiorativi. Ma questo non ha niente a che fare con la logica, nel significato ordinario. La colorazione può essere fatta con inchiostro su carta, io la faccio ogni giorno. Penso che sia stato chiamato così perché la gente usava matite colorate, ma in realtà significa segnare i candidati in modo distinto, e può essere fatto con simboli. Cerchio e "triangolo" i candidati. Ultimamente, faccio questa parte a matita, con i candidati segnati con l'inchiostro, così se decido di abbandonare una colorazione, posso cancellarla facilmente, lasciando i candidati intatti.

Non è necessario alcun "backtracking" se si usa la colorazione. Piuttosto, si va avanti verso la soluzione.

Indovinare nel senso ordinario del sudoku può essere una cattiva strategia, o una strategia potente ed efficace, a seconda di come viene fatta. E se un "indovinello" viene scelto sulla base di un'analisi che dimostra che scoprirà una soluzione, non è veramente un indovinello. È una scelta informata.

I sudoku sono puzzle logici, ma la gente mescola la logica con la reattività e il giudizio e il "bene" e il "male".

Ma una semplice risposta alla domanda qui: No, indovinare non è l'unico modo. Non c'è sudoku che non possa essere risolto con l'analisi logica, e da esseri umani, non solo dal computer.