Exact cover problem del Sudoku

[Javino89]

Salve. Sto cercando di creare la matrice corrispondente all'"exact cover problem del Sudoku". Dovrei aver capito come è strutturata, mi sono letto la teoria, ma ho difficoltà ad implementarla in Java.

Per chi non lo sapesse, creare l'exact cover problem del Sudoku serve per implementare un algoritmo molto efficiente per la sua risoluzione/generazione.

Nell'exact cover problem si ha una matrice di 0 ed 1. Nel caso specifico del Sudoku le colonne
rappresentano i vincoli ed ogni riga (se ho capito bene) dovrebbe rappresentare ogni possibile posizione di ogni numero.

Quindi si hanno:

729 righe, dato che i valori possibili sono i numeri da 1 a 9, e tutte le possibili posizioni sono 81 (quindi 729 = 9 x 9 x 9)

324 colonne:

- le prime 81 sono identificate dalle 81 celle e si utilizzano per indicare che un valore è stato piazzato in una determinata cella
- le successive 81 sono identificate dalle 9 righe e dai 9 possibili valori. Un entry nella colonna R = 3, S = 7, significa che la terza riga contiene il valore 7.
- le successive 81 (di nuovo) sono la stessa cosa del punto precedente ma per le colonne.
- Le ultime 81 sono per i 9 box grandi 3x3 ed i 9 possibili valori.

Questo link mostra la situazione: http://www.stolaf.edu/people/hansonr...overmatrix.htm

Bene, io dovrei generare quella matrice, e poi modificarla in base al Sudoku da risolvere che ho in
ingresso. Però è un po macchinosa la cosa e mi servirebbe qualche indizio.. ho sempre odiato le matrici

[schumy2000]

non capisco il tuo problema:

//creazione
int matrice[][][]=new int[9][9][9];

//modifica
matrice[4][2][5]=7;

Così puoi costruire/modificare la matrice.

Ciao.

[Javino89]

Si ok, queste sono le basi di java xD. Non è questo il problema, il problema è creare la matrice specifica che ti ho detto.

Comunque di base dovrebbe essere così:

int[] R = new int[9 * 9 * 9][9 * 9 * 4];

// cicli per inizializzare i vincoli riga-colonna

// cicli per inizializzare i vincoli di riga

// cicli per inizializzare i vincoli di colonna

// cicli per inizializzare i vincoli dei box

return R

La matrice ottenuta va poi modificata in base al Sudoku da risolvere.

R è una matrice di 0 ed 1, ed una cella della matrice R contiene 1 se e solo se la riga che descrive la posizione del numero (1 - 9) soddisfa il vincolo della colonna relativa.