{"id":2470,"date":"2012-01-09T23:09:11","date_gmt":"2012-01-09T22:09:11","guid":{"rendered":"https:\/\/xmau.com\/wp\/ilpost\/?p=2470"},"modified":"2022-10-11T10:30:42","modified_gmt":"2022-10-11T08:30:42","slug":"sudoku-minimali-e-massimali","status":"publish","type":"post","link":"https:\/\/xmau.com\/ilpost\/2012\/01\/09\/sudoku-minimali-e-massimali\/","title":{"rendered":"Sudoku minimali e massimali"},"content":{"rendered":"

Immagino che sappiate quasi tutti cos’\u00e8 un sudoku, almeno se in questo millennio siete vissuti sul pianeta Terra. Se poi siete assidui lettori di questo blog, vi ricordate sicuramente che due anni fa ho anche spiegato cos’\u00e8 il sudoku dal punto di vista matematico<\/a>: la parte matematica non sono certo i numeri dello schema, che possono essere sostituiti tranquillamente da lettere, ideogrammi o colori, quanto piuttosto la struttura dello schema completo. I matematici possono divertirsi a risolvere i sudoku esattamente come chi matematico non \u00e8: ma i neuroni di un Vero Matematico si mettono subito in moto per immaginare qualche propriet\u00e0 massimale o minimale dei giochi stessi. Detto in altre parole, qual \u00e8 il numero minimo di caselle che devono essere fornite per essere certi di risolvere il gioco? Ricordo che per “risolvere un sudoku” occorre che la soluzione sia unica; inoltre, a differenza degli schemi che si vedono su giornali e riviste, il matematico non si cura della simmetria dello schema di partenza.<\/p>\n

Credo che nessuno di voi far\u00e0 fatica a dimostrare che un sudoku con solo sette caselle riempite non potr\u00e0 mai essere risolubile. Provate a pensarci un momento, prima di continuare a leggere… Occhei, ci siete arrivati? Anche supponendo che le sette caselle contengano tutti numeri diversi \u00e8 chiaro che ci saranno due numeri, chiamiamoli a<\/i> e b<\/i>, che non appaiono nello schema. Bene, ovviamente non potremmo mai distinguere uno schema completato in un certo modo da quello che otteniamo scambiando a<\/i> e b<\/i>, giusto? Ecco, abbiamo dimostrato che la soluzione non pu\u00f2 essere unica. <\/p>\n

Certo che 7 \u00e8 soltanto un limite inferiore, e anche piuttosto rozzo: fino alla fine del 2011 infatti si sapeva solo che esistono degli schemi con 17 caselle riempite che avevano una soluzione unica, ma non si riusciva a scendere sotto questo limite. Per la cronaca, c’\u00e8 un tizio, tal Gordon Royle della University of Western Australia, che sta catalogando<\/a> tutti gli schemi di sudoku da 17 caselle. Mentre sto scrivendo ne ha 49151: se qualcuno trova troppo semplici gli schemi usuali pu\u00f2 provare a divertirsi con quelli. Io non ci tento nemmeno.<\/p>\n

Ordunque: a Capodanno, invece che smaltire il cenone, Gary McGuire dello University College di Dublino ha pubblicato su arXiv un articolo<\/a>, scritto insieme a Bastian Tugemann e Gilles Civario, che dimostra che effettivamente 17 \u00e8 il limite cercato: insomma, un qualunque schema di sudoku con sedici o meno caselle riempite ha pi\u00f9 di una soluzione (oppure, per i pignoli – e si sa che i matematici sono pignoli – non ha nessuna soluzione). La scoperta \u00e8 stata resa nota da Nature<\/a>: qui in Italia ne ha appena scritto Stefano Pisani<\/a>, anche se io non ho ancora aperto il suo articolo perch\u00e9 altrimenti rischiavo non solo di scrivere le stesse cose ma anche di scriverle nello stesso modo. <\/p>\n

Come ha fatto McGuire a dimostrare che sedici non bastano? Con il sistema pi\u00f9 semplice possibile: provando tutte le combinazioni possibili, e vedendo che nessuna di esse portava a una soluzione univoca. Beh, non proprio cos\u00ec ma quasi: l’approccio brutale a forza bruta (permettetemi il pessimo gioco di parole) non sarebbe stato computazionalmente possibile, data l’esplosione pi\u00f9 che esponenziale del numero di combinazioni. L’approccio \u00e8 stato pertanto leggermente diverso, lavorando alla rovescia. Partendo da ciascuna griglia sudoku completa essenzialmente diversa – ruotarla, specchiarla o fare una permutazione dei numeri lascia la stessa griglia, in fin dei conti; il numero di queste griglie \u00e8 “solo” 5.472.730.538 – il gruppo di lavoro ha cercato tutti gli schemi che portano a una soluzione unica, e verificato che tali schemi avevano almeno diciassette caselle riempite. Per fare questo, hanno inizialmente cercato un numero sufficientemente ampio dei cosiddetti insiemi inevitabili<\/b> (unavoidable sets), gruppi di caselle tali che almeno una di esse deve essere riempita per assicurare l’unicit\u00e0 della soluzione. Il secondo passo \u00e8 stato enumerare tutti gli insiemi di 16 caselle che hanno almeno una casella in comune con ciascuno degli insiemi inevitabili; questi nella teoria dei grafi si chiamano hitting sets<\/b>. La logica del secondo passo dovrebbe essere chiara: se non do valori a nessuna delle caselle degli insiemi inevitabili, allora per definizione avr\u00f2 soluzioni multiple. Infine per ciascuno degli hitting set trovati si \u00e8 controllato se effettivamente avrebbe portato o no a una soluzione. Essendo la risposta stata “no”, il problema \u00e8 risolto.<\/p>\n

Peccato che il problema degli hitting set \u00e8 noto per essere NP-hard, cio\u00e8 uno dei pi\u00f9 complicati esistenti dal punto di vista computazionale (ho parlato qui<\/a> di problemi P e NP; vi basti sapere che nei problemi NP tutti gli algoritmi noti crescono esponenzialmente con la dimensione dei dati, e i problemi NP hard sono tutti equivalenti, nel senso che se mai si trovasse un algoritmo polinomiale per uno se ne potrebbe ricavare uno polinomiale per tutti gli altri). McGuire e colleghi sono per\u00f2 riusciti a trovare un algoritmo “non troppo esponenziale”, se mi passate il termine; l’algoritmo cresce s\u00ec esponenzialmente ma \u00e8 sufficientemente veloce per essere applicato ai dati del sudoku e avere richiesto “solo” 7 milioni di ore di CPU del cluster di computer dello University College. L’algoritmo \u00e8 tra l’altro la parte pi\u00f9 interessante di tutto il progetto, perch\u00e9 a detta degli autori pu\u00f2 essere riciclato nei test del software e soprattutto nella bioinformatica (le sequenze geniche che sono tanto di moda in questi anni…), per la serie “la matematica inutile non \u00e8 mai davvero inutile”.<\/p>\n

\"\"<\/a>
Un sudoku con 77 caselle riempite eppure non risolubile<\/figcaption><\/figure> Un’ultima considerazione: probabilmente qualcuno di voi si sar\u00e0 chiesto qual \u00e8 il massimo<\/b> numero di caselle riempite per cui si ha comunque un sudoku fallace, che cio\u00e8 abbia almeno due soluzioni. \u00c8 banale accorgersi che il massimo teorico dev’essere 77: se in una riga o una colonna manca una sola casella essa \u00e8 immediatamente riempibile, quindi ne devono mancare almeno due, e la configurazione minimale \u00e8 quella con quattro caselle mancanti ai lati di un rettangolo. Bene, per una volta la stima grossolana \u00e8 anche la soluzione al problema. Nello schema qui a fianco, tratto dal forum di un sito dall’evocativo nome di enjoysudoku<\/a>, potete vedere un esempio di schema con 77 caselle riempite e due soluzioni possibili; se preferite dirlo in altro modo, questo schema ha un insieme inevitabile di dimensione 4. Devo dire che non so se sia o no frustrante trovarsi uno schema di questo tipo…<\/p>\n","protected":false},"excerpt":{"rendered":"

Il 2012 si \u00e8 aperto con la dimostrazione che per avere un sudoku risolvibile \u00e8 necessario avere almeno 17 numeri. Come ci si \u00e8 arrivati? Forza (quasi) bruta.<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"default","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","ast-disable-related-posts":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-4)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-opacity":"","overlay-gradient":""}},"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"_jetpack_memberships_contains_paid_content":false,"activitypub_content_warning":"","activitypub_content_visibility":"","activitypub_max_image_attachments":4,"activitypub_interaction_policy_quote":"anyone","activitypub_status":"","footnotes":"","jetpack_publicize_message":"","jetpack_publicize_feature_enabled":true,"jetpack_social_post_already_shared":true,"jetpack_social_options":{"image_generator_settings":{"template":"highway","default_image_id":0,"font":"","enabled":false},"version":2},"jetpack_post_was_ever_published":false},"categories":[1],"tags":[],"class_list":["post-2470","post","type-post","status-publish","format-standard","hentry","category-uncategorized"],"jetpack_publicize_connections":[],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"jetpack_shortlink":"https:\/\/wp.me\/phh2yP-DQ","jetpack-related-posts":[{"id":2450,"url":"https:\/\/xmau.com\/ilpost\/2011\/09\/16\/esercizi-o-problemi\/","url_meta":{"origin":2470,"position":0},"title":"Esercizi o problemi?","author":".mau.","date":"16\/09\/2011","format":false,"excerpt":"Sappiamo che non esiste una via regia per la matematica, e che bisogna mettersi a faticare per ottenere dei risultati. Ma c'\u00e8 modo e modo di faticare: svolgere esercizi o risolvere problemi sono due attivit\u00e0 ben diverse.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2580,"url":"https:\/\/xmau.com\/ilpost\/2013\/03\/27\/ricondursi-al-caso-precedente\/","url_meta":{"origin":2470,"position":1},"title":"Ricondursi al caso precedente","author":".mau.","date":"27\/03\/2013","format":false,"excerpt":"Quella del titolo \u00e8 una frase tipica da matematico e fa spesso divertire chi matematico non \u00e8, per\u00f2 \u00e8 uno strumento molto potente quando lo si sa usare.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2634,"url":"https:\/\/xmau.com\/ilpost\/2013\/09\/06\/quanto-e-irragionevolmente-efficace-la-matematica\/","url_meta":{"origin":2470,"position":2},"title":"Quanto \u00e8 “irragionevolmente efficace” la matematica?","author":".mau.","date":"06\/09\/2013","format":false,"excerpt":"Ogni tanto la banda dei matematici non-platonisti si risveglia. Solo che il matematico tipico di filosofia ne sa ben poca","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":561,"url":"https:\/\/xmau.com\/ilpost\/2015\/05\/07\/dai-numeri-immaginari-ai-quaternioni\/","url_meta":{"origin":2470,"position":3},"title":"Dai numeri immaginari ai quaternioni","author":".mau.","date":"07\/05\/2015","format":false,"excerpt":"Una volta che si cambia punto di vista, si possono avere idee che portano a nuovi sviluppi... basta sapere accorgersi di cosa bisogna buttare via. Anche questo \u00e8 il bello dela matematica.","rel":"","context":"In \"analogie\"","block_context":{"text":"analogie","link":"https:\/\/xmau.com\/ilpost\/tag\/analogie\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":2614,"url":"https:\/\/xmau.com\/ilpost\/2013\/06\/03\/matematica-per-analogie\/","url_meta":{"origin":2470,"position":4},"title":"Matematica per analogie","author":".mau.","date":"03\/06\/2013","format":false,"excerpt":"Non \u00e8 che i matematici predichino bene e razzolino male: il punto \u00e8 che loro sono inconsciamente abituati a distinguere la scoperta di una propriet\u00e0 dalla sua dimostrazione, ma si dimenticano di mostrare il momento della scoperta.","rel":"","context":"Similar post","block_context":{"text":"Similar post","link":""},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]},{"id":593,"url":"https:\/\/xmau.com\/ilpost\/2015\/07\/03\/sapete-risolvere-questo-problema\/","url_meta":{"origin":2470,"position":5},"title":"Sapete risolvere questo problema?","author":".mau.","date":"03\/07\/2015","format":false,"excerpt":"Per trovare la soluzione a un problema \u00e8 spesso importante sapere quali domande fare.","rel":"","context":"In \"confirmation bias\"","block_context":{"text":"confirmation bias","link":"https:\/\/xmau.com\/ilpost\/tag\/confirmation-bias\/"},"img":{"alt_text":"","src":"","width":0,"height":0},"classes":[]}],"_links":{"self":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2470","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/comments?post=2470"}],"version-history":[{"count":1,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2470\/revisions"}],"predecessor-version":[{"id":2471,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/posts\/2470\/revisions\/2471"}],"wp:attachment":[{"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/media?parent=2470"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/categories?post=2470"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/xmau.com\/ilpost\/wp-json\/wp\/v2\/tags?post=2470"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}