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.
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;
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.
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. :-)