class SudokuSolverNg

More constraints: www.scanraid.com/BasicStrategies.htm www.krazydad.com/blog/2005/09/29/an-index-of-sudoku-strategies/ www2.warwick.ac.uk/fac/sci/moac/currentstudents/peter_cock/python/sudoku/

Constants

VERSION

Attributes

cols[R]
peers[R]
rows[R]
squares[R]
unitlist[R]
units[R]

Public Class Methods

new() click to toggle source
# File lib/sudokusolver_ng.rb, line 39
def initialize()
  @rows = ('A'..'I').to_a
  @cols = ('1'..'9').to_a
  @squares = cross(@rows, @cols)
  @unitlist = Array.new
  cols.each { |c| @unitlist.push(cross(rows, [c])) }
  rows.each { |r| @unitlist.push(cross([r], cols)) }
  for rb in ['ABC','DEF','GHI'] do
    for cb in ['123','456','789'] do
      @unitlist << cross(rb.split(''),cb.split(''))
    end
  end

  @units = Hash.new
  squares.each do |s|
    @units[s] = Array.new
    unitlist.each do |u|
      u.each do |x|
        @units[s].push(u) if s == x
      end
    end
  end

  @peers = Hash.new
  squares.each do |s|
    @peers[s] = Array.new
    units[s].each do |u|
      u.each { |s2| @peers[s] << s2 if s2 != s }
    end
  end

end

Public Instance Methods

assign(values, s, d) click to toggle source

Assign a value to a square in the Sudoku grid: Eliminate all other possible digits from the square by calling the eliminate function (mutually recursive)

# File lib/sudokusolver_ng.rb, line 89
def assign(values, s, d)
  values[s].split('').each do |d2|
    unless d2 == d
      return false if eliminate(values, s, d2) == false
    end
  end
  return values
end
check_solution(solution) click to toggle source

Verify the Sudoku solution

# File lib/sudokusolver_ng.rb, line 196
def check_solution(solution)
  values = Hash.new
  for s,d in squares.zip(solution.split(''))
    values[s] = d
  end

  unitlist.each do |u|
    tmp = Hash.new
    u.each do |s|
      tmp[values[s]] = true
    end
    return false unless tmp.keys.length == 9
  end
  return true
end
cross(a, b) click to toggle source

Cross-product

# File lib/sudokusolver_ng.rb, line 29
def cross(a, b)
  cp = Array.new # cross product
  a.each do |x|
    b.each do |y|
      cp << x+y
    end
  end
  return cp
end
eliminate(values, s, d) click to toggle source

Remove a possibility from a square. Recursively propagate the constraints: look at the source code for how this is done.

# File lib/sudokusolver_ng.rb, line 100
def eliminate(values, s, d)
  return values unless values[s].include?(d) ## Already eliminated.

  values[s] = values[s].sub(d,'') # Remove the digit from the string of possibilities
  #  values[s].sub!(d,'') => why doesn't sub!() work?

  return false if values[s].length == 0 # Contradiction: no more values (no more digits can be assigned)

  # Remove digit from all peers
              # If the square has only one remaining possibility, that is the assigned value for the square and
              # that value must be removed from all that square's peers.
  peers[s].each { |s2| return false unless eliminate(values, s2, values[s]) } if values[s].length == 1

  # Assign the digit to the square if, by elimination
              # this is the only square that has the digit as a possibility
  units[s].each do |u|
    dplaces = Array.new
    u.each { |s2| dplaces << s2 if values[s2].include?(d) }
    return false if dplaces.length == 0 # bad
    return false if assign(values, dplaces[0], d) == false if dplaces.length == 1
  end
  return values
end
parse_grid(g) click to toggle source

A grid is an 81 character string composed of the digits 0-9 A blank is represented as a period.

# File lib/sudokusolver_ng.rb, line 74
def parse_grid(g)
  g = g.chomp
  g = g.split('')
  values = Hash.new
  # Initially any square can be anything.
  squares.each { |s| values[s] = "123456789" }
  for s,d in squares.zip(g)
    return false unless assign(values, s, d) if d =~ /\d/
  end
  return values
end
print_grid(values) click to toggle source

Print a text Sudoku grid to STDOUT

string_solution(values) click to toggle source

Transform the solution into an 81 character string

# File lib/sudokusolver_ng.rb, line 187
def string_solution(values)
  solution = ""
  squares.each do |s|
    solution += values[s]
  end
  return solution
end