Sudoku solver in Ruby

README

A very simple Sudoku puzzle solver written in Ruby. This script is free every
way you look at it.

## Example usage

$ cat puzzle
 15 2
 7   8459
8 4795  6
    5 6
32  6  9
 61  3  2
  3246 1
1    9234
 49  1 6
$ ./sudoku.rb < puzzle
915624378
672318459
834795126
497152683
328467591
561983742
783246915
156879234
249531867


## Puzzle Format

The script expects puzzles to be in a particular format:
  - each row is separated by a newline
  - the givens are 1-9
  - empty chars are blank cells

Something like the following:

 15 2
 7   8459
8 4795  6
    5 6
32  6  9
 61  3  2
  3246 1
1    9234
 49  1 6

Lines can be shorter than 9 chars, the script will right pad with empty cells,
for e.g.:

   123456789            123456789
  " 15 2"         ===> " 15 2    "

sudoku.rb

#!/usr/bin/ruby

@cells = []
while line = ARGF.gets
  line.chomp!
  @cells += line.split("")
  if line.length < 9
    @cells += [" "] * (9 - line.length)
  end
end

def solve(cell)
  return true if cell > 80 
  legal_numbers = ("1".."9").to_a
  legal_numbers -= horizontal_range(cell)
  legal_numbers -= vertical_range(cell)
  legal_numbers -= neighbors(cell)
  while number = legal_numbers.pop
    @cells[cell] = number
    return cell if solve(find_empty_cell(cell))
    @cells[cell] = " "
  end
end

def find_empty_cell(cell)
  cell += 1 while cell < 81 and not @cells[cell].strip.empty?
  cell
end

def neighbors(cell)
  floor = cell / 27 * 27 + cell / 3 * 3 % 9
  indices = (floor..floor + 2).to_a +
  (floor + 9..floor + 11).to_a +
  (floor + 18..floor + 20).to_a
  @cells.values_at(*indices)
end


def horizontal_range(cell)
  floor = cell - cell % 9
  @cells[floor..floor + 8]
end

def vertical_range(cell)
  floor = cell % 9
  indices = (floor..floor + 72).select do |index|
    ((index - floor) % 9).zero?
  end
  @cells.values_at(*indices)
end

def test
  puts "Cells"
  puts @cells[0..8].inspect
  puts @cells[9..17].inspect
  puts @cells[18..26].inspect

  puts "Horizontal range"

  puts horizontal_range(0).inspect
  puts horizontal_range(4).inspect
  puts horizontal_range(8).inspect
  puts horizontal_range(9).inspect
  puts horizontal_range(10).inspect

  puts "Vertical range"

  puts vertical_range(0).inspect
  puts vertical_range(1).inspect
  puts vertical_range(9).inspect
  puts vertical_range(10).inspect

  puts "Find empty cell"
  puts find_empty_cell(0)

  puts "Neighbors"
  puts neighbors(19).inspect
  puts neighbors(40).inspect
end

#test
if solve(find_empty_cell(0))
  0.upto(8) do |n|
    puts @cells[(n * 9)..(n * 9 + 8)].join
  end
else
  puts "Could not solve this puzzle."
end