Il Sudoku (数独 , pronunciato / s ɯ ː . D o . K ɯ / in giapponese / s u . D o . K u / o / s lì . D o . K y / in francese ) è un gioco della forma di una griglia definita nel 1979 dalla americana Howard Garns , ma ispirata al quadrato latino , così come il problema dei 36 ufficiali della svizzera matematico Leonhard Euler .
Lo scopo del gioco è riempire la griglia con una serie di numeri (o lettere o simboli) tutti diversi, che non si trovano mai più di una volta sulla stessa riga, nella stessa colonna o nella stessa regione (detta anche “blocco ”, “gruppo”, “settore” o “sottogriglia”). Il più delle volte, i simboli sono numeri che vanno da 1 a 9, quindi le regioni sono 3 × 3 quadrati . Alcuni simboli sono già disposti nella griglia, il che consente una risoluzione progressiva del problema completo.
Il nome sudoku (数 独) nasce dall'abbreviazione della regola giapponese del gioco “ Sū ji wa doku shin ni kagiru ” (数字 は 独身 に 限 る ) , che letteralmente significa “numero (数字) limitato (限 る) a uno solo (独身) ”(implicito per casella, per riga e per colonna). Questa abbreviazione combina i caratteri sū (数 , “Numero” ) e doku (独 , “Unico” ) . Questo nome è un marchio registrato in Giappone dell'editore Nikoli Corporation Ltd. In giapponese , questa parola si pronuncia [ s ɯ ː . d o . k ɯ ] ; in francese è comunemente usato con una pronuncia francese, cioè ignorando la vocale lunga presente sulla prima "u" e modificando leggermente il timbro delle vocali "u": [ s y . d o . k y ] . In Giappone, Nikoli possiede ancora il nome sudoku ; i suoi concorrenti usano quindi un altro nome: possono riferirsi al gioco con il nome originale americano “ Number Place ” ( inglese : place numérale ), o anche con la parola “ Nanpure ” (ナplusプ レ ) , che è più corta. Alcuni editori non giapponesi scrivono il titolo "Su Doku".
Probabilmente ispirato al quadrato magico , questo gioco è noto per la prima volta ai matematici cinesi , dal -650 , con il nome di Luoshu (洛 书, , “Libro del fiume Luo ”). Di ordine 3 , potrebbe quindi essere rappresentato da diversi simboli e utilizzato nel feng shui .
Questi sono ovviamente gli indiani , inventori di segni chiamati numeri arabi , che si sono limitati alle figure, e gli arabi , probabilmente intorno al VII ° secolo, quando i loro eserciti conquistarono nord-ovest dell'India .
I primi quadrati magici di ordine 5 e 6 apparvero in un'enciclopedia pubblicata a Baghdad intorno al 983, l' Enciclopedia della Confraternita della Purezza ( Rasa'il Ikhwan al-Safa ).
Nel XIII ° secolo , il matematico cinese Yang Hui (杨辉/楊輝, , 1238-1298), che definisce anche il triangolo Pascal , sta lavorando su un approccio strutturale del quadrato magico di ordine 3 .
Il matematico francese Claude-Gaspard Bachet de Méziriac descrive un metodo per risolvere il problema del quadrato magico, prendendo come esempio un commerciante di vino che vuole conservare le bottiglie in una scatola 3×3 , nel suo “Problemi piacevoli e deliziosi che si fanno dal numeri”, pubblicato nel 1612 .
Il matematico svizzero Leonhard Euler (1707-1783) creò o almeno cita il " quadrato latino ", una tabella quadrata di n righe e n colonne riempite con n elementi distinti, ogni riga e ogni colonna contiene una sola copia.
Nel settimanale per bambini Le Petit Français Illustré ( numero 7 del13 aprile 1889, pag. 92 ), sotto il titolo generale "Problemi divertenti" viene proposto il seguente gioco: "Disponi le 9 cifre , 1, 2, 3, 4, 5, 6, 7, 8, 9, nelle 9 caselle della figura sottostante. sotto, in modo che il totale delle 3 cifre di ciascuna linea verticale, orizzontale e diagonale sia pari a 15 . "
Nel 1892 , in Francia , sul quotidiano monarchico Le Siècle , apparve la più antica griglia di sudoku conosciuta. Il6 luglio 1895, sempre in Francia, il quotidiano La France pubblica un'altra griglia di questo gioco su una griglia 9×9 , chiamata “ Quadrato magico diabolico ”, e prodotta da MB Meyniel .
La versione moderna del sudoku è stata inventata anonimamente dall'americano Howard Garns e pubblicata per la prima volta nel 1979 su Dell Magazines con il nome Number Place .
Nel aprile 1984, Maki Kaji (en) (鍜 治 真 起 , Nato nel 1951 ) , direttore della società Nikoli , pubblica per la prima volta, nella sua rivista mensile “ Getsukan Nikoli suto ” (月刊 ニ コ リ ス ト ) , Il numero del gioco Posto sotto il sostantivo “ Sūji wa dokushin ni kagiru ” (数字 は 独身 に 限 る), poi “ Sūdoku ” (数 独 ) .
La griglia di gioco mostrata a destra, a titolo di esempio, è un quadrato con nove riquadri per lato, suddivisi in altrettante sottogriglie quadrate identiche, dette “regioni”.
La regola generica del gioco, riportata all'inizio dell'articolo, è qui tradotta semplicemente: ogni riga, colonna e regione deve contenere tutte le cifre da uno a nove una sola volta. Formulato in modo diverso, ciascuno di questi insiemi deve contenere tutte le cifre da uno a nove.
Una regola non scritta ma comunemente accettata vuole anche che una buona griglia di sudoku, una griglia valida, presenti solo una e una sola soluzione . Non è sempre così...
I numeri sono usati solo per convenzione, le relazioni aritmetiche tra loro non sono utili (tranne nella variante Killer Su Doku , vedi sotto). Qualsiasi insieme di segni distinti - lettere, forme, colori, simboli - può essere utilizzato senza modificare le regole del gioco.Le riviste Dell , le prime a pubblicare le griglie, hanno utilizzato i numeri nelle loro pubblicazioni. Al contrario, Scramblets , di Penny Press , e Sudoku Word , di Knight Features Syndicate , usano entrambi le lettere.
L'interesse del gioco risiede nella semplicità delle sue regole e nella complessità delle sue soluzioni. Le griglie pubblicate hanno spesso un livello di difficoltà indicativo. L'editor può anche indicare un probabile tempo di risoluzione. Sebbene in generale le griglie contenenti le figure più precompilate siano le più semplici, non è sempre vero il contrario. La vera difficoltà del gioco risiede piuttosto nella difficoltà di trovare l'esatta sequenza dei numeri da sommare.
Questo gioco ha già ispirato diverse versioni elettroniche che portano un diverso interesse alla risoluzione dei puzzle di sudoku. La sua forma a griglia e l'uso giocoso lo rendono simile ad altri puzzle pubblicati sui giornali, come cruciverba e problemi di scacchi . Il livello di difficoltà può essere adattato e le griglie sono pubblicate sui giornali, ma possono anche essere create on demand su Internet.
Sebbene le griglie classiche siano le più comuni, esistono diverse varianti:
In Giappone vengono pubblicate altre varianti. Ecco un elenco incompleto:
Il kit di gioco del World Puzzle Championship 2005 contiene una variazione chiamata Digital Number Place : invece di contenere la rivelazione, la maggior parte delle celle contiene un numero parzialmente disegnato che prende in prestito l'ortografia del display a sette segmenti .
Il 31 agosto 2005, The Times ha iniziato la pubblicazione di Killer Su Doku , chiamato anche Samunamupure (che significa "luogo di convocazione"), che indica la somma delle celle raggruppate e non rivela alcun riquadro, il che aggiunge ulteriore difficoltà nella ricerca della soluzione, anche se può aiutare a risolvere. Valgono le altre regole.
Vengono pubblicate anche variazioni alfabetiche, che utilizzano lettere anziché numeri. Il Guardian li chiama Godoku e li chiama demoniaci. Knight Features preferisce il termine Sudoku Word . Il Wordoku di Top Notch rivela le lettere nel disordine, una parola che va dall'angolo in alto a sinistra a quello in basso a destra. Un giocatore con una buona cultura può trovarlo e usare la sua scoperta per andare verso la soluzione.
In francese, questa variante alfabetica ha vari nomi come lettere Sudoku, Mokitu ( Télé 7 jours ) o Mysmo ( Liberation ). Alcune griglie sono limitate a parole con solo lettere diverse. Altri accettano parole che contengono più volte la stessa lettera, nel qual caso ogni volta ha un'ortografia diversa, ad esempio: MAHaR A DJ a . Il Custom Sudoku creato da Miguel Palomo invece ammette una parola con vere lettere ripetute.
Il Codice Doku ideato da Steve Schaefer ha una frase completa, mentre il Super Wordoku di Top Notch contiene due parole di nove lettere, ciascuna situata su una delle diagonali principali. Questi giochi non sono considerati veri e propri giochi di sudoku dai puristi, poiché la logica non è sufficiente per risolverli, anche se hanno una soluzione unica. Top Notch afferma che questi giochi sono progettati per bloccare soluzioni composte da software di risoluzione automatica.
Le sperimentazioni agronomiche in campo, generalmente costituite da più appezzamenti quadrati o rettangolari, sono spesso organizzati sotto forma di blocchi casuali completi , cioè gruppi di appezzamenti contigui all'interno dei quali sono presenti tutti i diversi elementi da confrontare (ad esempio concimi diversi) e distribuiti in modo casuale.
Quando il numero totale di appezzamenti disponibili è pari a un quadrato (16, 25, 36, ecc. ), un'altra possibilità corrisponde alla nozione di quadrato latino , che è tale che i diversi elementi da confrontare sono presenti in ciascuna delle linee e in ciascuna delle colonne del grafico.
La sovrapposizione di questi due dispositivi può dar vita a quello che è stato chiamato il quadrato magico latino , in particolare da WT Federer nel 1955 . Nell'esempio mostrato a fianco, ciascuno dei sei elementi studiati (ad esempio sei diversi concimi) è presente in ciascuno dei sei blocchi di appezzamenti 2 × 3 , in ciascuna delle sei righe e in ciascuna delle sei colonne. Questo è rigorosamente un sudoku 6 × 6 .
Il Sudoku classico non è quindi altro che un magico quadrato latino 9×9 .
Uno degli antenati del sudoku nell'antichità era un quadrato di nove caselle da riempire con tre lettere (A, B e C) senza che la stessa lettera comparisse due volte nella stessa colonna, riga o diagonale.
I più antichi "quadrati magici" digitali conosciuti si trovano in Cina (chiamati Luoshu洛 书, il libro del fiume Luo ) dove i numeri erano rappresentati da diverse forme geometriche contenenti n cerchi (circa -300 ), e in India dove furono inventati chiamiamo numeri arabi . In origine hanno significati divinatori.
Nel Medioevo , furono gli arabi che la X ° secolo, avrebbe dato la prima applicazione puramente matematico e non più sacri quadrati magici.
Durante il Rinascimento , Cornelio Agrippa ( 1486 - 1535 ), usa sempre i quadrati magici a scopo esoterico.
Il matematico francese Pierre de Fermat ( 1601 (o 1607 ) - 1665 ) lavorò sui quadrati magici e li estese ai cubi magici.
Nel 1691 Simon de La Loubère spiega il funzionamento del quadrato magico utilizzato in Siam , nel suo libro Du Royaume de Siam , dove ha una funzione sacra.
Nel 1782 , il matematico svizzero Leonhard Euler immaginò un problema in una griglia. Alcuni attribuiscono quindi la paternità del sudoku alla Svizzera, sebbene il lavoro di Eulero riguardi i quadrati latini e la teoria dei grafi.
Consideriamo sei diversi reggimenti, ogni reggimento ha sei ufficiali di diversi gradi. Ci chiediamo ora come posizionare i 36 ufficiali in una griglia 6×6, al ritmo di un ufficiale per casella, in modo che ogni riga e ogni colonna contengano tutti i gradi e tutti i reggimenti.
In altre parole, è un quadrato greco-latino di ordine 6 (la combinazione di due quadrati latini, un quadrato latino per i reggimenti, un quadrato latino per i ranghi), un problema la cui risoluzione è impossibile. Eulero lo aveva già intuito a suo tempo, senza però dare una dimostrazione formale della sua congettura. Dirà:
“Ora, dopo tutta la fatica che ci siamo presi per risolvere questo problema, siamo stati costretti a riconoscere che un simile accordo è assolutamente impossibile, anche se non possiamo darne una dimostrazione rigorosa. "Nel 1901 , il francese Gaston Tarry dimostrò l'impossibilità del risultato grazie ad una ricerca esaustiva dei casi e incrociando i risultati.
Il legame tra il Sudoku e il problema dei 36 ufficiali è il vincolo che impedisce la ripetizione dello stesso elemento nella griglia, arrivando infine a un gioco che utilizza il principio del quadrato latino (combinazione di due quadrati latini nel caso del quadrato greco-latino, quadrato latino suddiviso in più regioni nel caso del sudoku).
Il sudoku ha antenati francesi che risalgono al 1895 . Il gioco non è apparentemente un'invenzione recente come molti credevano. Alla fine del XIX ° secolo, il francese giocato davvero riempire cancelli 9 × 9 divisi in 9 regioni, molto vicino a questo gioco (ma griglie iniziali incluse ulteriori vincoli sulla soluzione), che sono stati pubblicati sui principali quotidiani del tempo, rivela Pour la Science nella sua edizione digiugno 2006.
Secondo la rivista, la griglia più vicina a un sudoku, trovata dal francese Christian Boyer, è quella di B. Meyniel, pubblicata sul quotidiano La France du6 luglio 1895. Una variante simile era stata pubblicata poco prima, innovembre 1892, in Le Siècle , una variante che utilizzava numeri a due cifre.
Nel 1979 , uno scrittore di puzzle freelance Howard Garns ha creato il primo gioco come lo conosciamo oggi. Dell Magazines lo introdusse quello stesso anno in una pubblicazione per il mercato di New York , Dell Pencil Puzzles and Word Games , con il nome Number Place . Nikoli lo ha introdotto in Giappone inaprile 1984nella rivista mensile Nikolist .
Nel 1986 Nikoli introdusse due novità, che renderanno popolare il gioco: i quadrati svelati sono distribuiti simmetricamente attorno al centro della griglia e il loro numero è al massimo 30. Tuttavia, in questo momento, ignoriamo ancora le altre possibili simmetrie sul griglia il cui asse di simmetria è una delle due diagonali o delle due mediane (la colonna e la riga centrali). Oggi, la maggior parte dei principali giornali giapponesi , come Asahi Shimbun , pubblicano il gioco in questa forma di simmetria centrale. Ma nonostante questo aspetto estetico, le griglie sono generalmente di scarsa qualità, perché le tre proprietà relative a simmetria, unicità della soluzione e irriducibilità non possono essere facilmente raggiunte contemporaneamente!
Nel 1989 , Loadstar e Softdisk rilasciarono DigitHunt per Commodore 64 , forse il primo software per personal computer a creare puzzle di Sudoku. Una società continua a utilizzare questo nome.
Nel 1995 , Yoshimitsu Kanai ha pubblicato un generatore di software sotto il nome di Single Number (traduzione inglese di Sudoku), per Macintosh , in giapponese e in inglese e, nel 1996 , lo ha fatto di nuovo per Palm OS .
Nel 2005 , Dell Magazines anche pubblicato due riviste dedicate al Sudoku: Original Sudoku e Estrema Sudoku . Inoltre, Kappa Publishing Group rileva le griglie di Nikoli in GAMES Magazine con il nome Squared Away . Anche i giornali New York Post , USA Today e San Francisco Chronicle pubblicano questo gioco.I puzzle appaiono in alcune antologie di giochi , come The Giant 1001 Puzzle Book (sotto il nome di Nine Numbers ).
È dentro luglio 2005che il Sudoku, edito da Sport Cerebral , editore specializzato in giochi di puzzle, arrivi in Francia . Il primo numero venderà 20.000 copie, il doppio del solito quando uscirà un nuovo gioco: un record, secondo Xavier de Bure, amministratore delegato dell'editore. La Provenza pubblica i primi orari giornalieri su27 giugno 2005, seguito nell'estate del 2005 da Le Figaro , Liberation , Nice-Matin , 20 minuti , Metro e Le Monde . La rivista 1, 2, 3… Sudoku ha pubblicato il suo primo numero innovembre 2005.
Il fenomeno si è diffuso anche in Svizzera , Wayne Gould fornisce le classifiche al quotidiano francofono Le Matin che quell'anno ha venduto 150.000 libbre di sudoku. Le Temps , un altro quotidiano svizzero, pubblica sudoku da allorasettembre 2005.
Già nel 1997 , Wayne Gould , un neozelandese e giudice in pensione di Hong Kong , era incuriosito da un cancello parzialmente riempito in una libreria giapponese. Per sei anni ha sviluppato un programma che creava automaticamente queste griglie. Sapendo che i giornali britannici pubblicano da tempo cruciverba e giochi simili, promuove il Sudoku con il quotidiano The Times , che per la prima volta pubblica una griglia su12 novembre 2004.
Tre giorni dopo, anche il Daily Mail ha pubblicato una griglia con il nome Codenumber . Il Daily Telegraph presenta la sua prima griglia su19 gennaio 2005, seguito da altre pubblicazioni del Telegraph Group . Il20 maggio 2005Il Daily Telegraph di Sydney ha pubblicato per la prima volta la griglia.
Questo è quando il Daily Telegraph pubblica le griglie su base giornaliera, dal23 febbraio 2005, pur promuovendo questo in prima pagina, che altri giornali britannici cominciano a prestarvi attenzione. Il Daily Telegraph ha continuato la sua campagna promozionale quando si è reso conto che le sue vendite aumentavano semplicemente per la presenza di una griglia di Sudoku. Il Times era piuttosto tranquillo sull'immensa popolarità che circonda il suo concorso di Sudoku. Aveva già pianificato di sfruttare il suo vantaggio pubblicando un primo libro sul Sudoku.
Ad aprile emaggio 2005, il gioco era così popolare che diversi giornali nazionali lo pubblicavano regolarmente. Questi includono The Independent , The Guardian , The Sun (intitolato Sun Doku ) e The Daily Mirror . Quando la parola Sudoku è diventata popolare nel Regno Unito , il Daily Mail l'ha adottata al posto di Codenumber . Da allora in poi, i giornali hanno gareggiato nella loro immaginazione per spingere i loro cancelli. The Times e Daily Mail affermano di essere i primi ad aver pubblicato una griglia di sudoku, mentre The Guardian afferma, ironia della sorte, che le sue griglie costruite a mano, ottenute da Nikoli , forniscono un'esperienza migliore rispetto alle griglie create a mano utilizzando il software.
L'improvvisa popolarità del sudoku nel Regno Unito ha attirato la sua giusta quota di commenti dei media (vedi link esterni sotto) e ne sono seguite parodie , ad esempio la sezione G2 del quotidiano The Guardian si preannuncia essere il primo supplemento con una griglia per pagina. Il sudoku è diventato particolarmente visibile subito dopo le elezioni nel Regno Unito del 2005, spingendo alcuni commentatori a sostenere che soddisfaceva un bisogno tra i lettori politici. Un'altra spiegazione suggerisce che cattura e mantiene l'attenzione dei lettori, con molti che si sentono sempre più soddisfatti quando emerge la soluzione. Il Times crede che i lettori apprezzino sia i puzzle facili che quelli difficili. Di conseguenza, li pubblica fianco a fianco dal20 giugno 2005.
La televisione britannica si è affrettata a cavalcare l'onda della popolarità e Sky One manda in onda il primo spettacolo di sudoku, Sudoku Live , il1 ° luglio 2005, presentato dal matematico Carol Vorderman . Nove squadre di nove giocatori, inclusa una stella , ciascuna rappresentante una regione geografica, tentano di completare una griglia di Sudoku. Ogni giocatore ha in mano un dispositivo che gli permette di inserire un numero in una delle quattro celle di cui è responsabile. È consentito lo scambio con gli altri membri della squadra ma, poiché manca la familiarità, i concorrenti non lo fanno. Inoltre, il pubblico a casa partecipa contemporaneamente a un'altra competizione interattiva. Sky One ha tentato di creare entusiasmo per il suo programma attraverso un'enorme griglia di 84 m di lato. Tuttavia, aveva 1.905 soluzioni.
Questo improvviso aumento di popolarità nel Regno Unito e giornali internazionali che Sudoku è considerato il " cubo di Rubik del XXI ° secolo " (traduzione libera " il cubo di Rubik del 21 ° secolo "). Ad esempio, Wayne Gould ha fornito elenchi per circa 70 quotidiani in 27 paesi alla fine del 2005. Lo sviluppo di questa azienda è stato in parte finanziato dal governo britannico, che la vede come un mezzo per prevenire le malattie senili (in particolare l'Alzheimer).
Il 28 novembre 2005, la televisione svizzera francofona lancia un programma televisivo quotidiano, Su/do/ku , in cui due candidati si sfidano nell'arco di 5 giorni, al ritmo di 3 turni di 8 minuti al giorno. Tuttavia, la difficoltà nel far apparire questo tipo di gioco in televisione farà sì che lo spettacolo si fermi dopo alcune settimane.
Campionati Nazionali si svolgono anche come il 1 ° campionato di sudoku Francia (Parigi,18 dicembre 2019) vinto da AntFal, 19 anni. Questa competizione organizzata da Cerebral Sport premia il miglior giocatore dell'anno. L'agenzia di comunicazione verticale Décollage ha organizzato questo evento unico in Francia. Da allora, molti altri tornei sono stati organizzati in Francia.
Il problema di posizionare le cifre su una griglia n² × n² comprendente n × n regioni è NP-completo .
Il problema della risoluzione di un qualsiasi sudoku può essere formalizzato in modo equivalente da un problema di colorazione del grafico : l'obiettivo, nella versione classica del gioco, è applicare 9 colori su un dato grafico, a partire da una colorazione parziale (la configurazione iniziale della griglia) . Questo grafico ha 81 vertici, uno per cella. Ciascuna delle scatole Sudoku può essere marcato con una coppia ordinata (x, y) , dove x ed y sono numeri interi compresi tra 1 e 9. Due vertici distinti etichettati da (x, y) e (x 'y') sono collegate da un arco se e solo se:
Una griglia soluzione è anche un quadrato latino . La relazione tra le due teorie è ormai del tutto nota, poiché D. Berthier ha dimostrato, in The Hidden Logic of Sudoku , che una formula logica del primo ordine che non menziona i blocchi (o le regioni) è valida per il sudoku se e solo se è valida per le piazze latine.
Ci sono notevolmente meno griglie di soluzione rispetto ai quadrati latini, perché il Sudoku impone vincoli aggiuntivi (vedi sopra il numero di possibili griglie complete ).
Il numero massimo di rivelati senza che appaia immediatamente una sola soluzione, indipendentemente dalla variante, è la dimensione della griglia meno 4 : se due coppie di candidati non sono registrate e le celle vuote occupano gli angoli di un rettangolo, e cioè esattamente due celle si trovano in una regione, quindi ci sono due modi per registrare i candidati. L'opposto di questo problema, ovvero il numero minimo di unveil per garantire un'unica soluzione, è un problema irrisolto, anche se gli appassionati giapponesi hanno scoperto una griglia 9×9 senza simmetria che contiene solo 17 unveil, mentre 18 è il numero minimo di scoperti per griglie simmetriche 9 × 9.
Gordon Royle ritiene che due griglie complete dovrebbero essere considerate equivalenti se possono essere trasformate l'una nell'altra (o viceversa) da una qualsiasi combinazione delle seguenti operazioni:
Una griglia completa crea quindi un totale di 2 × 9! × (3!) ^ 8 = 1 218 998 108 160 griglie essenzialmente equivalenti. Si noti l'analogia con le operazioni matriciali in algebra lineare .
Numero di rack completiOvviamente, il numero di griglie complete è inferiore al numero di modi per posizionare nove cifre 1 , nove cifre 2 …, nove cifre 9 in una griglia di 81 quadrati. Il numero di griglie è quindi molto inferiore a
Infatti, in questo conteggio, non si tiene conto di alcun vincolo di unicità.
Il numero di possibili griglie complete è anche inferiore al numero di quadrati latini di lato 9 .
Infine, il numero di possibili griglie complete è inferiore a quello che corrisponde al numero di modi per costruire le regioni senza tener conto dei vincoli sulle righe e sulle colonne.
Nel 2005, Bertram Felgenhauer e Frazer Jarvis hanno dimostrato che questo numero di griglie era:
Questo numero è uguale a:
9! × 72 2 × 2 7 × 27 704 267 971L'ultimo fattore è un numero primo . Questo risultato è stato dimostrato da ricerche approfondite . Frazer Jarvis ha quindi notevolmente semplificato la dimostrazione attraverso un'analisi dettagliata. La dimostrazione è stata convalidata indipendentemente da Ed Russell. Jarvis e Russell successivamente hanno mostrato che tenendo conto delle simmetrie, c'erano 5.472.730.538 soluzioni. È stato compilato un catalogo completo di queste griglie.
Numero di griglie incompletePer quanto riguarda il seguente problema, sembra irrisolto: se siamo interessati al numero di problemi proponibili , questo numero è sconosciuto; d'altra parte sappiamo che è molto più grande del numero sopra indicato perché ci sono moltissimi modi di presentare griglie iniziali la cui (unica) soluzione porta alla stessa griglia completata (completa). Infatti, partendo da una griglia completa, possiamo costruire un problema che può essere proposto con il seguente metodo:
È facile notare che nelle prime fasi non è realmente necessaria alcuna scatola, il che rende possibile imporre un problema diverso da un dato problema "proponibile", semplicemente svuotando una delle scatole che era prevista in questo problema.
È facile mostrare, su alcuni esempi di griglie complete, fino a che punto si possono, per una stessa griglia completa, presentare griglie iniziali di difficoltà del tutto contrastanti, dalle griglie per principianti alle cosiddette griglie diaboliche ; è comunque molto facile, conoscendo una griglia diabolica iniziale , realizzare una griglia per principianti la cui unica soluzione completa sia identica a quella della griglia diabolica scelta!
Tuttavia, ora esiste una stima (basata su un approccio statistico) del numero totale di problemi minimi (vedi sezione "classificazione dei problemi").
Numero minimo di rivelatiA rivelarsi una scatola il cui contenuto è visibile su una griglia di Sudoku, c'è il problema del loro numero minimo.
Il numero massimo di "rivelati" in una griglia che non fornisce una soluzione univoca è una griglia intera meno quattro: se in una griglia completa vengono rimosse due occorrenze di due numeri, e queste occorrenze sono agli angoli di un rettangolo, e che due di queste celle sono nello stesso gruppo, quindi ci sono due soluzioni per completare la griglia. Essendo questa una caratteristica generale dei quadrati latini, la maggior parte dei puzzle di Sudoku ha lo stesso massimo.
Il problema di sapere quante caselle iniziali riempite sono necessarie per portare a un'unica soluzione è, ad oggi, senza una risposta certa. Il miglior risultato, ottenuto dai giapponesi, è di 17 quadrati senza vincolo di simmetria. Oggi sappiamo che c'è un numero molto grande di problemi con 17 rivelati (vedi un esempio a fianco con la sua soluzione).
Niente dice che non possa essere possibile con meno numeri. Secondo un articolo di Gary McGuire pubblicato nel sito di pre-pubblicazione ArXiv non è possibile definirne uno con solo 16 rivelati e con un'unica soluzione.
Un altro problema irrisolto: a questa data non esiste alcun risultato sul numero di griglie complete in un super sudoku ( griglia 16 × 16 ).
1) Ci sono molti approcci per risolvere i puzzle di Sudoku, alcuni dei quali possono essere fatti solo dal computer. Qui si tratterà solo dei metodi utilizzati dai giocatori.
2) Non si tratta di dare un elenco esaustivo di questi metodi (che richiederebbe un volume voluminoso), ma un semplice schema. Esistono molte varianti ed estensioni, come il pesce alettato , troppo specializzato per essere dettagliato qui.
3) Quali sono le modalità di risoluzione ammissibili per un giocatore? Qualsiasi risposta a questa domanda avrebbe una componente soggettiva; non riconoscere questo fatto all'inizio porterebbe a sterili litigi. La maggior parte dei giocatori rifiuta tentativi ed errori o congetture.
4) Esiste un sito di riferimento, Sudopedia, che presenta in maniera consensuale il vocabolario standard del Sudoku e le regole risolutive più famose. Solo in inglese, funziona sugli stessi principi di Wikipedia.
5) Il metodo più veloce per un computer è quello di provare sistematicamente tutti i candidati rimanenti uno alla volta. Applicato ricorsivamente, può risolvere tutti i problemi. Ma questo metodo, poco elegante, viene rifiutato da quasi tutti i giocatori. Al massimo, è accettata come ultima risorsa, quando nient'altro funziona.
Per molti metodi, la discussione riguarda l'appartenenza a una "regione" che può essere (per definizione) una riga, una colonna o un gruppo.
A livello elementare, devi spazzare la griglia per ogni numero da uno a nove e per ogni blocco:
Quando c'è una sola possibilità per una riga, una colonna o un blocco, è necessariamente lì che il numero deve essere registrato. Con un po' di esperienza è possibile visualizzare dei riquadri “illuminati” su tutta la griglia, dove può comparire questo numero, che permette di rilevare configurazioni più avanzate.
Quando un problema può essere risolto utilizzando solo le regole di base in questa sezione, i giocatori esperti possono fare a meno della scrittura esplicita dei candidati. Questi problemi corrispondono a livelli “facili” o “elementari”.
SingletonIl "singleton" corrisponde al caso banale in cui è rimasta solo una cella vuota in una "regione" (riga, colonna o blocco). In questo caso, il valore della cella è ovviamente l'unico numero mancante nella regione: è sia l'unico posto dove il numero mancante può essere messo (singleton nascosto), sia l'unico valore che può ricevere la cella vuota ( nuda single).
Questa configurazione si trova soprattutto alla fine del problema, quando quasi tutte le celle sono state riempite.
Più in generale, il "singleton" corrisponde al caso in cui vi sia (localmente) una sola soluzione: una cella può ricevere un solo valore (singleton nudo), oppure un valore può essere assegnato solo a una casella (singleton nascosto). ), qualsiasi altra scelta che comporti un'incoerenza immediata. Si contrappone a “coppie”, “terzine” e “quadruple”, dove la discussione riguarda più valori contemporaneamente.
Knockout - Singleton nascostoLa ricerca di un “singleton nascosto” equivale a porre la domanda “In questa regione (riga, colonna o blocco), quali caselle possono ospitare un 1 (2 o 3 o… 9)? »: Se la posizione è unica nella regione considerata, allora il candidato diventa un valore in questa posizione.
La ricerca di un singleton nascosto è tanto più semplice quanto il valore è frequente nella griglia: i vincoli di posizionamento aumentano, mentre diminuisce il numero di posizioni possibili.
La marcatura delle celle fornisce solo un piccolo valore aggiunto per la ricerca di singleton nascosti: in ogni caso, l'intera regione deve essere scansionata per verificare che il valore cercato appaia solo una volta come candidato. È per questo motivo che questi singleton vengono definiti "nascosti".
Al contrario, il "singleton nascosto" è spesso facilmente rilevabile da una scansione sistematica di cifre e blocchi, perché la sua posizione dipende solo dalla posizione della cifra considerata nei blocchi vicini, e dal fatto che i quadrati siano liberi o occupati nel blocco considerato. . Nell'esempio a fianco, quando si stimano le possibilità di "4" per il blocco in alto a destra, l'unica informazione necessaria per le caselle di "7" e "8" è che sono occupate da cifre diverse da 4; la conclusione è la stessa indipendentemente dal numero contenuto in queste caselle.
Eliminazione indirettaL'eliminazione indiretta è un'estensione dell'eliminazione diretta.
Quando spazziamo la griglia per individuare le caselle ammissibili per un determinato candidato, possiamo trovarci nella situazione in cui in un blocco le caselle ammissibili si trovano tutte sulla stessa riga (o sulla stessa colonna). In questo caso, qualunque sia la posizione finale del candidato nel blocco, questo allineamento impedisce al candidato di altre celle libere in questa stessa riga (o colonna) situate negli altri blocchi. In altre parole: se in un blocco i candidati sono sulla stessa riga, il candidato viene escluso dalle altre celle libere della riga.
Allo stesso modo, quando in due blocchi in linea, i candidati sono limitati a due linee, i candidati del terzo blocco possono essere solo sulla terza linea (e viceversa per le colonne).
Questo divieto può portare all'identificazione di un singleton nascosto, come nel primo esempio a lato. Può anche, in modo più sottile, portare alla conclusione che in un altro blocco di questa riga (o colonna), i candidati possono essere collocati solo sulla stessa riga o colonna, portando passo dopo passo a una catena di eliminazione indiretta. . Questa prima applicazione dell'eliminazione indiretta può quindi essere eseguita senza marcatura, ma richiede più riflessione.
Nell'esempio a fianco, dopo che le coppie identificabili sono state marcate, l'esame del candidato "1" permette ad esempio di identificare due singleton, concatenando quattro eliminazioni indirette. C'è solo un "1" nella cella "Aa", che vieta la presenza di un altro "1" nella riga "A" e nella colonna "a" (in giallo).
Il secondo metodo di scansione consiste nel chiedere, su un dato gruppo (riga, colonna o blocco): (1) quali sono quelli mancanti e (2) dove possono essere. L'obiettivo è identificare i "singleton nascosti" e, in mancanza di ciò, le coppie da contrassegnare.
Questo metodo è particolarmente banale nel caso in cui nell'entità manchi una sola cifra, nel qual caso il box è un “singleton”, sia un “singleton nudo” che un “singleton nascosto”, e la sua soluzione è immediata.
È tanto più fruttuoso quando ci sono più caselle riempite sull'entità considerata. Può quindi essere eseguita automaticamente non appena un'entità ha solo due caselle vuote rimaste (registrazione diretta delle coppie), quindi, in ordine di preferenza, quando un'entità ha solo tre, quattro o anche cinque caselle vuote. Uno sweep "sei vuoti" produrrà solo eccezionalmente frutti (ma potrebbe produrne alcuni).
Singleton nudoSe una cella accetta un solo candidato, questo è il valore di quella cella. Questo è chiamato "singleton nudo". Il caso è tanto più probabile che si verifichi quando la cella esaminata si trova all'intersezione di regioni abbastanza piene, il che aumenta i vincoli e limita il numero di possibili valori sulla cella esaminata.
Questo nome di “naked singleton” deriva dal fatto che nel software di assistenza alla risoluzione del sudoku, quando viene visualizzata la lista dei candidati su ogni cella, queste caselle sono immediatamente visibili (nude) perché sono le uniche che no. 'hanno un solo candidato (singleton). Per la cronaca, questa designazione di "singleton naked" ( naked single , inglese o letteralmente "bare single") può portare alcuni filtri di parental control a limitare l'accesso alle pagine di discussione sudoku...
Marcatura dei duplicatiIn questo tipo di sweep è utile marcare direttamente le coppie, cioè i quadrati della griglia dove sono rimasti solo due candidati. Queste caselle possono essere compilate dalla coppia di cifre, scritte in piccolo oa matita; e l'unica evoluzione possibile per tali scatole è passare all'uno o all'altro di questi valori. Il vantaggio di questa marcatura è duplice:
La marcatura delle coppie costituisce il secondo livello di risoluzione del sudoku. "Segnare una coppia" su una data cella consiste nel notare che su questa cella ci sono solo due possibili candidati.
La marcatura può essere fatta semplicemente inserendo le due cifre candidate nella casella, ma con una scrittura abbastanza piccola da essere cancellata dal valore finale. C'è solo un modo per portare informazioni a una scatola che trasporta una coppia, è dando il valore effettivo; pertanto, la marcatura delle coppie non porta a un sovraccarico grafico eccessivo.
È importante, in questa fase, notare che se effettivamente è utile la marcatura diretta delle possibilità limitate alle coppie in un riquadro, marcare così le possibilità più estese (tre, quattro possibili candidati, ...) ha invece nessun interesse (ed è una pratica per principianti).
coppie accoppiateQuando le coppie sono marcate, si può incontrare la stessa coppia di candidati in due celle dello stesso gruppo (riga, colonna o blocco). In questo caso le due celle occupate dalla coppia sono accoppiate e funzionano come se fossero occupate dai corrispondenti candidati, escludendo questi due candidati da tutte le altre celle libere di questo stesso gruppo (riga, colonna o blocco).
Alcuni casi particolari sono facilmente individuabili:
Prendere in considerazione queste coppie accoppiate può portare a notare nuove coppie. Nell'esempio a fianco, la ricerca di possibili candidati ha portato in particolare ad individuare due coppie “78” sulla colonna “e”. Delle sei celle vuote della colonna, quindi, solo quattro sono realmente libere, poiché due possono essere considerate quasi piene.
Durante la scansione della griglia per individuare le celle ammissibili per un determinato candidato, potremmo trovarci nella situazione in cui il candidato in esame appare in coppia sulla stessa riga o colonna. In questo caso, il candidato viene escluso dal resto di questa riga (o colonna), limitando le possibilità negli altri blocchi interessati da questa riga (o colonna).
coppie nascosteLe "coppie nascoste" di solito richiedono una ricerca sistematica per essere rilevate. Per rilevarli è necessario eseguire una scansione sistematica per blocco (riga, colonna o quadrato). Su ogni blocco, devi porti la domanda "dove sono gli 1" [...] "dove sono i 9". Se una delle cifre può trovarsi solo in due posizioni possibili, potrebbe far parte di una coppia nascosta; e se un'altra cifra può essere solo in queste stesse due posizioni, queste due cifre insieme formano una "coppia nascosta". In questo caso, poiché queste due cifre possono trovarsi solo in queste due posizioni, non è possibile che un'altra cifra si trovi nelle stesse posizioni, il che elimina le possibilità corrispondenti per le altre cifre.
La ricerca delle coppie nascoste è molto più noiosa, perché riguarda teoricamente 3x9 = 27 blocchi, per i quali è necessario verificare se una delle 9x8 / 2 = 36 coppie possibili può occupare solo due delle 9 caselle possibili. È possibile velocizzare un po' questa ricerca, osservando da un lato che se la ricerca è sistematica, una volta testata la coppia "ab" è inutile testare la coppia "ba", e soprattutto, sul d'altra parte, che se un quadrato è già occupato da un doubleton, una possibile coppia nascosta può riguardare solo questi stessi due elementi.
Ad esempio, nella figura allegata, sono state individuate tre coppie nascoste, che consentono di riempire una casella ciascuna:
Quando si cercano quelli mancanti su un gruppo in cui le coppie sono segnate, ci si può trovare nella situazione in cui il gruppo mostra due coppie "ab" e "bc" aventi un elemento "b" in comune. Occorre poi esaminare se un'altra cella di questo gruppo ammette come possibili valori solo questi stessi tre valori "abc". Se questo è il caso, questi tre valori sono necessariamente distribuiti su queste tre celle, e sono di conseguenza esclusi dalle altre celle libere del gruppo:
Queste ricerche sono più laboriose delle precedenti e per condurle in modo sistematico è più facile contrassegnare le celle. La nozione di candidato non è inerente al problema del Sudoku, ma deve essere introdotta dal giocatore per implementare la maggior parte dei metodi di risoluzione.
Quando un numero non è a priori impossibile in una cella, si dice che sia un candidato. Mentre le divulgazioni sono i dati iniziali del problema, l'insieme dei candidati si evolve durante il processo di risoluzione. Può solo diminuire; e ciò avviene quando è stato dimostrato (con i vari metodi di seguito descritti) che un candidato è di fatto impossibile. I fondamenti logici formali di questa nozione (che non è così ovvia come sembra) sono stati definiti e studiati in dettaglio in The Hidden Logic of Sudoku , un libro in lingua inglese ( The Hidden Logic of Sudoku ); fanno appello alla logica epistemica . Anche l'articolo From Constraints to Resolution Rules, Part I : Conceptual Framework , disponibile gratuitamente sulle pagine web del suo autore, espone questa logica nel quadro generale dei problemi di soddisfazione dei vincoli.
Ci sono due notazioni usate per i candidati: indicizzata e puntata.
Quando possiamo dedurre che un numero è necessariamente il valore di una cella:
Quando si utilizza una valutazione di possibili candidati, il metodo di eliminazione indiretta (menzionato sopra nei metodi "facili") si presenta quindi in due casi che consentono di escludere determinati candidati:
L'eliminazione indiretta può avvenire formalmente su cellule etichettate, ma la sua rilevazione non è tanto facilitata dall'etichettatura.
Gruppi nudi e nascostiI gruppi nudi e nascosti corrispondono a situazioni abbastanza simmetriche: nella stessa regione (riga, colonna o blocco), cerchiamo un gruppo di n (solitamente da due a quattro) numeri la cui presenza è possibile in altrettante celle vuote. e presentando una configurazione notevole, sia che la presenza di questi numeri sia impossibile nelle altre celle della stessa regione, sia che nessun altro numero possa comparire nelle celle del gruppo:
Vediamo che queste definizioni sono simmetriche: se un gruppo di n celle vuote in una regione forma un gruppo nudo con n candidati, le altre celle vuote formeranno un gruppo nascosto (con un numero possibilmente diverso di membri) con il resto dei candidati ; e viceversa.
La ricerca dei single nascosti è già stata fatta con la scansione elementare, e i single nudi sono già stati identificati con la ricerca dei mancanti e l'etichettatura delle coppie. Allo stesso modo, le coppie nude accoppiate possono essere identificate da una semplice marcatura delle coppie. Questi non banali gruppi nudi e nascosti possono portare notizie solo in regioni con molti riquadri liberi: almeno, se nella stessa regione c'è sia un gruppo nudo (di due o più riquadri) sia un gruppo nascosto (due o più riquadri ), la regione ha necessariamente almeno quattro o più caselle libere. Se una regione ha meno di quattro spazi liberi, non può essere ulteriormente ridotta; se un sottogruppo ha meno di quattro membri, non può essere compresso; e una volta che tale regione è stata ridotta, non è più necessario esaminarla successivamente.
Il metodo trova la sua piena applicazione solo da cinque celle libere e dalla ricerca di triplette nude: una regione di cinque celle libere può includere una tripletta nuda (e una coppia nascosta), una regione di sei celle può includere una terzina o una quadrupla nuda ( e, rispettivamente, una tripletta o una coppia nascosta), e così via.
Indipendentemente dal gruppo individuato, possiamo quindi eliminare i candidati:
Dopo questa riduzione, la situazione è di mutua esclusione: i numeri del gruppo non compaiono altrove, e nelle caselle ci sono solo i numeri del gruppo.
Gruppi nudiIl trattamento delle “coppie legate” è stato descritto con il tagging delle coppie, ed è stata evidenziata la possibilità di identificare talvolta alcune “terzene nude”. I "gruppi nudi" sono il caso più generale di questo trattamento. Il ragionamento è lo stesso sia che il gruppo sia di due, tre o quattro caselle (e qui si darà per tre caselle); ma chiede in pratica di segnare i candidati.
La regola è questa. Se nella stessa regione (riga, colonna o blocco) si osserva un gruppo di tre celle per le quali:
i) ci sono al massimo tre candidati, e
ii) tutti questi candidati sono presi dagli stessi tre valori;
quindi necessariamente, questi tre valori dovranno essere presi da queste tre caselle e non possono andare altrove in questa regione. La dimostrazione è fatta per assurdo : se uno di questi tre valori candidati fosse assegnato a una cella altra di questa regione, allora rimarrebbero solo due valori possibili per riempire queste tre celle, portando a un'impossibilità. Pertanto, quando viene individuata questa configurazione di gruppo, i valori del gruppo non possono essere presi dalle caselle che non appartengono al gruppo: nel resto della regione, i candidati corrispondenti a questi valori possono essere cancellati.
Quando n è maggiore di 2, capita frequentemente che almeno una delle celle del gruppo non abbia come candidate tutte le cifre della lista: si parla allora di gruppo "incompleto", ma ciò non toglie nulla alla lista la validità della manovra di eliminazione.
I gruppi nudi utilizzabili con questo metodo includono due, tre o quattro elementi. Si può infatti notare che il caso limite di “nudo gruppo” ad un elemento corrisponde al caso dei nudi singleton. Viceversa, se un “gruppo nudo” ha più di quattro elementi, vediamo che in pratica è associato simmetricamente ad un “gruppo nascosto” di meno di cinque elementi, che è più facile trovare.
Come nel caso dei “nudi single”, queste configurazioni prendono il nome dal fatto che sono immediatamente evidenti (svelate, quindi “nude”) sulle griglie in cui sono stati segnati i candidati. Infatti, questi “gruppi nudi” possono essere facilmente ricercati formalmente su una griglia dove i candidati sono stati marcati, e dove queste terzine sono state così rese più visibili: non appena una scatola ha solo un piccolo numero di candidati, stiamo cercando la possibilità di un tale gruppo, cercando di vedere se altre caselle nella stessa regione (riga, colonna o blocco) hanno vincoli simili.
Cerca "gruppi nudi"La ricerca dei “nudi gruppi” viene effettuata dopo aver contrassegnato i candidati, mediante scansione sistematica delle scatole contenenti due, tre o quattro candidati. Le tappe sono tipicamente, in ordine di difficoltà crescente:
Queste prime due scansioni possono essere eseguite anche quando sono contrassegnate solo le coppie candidate.
Se questa prima scansione fallisce, un "gruppo nudo" avrà necessariamente almeno tre candidati, inclusa almeno una cella completa (altrimenti il gruppo sarebbe stato rilevato nel passaggio precedente). Si formerà quindi una terzina o una quartina:
Se questa seconda scansione ha avuto esito negativo, un eventuale “gruppo nudo” avrà necessariamente quattro candidati, di cui almeno un riquadro completo. Come ultima risorsa, si può cercare su tutte le caselle con quattro candidati se questi stessi quattro candidati si trovano su quattro caselle diverse della stessa regione.
Gruppi nascostiUna prima osservazione è che il complemento di un gruppo nascosto è un gruppo nudo: se sulle n + c celle libere, un sottoinsieme di c celle forma un “gruppo nascosto” di c candidati (cioè che questi c candidati non compaiono nel n altre caselle), il resto delle n caselle forma un gruppo spoglio di n candidati (cioè i candidati del gruppo c non compaiono lì) .
Per cercare un gruppo nascosto, devi cercare un gruppo di valori c i cui candidati appaiono solo sulle celle c nella stessa regione. All'interno di questo insieme di riquadri, alcuni non contengono l'intero gruppo e possono contenere altri candidati esterni al gruppo. In alternativa, possiamo cercare questo stesso gruppo di c valori, che sono esclusi da n celle libere del gruppo.
La marcatura non permette di identificarli rapidamente, ed è necessaria una ricerca sistematica, che è all'origine della designazione di "gruppo nascosto": la loro identificazione è molto più laboriosa di quella di "gruppi nudi", e porta al sudoku di maggiore difficoltà. Va anche notato che la difficoltà aumenta molto fortemente con il numero di quadrati nel gruppo.
L'identificazione di gruppi nascosti può spesso essere effettuata indirettamente identificando gruppi di nudi più grandi. Nell'esempio a fianco, la ricerca di una tripletta nuda nella colonna “f” porta a notare il gruppo “367” in Df e Ff.
Abbiamo così gradualmente trovato un gruppo nudo di cinque candidati "36789". Il complemento, corrispondente alle caselle Af, Gf e Jf, corrisponde quindi ad un gruppo nascosto di tre valori "124".
La ricerca diretta di un gruppo nascosto riguarda piccoli gruppi di due o tre candidati (eccezionalmente quattro), quindi non può riguardare candidati che compaiono più spesso nella regione considerata. La ricerca consiste innanzitutto nel determinare i candidati che potrebbero formare un gruppo nascosto nella regione, quindi nel verificare sui candidati identificati se effettivamente formano un tale gruppo. Per usare l'esempio a fianco:
Per trovare queste configurazioni, cerchiamo di vedere se un candidato appare solo in un numero specifico di righe e colonne, per le quali viene determinato il numero di intersezioni.
Il ragionamento che consente l'eliminazione dei candidati è il seguente nel caso dell'X-Wing. Siano quattro caselle a, b, c, d (esempio: Fa, Fj, Jj, Ja) contenenti tutte un candidato comune K e formanti un rettangolo. Se sulle due linee (ab) e (cd), il candidato può essere presente solo in a o b, e in c o d, allora possiamo rappresentare l'X-Wing con il rettangolo abcd, o con le sue diagonali ( ac) e (bd) che formano una X. In questa situazione, l'insieme delle possibilità si riduce a due casi. Nel primo caso K è in a, quindi non può essere in b, né in d, né sulla colonna di a. Poiché K non può essere in d, è necessariamente anche in c, e quindi non può comparire nella colonna di c. Nel secondo caso K è in b, quindi non può essere in a, né in c, né nella colonna di b. Quindi K è necessariamente anche in d e non può comparire nella colonna di d. In entrambi i casi, senza sapere dove sarà K, vediamo che non può apparire né nella colonna di a, né nella colonna di b (tranne in a, b, c o d), il che ci consente di eliminare i candidati. Analogo ragionamento può essere svolto nel caso simmetrico in cui sono le linee che non possono accogliere il candidato.
Il caso Swordfish mostra una figura non di 4 vertici come l'X-Wing, ma di sei vertici. Possiamo vederlo come due rettangoli uniti da un vertice. Questo vertice comune non ha alcuna utilità nella figura, quindi sono rimasti solo sei vertici. Tecnicamente, devi trovare 3 righe (o colonne) in cui un candidato K appare solo in due caselle. Queste caselle sono allineate da una riga all'altra a due a due.
Una volta individuati, il trattamento formale di questi gruppi “in salamoia” è:
Nota : non esiste una regola peer per i blocchi.
Simmetrie generalizzate e tabella di risoluzione estesaIn The Hidden Logic of Sudoku , basato su una formalizzazione logica sistematica del gioco, sono state rese esplicite tutte le sue simmetrie generalizzate, in particolare tra righe e numeri, tra colonne e numeri e tra blocchi e numeri. È stato sviluppato un nuovo metodo di risoluzione, basato sul loro uso sistematico. Gli spazi rn , cn e bn (complementare al solito rc spazio ) sono stati così introdotta ( p. 35 della prima edizione). È stata progettata una griglia di risoluzione estesa, che mostra i collegamenti di coniugazione come riquadri (dello spazio rc , rn, cn o bn) con due candidati e può facilitare l'applicazione del metodo. In questo modo, i sottoinsiemi nascosti, così come gli X-wings, Swordfish e Jellysfish , appaiono tutti come semplici coppie, triplette o quadruple. In un quadro generale per la gestione delle stringhe, queste simmetrie sono state utilizzate per introdurre nuove regole di risoluzione, come le stringhe xy nascoste e le stringhe nrczt successive . Questo metodo è stato implementato in un risolutore, SudoRules, basato su tecniche di Intelligenza Artificiale e simulando un giocatore umano.
Quando le tecniche di eliminazione dei candidati basate su figure (o pattern ) semplici non sono sufficienti, è necessario ricorrere a figure più complesse, ad esempio catene. Una catena semplice è una sequenza di candidati tale che ciascuno è collegato al precedente. Si possono definire diversi tipi di stringhe, tutte da considerare generalizzazioni di un unico tipo base, la stringa xy .
Stringhe XyUna catena xy è una serie di celle comprendenti solo duplicati, vale a dire esattamente 2 candidati. Inoltre, queste scatole devono avere un collegamento tra loro: dobbiamo essere in grado di passare dall'una all'altra rimanendo nella stessa regione, seguendo il “filo” di un candidato. Ad esempio, per una serie di quattro celle "ben disposte", potremmo avere i seguenti candidati {1.9} {1.3} {3.6} {2.6}.
Nei casi interessanti di catene, due approcci consentono l'eliminazione dei candidati:
In questo caso, mostriamo che per qualsiasi casella X, esterna alla catena, contenente il candidato "a", e situata sia nella stessa regione della prima casella che nella stessa regione dell'ultima casella, questa casella non può contenere il candidato "un". Se "a" fosse vera in questa casella, allora "a" sarebbe falsa nella prima casella della stringa e la stringa verrebbe ridotta a {b} {c} {d} {a}. Ora "a" non può essere sia in X che nell'ultima casella della catena. Quindi X non può contenere "a".
Partendo da una cella A contenente {x, y} e che vediamo due diversi "percorsi" basati su stringhe del tipo {x, y} {y, z} {z, t} {t, u} ... in arrivo in corrispondenza di una cella B contenente {t, u}, allora può essere che indipendentemente dalla scelta di x o y nella prima cella, e quindi del percorso che seguiamo per eliminare i candidati, un candidato viene eliminato sistematicamente. Quindi abbiamo appena trovato una soluzione in una scatola. Ad esempio se la t dell'ultima casella viene eliminata nel caso in cui scegliamo y nella prima casella e seguiamo il percorso 1 : {x, y} {y, z} {z, t} {t, u} , ma anche nel caso in cui scegliamo x e seguiamo il percorso 2 : {x, y} {x, v} {v, u} {u, w} {w, y} {y, t} { t, u}, quindi u è la casella della soluzione B .
Questi ragionamenti sono comuni a tutti i tipi di catene.
Generalizzazioni delle stringhe xy: stringhe ALS e stringhe nrcztTra le generalizzazioni logiche "naturali" delle catene xy, abbiamo:
- Le stringhe ALS ( Almost Locked Sets ), le più vecchie e di gran lunga le più utilizzate dai giocatori sui forum di Sudoku; un collegamento in queste catene non è più un candidato ma un ALS ( Almost Locked Sets ), cioè un insieme di k celle (sulla stessa riga, stessa colonna o nello stesso blocco) i cui candidati appartengono a un insieme di k + 1 numeri;
- le stringhe xyt , xyz e xyzt nonché le loro controparti “nascoste” negli spazi rn , cn e bn (definite nella prima edizione di The Hidden Logic of Sudoku ); le catene nrczt, o catene supersimmetriche, che generalizzano le precedenti unendo tutte le celle degli spazi rc , rn, cn e bn (definite nella seconda edizione di The Hidden Logic of Sudoku ));
- una combinazione dei due, molti esempi dei quali possono essere trovati sul forum sudoku-factory .
In genere si richiede un problema, che poi diciamo ben formato , che abbia una e una sola soluzione. Ovviamente, questo requisito è principalmente per il creatore del problema.
Il requisito che ci sia una soluzione non è un problema per il giocatore. Se non è soddisfatto dal creatore, il giocatore sarà solitamente in grado di mostrare la contraddizione. Le regole sopra menzionate dovrebbero in realtà essere interpretate in un modo leggermente più sottile rispetto alla (normale) forma in cui sono state enunciate. La vera interpretazione è: "se c'è una soluzione e se il candidato C è vero, allora abbiamo una contraddizione". Da cui concludiamo "se c'è una soluzione, allora C è falso", ed eliminiamo C dai candidati. In questo modo, se il problema è contraddittorio, siamo sicuri che non troveremo una soluzione.
Il requisito dell'unicità è più delicato. È imposto al creatore, ma il giocatore non può in alcun modo controllarlo. In pratica, questo significa che, se viene proposto un problema che ha più soluzioni ma il giocatore applica regole derivanti dall'ipotesi di unicità, può quindi effettuare eliminazioni ingiustificate (e perdere soluzioni alternative o portare a una situazione in cui crede non ci sia soluzione ). Questo problema tende a scomparire in pratica poiché i creatori di problemi ora prendono più seriamente l'unicità.
Il principio del rettangolo proibitoConsidera quattro celle che formano un rettangolo che si estende su due righe, due colonne e solo due blocchi. Se il contenuto di queste quattro celle è:
ab ab
ab ab
quindi per qualsiasi soluzione del problema avente i valori
ab
ba
per le celle di questo rettangolo, c'è un'altra soluzione con i valori
ba
ab
e quindi il problema non può avere un'unica soluzione.
La configurazione iniziale è chiamata rettangolo proibito. Da lì, si possono definire diverse regole volte a prevenire che questa situazione si verifichi. Queste regole sono valide solo nel presupposto dell'unicità.
Esempi di regole basate sull'uso del rettangolo proibitoRegola UR1: nella configurazione (dove le quattro celle formano un rettangolo di due righe, due colonne e solo due blocchi):
ab ab
ab abc
eliminare a e b dall'ultima cella.
Regola UR2-H: nella configurazione (dove le quattro celle formano un rettangolo su due righe, due colonne e solo due blocchi):
ab abc
ab abc
dove le due celle a destra sono nello stesso blocco, eliminare c da qualsiasi altra cella relativa alle due celle a destra.
Ci sono molte varianti di queste regole.
Non esiste una classificazione universale dei vari problemi: qualsiasi classificazione si basa sulla scelta di un insieme di metodi di risoluzione. Possiamo però distinguere tra classificazioni ad ampia copertura (SER, SXT, NRCZT, ecc. ) e classificazioni a quattro o cinque livelli (da "semplice" a "diabolica"), come quelle pubblicate sui giornali. Questi ultimi di solito coprono solo problemi relativamente semplici, con SER non più di 5 o 6.
Va notato che ogni classificazione è solo indicativa e che, per un giocatore, due problemi aventi lo stesso valore in una classificazione possono presentare difficoltà molto diverse.
Una nozione generale molto utile da un punto di vista teorico è quella di problema minimo . Un problema si dice minimo (o, più raramente, “localmente minimo”) se ha un'unica soluzione e se, ogni volta che si cerca di portare via qualcosa di svelato, il puzzle ottenuto (che ovviamente ha sempre almeno una soluzione) . ) finisce per avere diverse soluzioni.
Quando vogliamo fare statistiche sulla classificazione dei problemi, dobbiamo sempre fare riferimento a insiemi di puzzle minimi, altrimenti queste statistiche non hanno molto significato: anzi, aggiungendo quanti rivelati vogliamo, scegliamo tra i suoi valori di soluzione, con un puzzle minimo, si possono ottenere moltissimi enigmi che avranno ovviamente la stessa soluzione, la maggior parte dei quali banali da risolvere.
Nota che è molto facile e veloce creare insiemi casuali di migliaia di problemi minimi dal computer (con, ad esempio, il software gratuito suexg (per maggiori dettagli sulla creazione di puzzle, vedi sotto).
La minimalità è un requisito aggiuntivo che a volte ci si aspetta dal creatore di problemi. Non ha effetto sul giocatore. Tuttavia, può essere difficile conciliare con altri requisiti aggiuntivi, come requisiti estetici, ad esempio di simmetria, ovvero che quelli esposti si trovano in un insieme di celle aventi una certa forma di simmetria. È più difficile creare problemi sia minimi che con determinate simmetrie (in particolare, suexg no).
Nel corso dell'anno 2008 è apparso che i classici generatori di problemi minimi, siano essi " bottom-up " o " top-down " (cioè che partono da una griglia vuota e la riempiono poco a poco o partono da una griglia completa ed eliminare gli indizi uno per uno) erano tutti fortemente sbilanciati a favore di problemi con pochi indizi. È stato introdotto un nuovo tipo di generatore: i generatori a controllo di polarizzazione. Anche loro sono di parte, ma il loro pregiudizio è noto e può quindi essere corretto. Vedere uno dei due libri Constraint Resolution Theories , Pattern-Based Constraint Satisfaction e Logic Puzzles o l'articolo disponibile sul sito web del suo autore Unbiased Statistics of a CSP - A Controlled-Bias Generator .
Il SER ( Sudoku Explainer Rating ) è di gran lunga la classificazione più utilizzata. Sudoku Explainer è un software gratuito (in java), sviluppato da Nicolas Juillerat e scaricabile dal web. Può essere usato per risolvere problemi ma anche per produrre una stima della loro difficoltà, chiamata loro SER. Questo assume valori da 1 a 11,7 (valore massimo noto fino ad oggi).
Le regole che utilizza (alcune delle quali si basano sul presupposto dell'unicità) sono abbastanza eterogenee e i valori assegnati abbastanza ad hoc . A titolo illustrativo, ecco i livelli associati ad alcune delle regole sopra definite.
I livelli superiori utilizzano vari tipi di catene:
Queste catene di forzatura dinamica sono una forma di tentativi ed errori.
In sostanza, la classificazione dei problemi più difficili si basa sul numero di inferenze elementari necessarie per l'eliminazione più difficile in una procedura per tentativi ed errori fino a due livelli (cioè - diciamo permettendo di fare ipotesi su un massimo di due candidati contemporaneamente) . Qui, inferenza elementare significa un singleton (nudo o nascosto), o l'eliminazione di un candidato in diretta contraddizione con uno o due valori noti o presunti per tentativi ed errori.
Questa classificazione, definita in The Hidden Logic of Sudoku , si basa sulla lunghezza massima della stringa nrczt necessaria per risolvere un problema. A differenza del SER, qui viene utilizzato un solo tipo di regola (le stringhe nrczt di varie lunghezze) e questa classificazione, puramente logica, indipendente dal presupposto di unicità e indipendente da qualsiasi implementazione, è compatibile con tutte le simmetrie del gioco.
Pur basandosi su regole quindi molto diverse da quelle alla base del SER, questa classificazione è strettamente correlata a questa: uno studio effettuato su 10.000 diversi problemi minimi (ottenuti con il generatore pseudocasuale suexg) fornisce un coefficiente di correlazione di 0,89. Ciò significa che queste due classificazioni catturano un aspetto importante di ciò che rende la complessità di un problema.
Statistiche della classificazione nrcztLe statistiche della classificazione nrczt sono disponibili:
- in tre libri: The Hidden Logic of Sudoku , Constraint Resolution Theories e Pattern-Based Constraint Satisfaction e Logic Puzzles
- e in due articoli dello stesso autore: Dai vincoli alle regole di risoluzione, parte II : catene, trecce, confluenza e T&E (basato su 10.000 problemi casuali minimi) e Statistiche imparziali di un CSP - Un generatore di bias controllato .
I seguenti risultati si basano sul nuovo generatore controllato da bias (e quasi sei milioni di problemi minimi casuali); sono imparziali. Questo generatore e la vasta collezione associata sono accessibili sulla piattaforma GitHub: https://github.com/denis-berthier/Controlled-bias_Sudoku_generator_and_collection
Il risolutore di Sudokus utilizzato per stabilire questa classificazione (SudoRules, parte del più generale software di risoluzione dei vincoli CSP-Rules) è accessibile sulla piattaforma GitHub: https://github.com/denis-berthier/CSP-Rules-V2 .1
La distribuzione percentuale per livelli di nrczt è la seguente:
Sapendo che la complessità effettiva di un problema cresce in modo quasi esponenziale con il suo SER o il suo NRCZT, queste cifre mostrano che:
1) la stragrande maggioranza dei problemi può essere risolta con tecniche relativamente semplici (qui, catene corte);
2) nonostante tutto permangono problemi molto complessi, che giustificano giocatori esperti alla continua ricerca di nuove regole che permettano di semplificare le soluzioni ottenute con le regole ad oggi note;
3) È molto improbabile che problemi eccezionalmente complessi (come il famigerato mostro di Pasqua ) vengano trovati da un generatore casuale e alcuni giocatori cercano costantemente di creare nuovi esempi "a mano".
Risultati collaterali: la tecnica dei generatori di bias controllati permette anche di stimare il numero di problemi minimi (3,10 × 10 ^ 37) nonché il numero di problemi minimi non equivalenti (2,55 × 10 ^ 25).
La maggior parte dei libri di testo di sudoku gli autori concordano sul fatto che diversi fattori influenzano la difficoltà di questi problemi, l'equazione di base, di cui tiene conto di modulo una certa ponderazione:
Tuttavia, questo problema di difficoltà è ancora oggetto di molti dibattiti nei forum di Sudoku, poiché si riferisce ai concetti e alle rappresentazioni visive che tutti sono disposti ad abbracciare. Ma può essere completamente chiarito se diamo priorità, dal semplice al complesso, alle tecniche e procedure che possiamo usare per avere successo in una griglia, e se consideriamo il nostro modo di giocare (osservare alcune regole di handicap, come la risoluzione integrale da solo ragionamento mentale, ovvero il divieto assoluto di riprodurre il problema della griglia in più griglie facendo ipotesi, ecc .).
Ma non dobbiamo confondere il livello del giocatore con il grado di difficoltà di una griglia. Alcuni giocatori riescono a superare una griglia ragionando mentalmente, senza scrivere multipli nelle caselle che successivamente ricevono solo il numero corretto, mentre altri lottano con caselle che presentano più candidati, o con più griglie, da ipotesi fatte a titolo gratuito, o sviluppate secondo alle categorie (righe, colonne e regioni) compresa, ad esempio, la griglia comune, che di fatto include una determinata tabella di risoluzione estesa. Per questo preferiamo classificare le griglie problema in cinque tipologie, all'interno delle quali troviamo diversi livelli di difficoltà:
Tipo 1Utilizzo di tecniche semplici tra cui "trovare la casella giusta per un dato numero e regione" mediante riduzione incrociata e "trovare il numero giusto per una data cella", mediante conteggio, sebbene quest'ultima sia un po' più noiosa della prima. In linea di massima, per questo tipo di griglia, il ragionamento viene fatto mentalmente, senza dover registrare i possibili candidati in una data cella, e il riempimento della griglia avviene gradualmente seguendo una delle innumerevoli tracce o sequenze che si presentano. È questo tipo di griglie che trovate frequentemente in siti web, giornali e riviste o create da software, classificandone erroneamente alcune nella categoria dei "difficili" o addirittura "diabolici"! Il motivo è che esiste una classe di griglie di tipo 1 , che è davvero difficile da superare con l'aritmetica mentale. E quindi, non sottovalutare le griglie di tipo 1 : ce ne sono di "facili", "medie" e anche "difficili".
Tipo 2Utilizzo di tecniche che consentano l'elaborazione di celle-con-più-candidati in un'unica dimensione; riga, colonna o regione, tra cui "rimozione a causa di coppie nude", "ripulitura di candidati nascosti" e "ripulitura di coppie camuffate". Alcune griglie di tipo 2 possono avere successo, come il tipo 1 , mentalmente. Altri, ad un livello superiore, richiedono di registrare, man mano, i candidati nelle celle di una regione, una riga o una colonna, senza però farlo per tutte le celle vuote, e vedere se possiamo semplificare i multipli con una delle tre tecniche precedenti. Le griglie più difficili di questo tipo 2 non si prestano a essere risolte finché tutte le celle non contengono i loro probabili candidati. In questo caso dobbiamo cercare di arrivare alla situazione ottimale della griglia: in ogni categoria (riga, colonna e regione), i gruppi di “multipli numericamente collegati” devono essere “indipendenti”. Possono essere utilizzate altre semplici tecniche di lavorazione unidimensionali, tra cui “stripping a causa di triplette nude” e “triplette mimetizzate sgrassanti”. Quest'ultimo è più doloroso da fare! Possiamo anche eliminare alcune figure con una semplice tecnica di elaborazione, questa volta in due dimensioni riga × regione o colonna × regione: "la distribuzione di un blocco in quattro domini complementari o alternati". Quindi, se opti per un esercizio mentale, questo tipo di griglia te ne offre alcuni molto difficili. E se ti permetti di scrivere i multipli nelle celle, hai degli esercizi di allenamento molto carini sulla strategia di trattare "gruppi indipendenti di multipli numericamente collegati".
Tipo 3Utilizzo di tecniche che consentano la semplificazione di celle-con-più-candidate, prima come per il tipo 2 , secondo un'unica dimensione; riga, colonna o regione, ma con una dimensione maggiore tra cui "eliminazione a causa di quadricipiti e quintuple nudi" e "sgrassaggio di quadricipiti e quintuple nascosti". Per procedere con quest'ultima tecnica, peraltro più laboriosa da eseguire, si tratta infatti di utilizzare "l'eliminazione a causa di uno o due gruppi nudi" ma di dimensioni minori!
Alcune griglie di tipo 3 richiedono un trattamento in due dimensioni (righe × colonne, righe × regioni e/o colonne × regioni) utilizzando processi molto più intelligenti, ma giustificabili tra cui X-Wing, Swordfish , Jellyfish , Squirmbag o il TPU, la tecnica derivante da il "principio di unicità della soluzione". Quindi, per questo tipo di griglia, non dovremmo sperare di arrivare alla soluzione solo ragionando mentalmente, senza aver ormai messo tutti i possibili candidati in tutte le celle. Sono possibili tre gradi di difficoltà, a seconda delle dimensioni dei gruppi nudi o mimetizzati, ma anche in base al loro numero.
Tipo 4La strategia adottata per griglie di questo tipo, che presentano casi più complessi, consiste nel tenere conto contemporaneamente delle tre dimensioni (righe × colonne × regioni). Occorre quindi poter "saltare" da una regione all'altra, attraverso i box, utilizzando dei "gateway" materializzati o da una riga, da una colonna o da una regione. In breve, devi creare "percorsi" tra le diverse caselle. Riconosceremo così processi simili a quelli già utilizzati dall'elaborazione bidimensionale compreso l'X-Wing ad esempio (i vertici non sono più quelli di un rettangolo, ma tra quelli di un poligono). Si noti che questa strategia si basa su una logica bivalente (per un numero fisso N e una data casella di multipli, p: “N è il valore” oppure no (p): “N non è il valore”).
Vista da una certa angolazione, si tratta di sovrapporre due o più griglie sulla stessa griglia-problema iniziale, di fare una coniugazione logica delle diverse proposizioni (concretizzate per cammini) e di determinare quelle delle griglie che portano ad una contraddizione con una delle regole che governano il gioco del sudoku, per trovare la giusta soluzione. È quindi come se si procedesse per formulazione per ipotesi, ma in modo indiretto! Bisogna ammettere che questo modo di fare dà più piacere a giocare e ad applicare procedure che a fare ipotesi per ottenere tavoli “poveri” a livello intellettuale! Usa matite colorate. Chi è già iniziato a questa tecnica riconoscerà griglie facili, medie e anche difficili.
Tipo 5Alcuni giornali, riviste, siti e software forniscono le cosiddette griglie "diaboliche" o addirittura "infernali". Molto spesso, queste griglie possono essere risolte con tecniche sviluppate fino ad oggi e sono molto meno difficili di quanto sembri. Una griglia diabolica, infatti, è quella che non può essere risolta da nessuno dei processi sinora sviluppati, se non formulando una o più ipotesi sulle figure da inserire in una o più caselle. Ovviamente è richiesta l'unicità della soluzione per la rete.
D'ora in poi, questo è l'unico modo per arrivare a una soluzione, in attesa dello sviluppo di nuovi processi "manuali".
Infine, è bene precisare che quando si tratta di costruire griglie problematiche, spesso è più facile ottenere una griglia di tipo 1 , e quasi raro trovare una griglia di tipo 4 o 5 . Il software sviluppato fino ad oggi parte ovviamente dai diversi metodi di risoluzione, per fabbricare un problema, ma il livello desiderato generalmente scende di uno o anche due gradi. Statisticamente si nota che la distribuzione di frequenza per tipologia si aggira intorno al 46%, 32%, 11%, 8% e 3%, dal primo tipo al quinto.
Per un professionista IT , programmare la ricerca di una soluzione attraverso contingenze o contingenze multiple (come richiesto per i problemi più difficili) è un compito relativamente semplice. Un tale programma imita un giocatore umano che cerca una soluzione senza ricorrere al caso.
È anche relativamente facile progettare un algoritmo di ricerca backtracking . Di solito, è sufficiente che l'algoritmo scelga 1 per la prima cella, quindi 2 per la successiva e così via finché non appare alcuna contraddizione. Quando appare una contraddizione, l'algoritmo prova un altro valore per la cella che fa apparire la contraddizione. Una volta esaurite tutte le possibilità per questa cella, l'algoritmo “torna sui suoi passi” e riparte dalla penultima cella.
Sebbene questo algoritmo non sia molto elegante, è sicuro di trovare una soluzione se ce n'è una. Una griglia 9×9 viene solitamente risolta in meno di tre secondi con un moderno personal computer che utilizza un interprete e in millisecondi con un linguaggio compilato . Tuttavia, ci sono griglie che sono particolarmente difficili da risolvere con il backtracking (vedi (in) Algorithmics of Sudoku # Algoritmo di forza bruta ).
Una particolare implementazione del backtracking consiste nell'utilizzare la programmazione logica , come implementato in Prolog . In questo caso il progettista fornisce al programma i vincoli della griglia (una cifra per riga, per colonna e per regione; le cifre riportate); questo programma prenderà le decisioni per risolvere il problema. Se ammettiamo che la rete ha una soluzione unica, la ricerca avrà sicuramente successo.
Donald Knuth ha sviluppato un algoritmo che utilizza liste a doppio collegamento ( dancing links ), e che è molto efficace nel risolvere questo tipo di sudoku in pochi millisecondi.
Un'altra soluzione, proposta nel 2007 dal ricercatore di metodi formali Nicolas Rapin, consiste nell'utilizzare la struttura del diagramma decisionale binario (in breve BDD) per risolvere e rappresentare all'interno di un'unica struttura lo spazio delle soluzioni di una rastrelliera. L'idea consiste nel modellare la presenza della cifra k nella riga i , colonna j , dalla variabile booleana denominata x_i_j_k prendendo per convenzione che il valore vero di questa variabile rappresenta la presenza della cifra k nella riga i , colonna j e la valore falso la sua assenza. Quindi hai bisogno di 9 × 9 × 9 variabili booleane per modellare una griglia sudoku 9 × 9. I vincoli insiti nel sudoku possono quindi essere scritti direttamente sotto forma di formule booleane e passati a una libreria di database. Questo approccio ha il vantaggio di poter risolvere non solo griglie di sudoku ben formate (con una sola soluzione) ma anche di enumerare tutte le soluzioni di griglie mal formate aventi più soluzioni (le soluzioni essendo date dai percorsi del diagramma che portano a foglio 1) o per dimostrare che una griglia mal formata non presenta alcuna soluzione. Questo metodo può quindi essere utile per risolvere, sviluppare e validare griglie. Impostando che → denota l'implicazione logica,! negazione e disgiunzione V, ecco un esempio di vincolo di regione: x_1_1_1 →! (x_1_2_1 V x_1_3_1 V x_2_1_1 V x_2_2_1 V x_2_3_1 V x_3_1_1 V x_3_2_1 V x_3_3_1). In linguaggio naturale questa espressione significa: se il numero 1 è presente nella riga 1 , colonna 1 , allora non è presente altrove nella sua regione . I vincoli di colonna sono della forma x_i_j_k →! ( x_h_j_k), quelli di riga della forma x_i_j_k →! ( x_i_h_k) e quello della presenza di una cifra per ogni casella i, j della forma x_i_j_h. Per le celle piene della griglia, i vincoli implicativi sopra (regione, riga, colonna) sono ridotti al conseguente (termine a destra dell'implicazione) poiché l'antecedente è vero. Durante l'implementazione di questa soluzione, osserviamo che l'efficienza generale è molto sensibile all'ordine in cui i vincoli vengono passati alla libreria di costruzione del BDD. Su un PC standard (1,6 GHz , 1 GB di RAM) il tempo di risoluzione per le griglie ben formate è compreso tra 1 s e 2 min 30 s (a seconda delle griglie). Sono disponibili implementazioni gratuite.
Ci sono anche molti programmi disponibili gratuitamente sul web, basati sull'implementazione di regole utilizzate dai giocatori: Sudoku , Sudoku Explainer , Sudoku Susser, Sudoktor, Sadman, il risolutore gsf. Il programma SudoRules, ora pubblico, si basa su tecniche di Intelligenza Artificiale ; fa parte di un software di risoluzione dei problemi di soddisfazione dei vincoli più generale (che include anche altri giochi di logica). È disponibile sulla piattaforma GitHub: https://github.com/denis-berthier/CSP-Rules-V2.1 .
Sembra che le classifiche di Dell Magazines , pioniere nel campo della pubblicazione, siano create dal computer. Di solito sono composti da 30 numeri distribuiti casualmente . L'autore delle griglie è sconosciuto. Durante l' inverno del 2000, Wei-Hwa Huang ha affermato di essere l'autore del programma che crea queste griglie; secondo lui, le porte precedenti erano costruite a mano. Il generatore sarebbe scritto in C++ e sebbene offra alcune opzioni per soddisfare il mercato giapponese ( simmetria e meno numeri), Dell preferisce non utilizzarle. Alcuni ipotizzano che Dell continui a utilizzare questo programma, ma non ci sono prove a sostegno della loro affermazione.
I puzzle di sudoku di Nikoli , uno dei principali produttori di sudoku in Giappone, sono costruiti a mano, con il nome dell'autore che appare con ogni puzzle pubblicato; le informative sono sempre presentate simmetricamente. Questo exploit è possibile conoscendo in anticipo il luogo in cui si troverà il rivelato e successivamente assegnando un numero alle celle così scelte. Il Number Place Challenger Dell visualizza anche il nome dell'autore. Le griglie pubblicate nella maggior parte dei giornali del Regno Unito verrebbero create automaticamente, ma usano la simmetria, il che implicherebbe che un essere umano le crei. The Guardian afferma che le sue griglie sono fatte a mano da giapponesi, ma non viene fatta alcuna menzione dell'autore. Sarebbero stati costruiti da persone di Nikoli. Il Guardian ha affermato che poiché sono costruiti a mano, contengono "suggerimenti sottili" altamente improbabili nelle griglie costruite al computer.
È possibile costruire griglie con più soluzioni o senza soluzioni, ma queste non sono considerate veri e propri sudoku. Come per molti altri giochi di logica, è necessaria una soluzione unica. È quindi necessaria una grande attenzione nella costruzione di una griglia, poiché un singolo numero fuori posto può rendere impossibile la risoluzione.
Sul Web è disponibile un software gratuito (suexg) che consente di creare problemi minimi (diverse decine al secondo).
La minimalità è un requisito aggiuntivo che a volte ci si aspetta dal creatore del problema, sebbene non abbia alcun effetto sul giocatore. Può essere difficile conciliare con altri requisiti aggiuntivi, come requisiti estetici, ad esempio di simmetria, ovvero che quelli esposti si trovano in un insieme di celle aventi una certa forma di simmetria. È più difficile creare problemi che siano sia minimi che con determinate simmetrie (in particolare, suexg no).