class Time
  def tenth
    time_time = ("%0.1f" % self)
    new_time = time_time.split(//)
    return (new_time[-2] + new_time[-1]).to_i
  end

  def hundth
    time_time = ("%0.2f" % self)
    new_time = time_time.split(//)
    return (new_time[-2] + new_time[-1]).to_i
  end
end

class Object
   def deep_clone
     Marshal.load(Marshal.dump(self))
   end
end
class Array
   def count(item)
     num = 0
     self.each{|v| num += 1 if v == item}
     return num
   end
end
class Sudoku
def initialize(table)
  @table_c = nil 
  if table.is_a?(String)
    if FileTest.exist?(table)
      if FileTest.zero?(table)
        print "File is empty or puzzle is not correct\n"
      end
      @table = []
      file = IO.readlines(table)
      for i in 0...file.size
       file[i].delete("\n")
       file[i].split(" ").each{|item|
       @table[i] = [] if !@table[i].is_a?(Array)
       @table[i] << (item == "0" ? nil : item)}
     end
    end
  elsif table.is_a?(Table)
    @table = table.board
  else
    print "table must be an array or a file with a puzzle\n"
  end
end
 
#Vertical
def deep_search(array, index, num)
  check = 0
  for i in 0...array.size
   if array[i][index] != num
     check += 1
   end
  end
  return check >= 8
end

#Across
def deep_search2(array, index, num)
  check = 0
  for i in 0...array.size
   if array[index][i] != num
     check += 1
   end
  end
  return check >= 8
end

def completed?(table)
  com = 0
   (1).upto(9){|v|
   com += 1 if Solved?(table, v, 0) == true
   com += 1 if Solved?(table, v, 1) == true
   }
  return com >= 18
end

def Sort(table)
  not_in = ""
  array = nil
  for i in 0...table.size
   array = table[i]
   for j in 0...array.size
    if !array.include?((j+1).to_s)
      not_in += (j+1).to_s
    end
   end
   for k in 0...array.size
    if array[k].nil?
      array[k] = not_in.deep_clone
    end
   end
   table[i] = array
   not_in = ""
  end
  return table
end


def Uniq(array, index)
  collect = ""
  for i in 0...array.size
    if array[i][index].size == 1
      collect += array[i][index]
    end
  end
  collect = collect.split(//)
  for i in 0...collect.size
    for j in 0...array.size
      str = array[j][index]
      next if str.size == 1 || str == collect[i]
      array[j][index].slice!(collect[i])
    end
  end
end

def Uniq2(array, index)
  collect = ""
  for i in 0...array.size
    if array[index][i].size == 1
      collect += array[index][i]
    end
  end
  collect = collect.split(//)
  for i in 0...collect.size
    for j in 0...array.size
      str = array[index][j]
      next if str.size == 1 || str == collect[i]
      array[index][j].slice!(collect[i])
    end
  end
end

def BlockUniq(table, index)
  collect = ""
  s = nil
  e = nil
  b = (index % 3) * 3
  d = b + 2
  case index
    when 0..2
      s = 0
      e = 2
    when 3..5
      s = 3
      e = 5
    when 6..8
      s = 6
      e = 8
  end
  for i in s..e 
   for j in b..d
    if table[i][j].size == 1
      collect += table[i][j]
    end
   end
  end
return if collect.size < 1
collect = collect.split(//)
for m in 0...collect.size
  for i in s..e 
   for j in b..d
    next if table[i][j].size == 1
      if table[i][j].include?(collect[m])
        table[i][j].slice!(collect[m])
      end
    end
   end
  end
end


def RemoveCopy(table, array = table.deep_clone)
  for i in 0...table.size
   Uniq(table, i)
  end
  if table == array
    return table
  else
    return RemoveCopy(table)
  end
 
end
def RemoveCopy2(table, array = table.deep_clone)
  for i in 0...table.size
   Uniq2(table, i)
  end
  if table == array
    return table
  else
    return RemoveCopy2(table)
  end
 
end

def ArrangeBlock(table, index)
  collect = ""
  str_c   = ""
  s = nil
  e = nil
  b = (index % 3) * 3
  d = b + 2
  case index
    when 0..2
      s = 0
      e = 2
    when 3..5
      s = 3
      e = 5
    when 6..8
      s = 6
      e = 8
  end
  for i in s..e 
   for j in b..d
    if table[i][j].size == 1
      collect += table[i][j]
    end
   end
  end
collect = collect.split(//)
  for i in s..e
   for j in b..d
    next if table[i][j].size == 1
    if table[i][j].size > 1
      table_s = table[i][j].deep_clone.split(//)
      for k in 0...table_s.size
       if !collect.include?(table_s[k])
         str_c += table_s[k].deep_clone
       end
      end
    end
  end
end
str_pack = str_c.split(//)
singleton = []
singStr = nil
str_pack.each{|item| singleton << [item,str_c.count(item)]}
singleton.each{|item|
if item[1] == 1
  singStr = item[0]
  break
end
}
return if singStr == nil
return if str_c.size < 1
for i in s..e 
   for j in b..d
    next if table[i][j].size == 1
      if table[i][j].include?(singStr)
        table[i][j] = singStr
        return
      end
   end
end

end

def SingleBlock(table, index)
  collect = ""
  str_c   = ""
  for i in 0...table.size
   if table[index][i].size == 1
     collect += table[index][1]
   end
  end
  return if collect.size < 1
  for i in 0...table.size
    next if table[index][i].size == 1
    if table[index][i].size > 1
      table_s = table[index][i].deep_clone.split(//)
      for k in 0...table_s.size
       if !collect.include?(table_s[k])
         str_c += table_s[k].deep_clone
       end
      end
    end
  end
  str_pack = str_c.split(//)
  singleton = []
  singStr = nil
  str_pack.each{|item| singleton << [item,str_c.count(item)]}
  singleton.each{|item|
  if item[1] == 1
    singStr = item[0]
    break
  end
  }
  return if singStr == nil
  return if str_c.size < 1
  for i in 0...table.size
    next if table[index][i].size == 1
      if table[index][i].include?(singStr)
        table[index][i] = singStr
        return
      end
   end
end

def ScanRowColumn(table, index)
  collect = []
  data = ""
  for i in 0...table.size
    if table[i][index].size > 1
      collect << table[i][index]
    end
  end
  collect.each{|item|
  if collect.count(item) > 1
    data = item
    break
  end
  }
  for i in 0...table.size
    next if table[i][index].size < 2
    next if table[i][index] == data
      if table[i][index].include?(data)
        table[i][index].slice!(data)
      end
  end
 
end


def ScanRowColumn2(table, index)
  collect = []
  data = ""
  for i in 0...table.size
    if table[index][i].size > 1
      collect << table[index][i]
    end
  end
  collect.each{|item|
  if collect.count(item) > 1
    data = item
    break
  end
  }
  for i in 0...table.size
    next if table[index][i].size < 2
    next if table[index][i] == data
      if table[index][i].include?(data)
        table[index][i].slice!(data)
      end
  end
 
end


def BlockSort(table, array = table.deep_clone)
  for i in 0...table.size
    ArrangeBlock(table, i)
    BlockUniq(table, i)
    RemoveCopy(table)
    RemoveCopy2(table)
    SingleBlock(table, i)
    ScanRowColumn(table, i)
    ScanRowColumn2(table, i)
  end
 
  if table == array
    return table
  else
    return BlockSort(table)
  end
end

def Solved?(table, index, type)
  count = 0
      for i in 0...table.size
       case type
         when 0#vertical
           count += 1 if table[i][index].size == 1
         when 1#horizontal
           count += 1 if table[index][i].size == 1
       end
      end
  return count >= 9
end


def testNumber(table, index)
  return if Solved?(table, index, 0) == true
  return if Solved?(table, index, 1) == true
  value = nil
  copy = table.deep_clone
  for i in 0...table.size
    next if table[index][i].size == 1
      if table[index][i].size > 1
        value = table[index][i].split(//)
        for j in 0...value.size
         table[index][i] = value[j]
         table = solveSudoku(table)
         if table != copy &&
           (Solved?(table, index, 0) == true ||
           Solved?(table, index, 1) == true)
           return
         else
           table = copy.deep_clone
         end
        end
      end
  end
end


def solveSudoku(table)
  k = Sort(table)
  m = RemoveCopy(k)
  s = RemoveCopy2(m)
  q = BlockSort(s)
  return q
end

def printResult(table)
  lines = "-"*9*8
  for i in table
    i.each{|item| print sprintf("%08s",item)}
    print "\n",lines,"\n"
  end
end

def Solve
  $time = Time.now.hundth
  print "Time is ", $time,"\n\n"
  result = solveSudoku(@table)
  for i in 0...result.size
   testNumber(result, i)
  end
  printResult(result)
end


end

class Table
  attr_accessor :normal
  attr_accessor :hard
  attr_accessor :table
  def initialize(table = 0)
    @table = table
    #Easy
    @normal =
    [
      [nil,'1',nil,'4','2',nil,nil,nil,'5'],
      [nil,nil,'2',nil,'7','1',nil,'3','9'],
      [nil]*7 + ['4',nil],
      ['2',nil,'7','1',nil,nil,nil,nil,'6'],
      [nil,nil,nil,nil,'4',nil,nil,nil,nil],
      ['6',nil,nil,nil,nil,'7','4',nil,'3'],
      [nil,'7'] + [nil]*7,
      ['1','2',nil,'7','3',nil,'5',nil,nil],
      ['3',nil,nil,nil,'8','2',nil,'7',nil]
    ]
    @hard =
    [
      [nil,'9',nil,'7',nil,nil,'8','6',nil],
      [nil,'3','1',nil,nil,'5',nil,'2',nil],
      ['8',nil,'6'] + [nil]*6,
      [nil,nil,'7',nil,'5',nil,nil,nil,'6'],
      [nil,nil,nil,'3',nil,'7',nil,nil,nil],
      ['5',nil,nil,nil,'1',nil,'7',nil,nil],
      [nil]*6 + ['1',nil,'9'],
      [nil,'2',nil,'6',nil,nil,'3','5',nil],
      [nil,'5','4',nil,nil,'8',nil,'7',nil]
    ]
  end
 
  def board
    case @table
      when 0
        return @normal
      when 1
        return @hard
    end
  end
 
  def CreateBoard
    return #TODO
  end
 
end
@table = Table.new(1)
@sudoku = Sudoku.new("puzzle.txt")
@sudoku.Solve
@time = Time.now.hundth
print "Time is ", @time,"\n\n"
@total = (@time - $time).abs
print "Total Time is ", @total,"\n\n"

Expand to see the code.