Sudoku
Sudoku ( giapponese : 数独, sūdoku ) è un gioco matematico che è stato inventato alla fine degli anni '70, ha guadagnato popolarità in Giappone negli anni '80, ed è diventato famoso a livello internazionale nel 2005 quando numerosi giornali hanno iniziato a pubblicarlo nella loro sezione hobby . [ 1 ]
Lo scopo del sudoku è riempire una griglia di 9 × 9 celle (81 celle) suddivisa in 3 × 3 sottogriglie (dette anche "caselle" o "regioni") con i numeri da 1 a 9 a partire da alcuni numeri già disposti in alcuni delle cellule. La forma iniziale del gioco è che ci sono nove elementi differenziati, che non devono essere ripetuti nella stessa riga, colonna o sotto-griglia. Un sudoku ben pianificato può avere solo una soluzione e deve avere almeno 17 indizi iniziali. [ 2 ] [ 3 ] La soluzione di un Sudoku è sempre un quadrato latino , anche se generalmente non è vero il contrario poiché il Sudoku ha la restrizione aggiunta che lo stesso numero non può essere ripetuto in una sotto-griglia.
Storia
Nel 18° secolo , il famoso matematico svizzero Leonhard Euler creò un sistema di probabilità per rappresentare una serie di numeri senza ripetersi. Per questo motivo, Eulero è considerato l'inventore di questo gioco. [ 4 ]
Già nel 1970 l'editore Math Puzzles and Logic Problems pubblicava una sezione chiamata Number place in modo che questo enigma matematico sarebbe diventato un hobby anche se anni dopo andò perso nell'oblio.
Nel 1984 il quotidiano giapponese Monthly Nikolist pubblicò una sezione hobby chiamata Sūji wa dokushin ni kagiru (数字は独身に限る) "i numeri devono essere unici" (letteralmente dokushin (独身) = "celibe, single "). È stato Maki Kaji , presidente di Nikoli , a nominarlo. Il nome è stato abbreviato in Sūdoku (sū = numero, doku = singolo). [ 5 ]
È diventato noto a livello internazionale nel 2005, quando diversi giornali hanno iniziato a pubblicarlo come hobby. [ 1 ]
Regole e terminologia
Il sudoku viene solitamente presentato come una tabella 9 × 9, composta da 3 × 3 sottotabelle chiamate "regioni" (chiamate anche "scatole" o "blocchi").
Alcune celle contengono già numeri, noti come "numeri dati" (o talvolta "indizi"). L'obiettivo è riempire le celle vuote, con un numero in ciascuna di esse, in modo tale che ogni colonna, riga e regione contenga i numeri 1–9 solo una volta.
Inoltre, ogni numero nella soluzione appare solo una volta in ciascuna delle tre "direzioni", quindi i "numeri devono stare da soli" evocando il nome del gioco.
Metodi di risoluzione
La casella contrassegnata in verde nella regione 3 × 3 nell'angolo in alto a sinistra deve contenere un 7.
La strategia per risolvere questo enigma può essere considerata come la combinazione di tre processi: tracciamento, marcatura e analisi.
Tracciamento
Nell'esempio sopra, tracciando avanti e indietro attraverso i sette situati in qualsiasi punto della griglia, il giocatore può rimuovere tutte le celle vuote nell'angolo in alto a sinistra che non possono contenere un 7. Questo lascia solo una cella possibile (contrassegnata in verde).
Contrassegnato
La scansione termina quando non è possibile scoprire nuovi numeri. A questo punto è necessario soffermarsi su qualche analisi logica. La maggior parte trova utile guidare questa analisi contrassegnando i numeri candidati nelle celle vuote. Ci sono due notazioni popolari: pedici e punti.
Nella notazione in pedice, i numeri candidati sono scritti piccoli in celle. Il rovescio della medaglia è che i puzzle originali sono pubblicati su giornali che di solito non lasciano molto spazio per contenere più di qualche cifra. Usando questa notazione, i risolutori spesso creano una copia più grande del puzzle e usano una matita appuntita.
La seconda notazione è un motivo a punti con un punto nell'angolo in alto a sinistra che rappresenta un 1 e un punto nell'angolo in basso a destra che rappresenta un 9. Questa notazione ha il vantaggio di poter essere utilizzata nel puzzle originale. È richiesta abilità nel posizionamento dei punti, perché l'esistenza di punti sfalsati o segni involontari porta inevitabilmente a confusione e non sono facili da rimuovere senza aggiungere ulteriore confusione.
Analisi
Ci sono due approcci principali:
- Nell'eliminazione , i progressi vengono fatti eliminando successivamente i numeri candidati per una o più celle, fino a quando non rimane una sola scelta. Dopo aver ottenuto ciascuna risposta, è necessario eseguire una nuova scansione (di solito controllando l'effetto dell'ultimo numero). Ci sono una serie di tattiche di eliminazione. Uno dei più comuni è la "cancellazione del candidato senza eguali". Si dice che celle con configurazioni di numeri candidati identiche corrispondano se il numero di numeri candidati in ciascuna è uguale al numero di celle che li contengono. Questo approccio può essere disapprovato dai puristi della logica per troppi tentativi ed errori , ma può arrivare rapidamente a soluzioni chiare.
Idealmente, è necessario trovare una combinazione di tecniche che eviti alcuni degli inconvenienti degli elementi sopra. Il conteggio di regioni, righe e colonne può diventare noioso. Digitare i numeri candidati in celle vuote può richiedere molto tempo. L'approccio "what-if" può creare confusione a meno che non sia ben organizzato. L'intento della domanda è trovare una tecnica che riduca al minimo il conteggio e la marcatura.
Un'analisi sistematica della logica e delle tecniche di risoluzione è stata pubblicata in inglese: "Pattern-Based Constraint Satisfaction and Logic Puzzles". [ 6 ]
Livelli di difficoltà
I programmi per computer che risolvono i sudoku possono stimare quanto sia difficile per un essere umano trovare la soluzione, in base alla complessità delle tecniche di risoluzione richieste. Questa stima consente agli editori di adattare i propri enigmi a persone con diverse esperienze di risoluzione. Alcune versioni "online" offrono anche vari livelli di difficoltà.
Costruzione
Un sudoku deve avere un'unica soluzione per essere considerato ben formulato; cioè dagli indizi iniziali può esserci un solo modo valido per riempire le celle rimanenti. Affinché un sudoku abbia un'unica soluzione, il numero di indizi iniziali deve essere almeno 17; questo è stato dimostrato nel 2012. [ 3 ]
La costruzione di un sudoku può essere eseguita in modo efficiente a mano predeterminando le posizioni dei numeri dati e assegnando loro dei valori per eseguire un processo deduttivo.
I puzzle di Nikoli sudoku sono costruiti a mano e il nome dell'autore appare nei titoli di coda accanto a ciascun puzzle ; i numeri dati si trovano sempre sotto forma di uno schema simmetrico. Anche i puzzle di Dell Number Place Challenger (vedi varianti di seguito) citano i crediti dell'autore. I sudoku che appaiono nella maggior parte dei giornali del Regno Unito sono apparentemente generati dal computer, ma impiegano probabili nei sudoku generati dal computer. La sfida per i programmatori di Sudoku è insegnare a un programma come costruire enigmi intelligenti in modi indistinguibili da quelli creati dagli umani; Wayne Gould ha impiegato sei anni per modificare il suo popolare show per credere di aver raggiunto quel livello.
Varianti
Sebbene il più comune sia che la tabella abbia dimensioni 9x9 con regioni 3x3, esistono numerose varianti. I giochi iniziali possono essere schede 4x4 con regioni 2x2; Sotto il nome Logi-5 sono state pubblicate tavole 5x5 con pentamini come regioni; il World Puzzle Championship ha pubblicato una tabella 6x6 con regioni 2x3 e una tabella 7x7 composta da 6 regioni composte da eptomini e una regione separata. Si possono trovare anche tavoli più grandi. Il quotidiano Times propone il Dodeka Sudoku , un tavolo 12x12 con 12 regioni 4x3. Le riviste Dell pubblicano spesso set 16x16 (la variante 16x16 utilizza in genere i simboli da 1 a G, anziché i simboli da 0 a F utilizzati in esadecimale ). L'editor di puzzle Nikoli propone il Sudoku gigante 25x25.
Un'altra variante comune consiste nell'aggiungere limiti al posizionamento dei numeri oltre a mantenere i normali requisiti su righe, colonne e regioni. I confini spesso assumono la forma di una "dimensione" in più; il più comune è forzare i numeri sulla diagonale principale del tavolo in modo che siano unici. I già citati giochi Number Place Challenger includono questa variante. Fanno parte di questa variante anche i giochi Daily Mail che utilizzano tavoli 6x6.
Il quotidiano americano USA Today pubblica un'altra variante denominata "Mini Sudoku", composta da un tavolo 6x6 con regioni 3x2. L'obiettivo è lo stesso del Sudoku originale, ma in questa variante vengono utilizzati solo i numeri da 1 a 6.
Un'altra variante è la combinazione di Sudoku e Kakuro in una tabella 9x9, chiamata Cross Sum Sudoku, in cui gli indizi sono dati attraverso somme incrociate. È anche possibile che gli indizi siano dati da criptoaritmi in cui ogni lettera rappresenta una singola cifra da 0 a 9. Un esempio è: NUMBER+NUMBER=KAKURO la cui unica soluzione è 186925+186925=373850. Un altro esempio è SUDOKU=IS*FUNNY la cui soluzione è 426972=34*12558.
Addoku combina elementi di Sudoku e Kakuro – di solito non vengono forniti numeri di partenza , ma invece la tabella 9x9 è divisa in regioni, ciascuna contenente la somma di tutti i numeri nella regione tenendo conto che non ci sono numeri ripetuti nella stessa regione. Quando si completa il tavolo, vengono mantenute anche le regole del Sudoku originale.
Una delle varianti più popolari è Hypersudoku . È pubblicato su giornali e riviste di tutto il mondo ed è anche noto per "NRC Handelsblad Sudoku", "Windoku", "Hyper-Sudoku" e "4-Frame Sudoku". La base è identica a quella del Sudoku originale, ma include ulteriori aree interne in cui devono apparire i numeri da 1 a 9. L'algoritmo che lo risolve è leggermente diverso dal normale Sudoku per l'influenza dei quadrati sovrapposti. Questa sovrapposizione fornisce al giocatore più informazioni che gli consentono di restringere le possibilità dei frame rimanenti. Il modo di giocare è simile a quello del Sudoku ma occorre prestare più attenzione ai quadrati e alle zone sovrapposte che alle righe e alle colonne.
Sono comuni anche i giochi creati da più schede di Sudoku. In Giappone è noto il Sudoku Gattai 5 (mix di 5), composto da 5 tavole 9x9 con sovrapposizioni nelle regioni d'angolo a forma di quinconce . In giornali come The Times o The Sydney Morning Herald , questa variante è conosciuta come Sudoku Samurai . Altri come il Baltimore Sun e il Toronto Star pubblicano questa variante nella loro edizione della domenica sotto il nome di High Five . Spesso non vengono forniti indizi nelle regioni sovrapposte. Vengono pubblicate anche varianti con tabelle sequenziali anziché sovrapposte, nelle quali i valori di determinate posizioni vengono trasferiti da una tabella all'altra.
Social Sudoku è una versione multiplayer digitale di Sudoku che consente a 2 giocatori di giocare contemporaneamente sullo stesso tabellone. Questa variante è stata creata da Crosswords Ltd. nel 2010 e rilasciata come app per la piattaforma iOS di Apple attraverso il suo Game Center . Social Sudoku [2] assegna punti a ciascun giocatore quando posiziona correttamente i numeri, bloccando la casella selezionata dall'altro giocatore. Le mosse errate fanno sì che il giocatore non abbia accesso al tabellone per 10 secondi, oltre a causare la perdita di punti.
Sono emerse anche varianti alfabetiche, a volte chiamate lettera Sudokus ( Wordokus ): non c'è differenza funzionale a meno che le lettere non formino parole. Alcune varianti, come quella in TV Guide , includono una parola sulla diagonale principale, in una riga o in una colonna una volta che il gioco è risolto; determinare la parola in anticipo può essere un aiuto per la risoluzione del gioco. Un Wordoku può contenere altre parole oltre alla parola principale. Come nell'esempio a destra, le parole “Kari”, “Park” e “Per” potrebbero essere parte della soluzione. Questo dovrebbe essere evitato sostituendo, ad esempio, il carattere “R” con il carattere “Q”. D'altra parte, Ripeto Sudoku permette di ripetere i simboli e Custom Sudoku mostra le parole sul tabellone prima di risolvere.
Un'altra variante senza differenze funzionali è il Quadratum Latinum con numerazione romana da Hebdomada Aenigmatum , la rivista di cruciverba tutta latina di Luca Desiata . [ 7 ]
Dotato di un mazzo standard di 81 carte da gioco del Set! Si può giocare a sudoku. La versione tridimensionale del Sudoku è stata inventata da Dion Church e pubblicata sul Daily Mail Telegraph nel maggio 2005. Esiste anche una versione del cubo di Rubik chiamata cuboku .
Ci sono molte altre varianti. Alcuni presentano forme diverse nella disposizione delle sovrapposizioni della tavola 9x9, come una farfalla, un mulino a vento o un fiore. [ 8 ] Altre versioni variano nella logica di risoluzione del gioco. Uno di questi è Greater Than Sudoku . In questa versione, ogni regione 3x3 contiene 12 simboli maggiori di (>) o minori di (<) sulla linea comune di due numeri adiacenti. [ 9 ] Un'altra variante di questo tipo è Clueless Sudoku in cui nove schede Sudoku 9x9 sono posizionate in una matrice 3x3. La cella centrale di ciascuna regione 3x3 in ciascuna delle 9 tabelle viene lasciata vuota, formando un decimo Sudoku senza celle complete; da qui il nome "senza indizi". [ 8 ]
Vedi anche
Riferimenti
- ^ a b Tony Crilly (2011). 50 cose da sapere sulla matematica Ed. Ariel. ISBN 978-987-1496-09-9 .
- ^ "Le chiavi matematiche per risolvere un sudoku", in Abc, 01/10/2012. [1] Un sudoku non può essere risolto se non c'è un minimo di 17 cifre-indizio all'inizio, poiché con meno "non esiste una soluzione univoca". Il più delle volte ha circa 25 cifre-indizio. Man mano che gli indizi scendono, più è difficile risolverli.
- ^ a b Gary McGuire, Bastian Tugemann, Gilles Civario (2013). "Non esiste un Sudoku a 16 indizi: risolvere il problema del numero minimo di indizi del Sudoku tramite l'enumerazione dei set di colpi " . Estratto il 5 novembre 2021 .
- ^ Stark, Florian (15 aprile 2013). "Wahrer Erfinder des Sudoku war ein Schweizer" (in tedesco) . Estratto il 24 febbraio 2020 .
- ^ "Storia del Sudoku" . Archiviato dall'originale il 24 settembre 2015 . Estratto il 26 luglio 2011 .
- ^ Denis Berthier (2012). Soddisfazione di vincoli e puzzle logici basati su modelli . Editori Lulu.com. ISBN 978-1-291-20339-4 .
- ^ Sito ufficiale di Hebdomada Aenigmatum
- ^ a b "www.janko.at" .
- ^ Pegg, Ed, Jr. (15 settembre 2005). "Giochi di matematica di Ed Pegg Jr.: variazioni di Sudoku" . MAAOnline . L'Associazione Matematica d'America . Archiviato dall'originale il 3-10-2005 . Estratto il 3 ottobre 2006 .
