Practice Backtracking and Brute-force with the exercise "Kakuro Solver"

Learning Opportunities

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

Statement

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   |

You can find here more information: https://en.wikipedia.org/wiki/Kakuro

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

Solve it

A higher resolution is required to access the IDE