sudoku solver, from Ruiby Quiz, adapted for mruby

sudoku.rb

# from Rosetta code, ruby version
# sudoku test finding in Groovy part

# tested with ruby 2.0 1.9 JRuby mri 1.0

def read_matrix(data)
  matrix = []
  fh=data.split("\n")
  (0..8).each { |i|
    l = fh.shift
    matrix[i] = []
    (0..8).each { |j|
      matrix[i][j] = l[j..j].to_i
    }
  }
  matrix
end
 
def permissible(matrix, i, j)
  ok = [true,true,true,true,true,true,true,true,true] 
  # Same as another in the column isn't permissible...
  (0..8).each { |i2|
    next if matrix[i2][j] == 0
    ok[matrix[i2][j] - 1] = false
  }
  # Same as another in the row isn't permissible...
  (0..8).each { |j2|
    next if matrix[i][j2] == 0
    ok[matrix[i][j2] - 1] = false
  }
  # Same as another in the 3x3 block isn't permissible...
  igroup = (div(i , 3) * 3)
  jgroup = (div(j , 3) * 3)
  (igroup..(igroup + 2)).each { |i2|
    (jgroup..(jgroup + 2)).each { |j2|
      next if matrix[i2][j2] == 0
      ok[matrix[i2][j2] - 1] = false
    }
  }
  # Convert to the array format...
  (1..9).select { |i2| ok[i2-1] }
end

def div(a,b) (a/b).floor end

def deep_copy_sudoku(matrix)
  matrix.collect { |row| row.dup }
end

class Array
 def min_by()
    min=[yield(self[0]),0]
    self.each_with_index { |v,i| vv=yield(v); min=[vv,i] if vv<min.first }
    self[min.last]
 end
end

def solve_sudoku(matrix)
  loop do
    options = []
    (0..8).each { |i|
      (0..8).each { |j|
        next if matrix[i][j] != 0
        p = permissible(matrix, i, j)
        # If nothing is permissible, there is no solution at this level.
        return nil if p.length == 0
        options.push({:i => i, :j => j, :permissible => p})
      }
    }
    # If the matrix is complete, we have a solution...
    return matrix if options.length == 0
 
    omin = options.min_by { |x| x[:permissible].length }
 
    # If there is an option with only one solution, set it and re-check permissibility
    if omin[:permissible].length == 1
      matrix[omin[:i]][omin[:j]] = omin[:permissible][0]
      next
    end
 
    # We have two or more choices. We need to search both...
    omin[:permissible].each { |v|
      mtmp = deep_copy_sudoku(matrix)
      mtmp[omin[:i]][omin[:j]] = v
      ret = solve_sudoku(mtmp)
      return ret if ret
    }
 
    # We did an exhaustive search on this branch and nothing worked out.
    return nil
  end
end
 
def print_matrix(matrix)
  if not matrix
    puts "Impossible"
    return
  end
 
  border = "+-----+-----+-----+"
  (0..8).each { |i|
    puts border if i%3 == 0
    (0..8).each { |j|
      print(j%3 == 0 ? "|" : " ")
      print(matrix[i][j] == 0 ? "." : matrix[i][j])
    }
    print "|\n"
  }
  puts border
end
# From Rosetta code, Groovy entry :
#3rd "exceptionally difficult" example in Wikipedia: ~ 2.3 seconds
#12.3....435....1....4........54..2..6...7.........8.9...31..5.......9.7.....6...8',
# Used in Curry solution:                             ~ 2.4 seconds
# 9..2..5...4..6..3...3.....6...9..2......5..8...7..4..37.....1...5..2..4...1..6..9',
# "AL Escargot", so-called "hardest sudoku" (HA!):    ~ 3.0 seconds
# 1....7.9..3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..',
# 1st "exceptionally difficult" example in Wikipedia: ~ 6.5 seconds
# 12.4..3..3...1..5...6...1..7...9.....4.6.3.....3..2...5...8.7....7.....5.......98',
# Used in Bracmat and Scala solutions:                ~ 6.7 seconds
# ..............3.85..1.2.......5.7.....4...1...9.......5......73..2.1........4...9',
# 2nd "exceptionally difficult" example in Wikipedia: ~ 8.8 seconds
# .......39.....1..5..3.5.8....8.9...6.7...2...1..4.......9.8..5..2....6..4..7.....',
# Used in MATLAB solution:                            ~15   seconds
# ....839..1......3...4....7..42.3....6.......4....7..1..2........8...92.....25...6',
# 4th "exceptionally difficult" example in Wikipedia: ~29   seconds
# ..3......4...8..36..8...1...4..6..73...9..........2..5..4.7..686........7..6..5..']
DATA=<<EEND 
3_4__267_
___3__4__
5__69__2_
_45___9__
6_______7
__7___58_
_1__67__8
__9__8___
_264__735
EEND

DATA=<<EEND 
..3......
4...8..36
..8...1..
.4..6..73
...9.....
.....2..5
..4.7..68
6........
7..6..5..
EEND
X=10
matrix = read_matrix(DATA) 
print_matrix(matrix)
puts
ret=nil
4.times { ret=solve_sudoku(matrix) }
st=Time.now
X.times { ret=solve_sudoku(matrix) }
et=Time.now
print_matrix(ret)
puts "duration #{(et-st).to_f} secs, #{(et-st).to_f*1000/X} ms by resolution"