Kakuro Solver

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

Tags

Grid, Combinatorics, Brute-force, Backtracking

Difficulty

Hard

Test cases

Example 1 (3 * 3) Test

Input

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

Output

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

Validator 1 (3 * 3) Validator

Input

3 3 | X | 8\ | 4\ | | \9 | | | | \3 | | |

Output

X,8\,4\ \9,6,3 \3,2,1

Test 2 (4 * 4) Test

Input

4 4 | X | 23\ | 9\ | 7\ | | \18 | | | | | \11 | | | | | \10 | | | |

Output

X,23\,9\,7\ \18,9,5,4 \11,8,1,2 \10,6,3,1

Validator 2 (4 * 4) Validator

Input

4 4 | X | 20\ | 17\ | 12\ | | \23 | | | | | \19 | | | | | \7 | | | |

Output

X,20\,17\,12\ \23,9,6,8 \19,7,9,3 \7,4,2,1

Test 3 (1 * 3) Test

Input

1 3 | \3 | | 2 |

Output

\3,1,2

Validator 3 (3 * 1) Validator

Input

3 1 | 7\ | | | | 3 |

Output

7\ 4 3

Example 2 (5 * 5) Test

Input

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

Output

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

Validator 4 (5 * 5) Validator

Input

5 5 | X | 17\ | 7\ | X | X | | \10 | | 2 | 24\ | X | | \18 | | | | 4\ | | X | \12 | | | | | X | X | \12 | | |

Output

X,17\,7\,X,X \10,8,2,24\,X \18,9,1,8,4\ X,\12,4,7,1 X,X,\12,9,3

Test 5 (9 * 8) Test

Input

9 8 | X | X | X | 11\ | 20\ | X | X | X | | X | 14\ | 29\15 | | | X | X | X | | \23 | | | | | 9\ | X | X | | \17 | | | 18\6 | | | 23\ | X | | X | \17 | | | \9 | | | X | | X | \15 | | | 13\15 | | | 10\ | | X | X | \5 | | | 5\11 | | | | X | X | X | \12 | | | | | | X | X | X | \7 | | | X | X |

Output

X,X,X,11\,20\,X,X,X X,14\,29\15,8,7,X,X,X \23,6,5,3,9,9\,X,X \17,8,9,18\6,4,2,23\,X X,\17,8,9,\9,1,8,X X,\15,7,8,13\15,6,9,10\ X,X,\5,1,4,5\11,4,7 X,X,X,\12,6,1,2,3 X,X,X,\7,3,4,X,X

Validator 5 (9 * 8) Validator

Input

9 8 | X | X | 44\ | 12\ | X | X | 38\ | 10\ | | X | \13 | | | 6\ | \16 | | | | X | 4\9 | | | | 11\5 | | | | \8 | | | \21 | | | | X | | \12 | | | 10\ | \5 | | | 11\ | | X | \9 | | | 17\ | \3 | | | | X | 3\15 | | | | 6\13 | | | | \9 | | | \16 | | | | X | | \8 | | | X | \10 | | | X |

Output

X,X,44\,12\,X,X,38\,10\ X,\13,5,8,6\,\16,9,7 X,4\9,3,4,2,11\5,2,3 \8,1,7,\21,4,9,8,X \12,3,9,10\,\5,2,3,11\ X,\9,2,7,17\,\3,1,2 X,3\15,4,3,8,6\13,4,9 \9,1,8,\16,9,2,5,X \8,2,6,X,\10,4,6,X

Test 6 (9 * 9) Test

Input

9 9 | X | X | 29\ | 15\ | X | 21\ | 5\ | X | X | | X | 16\3 | | | 6\3 | | | X | X | | \23 | | 6 | | | 2 | | 3\ | 4\ | | \31 | | | 3 | | | 10\4 | | | | X | 3\8 | | | 22\11 | | | | | | \25 | | 7 | | | 3 | | 4\ | X | | \5 | | | 3\13 | | | 2 | | X | | X | X | \8 | | | \4 | | | X | | X | X | \3 | | | X | X | X | X |

Output

X,X,29\,15\,X,21\,5\,X,X X,16\3,1,2,6\3,1,2,X,X \23,7,6,4,1,2,3,3\,4\ \31,9,8,3,5,6,10\4,1,3 X,3\8,3,5,22\11,5,3,2,1 \25,2,7,1,8,3,4,4\,X \5,1,4,3\13,6,4,2,1,X X,X,\8,1,7,\4,1,3,X X,X,\3,2,1,X,X,X,X

