sfida: sudoku layout

Marco Molteni molter a tin.it
Lun 18 Lug 2005 18:28:58 CEST


Avrete tutti sentito parlare del gioco sudoku, no? (fra parentesi ho letto
che e' stato inventato da un americano e poi copiato dai giapponesi).

Il gioco e' alquanto banale, non richiede alcun calcolo o conoscenza
matematica, si tratta di riempire una tabella 9x9 come segue:

+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+
|...|...|...|
|...|...|...|
|...|...|...|
+---+---+---+

dove ogni punto '.' rappresenta una casella, con le cifre dall'1 al 9,
con la restrizione che ogni riga, ogni colonna e ogni sottotabella 3x3
contengano una e una sola volta le 9 cifre.

In base alla difficolta' del gioco, nel layout vi sono un numero
variabile di cifre gia' inserite.

Il gioco si chiama "chiuso" se le cifre preinserite sono tali da
ottenere una sola soluzione, mentre si chiama "aperto" se si
possono ottenere piu' soluzioni valide.

Per esempio e' ovvio che se ci sono solo 2 o 3 cifre preinserite,
ci saranno multiple soluzioni.

Questa e' la sfida per la prima parte, cioe' scrivere un programmino
che generi un layout del gioco. La prossima sfida sara' scrivere un
programmino che risolva un layout dato.

E' anche ovvio che il gioco si puo' estendere a N simboli invece dei 9
originali.

Ecco quindi i problemi:

1. scrivere un programma che generi un layout 9x9 del sudoku, con:
1.1 il minimo numero di cifre preinserite per rendere il gioco "chiuso".
1.2 il numero di cifre preinserite specificabile dall'utente

2. scrivere un programma che generi un layout NxN del sudoku,
specificabile dall'utente, con:
2.1 e 2.2 come nel problema 1.
I simboli sono i seguenti: 1..9A..Z (alfabeto 26 lettere).

Il layout deve essere _identico_ al seguente, per poter in seguito
usare l'output del programma come input del programma risolutore:

N righe tanti sono i simboli, idem N colonne
ogni casella e': o il carattere spazio, o il carattere corrispondente
al simbolo.

Buon lavoro
marco

-- 


Maggiori informazioni sulla lista devel