sudoku高速化

sudoku.rbを高速化してみた。マトリックスを埋めたあとに、1つずつ数字を消す処理（reduce＋delete_one）を変えた。チェック済みかどうかを確認するのが面倒だったので、単純に1000回ランダムチェックを繰り返して「まあ大体調べたことになるだろう」という、すさまじい富豪アプローチだったのをやめて、ちゃんと1セル1チェックにした。それだけで100問の生成時間が110秒から30秒へと3.6倍に高速化した。さらに、マトリックスの各列を埋めるときに何回ぐらいのリトライで「やっても無駄」と判定するかの閾値を100回から30回に減らした（これを10回に減らせると規定回数のうちに1つもマトリックスが生成されないケースが出てくる）。これで約3倍のスピードアップ。

合計10倍の速度アップ。110秒かかっていたものが10秒に縮んだ。Ruby 1.9だと実に4.7秒。表示を見ていると鬼のように速い感じがする。元の計算方法がひどすぎただけなのだけど。

#!/usr/bin/ruby

=begin
= sudoku
* データ構造は
  matrix = [1,2,3,4,,,,,,,81]
  yoko_index = [[0,1,2,...8], [9,10,11...17],
  tate_index = [[0,9,18,...72], [1,10,19...73],
  block_index = [[0,1,2,9,10,11,],[3,4,5,12,],,]
* blockは
  |0|1|2|
  |3|4|5|
  |6|7|8|
  という構造で、matrix[block_index(3)
=end

class Matrix
  attr_accessor :yoko_index, :tate_index, :block_index, :matrix

  def initialize
    @matrix = Array.new(81,0)

    @yoko_index = Array.new
    (0..8).each{|i|
      @yoko_index[i] = Array.new
      s = i * 9
      (s..s+8).each{|j|
        @yoko_index[i] << j
      }
    }

    @tate_index = Array.new
    (0..8).each{|i|
      @tate_index[i] = Array.new
      (0..8).each{|j|
        @tate_index[i] << (j * 9) + i
      }
    }

    @block_index = Array.new
    block_pattern = [0,1,2,9,10,11,18,19,20]
    (0..8).each{|i|
      @block_index[i] = block_pattern.map{|j|
        (j + (i / 3) * 27) + ((i % 3) * 3)}
    }
  end

  def yoko(x)
    @yoko_index[x].collect{|x| @matrix[x]}
  end

  def tate(x)
    @tate_index[x].collect{|x| @matrix[x]}
  end

  def block(x)
    @block_index[x].collect{|x| @matrix[x]}
  end

  def which_block(x,y)
    ((y / 3) * 3) + (x / 3)
  end

  def index(x,y)
    x + (y * 9)
  end

  def fill_matrix
    srand
    100.times{|i|
      break if self.try_fill_matrix
    }
#    puts self.to_s
# average 7.53 times
  end

  def try_fill_matrix
    count = 0
    abandon_flag = false

    @matrix.fill(0)

    (0..8).each{|y|
      repeat_flag = true
      break if(abandon_flag == true)
      until(repeat_flag == false)
        count += 1
        if (count > 20)
          abandon_flag = true
          @matrix.fill(0)
          break
        end
        seeds = (1..9).to_a
        (0..8).each{|x|
          appear = tate(x) | block(which_block(x,y))
          n = (seeds - appear).pick_one
          @matrix[index(x,y)] = n
          seeds.delete(n)
          if((x == 8) && (!yoko(y).include?(nil)))
            repeat_flag = false
          end
        }
      end
      }
    !abandon_flag
  end

  def make_new_puzzle
    self.fill_matrix
    self.reduce
  end

  def reduce
    srand
    candidate = (0..80).to_a
    candidate.delete_if{|i| @matrix[i] == 0}
    
    while(candidate.size > 0)
      c = candidate.pick_one
      if(uniq_solution?(c))
        @matrix[c] = 0
      end
      candidate.delete(c)
    end
    self.to_s
    puts (0..80).to_a.delete_if{|i| @matrix[i] == 0}.size
  end

  def uniq_solution?(n)
    i = @matrix[n]
    x = n % 9
    y = n / 9

    (1..9).to_a.delete_if{|n| n == i}.each{|j|
      if(!tate(x).include?(j) &&
         !yoko(y).include?(j) &&
         !block(which_block(x,y)).include?(j))
        return false
      end
    }
  end

  def to_s
    print "-"*19,"\n"
    (0..8).each{|y|
      i = 0
      yoko(y).each{|n|
        if((i % 3) == 0)
          separator = "|"
        else
          separator = " "
        end
        n = " " if n == 0
        print separator, n
        i += 1
      }
      print "|\n"
      if(((y + 1) % 3) == 0)
        print "-"*19,"\n"
      end
    }
  end
end

class Array
  def pick_one
    r = rand(self.size)
    self[r]
  end
end

#m = Matrix.new
#m.make_new_puzzle

(sudoku.rb)