Kuroro Solver Documentation

Introduction

This program is designed to solve Kakuro puzzles. The puzzles are loaded from an external file. The initial blank grid is shown, followed by the completed grid.

Grid File Format

The following is a reference to the format of the Kakuro grid files.

First line is a space seperated line with the rows, cols, and delimiter type (which can be SPACE or TAB, in caps). Rows and columns include the first row and column that have no empty cells.
- ex: 12 10 TAB
Next n lines (where n is the rows from the first line) contain the grid data, seperated by the delimiter from the first line, in the following format:
- a black square should be a single slash (\)
- a clue square should have the column clue before the slash and the row clue after the slash (12\13 or 5\ or \3)
- an empty square should be an x
- example line:
```
 \      18\     32\5    x       x       11\6    x       x       x       9\
```

Example of what could be in a file:

 12 10 TAB
 \      \       27\     4\      \       \       9\      11\     \       \
 \      6\11    x       x       7\      \3      x       x       16\     13\
 \10    x       x       x       x       28\24   x       x       x       x
 \10    x       x       5\6     x       x       28\     11\13   x       x
 \      \12     x       x       29\10   x       x       x       x       7\
 \      9\      18\41   x       x       x       x       x       x       x
 \4     x       x       11\23   x       x       x       4\3     x       x
 \28    x       x       x       x       x       x       x       27\     \
 \      13\29   x       x       x       x       15\11   x       x       5\
 \15    x       x       12\     4\14    x       x       9\12    x       x
 \10    x       x       x       x       \13     x       x       x       x
 \      \       \12     x       x       \       \14     x       x       \

Comments may optionally be put on lines after the last, they will not be read into the program at all.

Program Operation

Whenever a cell is filled in with a possibility, that digit is removed from the possibilities of all other cells within the row and column that intersect the cell that was filled in.

The following is an outline of how the Kakuro Solver solves puzzles:

Read in the blank Kakuro grid from the given file.
Go through every empty cell in the grid and calulate the digits that are possible given the row and column clues that intersect the cell. This is done as follows:
1. Calculate the valid possibilities for the row clue that intersects the cell.
2. Calculate the valid possibilities for the column clue that intersects the cell.
3. Calculate the intersection of those possibilities, any possibilities that do not intersect are invalid.
Iterate through the entire grid, stopping at blank cells. If there is a single digit possible to go into that cell, fill the cell in with that possibility.
Iterate through the entire grid, stopping at clues. The row or column of the clue is checked for one remaining empty cell. This is done as follows:
1. Determine how many cells are empty.
2. Calculate the total of all non-empty cells.
3. If the total number of empty cells is 1, subtract the total of the non-empty cells from the clue and fill in the empty cell.
If step 4 causes a change in the grid, return to step 3. Otherwise, continue.
Iterate through the entire grid, stopping at clues. For each clue stopped at, determine if the possibilities of each cell within that clue are valid with regards to cells filled in and the cells intersecting the clue's cells. This is done as follows:
1. Get the digits of the cells that are filled in.
2. If all cells are filled in, continue to the next clue.
3. Check all the valid combinations of the clue, eliminating the ones that do not intersect the digits already used (or just add it if all cells are still empty).
4. Iterate through each cell within the clue, stopping at blank cells. Do the following with the blank cell:
  1. Iterate through the possibilities of the empty cell. On each possiblity, do the following:
    1. Add the possibility to the set of used digits for the clue.
    2. Iterate through the valid combinations for the clue. Do the following for each combination:
      1. Find the intersection of the combination and the used possibilties. If the intersection does not match the used possibilities, the combination is invalid and will be skipped.
      2. Recursively check all other empty cells within the clue to see if their remaining possibilities will be valid. This is done by checking if adding one of the other possibilities for the other empty cells would invalidate the combination being checked. Break from the loop if that's the case.
    3. If the above loop is broken before getting to the end, the combination is valid, add the possibility checked to the list of valid possibilities.
  2. Update the possibilities of the empty cell.
If step 6 makes no changes, deem the grid to be invalid and break from the loop. Otherwise, return to step 3.
Once the above is completed, you will either be shown a completed grid or an incomplete grid with the possibilities that were not fulfilled.