M.Hiroi's Home Page
http://www.geocities.jp/m_hiroi/

Ruby Programming

Ruby Junk Scripts

[ PrevPage | R u b y | NextPage ]

小町算

[問題] 小町算

1 から 9 までの数字を順番に並べ、間に + と - を補って 100 になる式を作ってください。

例:1 + 2 + 3 - 4 + 5 + 6 + 78 + 9 = 100

パズルの世界では、1 から 9 までの数字を 1 個ずつすべて使った数字を 小町数 といいます。たとえば、123456789 とか 321654987 のような数字です。小町算 というものもあり、たとえば 123 + 456 + 789 とか 321 * 654 + 987 のようなものです。この問題は小町算の中でも特に有名なパズルです。

●プログラム

#
# komachi.rb : 小町算
#
#              Copyright (C) 2006 Makoto Hiroi
#

# eval 版
def komachi(n, expr)
  if n == 10
    if eval(expr) == 100
      print expr, "=100\n"
    end
  else
    komachi(n + 1, expr + "+" + n.to_s)
    komachi(n + 1, expr + "-" + n.to_s)
    komachi(n + 1, expr + n.to_s)
  end
end

komachi(2, "1")

●実行結果

1+2+3-4+5+6+78+9=100
1+2+34-5+67-8+9=100
1+23-4+5+6+78-9=100
1+23-4+56+7+8+9=100
12+3+4+5-6-7+89=100
12+3-4+5+67+8+9=100
12-3-4+5-6+7+89=100
123+4-5+67-89=100
123+45-67+8-9=100
123-4-5-6-7+8-9=100
123-45-67+89=100

騎士の周遊

[問題] 騎士の周遊

騎士(ナイト)はチェスの駒のひとつで、将棋の桂馬の動きを前後左右にとることができます。次の図を見てください。

    ┌─┬─┬─┬─┬─┐
    │  │●│  │●│  │
    ├─┼─┼─┼─┼─┤        ┌─┬─┐ 
    │●│  │  │  │●│        │K│  │ 
    ├─┼─┼─┼─┼─┤    ┌─┼─┼─┼─┐ 
    │  │  │K│  │  │    │  │  │  │  │ 
    ├─┼─┼─┼─┼─┤    ├─┼─┼─┼─┤ 
    │●│  │  │  │●│    │  │  │  │  │ 
    ├─┼─┼─┼─┼─┤    └─┼─┼─┼─┘ 
    │  │●│  │●│  │        │  │  │ 
    └─┴─┴─┴─┴─┘        └─┴─┘ 

 ●:ナイト (K) が動ける位置        問題A

                   図 : 騎士の周遊

このナイトを動かして、どのマスにもちょうど一回ずつ訪れて出発点に戻る周遊経路を求めるのが問題です。ちなみに、4 行 4 列の盤面には解がありませんが、6 行 6 列、8 行 8 列の盤面には解が存在します。大きな盤面を解くのは大変なので、問題 A の盤面でナイトの周遊経路を求めてください。

●プログラム

この問題は盤面が小さいので、単純な深さ優先探索で簡単に解くことができます。図に示すように、盤面のマスに番号をつけます。

      ┌─┬─┐           ┌─┬─┐     
      │K│  │           │0│1│     
  ┌─┼─┼─┼─┐   ┌─┼─┼─┼─┐ 
  │  │  │  │  │   │2│3│4│5│ 
  ├─┼─┼─┼─┤   ├─┼─┼─┼─┤ 
  │  │  │  │  │   │6│7│8│9│ 
  └─┼─┼─┼─┘   └─┼─┼─┼─┘ 
      │  │  │           │10│11│     
      └─┴─┘           └─┴─┘     

         盤面                 番号

          図 : 盤面と番号の関係

あとは隣接リストを定義して、深さ優先探索で周遊経路を探索するだけです。

#
# knight.rb : 騎士の周遊
#
#             Copyright (C) 2006 Makoto Hiroi
#

# 隣接リスト
$adjacent = [
[5, 6, 8],
[2, 7, 9],
[1, 8,10],
[9, 11],
[6, 10],
[0, 7, 11],
[0, 4, 11],
[1, 5],
[0, 2],
[1, 3, 10],
[2, 4, 9],
[3, 5, 6]]

