Miloping

This is the first week free from the shackles of routine, drudgery, and free lunches. And, now enjoying the leisurely submission to every flitting distraction in my headspace, I do so hungrily; reminded by every empty growl from my stomachspace.

With so much time and no one to look over my shoulder, I should probably be curled up in a ball somewhere sleeping. But instead here before you is something I wrote at the beginning of the year, due to a displacement of time in my favor, I present: a Sudoku solver in Ruby!

Only recently have I made it available online because I thought it needed some work (and still do): I want to make it solve puzzles of any size.

This solver uses a brute-force kind of approach, traversing the tree of possibilities depth-first. However, it attempts to be clever where it can.

The puzzle itself is stored in an array called @cells. So a standard 9×9 puzzle would be @cells.length # => 81.

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

The while loop populates the array from STDIN. It assumes that each char is a value in the cell. The following puzzle would read into the array like this:

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

# becomes [" ", "1", "5", " ", "2", " ", " ", " ", " ", " ",7", ...]

The idea behind the solver is simple:

1. Move through the array to find an empty cell
2. Write a legal number into it
3. Success, if we reach the end of the array; failure, if we run out of legal numbers before the end of the array

The main dish is the solve function, which accepts the index of the to-be-processed cell:

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

A legal number has two constraints:

• it is a value inclusively between 1 and 9
• it is a value not in the same vertical or horizontal line or in the 3×3 neighborhood

While there are legal numbers not attempted, it sets the cell value to one of the numbers, and recursively calls itself on the next empty cell.

A nil is implicitly if the list of legal numbers is exhausted, which results in backtracking to a cell where there are unattempted legal numbers.

The neighborhood, vertical and horizontal range of a cell are expressed by these functions:

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

I have in mind to illustrate this code with drawings, but that will have to wait because the day has moved along, and lunch appointments are calling.