OliForum Matematico

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?

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?

sisi, basta ke si possa completare il gioco.

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

Non preoccuparti: fph e' un intenditore!
in caso da' una mano lui, che "esce pazzo" per il sudoku

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

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..

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..

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.

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

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.

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

Scordatevi il mio ultimo post: ho scritto sl scemita!
ps: stiamo tt aspettando il post di fph!

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.

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

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?

Jacobi ha scritto:nn sl xke a una prima lettura sembra banale

A me a una prima lettura non sembra banale...

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!! 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...

il grande giove ha dato il suo parere.. dai siamo tt diversi: a me sembrava banale, fino a qndo nn ho provato a risolverlo..

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...