def solve(path)
  for x in $adjacent[path[-1]]
    if path.size == 12
      if x == path[0]
        path.each do |x|
          print x, " "
        end
        print "\n"
      end
    elsif not path.member?(x)
      path << x
      solve(path)
      path.pop
    end
  end
end

solve([0])

●実行結果

0 5 7 1 9 3 11 6 4 10 2 8 
0 6 4 10 9 3 11 5 7 1 2 8 
0 8 2 1 7 5 11 3 9 10 4 6 
0 8 2 10 4 6 11 3 9 1 7 5 

4 通りの周遊経路が表示されましたが、逆回りの経路があるので、実際の経路は次の 2 通りになります。


      ┌─┬─┐           ┌─┬─┐     
      │0│3│           │0│9│     
  ┌─┼─┼─┼─┐   ┌─┼─┼─┼─┐ 
  │10│5│8│1│   │10│5│2│7│ 
  ├─┼─┼─┼─┤   ├─┼─┼─┼─┤ 
  │7│2│11│4│   │1│8│11│4│ 
  └─┼─┼─┼─┘   └─┼─┼─┼─┘ 
      │9│6│           │3│6│     
      └─┴─┘           └─┴─┘     

            図 : 周遊経路

魔方陣

[問題] 魔方陣
 ┌─┬─┬─┐  
 │A│B│C│  
 ├─┼─┼─┤  
 │D│E│F│  
 ├─┼─┼─┤  
 │G│H│I│  
 └─┴─┴─┘  

上図の A から I の場所に 1 から 9 までの数字をひとつずつ配置します。どの行の和も、どの列の和も、どの対角線の和も等しくなるような配置を見つけてください。

●プログラム

単純な生成検定法(とても遅い)。

#
# magic.rb : 魔方陣
#
#            Copyright (C) 2006 Makoto Hiroi
#

# 直線
$line_table = [
  [0,1,2], [3,4,5], [6,7,8],
  [0,3,6], [1,4,7], [2,5,8],
  [0,4,8], [2,4,6]]

# 直線 n の合計値を求める
def line_sum(n, board)
  sum = 0
  for x in $line_table[n]
    sum += board[x]
  end
  sum
end

# チェック
def check(board)
  n = line_sum(0, board)
  for i in 1 ... 8
    return false if n != line_sum(i, board)
  end
  true
end

# 盤面の表示
def print_board(board)
  for x in 0 ... 9
    print board[x], " "
    print "\n" if x % 3 == 2
  end
  print "\n"
end

# 魔方陣の解法
def solve(n = 1, board = [])
  if n == 10
    print_board(board) if check(board)
  else
    for x in 1 .. 9
      unless board.member?(x)
        board << x
        solve(n + 1, board)
        board.pop
      end
    end
  end
end

# 実行
solve

●実行結果

2 7 6 
9 5 1 
4 3 8 

2 9 4 
7 5 3 
6 1 8 

4 3 8 
9 5 1 
2 7 6 

4 9 2 
3 5 7 
8 1 6 

6 1 8 
7 5 3 
2 9 4 

6 7 2 
1 5 9 
8 3 4 

8 1 6 
3 5 7 
4 9 2 

8 3 4 
1 5 9 
6 7 2 

実行時間 24.25 秒 (Windows XP, Celeron 1,40 GHz, Ruby 1.8.3)

●プログラムの改良

枝刈りを追加して高速化したバージョンです。

 ┌─┬─┬─┐   
 │A│B│C│   
 ├─┼─┼─┤   A < C < G  
 │D│E│F│   
 ├─┼─┼─┤   A < I
 │G│H│I│   
 └─┴─┴─┘   

  図:対称解のチェック

魔方陣の場合、回転解が 4 種類あって、鏡像解が 2 種類あります。四隅の大小関係をチェックすることで、これらの対称解を排除することができます。また、早い段階で枝刈りを行うため、盤面の番号と試行順序を下図のように工夫します。


 ┌─┬─┬─┐  (1) B[0] + B[1] + B[4] => N 
 │0│4│1│  (2) B[0] + B[2] + B[5] == N
 ├─┼─┼─┤  (3) B[0] + B[3] + B[6] == N &&
 │5│6│7│      B[1] + B[2] + B[6] == N
 ├─┼─┼─┤  (4) B[1] + B[3] + B[7] == N &&
 │2│8│3│      B[5] + B[6] + B[7] == N
 └─┴─┴─┘  (5) B[2] + B[3] + B[8] == N &&
                     B[1] + B[3] + B[7] == N

  図:盤面の番号と試行順序

