[Community Puzzle] Kakuro Solver

https://www.codingame.com/training/hard/kakuro-solver

Send your feedback or ask for help here!

Created by @Q12,validated by @Djoums,@Clafrelie and @field3.
If you have any issues, feel free to ping them.

Hm… I have everything working except Validator 5, and no idea why that single case is failing with no feedback. Test 5 works ok.

This is Validator 5 input and output:
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

Hope this will help you.

2 Likes

Excellent! That helped! I had a slight bug that would sometimes allow incorrect sums. 100% now!

Thanks!

And cool puzzle by the way!

1 Like

Glad that helped you and thanks for your comment!

i had issues with validator 5 and 8.
using your inputs above helped me to fix the last bug, and now everything is OK :slight_smile:
l liked the puzzle. it deserved its place in the puzzle of the week.

1 Like

Interesting puzzle. I personnaly have issue with validator 3 (3x1) and 4 (5x5) while I validate all the other ones.
I checked from my side that the specials cases of 3x1 and 1x3 are working for many different cases and it seems to work fine, so i am a bit stuck here…

Here is similar test case to validator 3:
input:

3 1
|  9\   |
|       |
|   4   |

output:

9\
5
4

Try to use it, this should help.

2 Likes

Thanks Q12 ! Was also a strange unexpected bug. This helped me fix it, and passed the two last missing validators

1 Like

Hi! Thank you for a great puzzle.
It seems none of the test-cases (including hidden ones that determine your score) require any guesswork beyond the single-sum level. I managed to get 100% with an algorithm equivalent to this (only more optimized):
SPOILERS AHEAD

  1. Parse the board into a matrix of cells, and a vector of sequences - each sequence being a vector of ptrs to cells + a target sum.
  2. Initialize every cell with every possibility, 1…9
  3. For each sequence, use backtracking to find every possible sequence of values that can make it up. Update the sequence cells’ possibilities accordingly.
  4. Repeat step 3 as long as it has an effect.

This algorithm can’t solve every Kakuro board! Some require the effects of guesses to cascade between sequences before deciding which guess is correct. For example: Kakuro Puzzles - Free Hard Kakuro for 20/June/2007
You might want to add some harder test-cases to force a complete solution.

2 Likes

Hi koorkevani, glad to hear you like the puzzle!
My algorithm for solving the puzzle must be different from you, because I was able to solve the Kakuro puzzle example you gave: Kakuro Puzzles - Free Hard Kakuro for 20/June/2007.

From your comment I understand that my puzzle can be solved without having the ability to solve the Kakuro example puzzle you gave (and others), therefore I add it as a test case.

Thank you for your comment!!

3 Likes

I love this puzzle very much!!! I only have issue with validator 10 (7*7). Do anyone know the input and output of validator 10?

1 Like

Nice to hear!!
Here is validator 10 (7 * 7) input and output:
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
2 Likes