[Community Puzzle] Kakuro Solver

Puzzles
#1

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.

#2

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

#3

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
#4

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
#5

Glad that helped you and thanks for your comment!

#6

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

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…

#8

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
#9

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

1 Like
#10

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
#11

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
#12

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
#13

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
#14

Excellent puzzle Q12!. What’s the best time you got for the Test 10 (7 x 7). The best I could do was 39 milliseconds (in C#). Looking for further optimizations, but not sure if I can find any.

1 Like
#15

Glad you like it! my best time for Test 10 (7 x 7) is (in average) 47 milliseconds, in JavaScript. I think I could lower this down by 1 or 2 milliseconds because I am pushing a lot into lists which wasting a lot of time (and the fact I am using list).