per i sudokisti e non solo

Conteggi, probabilità, invarianti, logica, matematizzazione, ...
Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

per i sudokisti e non solo

Messaggio da Jacobi » 05 mar 2009, 17:54

E data una scacchiera 9x9 riempita da spazi vuoti e numeri da 1 a 9. Diciamo che detta scacchiera e sudocabile se e possibile completarla in modo tale che si rispettina le regole del sudoku. Quante sono le scacchiere sudokabili?
MIND TORNA CON NOI

Avatar utente
kn
Messaggi: 508
Iscritto il: 23 lug 2007, 22:28
Località: Sestri Levante (Genova)
Contatta:

Messaggio da kn » 05 mar 2009, 18:27

se e possibile completarla in modo tale che si rispettina le regole del sudoku
Quindi vanno bene anche scacchiere completabili in più di un modo?
Viviamo intorno a un mare come rane intorno a uno stagno. (Socrate)

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 05 mar 2009, 23:07

sisi, basta ke si possa completare il gioco.

ps: qsto problema mi e venuto in mente oggi mentre facevo un sudoku :D e nn ho ancora provato a risolverlo, per cui nn so la difficolta, so sl ke nn e immediato.
MIND TORNA CON NOI

Avatar utente
SkZ
Messaggi: 3333
Iscritto il: 03 ago 2006, 21:02
Località: Concepcion, Chile
Contatta:

Messaggio da SkZ » 05 mar 2009, 23:20

Non preoccuparti: fph e' un intenditore! :D
in caso da' una mano lui, che "esce pazzo" per il sudoku :wink:
impara il [tex]~\LaTeX[/tex] e mettilo da par[tex]\TeX~[/tex]

Software is like sex: it's better when it's free (Linus T.)
membro: Club Nostalgici
Non essere egoista, dona anche tu! http://fpv.hacknight.org/a8.php

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 06 mar 2009, 10:41

:lol: :lol: :D
MIND TORNA CON NOI

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 06 mar 2009, 15:50

Sono anche io pazzo per il sudoku... Diciamo che è un problema SPAVENTOSAMENTE difficile...

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 06 mar 2009, 16:52

fin' ora sn arrivato a dire soltanto che, se n e il numero di scacchiere gia risolte (cioe quando uno ha completato il gioco, quindi senza spazi vuoti), il numero di quelle sudokabili e $ n(2^{81}-2) $: basta prendere la scacchiera completa e togliere un suo sottoinsieme ( i sottoinsiemi sn $ 2^{81} $ ) a cui va escluso, pero, la scacchiera completa e quella vuota .
Il problema ora e proprio quello di trovare n.. :roll:

Comunque credo ke il problema nn mmetta una soluzione che usi la combinatoria classica, xke qsta richiederebbe l'elaborazione di un algoritmo x poter risolvere il gioco, e nn credo ke ci sia uno applicabili in ogni caso..
MIND TORNA CON NOI

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 06 mar 2009, 17:33

Jacobi ha scritto:richiederebbe l'elaborazione di un algoritmo x poter risolvere il gioco, e nn credo ke ci sia uno applicabili in ogni caso..
Questa non l'ho capita. :shock:

Inoltre, nota che hai over-contato un bel po' di configurazioni, nel conteggio precedente.

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 06 mar 2009, 18:15

Tibor Gallai ha scritto:
Jacobi ha scritto:richiederebbe l'elaborazione di un algoritmo x poter risolvere il gioco, e nn credo ke ci sia uno applicabili in ogni caso..
Questa non l'ho capita. :shock:

Inoltre, nota che hai over-contato un bel po' di configurazioni, nel conteggio precedente.
Scordatevi il mio ultimo post: ho scritto sl scemita! :cry: :P
ps: stiamo tt aspettando il post di fph! :P
MIND TORNA CON NOI

Tibor Gallai
Messaggi: 1776
Iscritto il: 17 nov 2007, 19:12

Messaggio da Tibor Gallai » 06 mar 2009, 23:56

Su wikipedia dice un po' di roba: almeno le configurazioni sudokabili senza caselle vuote sono state contate... Come c'era da aspettarsi, con l'uso della forza bruta.
Invece, sulle sudokabili in generale non ho trovato nulla, ad un'occhiata veloce.

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

nessuno?

Messaggio da Jacobi » 09 mar 2009, 19:20

dai.. nessuno ci prova?
a me sembra proprio un bel problema, nn sl xke a una prima lettura sembra banale, ma anke x il fatto ke in giro su internet nn l'ho trovato qsto numero, e quindi mi incuriosiva vedere se qualcuno lo sapeva calcolare.

ps: aspettiamo sempre il parere di fph :D
MIND TORNA CON NOI

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 10 mar 2009, 16:13

Ma Jacobi, è un problema PAZZESCO! È quasi impossibile. Non basta che i numeri che sono già inseriti rispettino le regole del sudoku, ma è necessario che quelli che si inseriscono di conseguenza non producano contraddizioni. Come fai a prevedere questi casi?

Avatar utente
giove
Messaggi: 519
Iscritto il: 22 mag 2006, 14:56
Località: Pisa / Brescia

Re: nessuno?

Messaggio da giove » 10 mar 2009, 19:08

Jacobi ha scritto:nn sl xke a una prima lettura sembra banale
A me a una prima lettura non sembra banale... :roll:

Jacobi
Messaggi: 227
Iscritto il: 08 mar 2007, 16:29

Messaggio da Jacobi » 11 mar 2009, 11:11

Enrico Leon ha scritto:Ma Jacobi, è un problema PAZZESCO! È quasi impossibile. Non basta che i numeri che sono già inseriti rispettino le regole del sudoku, ma è necessario che quelli che si inseriscono di conseguenza non producano contraddizioni. Come fai a prevedere questi casi?
Io di certo nn lo so!! :D Ci ho gia provato x un giorno intero, da qndo ho fatto colazione, fino alla sera prima di dormire, e nn mi e venuto niente. cmq di qste tipologie di problemi, in cui dv inserire dei nuemri ke rispettano delle regole e poi inserirne altri ke continuamo a rispettarla si incontrano nn raramente in combinatoria! quindi pensavo ke qualcuno dei + esperti del forum fosse in grado di risolverlo.

giove ha scritto:
Jacobi ha scritto:nn sl xke a una prima lettura sembra banale
A me a una prima lettura non sembra banale... :roll:
il grande giove ha dato il suo parere.. :D dai siamo tt diversi: a me sembrava banale, fino a qndo nn ho provato a risolverlo.. :(
MIND TORNA CON NOI

Enrico Leon
Messaggi: 237
Iscritto il: 24 nov 2008, 18:08
Località: Gorizia

Messaggio da Enrico Leon » 11 mar 2009, 14:10

Beh, io non sono molto esperto in combinatoria, ho seguito un breve corso all'università ma niente di più. Ti credo comunque. È che in un normale sudoku ci sono ben 81 numeri, e ci sono condizioni non solo su righe e colonne ma anche nei riquadri: è questo che complica notevolmente le cose. Potrebbe essere simpatico capire quanti sono gli schemi "sudokabili" se sono presenti all'inizio 2 numeri soli. Ma anche così mi pare che bisogna fare un bel po' di conti...

Rispondi