Validator 6 (9 * 9) Validator

Input

9 9 | X | X | 12\ | 23\ | X | 3\ | 26\ | X | X | | X | \4 | | | 10\10 | | | X | X | | X | 4\27 | | 9 | | | 5 | 14\ | X | | \16 | | 5 | | | 15\16 | | | 15\ | | \6 | | | | 15\10 | | 3 | | | | X | 3\ | 6\25 | | | 5 | | | | | \5 | | | 9\3 | | | \8 | | | | \15 | | | | 4 | | X | X | X | | X | \10 | | | | | X | X | X |

Output

X,X,12\,23\,X,3\,26\,X,X X,\4,1,3,10\10,2,8,X,X X,4\27,4,9,8,1,5,14\,X \16,1,5,8,2,15\16,9,7,15\ \6,3,2,1,15\10,4,3,1,2 X,3\,6\25,2,6,5,1,4,7 \5,2,3,9\3,2,1,\8,2,6 \15,1,2,5,4,3,X,X,X X,\10,1,4,3,2,X,X,X

Test 7 (12 * 10) Test

Input

12 10 | X | X | 12\ | 13\ | X | 9\ | 14\ | X | 28\ | 12\ | | X | 15\15 | | | 12\12 | | | \16 | | | | \22 | | | | | | | 16\4 | | | | \12 | | | 10\6 | | | 19\14 | | | | | X | X | 36\17 | | | 24\17 | | | | 3\ | | X | 17\7 | | | 19\16 | | | \5 | | | | \16 | | | \24 | | | | 4\3 | | | | \17 | | | 4\11 | | | 6\5 | | | X | | X | 18\12 | | | | 6\3 | | | 21\ | 8\ | | \6 | | | | 3\3 | | | 16\11 | | | | \10 | | | \29 | | | | | | | | \17 | | | \4 | | | \11 | | | X |

Output

X,X,12\,13\,X,9\,14\,X,28\,12\ X,15\15,6,9,12\12,3,9,\16,7,9 \22,7,2,4,3,1,5,16\4,3,1 \12,8,4,10\6,1,5,19\14,7,5,2 X,X,36\17,9,8,24\17,2,9,6,3\ X,17\7,6,1,19\16,7,9,\5,4,1 \16,9,7,\24,7,9,8,4\3,1,2 \17,8,9,4\11,3,8,6\5,3,2,X X,18\12,2,1,9,6\3,2,1,21\,8\ \6,2,1,3,3\3,2,1,16\11,9,2 \10,7,3,\29,2,1,3,9,8,6 \17,9,8,\4,1,3,\11,7,4,X

Validator 7 (12 * 10) Validator

Input

12 10 | X | 11\ | 12\ | X | X | 7\ | 10\ | X | 32\ | 16\ | | \17 | | | 27\ | \8 | | | \13 | | | | \7 | | | | 13\5 | | | 12\12 | | | | X | X | \6 | | | 12\15 | | | | X | | X | 23\ | 33\24 | | | | 15\4 | | | 23\ | | \22 | | | | 9\13 | | | 34\11 | | | | \29 | | | | | 5\30 | | | | | | \17 | | | 16\5 | | | 7\24 | | | | | X | \12 | | | 12\14 | | | | X | X | | X | 11\17 | | | | 14\5 | | | 7\ | 16\ | | \3 | | | \6 | | | \23 | | | | | \15 | | | \12 | | | X | \8 | | |

Output

X,11\,12\,X,X,7\,10\,X,32\,16\ \17,9,8,27\,\8,3,5,\13,6,7 \7,2,4,1,13\5,4,1,12\12,3,9 X,X,\6,2,4,12\15,4,9,2,X X,23\,33\24,8,9,7,15\4,3,1,23\ \22,6,7,9,9\13,5,8,34\11,5,6 \29,9,5,7,8,5\30,7,6,8,9 \17,8,9,16\5,1,4,7\24,9,7,8 X,\12,3,9,12\14,1,6,7,X,X X,11\17,2,7,8,14\5,1,4,7\,16\ \3,2,1,\6,1,5,\23,8,6,9 \15,9,6,\12,3,9,X,\8,1,7

