• 38

## Learning Opportunities

This puzzle can be solved using the following concepts. Practice using these concepts and improve your skills.

## Goal

Kakuro puzzles are similar to crosswords, but use digits (from 1 to 9) instead of letters.

Rules :
- All empty cells need to be filled in with digits, in such a way that all the given sums are respected.
- You are not allowed to use the same digit more than once to obtain a given sum.

Notation :
- 'X' : represents a cell that you don't need to fill.
- Empty cell : represents a cell that you need to fill with a digit (1 - 9).
- Cell with digit : the given digit is part of the solution, don't change it.
- Cell with backslash : the required sum of the corresponding cells.
- X\ : the vertical sum X of the cells downwards,
- \X : the horizontal sum X of the cells to the right,
- X\Y : the vertical sum X of the cells downwards, and the horizontal sum Y of the cells to the right.

Each Kakuro puzzle has an unique solution. Good luck!

Example 1:
height = 3, width = 3

|   X  |  9\  |  11\  |
| \17 | | |
| \3 | | |

For the horizontal sum to be 3 in the second row, we have 2 options: (2, 1) and (1, 2).
For the vertical sum to be 11 in the second column, we have 8 options: (9, 2), (2, 9), (8, 3), (3, 8), (7, 4), (4, 7), (6, 5) or (5, 6).
If we combine those options we find that the value in the bottom right cell has to be 2.

|   X  |  9\  |  11\  |
| \17 | | |
| \3 | | 2 |

Since 2 is now fixed, we can deduce the value of its neighbors : 11 - 2 = 9, and 3 - 2 = 1.

|   X  |  9\  |  11\  |
| \17 | | 9 |
| \3 | 1 | 2 |

Finally we can deduce the last value in the same way : 9 - 1 = 8, or 17 - 9 = 8.

So the solution is:

|   X  |  9\  |  11\  |
| \17 | 8 | 9 |
| \3 | 1 | 2 |

Example 2:
height = 5, width = 5

|  X   | 17\  | 6\   |   X   |  X   |
| \9 | 8 | | 24\ | X |
| \20 | | | | 4\ |
| X | \14 | | | |
| X | X | \8 | | |

In this kakuro grid we have a given digit, 8, which means it's part of the solution and we can use it to solve the puzzle.
Substracting 8 from the vertical sum 17, we get 9 as the cell value beneath it.
Substracting 8 from the horizontal sum 9, we get 1 as the cell value to the right.

|  X   | 17\  | 6\   |   X   |  X   |
| \9 | 8 | 1 | 24\ | X |
| \20 | 9 | | | 4\ |
| X | \14 | | | |
| X | X | \8 | | |

Now by combining our options in each cell like we did in example 1, and using some guess work, we find that the solution is :

|  X   | 17\  | 6\   |   X   |  X   |
| \9 | 8 | 1 | 24\ | X |
| \20 | 9 | 3 | 8 | 4\ |
| X | \14 | 2 | 9 | 3 |
| X | X | \8 | 7 | 1 |

Thanks to Djoums that helped me with the puzzle.
Input
Line 1: integer height, integer width
Next height lines: string line
Output
The kakuro grid with comma between cells.
Constraints
Sums are natural numbers (positive and integer)
1 <= height <= 18
1 <= width <= 15
Example
Input
3 3
|   X   |   9\  |  11\  |
|  \17  |       |       |
|  \3   |       |       |
Output
X,9\,11\
\17,8,9
\3,1,2

A higher resolution is required to access the IDE