Kakuro

Are you trying to develop the algorithm to solve existing puzzles or the algorithm to create kakuro puzzles?

If the latter, I assume that you are looking for more than the simple and obviously correct algorithm of: surf web, find kakuro site, extract puzzle, repeat as often as desired.

Presumably puzzle generation is driven by building a solver and then randomly generating psuedo puzzles, and attempting to solve them until one finds one that actually has a single unique solution.

marlin314a at 2007-7-14 22:32:12 >

// 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)

boolean valid(int i, int digit){

if((digitsUsed & digit) != 0) return false; // digit was already in use

if((cellsLeft > 1 && total > i) || (cellsLeft == 1 && total == i)) return true;

return false;

}

void add(int i){ // 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) {showSolution(); return Cell.DONE;}

Cell c = Cell.all[cellIndex];

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;

}

}

Note - I have left out all the code that sets up the puzzle (creates the cells and the sums and puts all the cells into the "all" array.) I have also left out the showSolution code. At the time showSolution is called cell.val holds the solution. You need to decide how you want to read in a problem and how to spew out the solution.

No effort is made to sort the back portion, the unsolved cells after each individual place operation. Doing so will result in an enormous optimization that will greatly reduce the work that the computer does in searching for a solution. The idea is that after you have placed a cell, you want to next consider a cell that is in the same row or in the same col as the placed cell. Furthermore, you want to move all bottle necks toward the front of the list.

This need not be beastly hard. place() is given a cellIndex to work with, but is under no requirement to actually place that cell, you could first swap the cell at that index with any greater index and proceed from there, thus the first step of place could be a search for cells that are particularly easy to place. The most obvious candidate being a cell whose row or col has just been reduced to having only one cell left. You could detect this event (having a cellsLeft count decreased to 1 by the add routine), stuff that sum into a slot and then on the next call to place first search for a cell that has that sum either as a row or a col.

None the less, when I consider the trade off, of me working to write more code versus the computer doing millions more calculations that necessary every time it is run, hands down the computer loses. let it grind!

Lastly, this is all psuedo code, typed directly into notepad, neither checked by any compiler nor in any way tested. Caveat emptor!

marlin314a at 2007-7-14 22:32:12 >