はじめてのRuby

Rubyを勉強しているよ! ifとforと配列とメソッドの書き方を覚えたよ!
週末の新聞にナンバープレース(数独)の問題が載っていたので、それを解くプログラムを書くことにした。お題はこれ。

	5						7
6			1		2			9
	7	2				6	3
2	3						1	8
		4	8		7	2
7				5				3
	6						9
5		8	3		6	1		7
4			9		8			5

データの持ち方は迷ったが、ひとまず単純に81要素の配列にする。

init = [nil, 5, nil, nil, nil, nil, nil, 7, nil,
        6, nil, nil, 1, nil, 2, nil, nil, 9,
        nil, 7, 2, nil, nil, nil, 6, 3, nil,
        2, 3, nil, nil, nil, nil, nil, 1, 8,
        nil, nil, 4, 8, nil, 7, 2, nil, nil,
        7, nil, nil, nil, 5, nil, nil, nil, 3,
        nil, 6, nil, nil, nil, nil, nil, 9, nil,
        5, nil, 8, 3, nil, 6, 1, nil, 7,
        4, nil, nil, 9, nil, 8, nil, nil, 5]

デバッグしやすいように、配列を9×9で表示するメソッドを書く。

def show_table(data)
  for i in 0..8
    if i == 3 || i == 6 then
      puts " +===+===+===++===+===+===++===+===+===+ "
    else
      puts " +---+---+---++---+---+---++---+---+---+ "
    end

    for j in 0..8
      if j == 3 || j == 6 then
        print " || "
      else
        print " | "
      end

      print data[i * 9 + j] == nil ? " " : data[i * 9 + j]
    end
    puts " |"
  end

  puts " +---+---+---++---+---+---++---+---+---+ "
  puts
end

出力はこんな感じ。(aa記法を使ってもなぜか整形が崩れる・・・)

 +---+---+---++---+---+---++---+---+---+
 |   | 5 |   ||   |   |   ||   | 7 |   |
 +---+---+---++---+---+---++---+---+---+
 | 6 |   |   || 1 |   | 2 ||   |   | 9 |
 +---+---+---++---+---+---++---+---+---+
 |   | 7 | 2 ||   |   |   || 6 | 3 |   |
 +===+===+===++===+===+===++===+===+===+
 | 2 | 3 |   ||   |   |   ||   | 1 | 8 |
 +---+---+---++---+---+---++---+---+---+
 |   |   | 4 || 8 |   | 7 || 2 |   |   |
 +---+---+---++---+---+---++---+---+---+
 | 7 |   |   ||   | 5 |   ||   |   | 3 |
 +===+===+===++===+===+===++===+===+===+
 |   | 6 |   ||   |   |   ||   | 9 |   |
 +---+---+---++---+---+---++---+---+---+
 | 5 |   | 8 || 3 |   | 6 || 1 |   | 7 |
 +---+---+---++---+---+---++---+---+---+
 | 4 |   |   || 9 |   | 8 ||   |   | 5 |
 +---+---+---++---+---+---++---+---+---+

あとは解く。解き方はいくつか考えたが、問題は9×9と限られているので、力づくでバックトラック。

def check_row(table, position, value)
  for i in 0..8
    if table[position / 9 * 9 + i] == value then
      return false
    end
  end

  return true
end

def check_column(table, position, value)
  for i in 0..8
    if table[i * 9 + position % 9] == value then
      return false
    end
  end

  return true
end

def check_block(table, position, value)
  upper_left = position / 27 * 27 + position % 9 / 3 * 3
  for i in 0..8
    if table[upper_left + i / 3 * 9 + i % 3] == value then
      return false
    end
  end

  return true
end

def proceed(init, result, position)
  if position > 80 then
    return true
  end

  if init[position] != nil then
    result[position] = init[position]
    return proceed(init, result, position + 1)
  else
    for i in 1..9
      if check_row(result, position, i) && check_column(result, position, i) && check_block(result, position, i) then
        result[position] = i


        if proceed(init, result, position + 1) then
          return true
        end
      end
    end

    result[position] = nil
    return false
  end
end

show_table(init)

result = []
for i in 0..80
  result[i] = init[i]
end

if proceed(init, result, 0) then
  show_table(result)
else
  puts "no answer"
end

いちおう答えは出る。

 +---+---+---++---+---+---++---+---+---+
 | 1 | 5 | 9 || 6 | 8 | 3 || 4 | 7 | 2 |
 +---+---+---++---+---+---++---+---+---+
 | 6 | 4 | 3 || 1 | 7 | 2 || 5 | 8 | 9 |
 +---+---+---++---+---+---++---+---+---+
 | 8 | 7 | 2 || 5 | 9 | 4 || 6 | 3 | 1 |
 +===+===+===++===+===+===++===+===+===+
 | 2 | 3 | 5 || 4 | 6 | 9 || 7 | 1 | 8 |
 +---+---+---++---+---+---++---+---+---+
 | 9 | 1 | 4 || 8 | 3 | 7 || 2 | 5 | 6 |
 +---+---+---++---+---+---++---+---+---+
 | 7 | 8 | 6 || 2 | 5 | 1 || 9 | 4 | 3 |
 +===+===+===++===+===+===++===+===+===+
 | 3 | 6 | 1 || 7 | 2 | 5 || 8 | 9 | 4 |
 +---+---+---++---+---+---++---+---+---+
 | 5 | 9 | 8 || 3 | 4 | 6 || 1 | 2 | 7 |
 +---+---+---++---+---+---++---+---+---+
 | 4 | 2 | 7 || 9 | 1 | 8 || 3 | 6 | 5 |
 +---+---+---++---+---+---++---+---+---+

しょぼいっす・・・。

• 配列result[]を初期化するとき、もっと簡単にコピーする方法がありそう
• check_row、check_column、check_blockのロジックはほとんど同じなので、ブロックを使うと1つにできそう
• forでループを回すのがRubyっぽくないような気がする
• proceed()でinitを引きずりまわさないで済む方法があるはず
• バックトラックするときにわざわざresult[]にnilをセットし直しているのがスマートに見えない
• そもそもアルゴリズムがしょぼい

勉強しながら書き直してみよう。
この日記を読んだ人へのお願い。他にもしょぼいところがあれば教えてください。でも、コードの書き方は決して教えないでください。