Test 8 (18 * 10) Test

Input

18 10 | X | 20\ | 15\ | 11\ | X | X | 19\ | 8\ | X | X | | \6 | | | | X | 16\4 | | | 17\ | 7\ | | \19 | | | | 30\30 | | | | | | | \12 | | | 14\22 | | | | 12\10 | | | | X | \21 | | | | \10 | | | 23\ | 27\ | | X | 6\ | 23\17 | | | 9\ | 9\20 | | | | | \12 | | | \19 | | | | \17 | | | | \8 | | | 7\ | 14\3 | | | 21\16 | | | | X | \22 | | | | | 6\11 | | | | | X | 28\ | 10\12 | | | 14\8 | | | 10\ | X | | \13 | | | | 12\29 | | | | | 9\ | | \11 | | | \14 | | | 10\ | \8 | | | | \9 | | | 9\6 | | | | 4\4 | | | | \7 | | | | 10\ | \4 | | | 10\ | X | | X | 7\ | 15\12 | | | 5\7 | | | | 8\ | | \13 | | | 3\6 | | | | 6\3 | | | | \16 | | | | | | \12 | | | | | X | X | \4 | | | X | \7 | | | |

Output

X,20\,15\,11\,X,X,19\,8\,X,X \6,3,1,2,X,16\4,1,3,17\,7\ \19,8,2,9,30\30,9,2,5,8,6 \12,9,3,14\22,6,7,9,12\10,9,1 X,\21,9,5,7,\10,7,3,23\,27\ X,6\,23\17,9,8,9\,9\20,9,5,6 \12,4,8,\19,9,3,7,\17,9,8 \8,2,6,7\,14\3,1,2,21\16,7,9 X,\22,9,2,6,5,6\11,5,2,4 X,28\,10\12,4,8,14\8,1,7,10\,X \13,9,3,1,12\29,8,5,9,7,9\ \11,7,4,\14,9,5,10\,\8,2,6 \9,8,1,9\6,3,1,2,4\4,1,3 \7,4,2,1,10\,\4,1,3,10\,X X,7\,15\12,8,4,5\7,4,1,2,8\ \13,4,9,3\6,2,1,3,6\3,1,2 \16,3,6,2,1,4,\12,4,3,5 X,X,\4,1,3,X,\7,2,4,1

Validator 8 (18 * 10) Validator

Input

18 10 | X | X | 42\ | 4\ | X | X | 11\ | 5\ | X | X | | X | \4 | | | 8\ | \13 | | | 42\ | X | | X | 17\6 | | | | 8\11 | | | | 9\ | | \14 | | | \8 | | | 22\ | \6 | | | | \16 | | | 16\ | \11 | | | 17\16 | | | | X | \12 | | | 3\ | \23 | | | | X | | X | 14\18 | | | | 10\21 | | | | 5\ | | \17 | | | 6\8 | | | 4\ | \7 | | | | \15 | | | | 12\7 | | | 10\8 | | | | X | 11\ | 30\10 | | | 4\8 | | | 36\ | 3\ | | \16 | | | \4 | | | 11\6 | | | | | \3 | | | 9\ | 8\5 | | | 3\4 | | | | X | \19 | | | | \12 | | | | X | | X | 10\6 | | | | 4\ | \9 | | | 12\ | | \4 | | | \3 | | | 10\ | \7 | | | | \14 | | | 9\ | 12\5 | | | 10\17 | | | | X | \20 | | | | \14 | | | | X | | X | X | \5 | | | X | \15 | | | X |

Output

X,X,42\,4\,X,X,11\,5\,X,X X,\4,1,3,8\,\13,9,4,42\,X X,17\6,2,1,3,8\11,2,1,8,9\ \14,8,6,\8,5,3,22\,\6,4,2 \16,9,7,16\,\11,5,6,17\16,9,7 X,\12,5,7,3\,\23,9,8,6,X X,14\18,8,9,1,10\21,7,9,5,5\ \17,8,9,6\8,2,6,4\,\7,3,4 \15,6,4,5,12\7,4,3,10\8,7,1 X,11\,30\10,1,9,4\8,1,7,36\,3\ \16,9,7,\4,3,1,11\6,3,1,2 \3,2,1,9\,8\5,3,2,3\4,3,1 X,\19,8,6,5,\12,9,1,2,X X,10\6,2,3,1,4\,\9,2,7,12\ \4,1,3,\3,2,1,10\,\7,4,3 \14,9,5,9\,12\5,3,2,10\17,8,9 X,\20,4,7,9,\14,8,1,5,X X,X,\5,2,3,X,\15,9,6,X

