BY NIKHIL NARAYANAN
I’m Nikhil Narayanan, an individual JAVA GUI dev, I work with SWING and AWT, and have started taking interest in JS and android development recently. You may recognize me from the discussions “A Sudoku Solving Algorithm” and “JAVA: The Birth Of A New Age”.
Last time we talked about an algorithm to solve Sudoku puzzles, so in the spirit of combinatorial logic puzzles, I bring to you Sudoku’s younger brother, Kakuro! Before we discuss the approach a brute force computer program would use to solve the puzzle, let’s understand what exactly Kakuro is, and how the board works.
Ready? Let’s dive right in!
Kakuro or Kakkuro is a combinatorial logic puzzle that we consider as the mathematical analogue of the crossword. Kakuro puzzles rely on the summation of numbers from 1-9 to obtain a 1-digit/2-digit sum while sticking to a set of constraints, it’s a regular in most newspapers with puzzle sections, I myself started devising an algorithm to solve this board only after seeing it in the ‘Mumbai Mirror-Sunday Edition’. What many people don’t know is that kakuro in itself is second only to Sudoku in numerical combinatorial puzzles and that while Sudoku doesn’t really have any other synonyms, Kakuro was renamed to cross-sums in some newspapers. But its original name ‘Kakuro’ remains the most popular name to date.
The Board:
The Kakuro board’s structure is analogous to a Crossword board, but we have numbers here instead of letters.
To make explaining the board and by extension, the solving algorithm simpler, I will be defining some terms. Note that these terms are not official definitions but simply a means to reach our target of understanding this board.
CELL: Any grid box within the Kakuro Board.
MASTER CELL: Any cell with a diagonal split between the numbers inside the cell.
EMPTY CELL: An empty cell that is yet to be filled with a number.
BLANK CELL: An empty cell that is NOT supposed to be filled.
Consider the following master cell (15/29):
The 4 empty cells to the right of ’29’ must consist of a digit from 1-9 each, no repetitions allowed. Finally, the sum of all these digits should be 29.
Similarly, for the same master cell
We see that the number ’15’ is oriented/facing downwards, with 5 empty cells to fill. This means that each of these grid cells must be filled with a number between 1 and 9 (both limits inclusive) such that their sum is equivalent to 15, with no repetitions allowed.
Going by this pattern, the solution of the board used as an example above is:
Looking at this board, you can see how subsequently the numbers are filled into empty cells by using the master cells’ numbers’ as a summation guideline and respecting the constraint of every digit in the summation sequence is unique, single-digit and non-zero.
The Solving Algorithm:
Firstly, let’s see how we can calculate the solutions to fill in with respect to a particular master cell:
Here’s a method is written in JAVA which in short is my choice of programming language( read JAVA: The Birth Of A New Age for why I use JAVA):
//returns all possible numerical combinations for a specific kakuro row or column(empty)
public static ArrayList<Long> combinePermute(int sum,int boxes)
{
ArrayList<Long> rs=new ArrayList<>(0);
String min=”1″;
String max=”9″;
for(int k=0;k<(boxes-1);++k)
{
min+=”0″;
max+=”9″;
}
long minimum=Long.parseLong(min);
long maximum=Long.parseLong(max);
for(;minimum<=maximum;++minimum)
{
if(isUnique(minimum)&&(sumOfDigits(minimum)==sum)&&(!new
Long(minimum).toString().contains(“0”)))
{rs.add(minimum);}
}
return rs;
}
This method basically returns a set of solutions for a particular number of empty cells and a master cell sum. For example, if the master cell had a sum value of 4 and the number of empty cells 2, we would get the following values in return 13,31. These are possible solution strings that we can fill into the empty cells as such:
And now, in order to complete, a method to only select solution strings for the empty cells which will conform to some of the filled cells solutions
//Returns all numerical combinations which comply with the constraint so provided
public static ArrayList<Long> constraintSort(ArrayList<Long> solns,String constraint)
{
ArrayList<Long> sorted=new ArrayList<>(0);
for(Long cnum:solns)
{
String s=cnum.toString();
for(int k=0;k<s.length();++k)
{
char og=s.charAt(k);
char n=constraint.charAt(k);
if(!((og!=n)&&(n!=’0′)))
{sorted.add(cnum);}
}
}
return sorted;
}
Now we may use the sudoku solver algorithm technique to mix and match solutions till we get the correct solution configuration.
Something the reader would probably have assumed in the meantime is that given the numerous differences between the structure and rules of a Sudoku board and a Kakuro board, the way a computer program might solve the boards would be different. This assumption, however, is, at least for my techniques, wrong- The reason being my solving techniques rely on brute force algorithms, an algorithm that tests every possibility before it hits on the right configuration/state of the board, forming possible solutions simply by following the rules of the game, putting these solutions into a sample board and combining different solutions with each other until we finally find the right configuration of the board.
In the sudoku algorithm, we used these 3 rules while filling a grid box->. The number had to be unique in its own row, column and region. Whenever there were multiple possible solutions for one particular grid box, the board would be cloned and each solution would be filled into that particular grid box of a cloned board. Later we would add these boards to an Array/ArrayList and solve the board at the first index of the array, adding cloned child boards to the end of the list and removing the parent at index 0.
If we hit a board where we filled an invalid solution for a particular grid box, we will eventually get stuck. We won’t be able to fill in any other solutions. Therefore we remove the parent board and continue parsing the list. Eventually, you will only have one filled board. This is the final solution board.
The reason I am emphasizing on the way we solve a sudoku board, is because although the way we fill a grid box is different for the two puzzles, the fact remains that in both boards a particular grid box/ set of grid boxes can be filled while pertaining to the rules, but only one solution set is actually valid and given we don’t know which solution is correct at which point in the board, we cannot determine at which position the incorrect substitution was made, leaving us in a fix.
Therefore using the sudoku solver algorithm to mix and match the configurations we obtained will help us complete the board.
PS: An application file of the sudoku puzzle solver is now available for desktop/PC, download the software from:
https://bleachichigoanime.wixsite.com/website/my-work
