Sudoku Solver

=begin

  ruby/sudoku_solver.rb
  by IceDragon
  at 28/09/2012

  :x The most inefficient solver known to man

=end

module ArrayTools

  def self.rotate(array, n=1)
    array.concat(array.slice!(0, n))
  end

end

# // Main module
module Sudoku

  # // A constant is fitting cause this stuff never changes :x
  XSIZE = 9
  YSIZE = 9

  XBLOCK_SIZE = 3
  YBLOCK_SIZE = 3

  private
  # // Bleh, lazy method for making multi_dimensional arrays
  # // Initializes the array with elements of 0
  # // return Array<Array<int>>
  # // Array[y][x] => int
  def self.multi_dim_array2(ysize, xsize, populate=0)
    Array.new(ysize) do Array.new(xsize, populate) end
  end

  def self.index_to_xy(index, xsize=XSIZE)
    x = index % xsize
    y = index/xsize
    return x, y
  end

  def self.obj_in_column?(array, obj, x)
    for y in 0...YSIZE
      if array[y][x] == obj
        #puts "#{obj} is present in column #{x}"
        return true
      end
    end
    #puts "#{obj} is not present in column #{x}"
    return false
  end

  def self.obj_in_row?(array, obj, y)
    if array[y].include?(obj)
      #puts "#{obj} is present in row #{y}"
      return true
    else
      #puts "#{obj} is not present in row #{y}"
      return false
    end
  end

  def self.obj_in_block?(array, obj, xp, yp)
    block_x = xp / XBLOCK_SIZE
    block_y = yp / YBLOCK_SIZE
    bxs = block_x * XBLOCK_SIZE
    bys = block_y * YBLOCK_SIZE
    for y in bys...(bys + YBLOCK_SIZE)
      row = array[y]
      for x in bxs...(bxs + XBLOCK_SIZE)
        if row[x] == obj
          #puts "#{obj} is present in #{block_x}, #{block_y}"
          return true
        end
      end
    end
    #puts "#{obj} is not present in #{block_x}, #{block_y}"
    return false
  end

  def self.obj_valid_pos?(array, obj, x, y)
    return false if obj_in_column?(array, obj, x)
    return false if obj_in_row?(array, obj, y)
    return false if obj_in_block?(array, obj, x, y)
    return true
  end

  public

=begin

  Sudoku is a 9x9 grid

=end
  def self.generate()
    xsize, ysize = XSIZE, YSIZE
    begin
      res = nil
      while !res
        result   = multi_dim_array2(ysize, xsize, " ")
        lead_row = (1..XSIZE).to_a.sort_by do rand() end
        result[0].replace(lead_row)
        res = solve_table(result)
      end
      # // Black out at random
      for y in 0...ysize
        for x in 0...xsize
          next unless rand(2) == 0
          res[y][x] = " "
        end
      end
      result = res
    end
    result
  end

  def self.solve_table(result)
    for y in 0...YSIZE
      inds = ((1..YSIZE).to_a - result[y]).sort_by do rand() end
      x = 0
      while x < XSIZE
        #sleep(0.1)
        #system('cls')
        #puts "Generating Row: #{y}"
        #print_multi_dim_array2(result, YSIZE)
        #puts "Row: #{result[y].join('|')}"
        id = inds[0]
        if result[y][x] != " "
          x += 1
        elsif obj_valid_pos?(result, id, x, y) and result[y][x] == " "
          inds.delete(id)
          result[y][x] = id
          x += 1
        elsif !inds.empty? and !inds.any? do |a| obj_valid_pos?(result, a, x, y) end
          return nil
        else
          ArrayTools.rotate(inds, 1)
        end
      end
    end
    return result
  end

  def self.solve(sudoku_array)
    res = nil
    while !res
      result = Marshal.load(Marshal.dump(sudoku_array))
      res = solve_table(result)
    end
    return res
  end

end

# // Method used for printing multi dimensional arrays
def print_multi_dim_array2(array, ysize, joint=" | ")
  # // We start from y not x
  # // since we write line by line, and not column by column :)
  for y in 0...ysize
    row = array[y]
    print(" #{Array.new(row.size, "-").join(joint)}\n")
    print(" #{row.join(joint)}\n")
  end
end

# // C habits die hard
def main()
  sudoku_array = Sudoku.generate()
  puts "To solve:"
  print_multi_dim_array2(sudoku_array, Sudoku::YSIZE)
  puts "Solving..."
  time_then = Time.now
  result = Sudoku.solve(sudoku_array)
  time_elapsed = Time.now - time_then
  puts "Solved in: #{time_elapsed.round(0)}sec(s)"
  print_multi_dim_array2(result, Sudoku::YSIZE)
  # // C habits really die hard :x
  return 0;
end

# // My Usual ruby block :)
begin
  main()
rescue(Exception) => ex
  # // Output to console
  p ex
  puts ex.backtrace
  #raise ex # // Only if your using RM :)
end