Test 9 (15 * 15) Test

Input

15 15 | X | X | X | X | 16\ | 10\ | X | X | X | 3\ | 16\ | X | X | X | X | | X | 17\ | 3\ | \10 | | | X | X | \9 | | | 24\ | 16\ | X | X | | \11 | | | 6\13 | | | 7\ | X | \25 | | | | | X | X | | \12 | | | | 23\3 | | | X | X | X | 4\16 | | | X | X | | X | X | 29\13 | | | | | 16\ | X | 29\10 | | | X | X | X | | X | 4\17 | | | | 3\9 | | | 3\8 | | | 16\ | 3\ | X | X | | \6 | | | \9 | | | 11\17 | | | | \10 | | | 10\ | X | | \12 | | | 16\ | 3\3 | | | 17\10 | | | 4\10 | | | | 17\ | | X | \19 | | | | \13 | | | 4\10 | | | 7\ | \10 | | | | X | X | \8 | | | 3\14 | | | | 23\7 | | | 23\13 | | | | X | X | X | X | 6\4 | | | \9 | | | 29\13 | | | | X | | X | X | X | 16\3 | | | X | X | \23 | | | | | 4\ | 16\ | | X | X | \10 | | | 16\ | 4\ | X | \14 | | | 3\17 | | | | | X | X | \21 | | | | | X | X | \7 | | | \12 | | | | X | X | X | X | \10 | | | X | X | \10 | | | X | X | X |

Output

X,X,X,X,16\,10\,X,X,X,3\,16\,X,X,X,X X,17\,3\,\10,7,3,X,X,\9,2,7,24\,16\,X,X \11,9,2,6\13,9,4,7\,X,\25,1,9,8,7,X,X \12,8,1,3,23\3,2,1,X,X,X,4\16,7,9,X,X X,X,29\13,2,6,1,4,16\,X,29\10,1,9,X,X,X X,4\17,7,1,9,3\9,2,7,3\8,5,3,16\,3\,X,X \6,1,5,\9,8,1,11\17,9,1,7,\10,9,1,10\,X \12,3,9,16\,3\3,2,1,17\10,2,8,4\10,7,2,1,17\ X,\19,8,9,2,\13,5,8,4\10,9,1,7\,\10,2,8 X,X,\8,7,1,3\14,2,9,3,23\7,3,4,23\13,4,9 X,X,X,X,6\4,1,3,\9,1,8,29\13,2,8,3,X X,X,X,16\3,1,2,X,X,\23,9,7,1,6,4\,16\ X,X,\10,7,3,16\,4\,X,\14,6,8,3\17,9,1,7 X,X,\21,9,2,7,3,X,X,\7,5,2,\12,3,9 X,X,X,X,\10,9,1,X,X,\10,9,1,X,X,X

Validator 9 (15 * 15) Validator

Input

15 15 | X | X | X | 16\ | 3\ | X | X | X | X | X | X | 42\ | 6\ | X | X | | X | 16\ | 6\9 | | | 23\ | 10\ | X | 17\ | 7\ | \8 | | | X | X | | \30 | | | | | | | \11 | | | \6 | | | X | X | | \10 | | | 24\ | \8 | | | \9 | | | 3\10 | | | X | X | | X | \12 | | | 17\10 | | | 3\ | 16\9 | | | | X | X | X | | X | X | \15 | | | 6\15 | | | | 6\8 | | | 3\ | X | X | | X | X | \19 | | | | 23\11 | | | | 7\7 | | | X | X | | X | X | X | 17\ | 28\9 | | | X | \15 | | | | | X | X | | X | X | \18 | | | | | 16\ | 4\3 | | | 17\ | 24\ | X | X | | X | X | \11 | | | 3\17 | | | | 30\17 | | | | X | X | | X | X | X | \8 | | | 7\19 | | | | 7\17 | | | 7\ | X | | X | X | X | 7\7 | | | | 17\ | \9 | | | \10 | | | 16\ | | X | X | \5 | | | \11 | | | \10 | | | 4\ | 3\11 | | | | X | X | \7 | | | \12 | | | \26 | | | | | | | | X | X | \9 | | | X | X | X | X | X | \3 | | | X | X |

