Solving a Kakuro
CSP modeling in Artificial Intelligence
Kakuro
Kakuro is a kind of logic puzzle that is often referred to as a mathematical transliteration of the crossword. The objective of the puzzle is to insert a digit from 1 to 9 inclusive into each white cell such that the sum of the numbers in each entry matches the clue associated with it and that no digit is duplicated in any entry. It is that lack of duplication that makes creating Kakuro puzzles with unique solutions possible, and which means solving a Kakuro puzzle involves investigating combinations more, compared to Sudoku in which the focus is on permutations.
In "Artificial Intelligence" speciality at the faculty, we were asked to model, in the form of a CSP, a Kakuro grid to find the constraints in order to create a game solving algorithm.
CSP : Constraints Satisfaction Problems
A CSP is a mathematical problem where we look for states or objects satisfying a certain number of constraints or criteria. By using this principle on the Kakuro, we have a suitable way to determine and manage all the constraints that a Kakuro grid can pose. We can thus model it and solve it correctly by having all the necessary constraints.
- A list of variables (the components of the problem)
- An association domain for each variable (here the numbers 0 to 9)
- A list of constraints (which are the problem constraints)
- A set of compatibility relationships
The constraints of Kakuro
There are two main constraints that emerge from a Kakuro grid : the sum of the figures, which should result in the number registered in the original column or line box; and that a sum can not contain two of the same number (if the sum is 12 and that there are 4 boxes, the solution "3 + 2 + 3 + 4" is not correct because 3 appears two times).
The project
Unfinished for lack of time, the project was to implement two solution algorithms in C to solve a grid of Kakuro. This was backtracking algorithm and Forward-Checking algorithm. Only the backtracking algorithm has been achieved. It is implemented iteratively and works with a stack system to operate the CSP variable list.
Here's the code :
/***********************************************************
Backtrack algorithm.
Return 1 if a soluce was found, 0 otherwise.
************************************************************/
int backtrack(GrilleDeJeu jeu, CSP* csp) {
int i;
variable var;
int consistant = 0;
int valeur;
// While the list of variables is empty.
while(csp->V != NULL) {
// Next variable to test.
var = depiler_var(&(csp->V));
consistant = 0;
// While there are values in the domain of variables to be tested.
while((valeur = domaineVide(var.domaine)) != -1) {
var.domaine[valeur - 1] = 0;
consistant = 0;
// If value is a soluce.
if ((consistant = valeur_consistante(jeu, var, valeur)) == 1) {
// We affect the value to the corresponding box.
jeu.cases_blanches[var.case_blanche->id].valeur = valeur;
// The values of the cells associated with the sum constraints are updated.
mettreAJourContraintesSomme(var, valeur, &jeu);
// This assignment is stacked in the list of assignments.
empiler_debut(&(csp->A), var);
break;
}
}
// If no value was a soluce
if (consistant == 0) {
// We reset the value of the box to 0.
var.case_blanche->valeur = 0;
// If no assignment could be possible.
if (csp->A == NULL) {
return 0;
}
// Domain reset.
for(i = 0; i < 9; i++)
{
var.domaine[i] = 1;
}
// We put the variable at the top of the list.
empiler_debut(&(csp->V), var);
// We put the variable browsed at the top of the list.
empiler_debut(&(csp->V), csp->A->var);
// Remove the current assignment from the list.
depiler_var(&(csp->A));
}
}
return 1;
}
The report is available below.