Awesome

Ada-Sodoku

Small Library for Sodoku grid solving / finding. This don't use smart algorithm for sodoku finding, but lead to "brut force" combinatory evaluation of solutions, in an optimized way.

Implementation

In the implementation, we use two types :

a Grille type definition that handle the grid configuration, that mean an array of numbers, handling the number position in the grid.

   type Grille is array (column,line) of Matrice;
   pragma Pack(Grille);

the primitives available on this type are :

   -- fonctions de manipulation d'une grille de sodoku
   procedure Put(G : in out Grille; R : Ref ; N : Number);

   function Get(G : in Grille; R : Ref) return Number;

In searching solutions, this data structure is not optimized as there are impossible alternatives, so a Search Type is setted up for handling impossible combinaison.

in the Search type we store the the combination alternatives for speed up the search :

   type Search is record
      G : Grille;
      P : Grille_Possibilite;
   end record;
    
   type Grille_Possibilite is
 		array (column, line) of Matrice_Possibilite;
   pragma Pack(Grille_Possibilite);

Extra primitives are setted up on this type, for handling possible moves :

   -- liste des possibilités pour une case dans la grille
   type Possibilite is array (1 .. Number'Last) of Boolean;
   pragma Pack(Possibilite);

   --
   -- Liste les possibilités pour une case de la grille ...
   --
   function List_Possibilite (S : in Search;
  R :Ref) return Possibilite;

   -- Compte le nombre de possibilités pour une case ..
   function Count_Possibilite (S : in Search;
   R :Ref) return Natural;

Conversions can be done between thoses 2 types thanks to :

   -- converti une grille de sodoku en grille de recherche
   function To_Search(G : in Grille) return Search;

Combinatory library

for evaluating the whole solutions, a custom combinatory library has been setted up for handling large binary numbers and be able to iterate about thoses large numbers.

Next

This library has been used for searching a brand large number of grids, but could be interesting to be distributed among a large number of computers, using the distributed annexes. :-)