Recentemente ho scaricato e installato Microsoft Visual Studio 2015 Community Edition (da https://www.visualstudio.com/ ) un pò per provare le novità, un pò per giocarci e magari trarne qualche spunto per qualche articolo da pubblicare!
Il compito che mi sono dato è stato quello di scrivere un bel risolutore di Sudoku in C#. Il risultato di questo lavoro lo potete scaricare, completo di sorgenti naturalmente, dalla sezione download di questo sito.
In passato avevo già scritto un algoritmo per risolvere un Sudoku e lo avevo già implementato sia in Delphi che in Javascript: si è trattato quindi di fare il porting del risolutore e divertirsi con un pò con l'interfaccia grafica.
La classe Solver ha un utilizzo molto semplice:
- nel costruttore passiamo lo schema da risolvere in forma di matrice di interi, di dimensione 9 x 9 (in futuro aggiungerò anche un metodo separato per caricare un nuovo schema);
- richiamiamo il metodo Solve() passando una matrice vuota che verrà "riempita" con il risultato, se trovato.
Qui di seguito riporto il codice della classe Solver: la tecnica utilizzata è un semplice algoritmo ricorsivo brute-force che lavora in questo modo:
- se la casella è vuota determiniamo tutti i possibili valori richiamando la funzione FillUsableDigits()
- per ogni possibile cifra inseribile richiamiamo lo stesso algoritmo che quindi analizzerà la casella vuota successiva.
Attualmente questo algoritmo termina alla prima soluzione trovata; eventualmente in futuro si potrebbe evolvere per trovare tutte le possibili soluzioni e restituire una lista di matrici.
Infine, è da notare che l'algoritmo richiede che lo schema in input sia corretto ed è per questo motivo che prima di iniziare viene richiamata la funzione CheckTable().
using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;
class Solver
{
int[,] working;
//-------------------------------------------------------
public Solver()
{
working = new int[9, 9];
}
//-------------------------------------------------------
public Solver(int[,] ar)
{
int i, j;
working = new int[9, 9];
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
working[i, j] = ar[i, j];
}
}
}
//-------------------------------------------------------
public bool Solve( int[,] sol)
{
int i, j;
bool res;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
sol[i, j] = 0;
}
}
if(!CheckTable())
{
return false;
}
res = Solve(0, 0);
if( res )
{
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
sol[i, j] = working[i, j];
}
}
}
return res;
}
//----------------------------------------------------------
private bool CheckTable()
{
int i, j;
for (i = 0; i < 9; i++)
{
for (j = 0; j < 9; j++)
{
if (!CheckValue(i, j))
return false;
}
}
return true;
}
//----------------------------------------------------------
private bool CheckValue( int row, int col )
{
int first_row, first_col;
int i, j;
int val = working[row,col];
if (val == 0)
return true;
//------------------------------------------------------------
// test row
//------------------------------------------------------------
for (i = 0; i < 9; i++)
{
if ((i != col) && (working[row,i] == val))
return false;
}
//------------------------------------------------------------
// test column
//------------------------------------------------------------
for (i = 0; i < 9; i++)
{
if ((i != row) && (working[i,col] == val))
return false;
}
//------------------------------------------------------------
// test block
//------------------------------------------------------------
if (row > 5) first_row = 6;
else
{
if (row > 2)
first_row = 3;
else
first_row = 0;
}
if (col > 5) first_col = 6;
else
{
if (col > 2)
first_col = 3;
else
first_col = 0;
}
for (i = first_row; i < (first_row + 3); i++)
{
for (j = first_col; j < (first_col + 3); j++)
{
if ((i != row) && (j != col) &&
(working[i,j] == val))
return false;
}
}
return true;
}
//----------------------------------------------------------
private bool Solve(int st_row, int st_col )
{
int row, col, digit;
int [] usabledigits = new int [9];
for (row = st_row; row < 9; row++)
{
for (col = st_col; col < 9; col++)
{
if (working[row,col] == 0)
{
fillUsableDigits(row, col, usabledigits);
for (digit = 1; digit <= 9; digit++)
{
if (usabledigits[digit - 1] == 1)
{
working[row,col] = digit;
if (Solve(row, col))
return true;
working[row,col] = 0;
}
}
return false;
}
}
st_col = 0;
}
return true; // solution found!
}
//----------------------------------------------------------
private void fillUsableDigits( int row, int col, int []ar )
{
int first_row;
int first_col;
int i;
int j;
for (i = 0; i < 9; i++)
ar[i] = 1;
for (i = 0; i < 9; i++)
{
if (working[row,i] != 0)
ar[working[row,i] - 1] = 0;
if (working[i,col] != 0)
ar[working[i,col] - 1] = 0;
}
if (row > 5)
first_row = 6;
else
{
if (row > 2)
first_row = 3;
else
first_row = 0;
}
if (col > 5)
first_col = 6;
else
{
if (col > 2)
first_col = 3;
else
first_col = 0;
}
for (i = first_row; i < (first_row + 3); i++)
for (j = first_col; j < (first_col + 3); j++)
if (working[i,j] != 0)
ar[working[i,j] - 1] = 0;
}
}