Vedremo insieme come scrivere un programma per trovare la soluzione ad un sudoku. Ripassiamo le regole del gioco. Si gioca su una griglia 9x9 divisa in altre griglie 3x3 che chiameremo regioni o riquadri. Il sudoku inizia con una griglia già contenente dei numeri, l'obbiettivo del gioco è quello di riempire le celle vuote con i numeri compresi da 1 a 9 (un solo numero per cella) seguendo questa regola: Lo stesso numero può comparire una sola volta per ogni riga, colonna e regione.

Come fare?

Di seguito è riportata la mia soluzione al gioco, non è detto che sia l'unica e non è detto che sia la migliore. È solo la mia soluzione, se qualcuno di voi lettori ne trova qualcuna con complessità minore, più performante o che occupa meno memoria scrivetemi pure.

Abbiamo bisogno di una matrice per contenere il risultato del sudoku, schema, di dimensioni 9x9 e di un'altra matrice m a 3 dimensioni 9×9×9 dove ogni elemento assumerà i valori SET o UNSET. La matrice m sta ad indicare per ogni cella se è possibile o meno inserire un numero. Ad esempio se c'è il valore SET nelle caselle (x, y, 5) e (x, y, 6) significa che nella posizione (x, y) dello schema è possibile inserire il numero 5 e il numero 6. In questo caso non potremmo inserirne nessuno dei due perché non abbiamo ancora la certezza di quale dei due sia quello giusto.

Possiamo inserire un numero nel sudoku nella posizione (x, y) quando nella matrice m si verifica una di queste condizioni:

• C'è un solo valore a SET nel vettore (x, y, z) per ogni z in [0, 9], allora se (x, y, z1) è il valore a SET in (x, y) possiamo inserire il valore z1 + 1
• C'è un solo valore a SET nel vettore (x, y, z) per ogni y in [0, 9], allora se (x, y1, z) è il valore a SET in (x, y1) possiamo inserire il valore z + 1
• C'è un solo valore a SET nel vettore (x, y, z) per ogni x in [0, 9], allora se (x1, y, z) è il valore a SET in (x1, y) possiamo inserire il valore z + 1
• C'è un solo valore a SET in un riquadro, se (x, y, z) è il valore a SET allora in (x, y) possiamo inserire il valore z + 1

Ogni volta che inseriamo un numero nello schema dobbiamo settare al valore UNSET nella metrice m la riga, colonna, profondità e riquadro della posizione del valore inserito. Questo, logicamente, sta ad indicare che se ho inserito un numero nello schema allora non è possibile inserire lo stesso numero nella stessa riga, colonna, riquadro (e nella cella stessa.)

[caption id="attachment_231" align="alignnone" width="500" caption="shematizzazione della matrice m"][/caption] Nella figura potete vedere quali celle verranno coinvolte della matrice m se si inserisce il numero nella casella bianca.

Da dove iniziare

Si inizia con uno schema vuoto, e con la matrice m inizializzata tutta a SET. Si procede inserendo i numeri presenti nello schema di partenza e UNSET-tando di conseguenza le celle di m ad ogni inserimento di un nuovo numero. Finiti i numeri dello schema iniziale si analizza m cercando, secondo le condizioni viste precedentemente, se possiamo inserire un numero. Trovato il numero da inserire, viene scritto in schema e aggiornata m esattamente come abbiamo fatto in precedenza.

Un pò di codice

Il linguaggio che ho scelto per questo tipo di programma è l'ANSI C. Vediamo il codice.

/* * sudoku - Version 0.1 * * Copyright (C) 2009 Danilo Abbasciano * * This program is free software; you can redistribute it and/or modify * it under the terms of the GNU General Public License as published by * the Free Software Foundation; either version 2 of the License, or * (at your option) any later version. * * This program is distributed in the hope that it will be useful, * but WITHOUT ANY WARRANTY; without even the implied warranty of * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the * GNU General Public License for more details. * * You should have received a copy of the GNU General Public License * along with this program; if not, write to the Free Software * Foundation, Inc., 59 Temple Place, Suite 330, Boston, MA 02111-1307 USA * * Bug Report: * */

include #include #include #define ALL -1

define SOMMA 0

define AZZERA 1

define SET 1

define UNSET 0

define DIM (rig*col)

int rig, col;

char m[9][9][9]; char schema[9][9];

int ins_number(int x, int y, int n, int inseriti); int griglia(int x, int y, int z, int mode); int solve(int inseriti); void stampa();

