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

# Calculating single-digit summands

On 11 Dec 2005 13:53:28 -0800, “draq” [email protected] wrote:

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

I don’t understand the rules of the game from your writeup.

On Dec 11, 2005, at 3:57 PM, draq wrote:

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

One thing that your code could really use is better names. Variables

like “arr”, “t”, and even “calc” tell me very little, as I’m trying

to read you code.

Next, there’s a lot more iterators than just each() and using them

can make your code more expressive. Some examples:

def sum (arr)

i = 0

arr.each do |k| i += k end

i

end

# … or …

def sum( enum )

inject { |sum, n| sum + n }

end

arrj.each do |a|

arri.delete(a) if sum(a) != number

end

# … or …

arrj.delete_if { |a| sum(a) != number }

You can also simplify lines like the following by using destructive

method calls:

arri = arri.uniq

# … or …

arri.uniq!

Hope that gives you some ideas.

James Edward G. II

Would you like to add some asserts, so I can figure out the

specification?

How is the data entered?

Christer

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) }

}

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

I see, there is much to learn. ;-))

draq

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-part-iii.html

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

## … or …

def sum( enum )

inject { |sum, n| sum + n }

end

Don’t you need enum. ?

def sum(enum)

enum.inject {|sum,n| sum+n}

end

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

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-part-iii.html

Hopefully it’s now better understandable.

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 }

=> Enumerablearr = Array.new

=> []arr.is_a? Enumerable

=> truearr.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

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

[email protected]

“Ruby for Rails”, forthcoming from Manning Publications, April 2006!