Sudoku solver

gistfile1.rb

def cross(cols, rows)
  cols.split('').product(rows.split('')).map{|c, r| c + r}
end

$digits = '123456789'
$rows = 'ABCDEFGHI'
$cols = $digits
$squares = cross($rows, $cols)
$unitlist = $cols.split('').map{|c| cross($rows, c)} +
            $rows.split('').map{|r| cross(r, $cols)} +
            ['ABC', 'DEF', 'GHI'].product(['123', '456', '789']).map{|c, r| cross(c, r)}
$units = Hash[$squares.zip($squares.map{|s| $unitlist.select{|u| u.include?(s)}})]
$peers = Hash[$squares.zip($squares.map{|s| $units[s].flatten.uniq - [s]})]

def parse_grid(grid)
  values = Hash[$squares.zip($squares.map{$digits.dup})]
  grid_values(grid).each{|s, d|
    return false if $digits.include?(d) && !assign(values, s, d)
  }
  values
end

def grid_values(grid)
  chars = grid.split('').select{|c| $digits.include?(c) || '0.'.include?(c)}
  raise ArgumentError.new("can't convert grid into a Hash") if chars.size != 81
  Hash[$squares.zip(chars)]
end

def assign(values, s, d)
  other_values = values[s].delete(d)
  if other_values.split('').all?{|d2| eliminate(values, s, d2)}
    values
  else
    false
  end
end

def eliminate(values, s, d)
  return values if !values[s].include?(d)
  values[s] = values[s].delete(d)

  case values[s].size
  when 0
    return false
  when 1
    d2 = values[s]
    return false if !$peers[s].all?{|s2| eliminate(values, s2, d2)}
  end

  $units[s].each{|u|
    dplaces = u.select{|s2| values[s2].include?(d)}
    case dplaces.size
    when 0
      return false
    when 1
      return false if !assign(values, dplaces[0], d)
    end
  }

  values
end

def display(values)
  width = 1 + $squares.map{|d| d.size}.max
  line = (['-' * (width * 3)] * 3).join('+')
  $rows.split('').each{|r|
    $cols.split('').each{|c|
      print values[r + c].center(width)
      print '|' if '36'.include?(c)
      print "\n" if c == '9'
    }
    puts line if 'CF'.include?(r)
  }
  puts
end

def solve(grid)
  search(parse_grid(grid))
end

def search(values)
  return false if !values
  return values if $squares.all?{|s| values[s].size == 1}
  s, n = values.select{|s, d| d.size > 1}.min_by{|s, d| d.size}
  values[s].split('').map{|d| search(assign(values.dup, s, d))}.find{|v| v}
end

display(solve('003020600900305001001806400008102900700000008006708200002609500800203009005010300'))
display(solve('4.....8.5.3..........7......2.....6.....8.4......1.......6.3.7.5..2.....1.4......'))
display(solve('005300000800000020070010500400005300010070006003200080060500009004000030000009700'))