marcelgarus / kakuro

Kakuro solver

Kakuros are cool puzzles. This repo contains several solvers with different strategies.

Measurements

I conducted ten measurements for each value with prior warm-up.

todo = Not measured yet
oom = Out of memory and killed by the operating system
timeout = Took longer than 30 minutes

solver	small	wikipedia	15x15	20x20	30x30	book
naive	todo	todo	todo	todo	todo	todo
gradual	todo	todo	todo	todo	todo	todo
sum_reachable	todo	todo	todo	todo	todo	todo
prioritize	1.23 ms	376.48 ms	466.87 ms	364.07 s	timeout	todo
sum_reachable_no_set	335.41 us	5.12 ms	20.43 ms	208.78 ms	14.06 s	20.56 s
only_check_changes	170.99 us	792.26 us	2.18 ms	9.70 ms	595.41 ms	1.41 s
divide	23.48 us	1.55 ms	8.13 ms	143.76 ms	6.24 s	oom
connecting_cells	29.79 us	833.63 us	4.62 ms	18.25 ms	313.25 ms	oom
lazy	46.41 us	1.47 ms	7.63 ms	68.32 ms	10.46 s	oom
propagate_constraints	155.90 us	1.34 ms	8.05 ms	37.12 ms	oom	1.12 s
solution_in_rc	61.72 us	778.51 us	6.57 ms	33.40 ms	oom	193.86 ms
simpler_recursion_anchor	45.99 us	681.29 us	5.68 ms	28.64 ms	oom	178.51 ms
fxhashmap	39.12 us	641.78 us	5.35 ms	27.49 ms	oom	142.74 ms
better_vecs	34.61 us	597.71 us	5.75 ms	32.85 ms	oom	88.97 ms

Raw measurements

The values are median with standard deviation, as well as minimum and maximum.

• naive
  • small: todo
  • wikipedia: todo
  • 15x15: todo
  • 20x20: todo
  • 30x30: todo
  • book: todo
• gradual
  • small: todo
  • wikipedia: todo
  • 15x15: todo
  • 20x20: todo
  • 30x30: todo
  • book: todo
• sum_reachable
  • small: todo
  • wikipedia: todo
  • 15x15: todo
  • 20x20: todo
  • 30x30: todo
  • book: todo
• prioritize
  • small: 1.23 ms +- 0.64 %; 1.22 ms – 1.24 ms
  • wikipedia: 376.48 ms +- 0.23 %; 374.88 ms – 377.45 ms
  • 15x15: 466.87 ms +- 0.11 %; 465.69 ms – 467.73 ms
  • 20x20: 364.07 s +- 0.50 %; 360.01 s – 366.62 s
  • 30x30: >35 min
  • book: todo
• sum_reachable_no_set
  • small: 335.41 us +- 0.49 %; 333.95 us – 339.22 us
  • wikipedia: 5.12 ms +- 0.17 %; 5.10 ms – 5.13 ms
  • 15x15: 20.43 ms +- 2.91 %; 20.16 ms – 22.17 ms
  • 20x20: 208.78 ms +- 0.19 %; 208.28 ms – 209.42 ms
  • 30x30: 14.06 s +- 0.69 %; 13.98 s – 14.22 s
  • book: 20.56 s +- 1.00 %; 20.12 s - 20.79 s
• only_check_changes
  • small: 170.99 us +- 0.78 %; 169.85 us - 173.50 us
  • wikipedia: 792.26 us +- 10.94 %; 758.90 us - 1.05 ms
  • 15x15: 2.18 ms +- 4.99 %; 2.11 ms - 2.43 ms
  • 20x20: 9.70 ms +- 1.28 %; 9.55 ms - 9.96 ms
  • 30x30: 595.41 ms +- 0.84 %; 588.83 ms - 608.70 ms
  • book: 1.41 s +- 1.11 %; 1.38 s - 1.42 s
