Paint By Numbers(0)

http://codegolf.com/paint-by-numbers
カシコーなアルゴリズムは調べればたくさんあるのだと思いますが、短く書くにはどんな方法が良いでしょうか。最初に思いついた方法は、とりあえず1行だけに絞って考えられるすべてのパターンを書き出し、さらにその組み合わせで正解と合致するものを単純に探していくというもの。各行の可能性が少なければ、時間内に答えが見つけられるかなーと。10行で各行10通り程度だと、最悪1000万回調べなければ成らない。明らかにテストデータ依存です(;´Д｀)。まあ、とりあえずやってみないとどーしようもないな。どこかでサンプルコードとかが手に入れば楽チンなのだが。。。

以下、ちょっとしたテストコード

$data=[2,1,1]
$lineLength=10

$pb=[]
$sum=0
$data.map{|n|$sum+=n}

def makeLines(d,offset,s)
	i=offset
	len = $data[d]
	while (d<$data.size)&&((i+len)<=$lineLength)
		t=s.dup
		t[i,len]="X"*len
		makeLines(d+1,i+len+1,t)

		sum=0
		t.each_byte{|c|sum+=1 if c==?X}
		$pb<<t.dup if $sum==sum
		i+=1
	end
end

makeLines(0,0," "*$lineLength)
puts $pb.join("\n")

実行結果

XX X X    
XX X  X   
XX X   X  
XX X    X 
XX X     X
XX  X X   
XX  X  X  
XX  X   X 
XX  X    X
XX   X X  
XX   X  X 
XX   X   X
XX    X X 
XX    X  X
XX     X X
 XX X X   
 XX X  X  
 XX X   X 
 XX X    X
 XX  X X  
 XX  X  X 
 XX  X   X
 XX   X X 
 XX   X  X
 XX    X X
  XX X X  
  XX X  X 
  XX X   X
  XX  X X 
  XX  X  X
  XX   X X
   XX X X 
   XX X  X
   XX  X X
    XX X X

追記：テストコードその２

data=[[1,1],[3],[1,2]]
$lineLength=4
$pic=[]

def makeLines(pb,data,d,offset,s)
	i=offset
	len = data[d]
	while (d<data.size)&&((i+len)<=$lineLength)
		t=s.dup
		t[i,len]="X"*len
		makeLines(pb, data, d+1, i+len+1, t)

		sum=0
		t.each_byte{|c|sum+=1 if c==?X}
		pb<<t.dup if $sum==sum
		i+=1
	end
	pb
end

def makePict(pb,d,data)
	pb[d].size.times{|i|
		$pic[d]=pb[d][i]
		if d<data.size-1
			makePict(pb,d+1,data)
		else
			puts $pic,"\n"
		end
	}
end

pb=[]
data.size.times{|i|
	$sum=0
	data[i].map{|n|$sum+=n}
	makeLines(pb[i]=[], data[i], 0, 0, " "*$lineLength)
}

makePict(pb,0,data)

実行結果

X X 
XXX 
X XX

X X 
 XXX
X XX

X  X
XXX 
X XX

X  X
 XXX
X XX

 X X
XXX 
X XX

 X X
 XXX
X XX