●プログラム

#
# magic1.rb : 魔方陣
#
#             Copyright (C) 2006 Makoto Hiroi
#

# 直線の合計値を求める
def line_sum(board, line)
  sum = 0
  for x in line
    sum += board[x]
  end
  sum
end

# チェック
def check(n, board, sum)
  case n
  when 1
    board[0] < board[1]
  when 2
    board[1] < board[2]
  when 3
    board[0] < board[3]
  when 5
    sum == line_sum(board, [0,5,2])
  when 6
    sum == line_sum(board, [0,6,3]) && sum == line_sum(board, [1,6,2])
  when 7
    sum == line_sum(board, [1,7,3]) && sum == line_sum(board, [5,6,7])
  when 8
    sum == line_sum(board, [4,6,8]) && sum == line_sum(board, [2,8,3])
  else
    true
  end
end

# 盤面の表示
def print_board(board)
  printf("%d %d %d\n", board[0], board[4], board[1])
  printf("%d %d %d\n", board[5], board[6], board[7])
  printf("%d %d %d\n", board[2], board[8], board[3])
end

# 魔方陣の解法
def solve(n = 0, board = [], value = 0)
  for x in 1 .. 9
    unless board.member?(x)
      board << x
      value = line_sum(board, [0,4,1]) if n == 4
      if check(n, board, value)
        if n == 8
          print_board(board)
        else
          solve(n + 1, board, value)
        end
      end
      board.pop
    end
  end
end

# 実行
solve

●実行結果

2 9 4
7 5 3
6 1 8

実行時間 0.203 秒 (Windows XP, Celeron 1,40 GHz, Ruby 1.8.3)


8クイーン

[問題] 8クイーン

8 クイーンは 8 行 8 列のチェスの升目に 8 個のクイーンを互いの利き筋が重ならないように配置する問題です。これはコンピュータに解かせるパズルの中でもとくに有名な問題です。クイーンは将棋の飛車と角をあわせた駒で、縦横斜めに任意に動くことができます。解答の一例を次に示します。

  *-----------------*
  | Q . . . . . . . |
  | . . . . Q . . . |
  | . . . . . . . Q |
  | . . . . . Q . . |
  | . . Q . . . . . |
  | . . . . . . Q . |
  | . Q . . . . . . |
  | . . . Q . . . . |
  *-----------------*

図 : 8 クイーンの解答例

●プログラム

プログラムのポイントは斜めの利き筋のチェックです。次の図を見てください。

  右斜め上の利き筋          左斜め上の利き筋
   0 1 2 3 4 5 6 7         0 1 2 3 4 5 6 7
*-----------------*        *-----------------*    
|//////// | 8   -1 |\\\\\\\\ |
|//////// | 9   -2 |\\\\\\\\ |
|//////// | 10  -3 |\\\\\\\\ |
|//////// | 11  -4 |\\\\\\\\ |
|//////// | 12  -5 |\\\\\\\\ |
|//////// | 13  -6 |\\\\\\\\ |
|//////// | 14  -7 |\\\\\\\\ |
|//////// |        |\\\\\\\\ |
*-----------------*        *-----------------*

 x + y = constant           x - y = constant

        図:斜めの利き筋のチェック

斜めの利き筋は、行と列の位置を足す、または行から列を引くと一定の値になることを利用してチェックします。右斜め上の利き筋を $rflag, 左斜め上の利き筋を $lflag で表すことにすると、(x, y) にクイーンを置いた場合は次のようにセットします。

$rflag[x + y] = false
$lflag[x - y + N - 1] = false

バックトラックするときは true に戻します。

#
# queen.rb : 8クイーンの解法
#
#            Copyright (C) 2006 Makoto Hiroi
#

N = 8
$rflag = Array.new(2 * N - 1, true)
$lflag = Array.new(2 * N - 1, true)
$nflag = Array.new(N, true)

