llquiz-2014 http://ll.jus.or.jp/2014/

abcd.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
$str = "abcd"
data = %w[
  0 14  5 14
 32  0 38 12
 46 28  0  7
 33 18 44  0
]
data = data.map(&:to_i)
$data = data.each_slice($str.size).to_a
require 'pp'
pp $data

$positions = (0...$str.size).to_a
$max_cost = data.inject(&:+)

def visit(cost, cur_pos, visited=[cur_pos])
  return if $max_cost < cost
  cands = $positions - visited
  if cands.empty?
    puts [cost, visited.map{ |i| $str[i] }.join('') ]
    $max_cost = cost
    return
  end
  cands.each do |cand|
    visit(cost+$data[cur_pos][cand], cand, visited+[cand])
  end
end

visit(0, 0)

n-kings-10.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
$row = 10
data = %w[
0	0	1	0	0	0	1	0	0	1
0	0	0	0	1	0	0	0	0	0
0	0	0	0	0	0	0	0	0	1
0	0	0	0	0	0	0	1	0	0
0	0	1	0	1	0	0	0	0	0
1	0	0	0	0	0	0	0	0	1
0	0	0	1	0	0	0	0	0	0
0	0	0	0	0	0	0	0	0	0
0	0	0	0	0	0	0	1	0	0
0	1	0	0	0	1	0	0	0	0
]
data = data.map(&:to_i)

require 'pp'

$showed = []
def show(data)
  data = data.map { |i| i == 3 ? 0 : i }
  return true if $showed.include?(data)
  $showed << data
  pp data.each_slice($row).to_a if $DEBUG
  STDERR.write '.' if $showed.size % 100 == 0
  false
end

def set(data, n)
  return if n < 0 || data.size <= n
  data[n] = 3 if data[n] == 0
end

def fill(data)
  data = data.dup
  data.each_with_index do |n, i|
    case n
    when 1, 2
      if i % $row != 0
        set(data, i-1-$row)
        set(data, i-1)
        set(data, i-1+$row)
      end
      set(data, i-$row)
      set(data, i+$row)
      if i % $row != $row-1
        set(data, i+1-$row)
        set(data, i+1)
        set(data, i+1+$row)
      end
    end
  end
end

def rec_fill(data)
  data = fill(data)
  if show(data)
    return
  end
  if data.count(0) == 0
    return
  end
  data.each_with_index do |n, i|
    case n
    when 0
      data[i] = 2
      rec_fill(data)
      data[i] = 0
    end
  end
end

rec_fill(data)
p $showed.size

n-kings-3.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
$row = 3
data = %w[
1	0	0
0	0	0
0	0	0
]
data = data.map { |i| i == ?1 ? 1 : 0 }

require 'pp'

$showed = []
def show(data)
  return if $showed.include?(data)
  $showed << data
  pp data.each_slice($row).to_a
end

def set(data, n)
  return if n < 0 || data.size <= n
  data[n] = 2
end

def fill(data)
  data = data.dup
  data.each_with_index do |n, i|
    if n == 1
      if i % 3 != 0
        set(data, i-1-$row)
        set(data, i-1)
        set(data, i-1+$row)
      end
      set(data, i-$row)
      set(data, i+$row)
      if i % 3 != 2
        set(data, i+1-$row)
        set(data, i+1)
        set(data, i+1+$row)
      end
    end
  end
end

def rec_fill(data)
  data = fill(data)
  show(data)
  if data.count(0) == 0
    return
  end
  data.each_with_index do |n, i|
    if n == 0
      data[i] = 1
      rec_fill(data)
      data[i] = 0
    end
  end
end

rec_fill(data)

n-kings-5.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
$row = 5
data = %w[
1	0	0	0	1
0	0	1	0	0
1	0	0	0	1
0	0	1	0	0
0	0	0	0	0
]
data = data.map(&:to_i)

require 'pp'

$showed = []
def show(data)
  data = data.map { |i| i == 3 ? 0 : i }
  return true if $showed.include?(data)
  $showed << data
  pp data.each_slice($row).to_a
  false
end

def set(data, n)
  return if n < 0 || data.size <= n
  data[n] = 3 if data[n] == 0
end

def fill(data)
  data = data.dup
  data.each_with_index do |n, i|
    case n
    when 1, 2
      if i % $row != 0
        set(data, i-1-$row)
        set(data, i-1)
        set(data, i-1+$row)
      end
      set(data, i-$row)
      set(data, i+$row)
      if i % $row != $row-1
        set(data, i+1-$row)
        set(data, i+1)
        set(data, i+1+$row)
      end
    end
  end
end

def rec_fill(data)
  data = fill(data)
  if show(data)
    return
  end
  if data.count(0) == 0
    return
  end
  data.each_with_index do |n, i|
    case n
    when 0
      data[i] = 2
      rec_fill(data)
      data[i] = 0
    end
  end
end

rec_fill(data)
p $showed.size

pomiernald.rb

#!/usr/bin/env ruby
# -*- coding: utf-8 -*-
$str = 'pomiernald'
data = %w[
0 229 241 250 223 226 213 196 233 243
208 0 184 202 237 232 239 249 201 212
220 234 0 248 212 231 241 238 209 207
212 235 229 0 233 229 189 217 209 242
210 212 247 249 0 247 286 236 224 245
247 208 247 224 221 0 226 207 214 215
223 237 218 228 218 240 0 241 209 203
220 237 241 230 213 233 225 0 180 224
237 239 237 201 243 210 227 244 0 220
218 205 243 219 246 208 234 250 206 0
]
data = data.map(&:to_i)
$data = data.each_slice($str.size).to_a
require 'pp'
pp $data

$positions = (0...$str.size).to_a
$max_cost = data.inject(&:+)

def visit(cost, cur_pos, visited=[cur_pos])
  return if $max_cost < cost
  cands = $positions - visited
  if cands.empty?
    puts [cost, visited.map{ |i| $str[i] }.join('') ]
    $max_cost = cost
    return
  end
  cands.each do |cand|
    visit(cost+$data[cur_pos][cand], cand, visited+[cand])
  end
end

visit(0, 0)