Output

X,X,X,16\,3\,X,X,X,X,X,X,42\,6\,X,X X,16\,6\9,7,2,23\,10\,X,17\,7\,\8,5,3,X,X \30,7,2,9,1,8,3,\11,9,2,\6,4,2,X,X \10,9,1,24\,\8,6,2,\9,8,1,3\10,9,1,X,X X,\12,3,9,17\10,9,1,3\,16\9,4,2,3,X,X,X X,X,\15,7,8,6\15,4,2,9,6\8,1,7,3\,X,X X,X,\19,8,9,2,23\11,1,7,3,7\7,6,1,X,X X,X,X,17\,28\9,1,8,X,\15,1,4,8,2,X,X X,X,\18,8,1,3,6,16\,4\3,2,1,17\,24\,X,X X,X,\11,9,2,3\17,9,7,1,30\17,2,8,7,X,X X,X,X,\8,7,1,7\19,9,3,7,7\17,9,8,7\,X X,X,X,7\7,4,2,1,17\,\9,8,1,\10,9,1,16\ X,X,\5,2,3,\11,2,9,\10,6,4,4\,3\11,2,9 X,X,\7,1,6,\12,4,8,\26,9,2,3,1,4,7 X,X,\9,4,5,X,X,X,X,X,\3,1,2,X,X

Test 10 (7 * 7) Test

Input

7 7 | X | X | 9\ | 39\ | 21\ | 7\ | X | | X | 3\22 | | | | | X | | \18 | | | | | | X | | X | | 6\10 | | | | 3\ | | X | \9 | | | | 4\ | | | X | \15 | | | | | | | X | \14 | | | | | X |

Output

X,X,9\,39\,21\,7\,X X,3\22,7,9,5,1,X \18,1,2,8,3,4,X X,2,6\10,7,1,2,3\ X,\9,1,6,2,4\,2 X,\15,2,5,4,3,1 X,\14,3,4,6,1,X

Validator 10 (7 * 7) Validator

Input

7 7 | X | X | 38\ | X | 28\ | 35\ | X | | X | 24\ | | \17 | | | X | | \17 | | | 26\15 | | | 6\ | | \36 | | | | | | | | \32 | | | | | | | | X | \5 | | | \5 | | | | X | \12 | | | X | | X |

Output

X,X,38\,X,28\,35\,X X,24\,9,\17,9,8,X \17,9,8,26\15,8,7,6\ \36,8,7,9,6,5,1 \32,7,6,8,5,4,2 X,\5,3,2,\5,2,3 X,\12,5,7,X,9,X

Solution language

Solution

Stub generator input

Rate this contribution

+19

Make the contribution public (lvl 20+)

Comments

38 Comments

field3 Unnamed CodinGamer

over 3 years ago

✅ Approved the contribution. Comment: Because it's a good problem.

Q12 Unnamed CodinGamer

over 3 years ago

Thank you very much!!

Cpt.Illidan Unnamed CodinGamer

over 3 years ago

nice puzzle

Q12 Unnamed CodinGamer

over 3 years ago

Thanks

AdithShekharGatty Unnamed CodinGamer

over 3 years ago

Keep it up

Q12 Unnamed CodinGamer

over 3 years ago

Thanks!

Xophe Unnamed CodinGamer

over 3 years ago

Why is the input format not the same as the output format ? It would be far easier to parse, as I don't think the objective of this challenge is to write a parser.

Q12 Unnamed CodinGamer

over 3 years ago

First, thanks for your comment. Second, part of the challenge is the parsing part, I agree that it is not the big part of the puzzle. Third, in the start I made the output format same to the format of the input but because of the limit of maximum letters in the output's test cases and the fact that I wanted to increase the puzzle size I had to change the format of the output's test cases. I keep the the input format as before because there is no problem with the limit of the letters and I think that this format helps the solvers to understand the Kakuro better, it is look like real Kakuro puzzle.

Typingspeed Unnamed CodinGamer

over 3 years ago

Nice post. I found this is an informative and interesting post, so i think it is very useful and knowledgeable. I am glad to read this post hope your next article is are so useful for me so you are meet in next process for more information click this link below :- https://www.typingspeedtestonline.com/ https://www.digitalindiagov.in/