def print_line(q)
  print "| "
  for i in 0 ... N
    if i == q
      print "Q "
    else
      print ". "
    end
  end
  print "|\n"
end

def print_board(board)
  print "*-", "--" * N, "*\n"
  board.each do |x|
    print_line(x)
  end
  print "*-", "--" * N, "*\n"
end

def solve(n = 0, board = [])
  if board.size == N
    print_board(board)
  else
    for x in 0 ... N
      if $nflag[x] && $rflag[x + n] && $lflag[x - n + N - 1]
        $nflag[x] = false
        $rflag[x + n] = false
        $lflag[x - n + N - 1] = false
        board << x
        solve(n + 1, board)
        board.pop
        $nflag[x] = true
        $rflag[x + n] = true
        $lflag[x - n + N - 1] = true
      end
    end
  end
end

solve

●実行結果

*-----------------*
| Q . . . . . . . |
| . . . . Q . . . |
| . . . . . . . Q |
| . . . . . Q . . |
| . . Q . . . . . |
| . . . . . . Q . |
| . Q . . . . . . |
| . . . Q . . . . |
*-----------------*

 ・・・省略・・・

*-----------------*
| . . . . . . . Q |
| . . . Q . . . . |
| Q . . . . . . . |
| . . Q . . . . . |
| . . . . . Q . . |
| . Q . . . . . . |
| . . . . . . Q . |
| . . . . Q . . . |
*-----------------*

解は重複解を含めて全部で 92 通りです。


5パズル

[問題] 5 パズル
 ┌─┬─┬─┐    ┌─┬─┬─┐  
 │4│5│  │    │1│2│3│  
 ├─┼─┼─┤ => ├─┼─┼─┤  
 │1│2│3│    │4│5│  │  
 └─┴─┴─┘    └─┴─┴─┘  
     START              GOAL

5 パズルは上図に示すように 1 から 5 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を飛び越したり持ち上げたりすることはできません。START から GOAL までの最短手順を求めてください。

●プログラム

#
# five.rb : 5 パズル
#
#           Copyright (C) 2006 Makoto Hiroi
#
# board
# 0 1 2
# 3 4 5

# 隣接リスト
$adjacent = [
  [1, 3],
  [0, 2, 4],
  [1, 5],
  [0, 4],
  [1, 3, 5],
  [2, 4]]

# 局面を表すクラス
class State
  include Comparable
  attr_reader :board, :prev, :space
  
  def initialize(board, prev, space)
    @board = board
    @prev = prev
    @space = space
  end
  
  def <=>(a)
    @board <=> a.board
  end
  
  def make_new_state
    buff = []
    for x in $adjacent[@space]
      board = @board.dup
      board[@space] = board[x]
      board[x] = 0
      buff << State.new(board, self, x)
    end
    buff
  end
end

def print_board(board)
  6.times do |x|
    print board[x], " "
    print "\n" if x % 3 == 2
  end
  print "\n"
end

def print_answer(state)
  print_answer(state.prev) if state.prev
  print_board(state.board)
end

# start から goal までの最短手順を求める
def solve(start, goal)
  # 初期化
  q = []
  rp = 0
  q << State.new(start, nil, start.index(0))
  # 幅優先探索
  while rp < q.size
    for new_state in q[rp].make_new_state
      if new_state.board == goal
        print_answer(new_state)
        return
      elsif !q.member?(new_state)
        q << new_state
      end
    end
    rp += 1
  end
end

# 最長手数の局面を求める
def solve_max
  # 初期化
  q = []
  m = []
  rp = 0
  q << State.new([1,2,3,4,5,0], nil, 5)
  m << 0
  # 幅優先探索
  while rp < q.size
    for new_state in q[rp].make_new_state
      unless q.member?(new_state)
        q << new_state
        m << m[rp] + 1
      end
    end
    rp += 1
  end
  i = q.size - 1
  max_move = m[i]
  print "最長手数 ", max_move, "\n"
  begin
    print_board(q[i].board)
    i -= 1
  end while m[i] == max_move
end

# 反復深化
# history には動かした駒の番号をセットする
def solve_id(n, limit, space, goal, history)
  if n == limit
    if $board == goal
      p history
      throw :answer
    end
  else
    for x in $adjacent[space]
      piece = $board[x]
      if history[-1] != piece
        $board[space] = piece
        $board[x] = 0
        history << piece
        solve_id(n + 1, limit, x, goal, history)
        history.pop
        $board[x] = piece
        $board[space] = 0
      end
    end
  end
