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;
    }
}