I have tried to make an algorithm that finds all possible combinations of single-digit summands for a number. After an afternoon of hard and desperate work I got something inefficient (although it works). Maybe someone has a better idea. The link to the algorithm: http://secam.blogspot.com/2005/12/solving-kakuro-part-i.html

on 2005-12-12 00:00

on 2005-12-12 02:54

Would you like to add some asserts, so I can figure out the specification? How is the data entered? Christer

on 2005-12-12 19:06

This is a newer algorithm which works much more faster. def sum (arr) # sorry James Edward G. II, but I'm not using an enum. i = 0 arr.each do |k| i += k end i end def arr (depth, min=1, max=10-depth,t=[], arr=[]) (min..max).each do |i| t[depth-1] = i if depth > 0 arr(depth-1, i+1, max+1, t, arr) if depth > 1 arr << t.reverse.clone if depth == 1 end arr end def calc (number, depth) arri = arr(depth) arri.each do |a| arri.delete_if { |a| sum(a) != number } end arri end # examples calc(24, 3).each do |a| print "#{a} - " end puts calc(24, 4).each do |a| print "#{a} - " end puts # even summands of 45 can be calculated now. It was impossible with the older algorithm. calc(45, 9).each do |a| print "#{a} - " end puts

on 2005-12-12 19:12

```
Hi --
On Tue, 13 Dec 2005, draq wrote:
> arr << t.reverse.clone if depth == 1
I haven't been following this thread closely but just an observation:
Array#reverse gives you a new array, so you don't need to clone it.
David
--
David A. Black
removed_email_address@domain.invalid
"Ruby for Rails", forthcoming from Manning Publications, April 2006!
```

on 2005-12-12 20:46

On Dec 12, 2005, at 11:02 AM, draq wrote: > This is a newer algorithm which works much more faster. > > def sum (arr) > # sorry James Edward G. II, but I'm not using an enum. You don't think so? Let's ask Ruby... >> Array.ancestors.find { |par| par.to_s =~ /enum/i } => Enumerable >> arr = Array.new => [] >> arr.is_a? Enumerable => true >> arr.respond_to? :inject => true Ruby thinks so. Let's try a sum: >> arr = (1..10).to_a => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >> arr.inject { |sum, n| sum + n } => 55 Looks good to me. > arri.each do |a| > arri.delete_if { |a| sum(a) != number } > end The whole point of delete_if() is that you don't need the each(). Try taking it out. ;) James Edward G. II

on 2005-12-12 21:08

Since only single digit summands are under consideration, I don't think optimizations are important for this. Here's a simple brute force approach that performs reasonably well. It considers all possible subsets of [1,2,3,4,5,6,7,8,9] and rejects any with the wrong depth or sum. For this solution I reused the powerset method I wrote for a recent Ruby Q.. class Array def sum inject { |sum,x| sum += x } end def powerset for element_map in 0...(1 << self.length) do subset = [] each_with_index do |element, index| subset << element if element_map[index] == 1 end yield subset end end end def calc(number, depth) puts "number = #{number}, depth = #{depth}" candidates = (1..9).inject([]) { |a,x| a << x } candidates.powerset { |subset| next unless subset.length == depth next unless subset.sum == number p subset } end # examples (3..5).each { |depth| (10..20).each { |target| calc(target, depth) } }

on 2005-12-12 21:22

draq, Array mixes in Enumerable, so inject works. I added some asserts to be able to understand what your code does. As I can see, this solves only a partial problem: generating all combinations, given a sum and number of squares. This is calc(sum, count). Next step would probably be intersection(sum1, count1, sum2, count2) between a row and a column, listing the possible combinations. Curiousity: The list for arr(2) below, was too long. So I decided to cut it by writing a method for Array. Then I found it's already defined! First accepts zero or one argument. Defining a kakuro, so a program can solve it, seems to be a lot more hassle than defining a sudoku. Christer def sum (arr) arr.inject { |sum,i| sum += i } end def arr (depth, min=1, max=10-depth,t=[], arr=[]) (min..max).each do |i| t[depth-1] = i if depth > 0 arr(depth-1, i+1, max+1, t, arr) if depth > 1 arr << t.reverse.clone if depth == 1 end arr end def calc (number, depth) arri = arr(depth) arri.each do |a| arri.delete_if { |a| sum(a) != number } end arri end require 'test/unit' class TestKakuro < Test::Unit::TestCase def test_all assert_equal 12, sum([3,4,5]) assert_equal [[1, 2], [1, 3], [1, 4], [1, 5], [1, 6], [1, 7], [1, 8], [1, 9], [2, 3], [2, 4]], arr(2).first(10) assert_equal 9, arr(1).size assert_equal 36, arr(2).size assert_equal 84, arr(3).size assert_equal 126, arr(4).size assert_equal 126, arr(5).size assert_equal 84, arr(6).size assert_equal 36, arr(7).size assert_equal 9, arr(8).size assert_equal 1, arr(9).size assert_equal [[7, 8, 9]], calc(24,3) assert_equal [[1, 6, 8, 9],[2, 5, 8, 9], [2, 6, 7, 9],[3, 4, 8, 9], [3, 5, 7, 9],[3, 6, 7, 8], [4, 5, 6, 9],[4, 5, 7, 8]], calc(24, 4) assert_equal [[1, 2, 3, 4, 5, 6, 7, 8, 9]], calc(45, 9) end end

on 2005-12-13 19:24

Hello Christer, I don't see the problem. The list of arr(2) seems to be right. The numbers are [1,2] - [1,3] - [1,4] - [1,5] - [1,6] - [1,7] - [1,8] - [1,9] - [2,3] - [2,4] - [2,5] - [2,6] - [2,7] - [2,8] - [2,9] - [3,4] - [3,5] - [3,6] - [3,7] - [3,8] - [3,9] - [4,5] - [4,6] - [4,7] - [4,8] - [4,9] - [5,6] - [5,7] - [5,8] - [5,9] - [6,7] - [6,8] - [6,9] - [7,8] - [7,9] - [8,9]. I beg pardon for my lousy comments. I've tried to improve. You'll find the newest code at http://secam.blogspot.com/2005/12/solving-kakuro-p... Hopefully it's now better understandable.

on 2005-12-13 19:27

draq wrote: > Hello Christer, > > I don't see the problem. The list of arr(2) seems to be right. The > numbers are [1,2] - [1,3] - [1,4] - [1,5] - [1,6] - [1,7] - [1,8] - > [1,9] - [2,3] - [2,4] - [2,5] - [2,6] - [2,7] - [2,8] - [2,9] - [3,4] - > [3,5] - [3,6] - [3,7] - [3,8] - [3,9] - [4,5] - [4,6] - [4,7] - [4,8] - > [4,9] - [5,6] - [5,7] - [5,8] - [5,9] - [6,7] - [6,8] - [6,9] - [7,8] - > [7,9] - [8,9]. > > I beg pardon for my lousy comments. I've tried to improve. You'll find > the newest code at > http://secam.blogspot.com/2005/12/solving-kakuro-p... > Hopefully it's now better understandable. draq, I was using first(10) to keep the output short. Your code is working. Sorry about being unclear. christer