end

# 実行
solve([4,5,0,1,2,3], [1,2,3,4,5,0])

# 最長手数の局面を求める
solve_max

# 反復深化
$board = [4,5,0,1,2,3]
catch(:answer) do 
  for x in 1 .. 21
    print x, "\n"
    solve_id(0, x, 2, [1,2,3,4,5,0], [nil])
  end
end

●実行例

4 5 0 
1 2 3 

4 0 5 
1 2 3 

0 4 5 
1 2 3 

1 4 5 
0 2 3 

1 4 5 
2 0 3 

1 0 5 
2 4 3 

1 5 0 
2 4 3 

1 5 3 
2 4 0 

1 5 3 
2 0 4 

1 5 3 
0 2 4 

0 5 3 
1 2 4 

5 0 3 
1 2 4 

5 2 3 
1 0 4 

5 2 3 
1 4 0 

5 2 0 
1 4 3 

5 0 2 
1 4 3 

0 5 2 
1 4 3 

1 5 2 
0 4 3 

1 5 2 
4 0 3 

1 0 2 
4 5 3 

1 2 0 
4 5 3 

1 2 3 
4 5 0 
最長手数 21
4 5 0 
1 2 3 
# 反復深化
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
[nil, 5, 4, 1, 2, 4, 5, 3, 4, 2, 1, 5, 2, 4, 3, 2, 5, 1, 4, 5, 2, 3]

8パズル

[問題] 8 パズル
 ┌─┬─┬─┐    ┌─┬─┬─┐  
 │6│4│7│    │1│2│3│  
 ├─┼─┼─┤    ├─┼─┼─┤  
 │8│5│  │ => │4│5│6│  
 ├─┼─┼─┤    ├─┼─┼─┤  
 │3│2│1│    │7│8│  │  
 └─┴─┴─┘    └─┴─┴─┘  
     START              GOAL

8 パズルは上図に示すように 1 から 8 までの駒を並べるパズルです。駒の動かし方は、1 回に 1 個の駒を空いている隣の場所に滑らせる、というものです。駒を飛び越したり持ち上げたりすることはできません。START から GOAL までの最短手順を求めてください。

●プログラム

#
# eight.rb : 8 パズル
#
#            Copyright (C) 2006 Makoto Hiroi
#
# board
# 0 1 2
# 3 4 5
# 6 7 8

# 隣接リスト
$adjacent = [
  [1, 3],
  [0, 2, 4],
  [1, 5],
  [0, 4, 6],
  [1, 3, 5, 7],
  [2, 4, 8],
  [3, 7],
  [4, 6, 8],
  [5, 7]]

# 定数
FORE = 0
BACK = 1

# 局面を表すクラス
class State
  include Comparable
  attr_reader :board, :prev, :dir, :space
  
  def initialize(board, prev, dir, space)
    @board = board
    @prev = prev
    @dir = dir
    @space = space
  end
  
  def make_new_state
    buff = []
    for x in $adjacent[@space]
      board = @board.dup
      board[@space] = board[x]
      board[x] = 0
      buff << State.new(board, self, @dir, x)
    end
    buff
  end
end

# 盤面の表示
def print_board(board)
  9.times do |x|
    print board[x], " "
    print "\n" if x % 3 == 2
  end
  print "\n"
end

# FORE 方向の手順を表示
def print_answer_f(state)
  print_answer_f(state.prev) if state.prev
  print_board(state.board)
end

# BACK 方向の手順を表示
def print_answer_b(state)
  loop do
    state = state.prev
    break unless state
    print_board(state.board)
  end
end

# 最短手順を表示
def print_answer(state1, state2)
  if state1.dir == FORE
    print_answer_f(state1)
    print_answer_b(state2)
  else
    print_answer_f(state2)
    print_answer_b(state1)
  end
end

