due problemi di minimalita sul sudoku

[blackdie]

Tratti da un articolo di una rivista:

Penso che tutti conosciate quel gioco chiamato sudoku, tanto amato/odiato in questo ultimo periodo.
Per chi non lo conoscesse rimando a : http://it.wikipedia.org/wiki/Sudoku


a)Definiamo uno schema iniziale minimo quando rimuovere un singolo numero fa si che la soluzione non sia più unica.Quanti schemi minimi esistono?

b)Qual è il piu piccolo numero di cifre che devono essere inserite in un schema iniziale affiche la soluzione sia unica?

[Thomas]

proprio ieri leggevo su "le scienze" che sono problemi non ancora risolti ... a quanto ho capito non si conosce nemmeno il numero totale di Sudoku... ciò non toglie che magari qualcuno ci voglia provare (non io, benintesi!)...

ps: blackdie, che furbacchione!!

[carlo23]

Quegli posti da blackdie sono problemi di combinatorica alquanto interessanti...

Invece per quanto riguarda il sodoku di per se...beh non è che sia chissà quale gioco matematico!!
Infatti applicando quasi sempre la stessa strategia si risolvono tutti quanti (con un pò di pazienza)

[Admin]

Non mi spiego molto il successo del sudoku, mi sembra un gioco meccanico dalle strategie banali, forse lo chiamano gioco matematco perché ci sono i numeri.

[blackdie]

eh già thomas mi hai proprio beccato..ma volevo vedere se qualcuno aveva cmq il coraggio di provarci..

Dai su, non saranno poi cosi difficili...

Cmq anch'io ritengo il sudoku essere tutto tranne che un gioco matematico...

[blackdie]

Quegli posti da blackdie sono problemi di combinatorica alquanto interessanti...

SU dai carlo, questi problemi sono per te....

[fields]

Eh, eh, il sudoku è un problema matematico importantissimo, ragazzi. Avete presente il millenium prize, e il problema P vs NP?Bene, se qualcuno di voi trovasse un algoritmo veloce per risolvere il sudoku nella sua versione generale (ovvero griglie quadrate di lato n) avrebbe risolto il problema, e dimostrato che P=NP! Tuttavia tutti si aspettano che il sudoku, nella sua versione generale, sia inattaccabile, ovvero che non esista nessuna strategia in grado di risolverlo velocemente. Se qualche buon tempone avesse creato il sudoku con un quadrato di lato 20, già sarebbe molto molto difficile risolverlo (a mano).

[carlo23]

In effetti l'algoritmo più stupido per risolvere il sudoku è un bel brute force... che però ha complessità esponenziale.

Un buon algoritmo (ma solo per risolvere i sudoku, niente riguardo P vs NP) sarebbe di associare a ogni casella i possibili numeri che ci possono andare scritti (basandosi sulle caselle nello stesso quadrante, riga, colonna), scrivere un numero quando è l'unico possibile, usare un ciclo brute force tutte le volte che l'algoritmo va in stallo.

[fields]

Un buon algoritmo (ma solo per risolvere i sudoku, niente riguardo P vs NP) sarebbe di associare a ogni casella i possibili numeri che ci possono andare scritti (basandosi sulle caselle nello stesso quadrante, riga, colonna), scrivere un numero quando è l'unico possibile, usare un ciclo brute force tutte le volte che l'algoritmo va in stallo.

Eh sì, è un buon algoritmo in pratica, ma la cosa interessante risiede nelle seguenti osservazioni.

Cosa vuol dire, "scrivere un numero quando è l'unico possibile"? Qui sta il dilemma: come fai a dire se un numero è l'unico possibile? Chiaramente devi utilizzare risorse di calcolo, o uno schema di ragionamento preconfezionato che mostri che è davvero l'unico possibile. Ma a volte può succedere che sia possibile inserire un solo numero, ma che i tuoi criteri non siano abbastanza raffinati per accorgersene. Poi è chiaro che l'algoritmo funzionerà in pratica perché il problema è ridicolmente piccolo nelle dimensioni, ma sul fatto che sia un "buon algoritmo" ci sarebbe da discutere, perché magari usa la forza bruta in casi in cui un essere umano, con un ragionamento banale, verrebbe fuori in un battibaleno. E' questo il fascino del sudoku: sembra non esserci una strategia "intelligente", che eviti il ricorso alla forza bruta. Cioè, in un algoritmo, sembra sempre necessario inserire un ciclo "brute force", in cui vai alla cieca.