• divide
  • small: 23.48 us +- 8.30 %; 22.31 us – 28.99 us
  • wikipedia: 1.55 ms +- 0.84 %; 1.53 ms – 1.58 ms
  • 15x15: 8.13 ms +- 0.34 %; 8.10 ms – 8.18 ms
  • 20x20: 143.76 ms +- 1.01 %; 142.05 ms – 147.75 ms
  • 30x30: 6.24 s +- 1.02 %; 6.18 s – 6.36 s
  • book: oom
• connecting_cells
  • small: 29.79 us +- 6.25 %; 28.69 us – 34.81 us
  • wikipedia: 833.63 us +- 0.84 %; 822.23 us – 846.14 us
  • 15x15: 4.62 ms +- 0.53 %; 4.59 ms – 4.66 ms
  • 20x20: 18.25 ms +- 0.29 %; 18.19 ms – 18.38 ms
  • 30x30: 313.25 ms +- 0.85 %; 309.63 ms – 317.18 ms
  • book: oom
• lazy
  • small: 46.41 us +- 6.93 %; 43.21 us – 54.47 us
  • wikipedia: 1.47 ms +- 1.40 %; 1.45 ms – 1.52 ms
  • 15x15: 7.63 ms +- 1.29 %; 7.49 ms – 7.87 ms
  • 20x20: 68.32 ms +- 4.33 %; 64.57 ms – 74.80 ms
  • 30x30: 10.46 s +- 1.89 %; 9.96 s – 10.70 s
  • book: oom
• propagate_constraints
  • small: 155.90 us +- 3.30 %; 151.01 us – 166.42 us
  • wikipedia: 1.34 ms +- 3.23 %; 1.31 ms – 1.47 ms
  • 15x15: 8.05 ms +- 0.56 %; 7.99 ms – 8.14 ms
  • 20x20: 37.12 ms +- 2.45 %; 36.11 ms – 38.90 ms
  • 30x30: oom
  • book: 1.12 s +- 0.79 %; 1.10 s – 1.13 s
• solution_in_rc
  • small: 61.72 us +- 6.56 %; 56.98 us – 71.14 us
  • wikipedia: 778.51 us +- 1.55 %; 766.99 us – 803.07 us
  • 15x15: 6.57 ms +- 0.27 %; 6.53 ms – 6.60 ms
  • 20x20: 33.40 ms +- 0.69 %; 33.12 ms – 33.77 ms
  • 30x30: oom
  • book: 193.86 ms +- 4.22 %; 186.47 ms - 210.47 ms
• simpler_recursion_anchor
  • small: 45.99 us +- 7.82 %; 42.07 us – 55.11 us
  • wikipedia: 681.29 us +- 1.75 %; 669.13 us – 711.74 us
  • 15x15: 5.68 ms +- 0.49 %; 5.65 ms – 5.75 ms
  • 20x20: 28.64 ms +- 0.48 %; 28.44 ms – 28.82 ms
  • 30x30: oom
  • book: 178.51 ms +- 0.33 %; 177.46 ms - 179.62 ms
• fxhashmap
  • small: 39.12 us +- 10.26 %; 36.28 us – 49.70 us
  • wikipedia: 641.78 us +- 1.94 %; 630.47 us – 675.82 us
  • 15x15: 5.35 ms +- 0.80 %; 5.29 ms – 5.41 ms
  • 20x20: 27.49 ms +- 0.67 %; 27.20 ms – 27.81 ms
  • 30x30: oom
  • book: 142.74 ms +- 1.42 %; 140.26 ms – 146.90 ms
• better_vecs
  • small: 34.61 us +- 8.17 %; 31.95 us – 41.03 us
  • wikipedia: 597.71 us +- 2.06 %; 585.46 us – 631.27 us
  • 15x15: 5.75 ms +- 0.45 %; 5.73 ms – 5.80 ms
  • 20x20: 32.85 ms +- 0.31 %; 32.75 ms – 33.04 ms
  • 30x30: oom
  • book: 88.97 ms +- 1.18 %; 87.35 ms - 91.70 ms

Todo

• re-do benchmarks
• investigate oom -> endless recursive loop?
• invent new solvers