# start から goal までの最短手順を求める
# start と goal の双方向で探索する
def solve(start, goal)
  # 初期化
  q = []
  rp = 0
  h = {}
  q << State.new(start, nil, FORE, start.index(0))
  q << State.new(goal, nil, BACK, goal.index(0))
  h[start] = q[0]
  h[goal]  = q[1]
  # 幅優先探索
  while rp < q.size
    for new_state in q[rp].make_new_state
      old_state = h[new_state.board]
      if old_state
        if old_state.dir != new_state.dir
          print_answer(old_state, new_state)
          return
        end
      else
        q << new_state
        h[new_state.board] = new_state
      end
    end
    rp += 1
  end
end

# 移動距離
$distance = [
  [],                  # 0 dummy
  [0,1,2,1,2,3,2,3,4], # 1
  [1,0,1,2,1,2,3,2,3], # 2
  [2,1,0,3,2,1,4,3,2], # 3
  [1,2,3,0,1,2,1,2,3], # 4
  [2,1,2,1,0,1,2,1,2], # 5
  [3,2,1,2,1,0,3,2,1], # 6
  [2,3,4,1,2,3,0,1,2], # 7
  [3,2,3,2,1,2,1,0,1], # 8
]

# 反復深化(下限値枝刈り法)
# history には動かした駒を格納する
def solve_id1(n, limit, low, space, goal, history)
  if n == limit
    if $board == goal
      p history
      throw :answer
    end
  else
    for x in $adjacent[space]
      piece = $board[x]
      if history[-1] != piece
        new_low = low - $distance[piece][x] + $distance[piece][space]
        if n + new_low < limit
          $board[space] = piece
          $board[x] = 0
          history << piece
          solve_id1(n + 1, limit, new_low, x, goal, history)
          history.pop
          $board[x] = piece
          $board[space] = 0
        end
      end
    end
  end
end

# 実行
solve([6,4,7,8,5,0,3,2,1], [1,2,3,4,5,6,7,8,0])

# 反復深化
$board = [6,4,7,8,5,0,3,2,1]
catch(:answer) do
  low = 0
  for x in 0 .. 8
    piece = $board[x]
    low += $distance[piece][x] if piece > 0
  end
  for x in low .. 31
    print x, "\n"
    solve_id1(0, x, low, 5, [1,2,3,4,5,6,7,8,0], [nil])
  end
end

●実行例

6 4 7 
8 5 0 
3 2 1 

6 4 0 
8 5 7 
3 2 1 

6 0 4 
8 5 7 
3 2 1 

6 5 4 
8 0 7 
3 2 1 

6 5 4 
0 8 7 
3 2 1 

6 5 4 
3 8 7 
0 2 1 

6 5 4 
3 8 7 
2 0 1 

6 5 4 
3 0 7 
2 8 1 

6 5 4 
3 7 0 
2 8 1 

6 5 4 
3 7 1 
2 8 0 

6 5 4 
3 7 1 
2 0 8 

6 5 4 
3 0 1 
2 7 8 

6 0 4 
3 5 1 
2 7 8 

0 6 4 
3 5 1 
2 7 8 

3 6 4 
0 5 1 
2 7 8 

3 6 4 
2 5 1 
0 7 8 

3 6 4 
2 5 1 
7 0 8 

3 6 4 
2 0 1 
7 5 8 

3 6 4 
2 1 0 
7 5 8 

3 6 0 
2 1 4 
7 5 8 

3 0 6 
2 1 4 
7 5 8 

0 3 6 
2 1 4 
7 5 8 

2 3 6 
0 1 4 
7 5 8 

2 3 6 
1 0 4 
7 5 8 

2 3 6 
1 4 0 
7 5 8 

2 3 0 
1 4 6 
7 5 8 

2 0 3 
1 4 6 
7 5 8 

0 2 3 
1 4 6 
7 5 8 

1 2 3 
0 4 6 
7 5 8 

1 2 3 
4 0 6 
7 5 8 

1 2 3 
4 5 6 
7 0 8 

1 2 3 
4 5 6 
7 8 0 
# 反復深化
21
22
23
24
25
26
27
28
29
30
31
[nil, 7, 4, 5, 8, 3, 2, 8, 7, 1, 8,
      7, 5, 6, 3, 2, 7, 5, 1, 4, 6,
      3, 2, 1, 4, 6, 3, 2, 1, 4, 5, 8]

Copyright (C) 2006 Makoto Hiroi
All rights reserved.

[ PrevPage | R u b y | NextPage ]