OliForum Matematico

Intendo dire che per le scacchiere 4x4 e 9x9 e 16x16 e' possibile costruire degli automi deterministici a stati finiti che risolvono il problema.
Mentre per scacchiere di dimensioni (molto) piu' grandi tali automi non esistono ed ecco che scatta l'ipotesi NP.

Catraga ha scritto:Intendo dire che per le scacchiere 4x4 e 9x9 e 16x16 e' possibile costruire degli automi deterministici a stati finiti che risolvono il problema.
Mentre per scacchiere di dimensioni (molto) piu' grandi tali automi non esistono ed ecco che scatta l'ipotesi NP.

Dunque, è chiaro che per ogni n fissato esiste l'automa banale che risolve il problema (visto che per ogni n le configurazioni possibili sono finite), giusto? Per questo dicevo che non ha senso considerare la polinomialità se non rispetto a n variabile...

P.S.
Grazie per l'articolo!!!

io odio il sudoku.....
è un giochetto idiota, a me fa schifo.


E comunque P è diverso da NP, che volete farci, il mondo è fatto così....

Ebbene sì: i 'concontinentali' d'oltremanica avranno ad ottobre i loro bei campionati di Sudoku: "È un rompicapo matematico. Niente tecnologia, solo numeri da scrivere
Sudoku, nuovo gioco-mania d'Europa
In Gran Bretagna ha conquistato milioni di persone. E in Italia arriva anche un mensile. In futuro potrebbe sbarcare sui cellulari ...in Inghilterra avrà i suoi primi campionati nazionali a ottobre..." tratto da Corsera. se si divertono loro

io non capisco cos'abbiate da ridire sul sodoku: convengo che con la matematica non c'entra molto (almeno fin quando lo si risolve con tecniche "tradizionali"... poi, come ha affermato anche Odifreddi, lo si può risolvere anche con sistemi di equazioni, e in questo modo comincia ad entrarci con la mate), ma certo non è un passatempo stupido, richiede logica, pazienza e un pizzico di "intuizione visiva" per così chiamarla...
di sicuro è più educativo mettere il sudoku sui cellulari che space impact o snake; io lo paragonerei ai cruciverba e ad altri passatempi tipici delle riviste quali "La settimana enigmistica" ed altre...

insomma, è un gioco come tanti altri!

(ma concordo che non ha nulla a che vedere con le molteplici possibilità offerte dal cubo di Rubik o con il meraviglioso universo degli scacchi!... )

bye

Sodoku? Preferisco il Go-Moku

http://utenti.quipo.it/base5/jsgomoku/gomoku2.htm

Avete ragione entrambi
--> x karotto: era x sentirci superiorio agli Inglesi (1 volta tanto)

La situazione sta diventando tragica: passi il fatto che in una classe di 23 circa 10 persone siano appassionate di sudoku (in pratica tuttle le galline e i galli della classe), ma ora il mio prof di mate vuole farci delle lezioni sul sudoku!!

E un cosa terribile ragazzi! Dove andremo a finire?

...Scusate la domanda in po' inconsulta, ma... che diavolo di lezione vuole farvi il vostro prof su di un gioco che (per quanto ne so) richiede logica tendente a zero??

uhm...
tanto per andare sul delirio andante.. ha un senso chiedersi quanti siano i sudoku (sudoki?) associativi?
mi spiego, immaginiamo la casella nella $ i $-esima riga e $ j $-esima colonna come risultato di $ i*j $.
a questo punto, un sudoku è la tabella moltiplicativa dell'operazione binaria $ * $ su $ \mathbb{Z}_9 $. che sia invertibile, segue dalla richiesta che nessun numero sia ripetuto nella stessa riga/colonna. che esista un elemento neutro, può essere fatto imponendo che la colonna e la riga relative ad 1 contengano i numeri ordinatamente...
esistono (se sì, quanti sono, se è umanamente possibile contarli) i sudoku/i tali che $ (\mathbb{Z}_9, *) $ sia un gruppo?

A quanto pare dobbiamo fare i grafi quest'anno e il prof vuole farci vedere se i grafi sono applicabili o no al sudoku (che al plurale fa sudoku, essendo una parola giapponese ), anche se sinceramente non ho capito a cosa si riferisse... ( tra l'altro non ho capito neanche il post di ma_go.. gruppi? invertibile? )

p.s. in verità non so neppure cosa sia un gioco NP... qualcuno può spiegarmelo?

Non essendo molto esperto nell'argomento non mi azzardo a darti qualche spiegazione (che potrebbe poi risultare sbagliata...). In compenso, se te la cavi con l'inglese, c'è una bella paginetta html del Clay Mathematics Institute che spiega quale sia il problema più generale (P vs NP).
Spero possa esserti utile; per qualsiasi chiarimento chiedi a qualcuno in questo forum che ne sappia più di me (cioè praticamente tutti ).