Clafrelie Unnamed CodinGamer

over 3 years ago

✅ Approved the contribution. Comment: The difficulty could be discussed but the puzzle is nice and interesting

Q12 Unnamed CodinGamer

over 3 years ago

Thanks!

6po Unnamed CodinGamer

over 3 years ago

Nice puzzle but very similar to the Futoshiki one (which is a medium one).

Q12 Unnamed CodinGamer

over 3 years ago

Thanks :slight_smile: Sudoku is similar to Futoshiki but still different from him in few ways, like: you need to use combinatorics, you are using sums to find the right numbers (in Futoshiki you use "greater than" sign or "lesser than" sign). I also agree they are pretty similar - they both use brute force and backtraking.

roma_roma Unnamed CodinGamer

over 3 years ago

Cool puzzle!

Q12 Unnamed CodinGamer

over 3 years ago

Thanks!

Djoums Unnamed CodinGamer

over 3 years ago

✅ Approved the contribution. Comment: Good introduction to contraint solving, can be solved in several ways. (I fixed some text in the description before approving, feel free to change anything you don't like)

Q12 Unnamed CodinGamer

over 3 years ago

Thanks a lot for all your great help :grinning: I appreciate it :slight_smile:

Djoums Unnamed CodinGamer

over 3 years ago

I think you should briefly add what X/ and /X mean as cells, you jump right into an example without explaining what they are. Getting back to my previous post, I think this should be a hard puzzle only, because backtracking can solve every example fairly easily (as we saw together). Imo a very hard version would require the user to go into proper constraints solving, using matrix reduction for example. A good example of that is the haunted manor : https://www.codingame.com/... (check it out if you haven't, it's a great puzzle :))

Q12 Unnamed CodinGamer

over 3 years ago

Thank you for all your help :slight_smile: I will change the difficulty of the puzzle to Hard and I will make an explanation about what you said.

Q12 Unnamed CodinGamer

over 3 years ago

Hi ViktorCs and Gevater_Tod4711 I thought about what you said more and decided to change the output format.

ViktorCs Unnamed CodinGamer

over 3 years ago

I agree with Gevater_Tod4711, the output formatting is a bit too much. It even could be an easy puzzle in itself.

Q12 Unnamed CodinGamer

over 3 years ago

You just need to put '| cell |', and make sure that the cell has the same length as the longest cell in the kakuro grid, if he has not then add spaces to the left of it until it does. I don't want to do what Gevater_Tod4711 suggested because its look nicer in the current way and if someone wants to know what is the solution to this kakuro then it would be a lot easier to him to understand the solution in this way, also, this is part of why the puzzle is *Very Hard* :slight_smile:

Djoums Unnamed CodinGamer

over 3 years ago

I haven't tried it yet, but I'm wondering if brute force would work here, the search space doesn't seem very large (ofc I could be wrong :D). But it it does then I would lower the difficulty.

Q12 Unnamed CodinGamer

over 3 years ago

I add one more test case with a bigger board. I can't create a bigger board than 12 * 10 because my algorithm isn't fast enough. I checked what you said and I did just brute force after combining in each cell the possibilities and it couldn't pass the last validator, so I think the board is big enough so people would need to do more then just brute force. If you can do brute force that will pass all the tests cases I would love to know how you did it and maybe I will do it also which will allow me to create a test case with even bigger board so nobody will be able to pass the puzzle with just brute force :relaxed:

Tux4711 Unnamed CodinGamer

over 3 years ago

Cool puzzle :) An improvement could be to use an easier formatting for the output numbers (like CSV), so the focus is more on the puzzle instead of formatting the output correctly.

Q12 Unnamed CodinGamer

over 3 years ago

Thank you :grinning: I also thought about that but I wanted it to look like a real kakuro puzzle. I agree with you about that I need to change the way the output should be shown because it is too hard to show the output in this way. Maybe something like this (output example 1): -1 9\ 11\ \17 8 9 \3 1 2 (one space between each cell) Can you give me an example for how do you think it should look like? I would love to see it :slight_smile:

Q12 Unnamed CodinGamer

over 3 years ago

Hi I would like to hear your feedback :grinning:

ABOUT US CAREERS PRIVACY FAQ BLOG

The #1 tech hiring platform

SCREENING INTERVIEWING