- 39

## 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**string

`height`lines:`line`

Output

The kakuro grid with comma between cells.

Constraints

Sums are natural numbers (positive and integer)

1 <=

1 <=

1 <=

`height`<= 181 <=

`width`<= 15Example

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