4 of 4
replaced http://meta.codereview.stackexchange.com/ with https://codereview.meta.stackexchange.com/
Ruby Sudoku solver
This week's weekend challenge #3 seemed like a great opportunity to learn Ruby! Unfortunately, my workload and looming vacation did not cooperate. :( The puzzle will make forced moves automatically, but I was hoping to implement rules such as Naked Pairs before resorting to brute force.
But there's plenty of code to make a review worthwhile, and I'm hoping some experienced Ruby coders will give it a shot. I have included a few test puzzles (easy and medium solve to completion), and it's easy to add more. See the bottom for a sample test run.
The real meat of the algorithm is the interaction between the Cell and Group instances. Board merely instantiates everything and applies the initial puzzle state.
I'm looking for feedback on Ruby style (e.g. "avoid and and or as they are confusing"), correct use of idioms and the standard library, code organization, etc. This is a Ruby learning exercise, so I want to avoid picking up bad habits early. Since I haven't implemented any brute-force or complex solving yet, performance isn't an issue.
Board.rb
require 'Cell'
require 'Group'
require 'Inspector'
module Sudoku
# Builds the cells and groups and provides an API for setting up and interacting with the puzzle.
#
# Several debugging methods are provided that are being extracted to the inspector.
class Board
# Builds the board structure and initializes an empty puzzle.
#
# @param start [String] optional initial values passed to #setup
def initialize(start = nil)
@cells = Array.new(9) { |r| Array.new(9) { |c| Cell.new r, c } }
@rows = Array.new(9) { |i| Group.new :row, i }
@cols = Array.new(9) { |i| Group.new :col, i }
@boxes = Array.new(9) { |i| Group.new :box, i }
(0..8).each do |i|
connect @rows[i], row_cells(i)
connect @cols[i], col_cells(i)
connect @boxes[i], box_cells(i)
end
setup start if start
end
# Sets the initial values of the puzzle.
#
# Place each row on a separate line and nine cell values on each row.
# Whitespace is ignored around the row on each line. Each cell value
# may be a digit [1-9] or a period (.) if empty.
#
# @param start [String] optional initial values passed to #setup
#
# @example Nine queens
# .....9...
# ...9.....
# ......9..
# 9........
# .......9.
# .9.......
# ....9....
# ..9......
# ........9
def setup(puzzle)
r = 1
puzzle.split.each do |line|
c = 1
line.each_char do |n|
set(r, c, n.to_i, :start) if n =~ /[1-9]/
c += 1
end
r += 1
end
end
# Returns true if the cell can be set to the value.
#
# @param r [Fixnum] one-based row
# @param c [Fixnum] one-based column
# @param n [Fixnum] one-based cell value
# @return [Boolean]
def possible?(r, c, n)
cell(r, c).possible? n
end
# Returns true if the cell has been set to a value.
#
# @param r [Fixnum] one-based row
# @param c [Fixnum] one-based column
# @return [Boolean]
def known?(r, c)
cell(r, c).known?
end
# Sets the cell to the value for the given reason (omit when playing).
#
# @param r [Fixnum] one-based row
# @param c [Fixnum] one-based column
# @param n [Fixnum] one-based cell value
# @param reason [Symbol] one of :start, :choose, or :force
# @return [void]
#
# @raise [RuntimeError] if the cell is already set
# @raise [RuntimeError] if the value is not possible for the cell
def set(r, c, n, reason = :choose)
cell(r, c).set(n, reason)
end
# Iterates over each cell on the board from left-to-right and top-to-bottom.
#
# Used by the inspector.
#
# @yieldparam cell [Cell]
# @return [void]
def each_cell
@cells.each { |row| row.each { |cell| yield cell } }
end
def to_s
@cells.map { |row| row * "" } * "\n"
end
# Creates an inspector for this board.
#
# @return [Inspector] doesn't yet fully implement the output available in this class
def inspector
Inspector.new self
end
private
def cell(r, c)
@cells[r - 1][c - 1]
end
def row_cells(r)
Array.new(9) { |c| @cells[r][c] }
end
def col_cells(c)
Array.new(9) { |r| @cells[r][c] }
end
def box_cells(b)
box_r = b % 3 * 3
box_c = b / 3 * 3
Array.new(9) { |i| @cells[box_r + i % 3][box_c + i / 3] }
end
def connect(group, cells)
cells.each { |cell| cell.join group }
end
### Debugging
public
def inspect
"Board State\n#{to_s}"
end
def debug
debug_cells
debug_rows
debug_cols
debug_boxes
end
def debug_cells
puts "Cell Possibilities"
puts @cells.map { |row| row.map { |cell| cell.debug } * " " } * "\n"
end
def debug_rows
puts "Row Possibilities"
debug_group(@rows)
end
def debug_cols
puts "Column Possibilities"
debug_group(@cols)
end
def debug_boxes
puts "Box Possibilities"
debug_group(@boxes)
end
private
def debug_group(groups)
puts groups.map { |group| group.debug } * "\n"
end
end
end
Group.rb
require 'set'
module Sudoku
# Tracks the cells that make up a single row, column, or 3x3 box, which are still available
# to be set to which values, and the values still left to be set somewhere in the group.
class Group
# Creates an empty group of the given type.
#
# @param type [Symbol] either :row, :col, or :box
# @param index [Fixnum] zero-based index
def initialize(type, index)
@type, @index = type, index
@id = "#{type}-#{index + 1}"
@knowns = {}
@possibles = Hash[(1..9).map { |n| [n, Set.new] }]
end
attr_reader :id, :type, :index
# Makes the cell available for the given value or all values.
#
# @param cell [Cell] the cell that can be set to the value
# @param n [Fixnum or nil] omit to make the cell available for every value
# @return [void]
def available(cell, n = nil)
if n
@possibles[n] << cell
else
@possibles.each_value { |cells| cells << cell }
end
end
# Makes the cell unavailable to receive the value.
#
# If the value has only one cell possibility left, it is set to the value.
#
# @param cell [Cell] the cell that can no longer be set to the value
# @param n [Fixnum] one-based cell value
# @return [void]
def unavailable(cell, n)
# puts "%s - unavail: %s -> %d: %s" % [id, cell.id, n, debug]
cells = @possibles[n]
cells.delete cell
if cells.size == 1 and !known? n
cells.take(1).first.set n, :force
end
end
# Returns true if a cell in this group has been set to the value.
#
# @param n [Fixnum] one-based cell value
# @return [Boolean] true if set; false if still available for this group
def known?(n)
!!@knowns[n]
end
# Returns true if no cell in this group has been set to the value.
#
# @param n [Fixnum] one-based cell value
# @return [Boolean] false if none set; true if still available for this group
def possible?(n)
!@knowns[n]
end
# Returns the number of cells that can still be set to the value.
#
# @param n [Fixnum] one-based cell value
# @return [Fixnum]
def num_possible(n)
@possibles[n].size
end
# Stores that the cell has been set to the value and removes the value as a possible from other cells.
#
# @param cell [Cell] the cell that was just set
# @param n [Fixnum] one-based cell value
# @return [void]
def known(cell, n)
# puts "%s - known : %s -> %d: %s" % [id, cell.id, n, debug]
raise "#{@knowns[n]} in #{@id} already known for #{n}" if known? n
raise "#{cell} in #{@id} not possible for #{n}" unless @possibles[n].delete? cell
@knowns[n] = cell
@possibles[n].each { |possible| possible.unavailable self, n }
end
# Returns a string denoting which values are still possible and in how many cells.
#
# @return [String] first group: possible values are as-is; not possible values are dots;
# second group: number of available cells per cell value
def debug
((1..9).map { |n| possible?(n) ? n : "." } * "") + " " + ((1..9).map { |n| num_possible n } * "")
end
end
end
Cell.rb
require 'set'
module Sudoku
# Models a single cell that tracks the possible values to which it may be set
# and the current value if already set.
class Cell
# Creates an empty cell at the given row and column.
#
# @param r [Fixnum] zero-based row number
# @param c [Fixnum] zero-based column number
def initialize(r, c)
@r, @c = r, c
@id = "(#{r + 1},#{c + 1})"
@initial = @current = nil
@possibles = (1..9).to_set
@groups = []
end
# Joins the given group and makes this cell available for all numbers.
#
# @param group [Group] contains this cell
# @return [void]
def join(group)
@groups << group
group.available self
end
attr_reader :id, :r, :c, :initial, :current
# Returns true if this cell can be set to the value.
#
# @param n [Fixnum] one-based cell value
# @return [Boolean]
def possible?(n)
!known? and @possibles.include? n
end
# Iterates over each value this cell can be set to.
#
# @yieldparam n [Fixnum] one-based cell value
# @return [void]
def each_possible
@possibles.each { |n| yield n } if !known?
end
# Returns true if this cell has been set to a value.
#
# @return [Boolean]
def known?
!!@current
end
# Removes a value from this cell's set of possibilities.
#
# If this leaves the cell with but one possibility, the cell is set to it.
#
# @param n [Fixnum] one-based cell value
# @return [void]
#
# @raise [RuntimeError] if n is the only possibility left
def known(n)
if possible? n
raise "No possibilities left for cell #{@id}" if @possibles.size == 1
@possibles.delete n
set(@possibles.take(1).first, :force) if @possibles.size == 1
end
end
# Notifies this cell's groups that the value is no longer possible for this cell.
#
# @param n [Fixnum] one-based cell value
# @return [void]
#
# @todo Merge with #known.
def unavailable(group, n)
# puts " - unavail: %s -> %d: %s from %s" % [id, n, debug, group.id]
@groups.each { |possible| possible.unavailable self, n }
known n
end
# Sets this cell to the value and notifies each group.
#
# @param n [Fixnum] one-based cell value
# @param reason [Symbol] either :setup, :choose, or :force
# @return [void]
#
# @raise [RuntimeError] if this cell is already set
# @raise [RuntimeError] if the value is not possible for this cell
def set(n, reason)
puts " - %-7s: %s -> %d: %s" % [reason, id, n, debug]
@initial = n if reason == :initial
return if @current == n
raise "cannot change #{@id} from #{@current} to #{n}" if @current
raise "Cannot set #{@id} to #{n}" if !possible? n
@possibles.delete n
@current = n
@groups.each do |group|
group.known self, n
@possibles.each { |n| group.unavailable self, n }
end
@possibles.clear
end
# Returns the current value of this cell if set or a dot if not.
#
# @return [String] single digit or a dot
def to_s
(@current || ".").to_s
end
# Returns a string denoting which values are still possible.
#
# @return [String] possible values are as-is; not possible values are dots
def debug
(1..9).map { |n| possible?(n) ? n : "." } * ""
end
end
end
Test.rb
require 'Board'
module Sudoku
# Creates several test puzzles from easy to evil.
#
# @see http://www.websudoku.com/
module Test
def self.easy
self.test <<-PUZZLE
..38.4.5.
84......7
6....29..
.18.5..9.
2.6.7.4.5
.3..4.86.
..51....8
1......79
.6.5.7.2.
PUZZLE
end
def self.medium
self.test <<-PUZZLE
.5.....7.
9428.....
....6...5
48..765..
.93...78.
..598..14
7...4....
.....8193
.1.....4.
PUZZLE
end
def self.hard
self.test <<-PUZZLE
.....5.8.
.8....5.1
..5.12.69
......17.
.2.....3.
.19......
15.34.7..
8.7....1.
.6.9.....
PUZZLE
end
def self.evil # http://www.websudoku.com/?level=4&set_id=6247568390
self.test <<-PUZZLE
.4.2.....
.....13.7
..5...91.
.8..13...
..3.6.5..
...72..4.
.12...4..
8.69.....
.....2.3.
PUZZLE
end
def self.test(puzzle)
puts "Initial Puzzle"
puts puzzle
b = Board.new puzzle
b.debug
b.inspector.cells
b
end
end
end
Inspector.rb
module Sudoku
# Assists debugging the internal state of the board.
class Inspector
# Stores the board for inspection
#
# @param board [Board]
def initialize(board)
@board = board
end
# Displays the current cell values.
def current
rows = []
row = nil
@board.each_cell do |cell|
if cell.c == 0
row = ""
rows << "" if cell.r != 0 && cell.r % 3 == 0
end
row += " " if cell.c != 0 && cell.c % 3 == 0
row += cell.to_s
rows << row if cell.c == 8
end
puts "Current Puzzle"
puts
puts rows * "\n"
end
# Displays the available values for each cell.
def cells
grid = ([["... " * 9] * 3, ""].flatten * 9).map(&:clone)
@board.each_cell do |cell|
r, c = 4 * cell.r, 4 * cell.c
cell.each_possible do |n|
grid[r + (n - 1) / 3][c + (n - 1) % 3] = n.to_s
end
end
puts "Cell Possibilities"
puts
puts grid * "\n"
end
def inspect
"Inspector"
end
end
end
Sample Test Run
-> require 'Test' -> Sudoku::Test::easy Initial Puzzle ..38.4.5. 84......7 6....29.. .18.5..9. 2.6.7.4.5 .3..4.86. ..51....8 1......79 .6.5.7.2. start : (1,3) -> 3: 123456789 start : (1,4) -> 8: 12.456789 start : (1,6) -> 4: 12.4567.9 start : (1,8) -> 5: 12..567.9 start : (2,1) -> 8: 12.456789 start : (2,2) -> 4: 12.4567.9 start : (2,9) -> 7: 123..67.9 start : (3,1) -> 6: 12..567.9 start : (3,6) -> 2: 123.5.7.9 start : (3,7) -> 9: 1.34...89 start : (4,2) -> 1: 123.56789 start : (4,3) -> 8: .2.456789 start : (4,5) -> 5: .234567.9 start : (4,8) -> 9: .234.67.9 start : (5,1) -> 2: .2345年7月9日 start : (5,3) -> 6: ...4567.9 start : (5,5) -> 7: 1.34..789 force : (3,4) -> 7: 1.3.5.7.. force : (3,2) -> 5: ....5.... force : (3,3) -> 1: 1........ force : (3,5) -> 3: ..3...... start : (5,7) -> 4: 1.345..8. force : (5,9) -> 5: 1.3.5..8. start : (5,9) -> 5: ......... start : (6,2) -> 3: ..3...7.9 force : (5,2) -> 9: ........9 start : (6,5) -> 4: 12.4.6.89 force : (4,1) -> 4: ...4..7.. force : (4,7) -> 7: .23..67.. force : (6,5) -> 4: ......... start : (6,7) -> 8: 12...6.8. force : (5,6) -> 8: 1.3....8. force : (6,7) -> 8: ......... start : (6,8) -> 6: 12...6... start : (7,3) -> 5: .2.45.7.9 force : (6,1) -> 5: ....5.7.. force : (6,3) -> 7: ....5.7.. force : (6,1) -> 5: ......... force : (7,3) -> 5: ......... start : (7,4) -> 1: 1234.6..9 force : (5,8) -> 1: 1.3...... force : (5,4) -> 3: 1.3...... force : (4,9) -> 3: .23...... force : (4,4) -> 2: .2...6... force : (4,6) -> 6: ..3..6... force : (4,4) -> 2: ......... force : (6,9) -> 2: 12....... force : (5,8) -> 1: ......... force : (6,6) -> 1: 1.......9 force : (6,4) -> 9: 1.......9 force : (6,6) -> 1: ......... start : (7,9) -> 8: ...4.6.89 force : (7,8) -> 4: .234..7.. force : (3,9) -> 4: ...4...8. force : (3,8) -> 8: ...4...8. force : (3,9) -> 4: ......... force : (7,8) -> 4: ......... force : (7,9) -> 8: ......... start : (8,1) -> 1: 1.3...7.9 force : (8,1) -> 1: ......... start : (8,8) -> 7: .23...7.. force : (8,8) -> 7: ......... start : (8,9) -> 9: .....6..9 force : (8,9) -> 9: ......... start : (9,2) -> 6: .2...678. force : (9,2) -> 6: ......... force : (8,2) -> 8: .2.....8. force : (9,5) -> 8: .2...6.89 force : (9,5) -> 8: ......... force : (8,2) -> 8: ......... force : (1,9) -> 6: 1....6... force : (9,9) -> 1: 1....6... force : (9,9) -> 1: ......... start : (9,4) -> 5: ...45.... force : (2,6) -> 5: ....5...9 force : (2,4) -> 6: .....6... force : (2,4) -> 6: ......... force : (8,6) -> 3: ..3...... force : (8,6) -> 3: ......... force : (9,4) -> 5: ......... force : (8,7) -> 5: .2..56... force : (9,4) -> 5: ......... force : (8,7) -> 5: ......... force : (7,7) -> 6: .23..6... force : (8,5) -> 6: .2...6... force : (7,5) -> 2: .2...6..9 force : (8,5) -> 6: ......... force : (1,2) -> 2: .2....7.. force : (1,7) -> 1: 1........ force : (2,5) -> 1: 1.......9 force : (1,7) -> 1: ......... force : (1,7) -> 1: ......... force : (2,3) -> 9: .2......9 force : (1,5) -> 9: 1.......9 force : (2,3) -> 9: ......... force : (1,5) -> 9: ......... force : (2,5) -> 1: ......... force : (2,5) -> 1: ......... force : (1,1) -> 7: ......7.. force : (1,1) -> 7: ......... force : (7,2) -> 7: .2....7.. force : (1,2) -> 2: ......... force : (1,1) -> 7: ......... force : (9,6) -> 7: ......7.9 force : (9,6) -> 7: ......... force : (7,2) -> 7: ......... force : (7,6) -> 9: ........9 force : (7,6) -> 9: ......... force : (9,1) -> 9: ..3...7.9 force : (7,1) -> 3: ..3.....9 force : (1,1) -> 7: ......... force : (2,3) -> 9: ......... force : (9,1) -> 9: ......... force : (9,6) -> 7: ......... force : (1,2) -> 2: ......... force : (7,7) -> 6: ......... force : (7,7) -> 6: ......... force : (8,3) -> 2: .2.4..... force : (8,3) -> 2: ......... force : (9,3) -> 4: ...4..... force : (9,3) -> 4: ......... force : (8,4) -> 4: ...45.... force : (8,4) -> 4: ......... force : (9,3) -> 4: ......... force : (9,4) -> 5: ......... start : (9,6) -> 7: ......... start : (9,8) -> 2: .23...... force : (2,7) -> 2: .23...... force : (2,8) -> 3: .23...... force : (9,7) -> 3: .23...... force : (2,7) -> 2: ......... force : (2,8) -> 3: ......... force : (9,7) -> 3: ......... force : (9,8) -> 2: ......... force : (9,8) -> 2: ......... force : (2,7) -> 2: ......... Board State 723894156 849615237 651732984 418256793 296378415 537941862 375129648 182463579 964587321
David Harkness
- 8.9k
- 1
- 27
- 44
lang-rb