int main(int argc, char *argv[]) { int x, y, z, ins = 0; FILE *f; char s[10];

if (argc != 2) { printf("Usare: %s [schema]\n", argv[0]); return 1; }

rig = col = 3;

if ((f = fopen(argv[1], "r")) == NULL) return 1;

/* inizzializzazione */ for (x = 0; x < DIM; x++) for (y = 0; y < DIM; y++) for (z = 0; z < DIM; z++) m[x][y][z] = SET;

x = 0; while (fscanf(f, "%s\n" , s) && x < DIM) { for (y = 0; s[y] != '\0'; y++) { if (s[y] >= '1' && s[y] <= '9') ins = ins_number(x, y, s[y] - '0', ins); } x++; } fclose(f);

if (!solve(ins)) { printf("Impossibile risolvere \"%s\".\n", argv[1]); return 1; }

stampa(); return 0; }

int ins_number(int x, int y, int n, int inseriti) { if (m[x][y][n-1] == UNSET) { printf("error: nella posizione (%d,%d) non puo` esserci il numero %d\n", x,y,n); stampa(); exit(1); } schema[x][y] = n; griglia(x, y, n-1, AZZERA); griglia(ALL, y, n-1, AZZERA); griglia(x, ALL, n-1, AZZERA); griglia(x, y, ALL, AZZERA);

return inseriti + 1; }

int solve(int inseriti) { int x, y, z, i; int trace;

while (inseriti < DIM * DIM) { trace = inseriti;

for (x = 0; x < DIM; x++)
  for (y = 0; y < DIM; y++)
if ((z = griglia(x, y, ALL, SOMMA)) != -1)
  inseriti = ins\_number(x, y, z+1, inseriti);

for (x = 0; x < DIM; x++)
  for (z = 0; z < DIM; z++)
if ((y = griglia(x, ALL, z, SOMMA)) != -1)
  inseriti = ins\_number(x, y, z+1, inseriti);

for (y = 0; y < DIM; y++)
  for (z = 0; z < DIM; z++)
if ((x = griglia(ALL, y, z, SOMMA)) != -1)
  inseriti = ins\_number(x, y, z+1, inseriti);

for (z = 0; z < DIM; z++)
  for (x = 0; x < DIM; x += rig)
for (y = 0; y < DIM; y += col)
  if ((i = griglia(x, y, z, SOMMA)) != -1)
    inseriti = ins\_number(x + (i / rig), y + (i % col), z+1, inseriti);

if (trace == inseriti) return 0;

} return 1; }

int griglia(int x, int y, int z, int mode) { int somma = 0; int index = 0; int a, b;

if (x != ALL && y != ALL && z != ALL) { /* riquadro */ x = (x / col) * col; y = (y / rig) * rig; for (a = 0 ; a < col; a++) for (b = 0 ; b < rig; b++) if (mode == SOMMA && m[a + x][b + y][z] == SET) { somma++; index = a*rig + b; } else if (mode == AZZERA) m[a + x][b + y][z] = UNSET;

} else { for (a = 0; a < DIM; a++) switch (mode) { case AZZERA : if (x == ALL) m[a][y][z] = UNSET; else if (y == ALL) m[x][a][z] = UNSET; else if (z == ALL) m[x][y][a] = UNSET; break; case SOMMA: if (x == ALL && m[a][y][z] == SET) { somma++; index = a; } else if (y == ALL && m[x][a][z] == SET) { somma++; index = a; } else if (z == ALL && m[x][y][a] == SET) { somma++; index = a; } } } return (somma == 1)? index : -1; }

void stampa() { int x, y; printf("\n"); for (x = 0; x < DIM; x++) { for (y = 0; y < DIM; y++) { if (y % col == 0) printf(" "); printf(" %d", schema[x][y]); } if (x % rig == 2) printf("\n"); printf("\n"); } }

Le funzioni sono poche ed abbastanza chiare. C'è ins_number() inserisce un numero aggiornando le due matrici, griglia() ci aiuta per le operaizoni sulla matrice m, solve() trova la soluzione ad Sudoku, ed infine stampa() visualizza a video la matrice schema.

Il programma accetta in input un file con lo schema iniziale in questo formato. Dove ci sono i numeri dello schema iniziale. Per le caselle vuote dovremmo inserire qualsiasi carattere diverso da una cifra. ########6 76##9###8 ##5#8#17# ####13### #412#983# ###76#### #26#3#5## 9###4##1# 8######4# e stampa la soluzione

1 8 2 5 7 4 3 9 6 7 6 4 3 9 1 2 5 8 3 9 5 6 8 2 1 7 4

2 7 8 4 1 3 9 6 5 6 4 1 2 5 9 8 3 7 5 3 9 7 6 8 4 2 1

4 2 6 1 3 7 5 8 9 9 5 3 8 4 6 7 1 2 8 1 7 9 2 5 6 4 3

Buon Sudoku a tutti.