kspeciall
Messages postés1Date d'inscriptionlundi 30 juillet 2007StatutMembreDernière intervention30 juillet 2007
-
30 juil. 2007 à 12:48
cs_loloof64
Messages postés342Date d'inscriptionvendredi 1 septembre 2006StatutMembreDernière intervention 6 novembre 2012
-
26 mai 2009 à 15:33
Bonjour à tous,
Je dois faire un solveur de kakuro en java dans le cadre d'un projet complémentaire et je galère un peu. Je voulais savoir si quelqu'un à déjà réaliser ce solveur et si oui si vous pouviez me donner les classes de bases. Je sais que je devrais le faire tout seul mais je suis actuellement en stage à l'étranger et je manque de temps pour faire le solveur que je dois rendre dans un mois.
cs_loloof64
Messages postés342Date d'inscriptionvendredi 1 septembre 2006StatutMembreDernière intervention 6 novembre 2012 26 mai 2009 à 15:33
Désolé de poster ce message en retard, mais comme le code d'origine comportait quelques erreurs qui le rendaient inexploitables (son auteur précise qu'il ne l'avait pas testé), j'ai pensé qu'il était utile de proposer ici des modifications : d'autant plus que j'ai eu un peu de mal à corriger les erreurs .
// recursive backtrack for Kakuro
class Cell{ // you make one of these for each cell that gets a number filled into it
// every cell participates in both a row sum and a col sum
static Cell[] all; // all Created cells - you figure out how to build this
int val; // holds the solution value
Sum row;
Sum col;
static class Sum{ // you build one of these for each row sum and one for each col sum
// you figure out how to initialize this but note: two cells that share a row
// MUST actually have the same row Sum embedded in them. the backtracking
// assumes that shared data is in fact shared and not copied.
int total; // total needed in remaining cells
int digitsUsed = 0; // bitsset that keeps track of all digits already used in this row,or col
int cellsLeft; // count of slots in this row or col (updated by place)
/*
* Default constructor
* Be Carrefull ! Field cellsLeft must be initialised before
* using valid(int, int) methods
* => this method is based on cellsLeft field value .
*/
Sum(){
}
/*
* Usefull constructor
* Should be preferred to the default constructor .
*/
Sum(int r, int n){
total = r;
cellsLeft = n;
}
//For methods valid, add, and remove : 'digit' must be 2< 1 && total > i) || (cellsLeft 1 && total i)) return true;
return false;
}
void add(int i, int digit){ // only called for valid entries
total -= i;
digitsUsed |= digit; // set bit indicating digit is used
cellsLeft--;
}
void remove(int i, int digit){ // called when backing out a result
total += i;
digitsUsed &= ~digit; // unset bit indicating digit is used
cellsLeft++;
}
}
static final int DONE = 1;
static final int BACKTRACK = 2;
static void solve(){
place(0);
System.out.println("That's all, folks!");
}
static int place(int cellIndex){ // tries to place value in this cell
if(cellIndex == Cell.all.length) {return Cell.DONE;}
Cell c = Cell.all[cellIndex];
int digit = 1;
for(int i = 1; i<10; i++){
if (c.row.valid(i,digit) && c.col.valid(i,digit) ){
c.val = i; //set the value in the cell
c.row.add(i,digit);
c.col.add(i,digit);
if(Cell.DONE == place(cellIndex+1)) return Cell.DONE;
c.row.remove(i, digit); // back out because last place failed
c.col.remove(i, digit);
digit *= 2; // advance digit bit
} // else digit not legit so don't place, just try next number
} // end of digits and not yet done so...Backtrack
return Cell.BACKTRACK;
}