Skip to content

Instantly share code, notes, and snippets.

@pwnall pwnall/puzzle.txt
Last active Aug 29, 2015

Embed
What would you like to do?
Quick and dirty Sudoku solver
x x x 4 x 6 x x x
x 5 6 x x x 3 9 x
x 9 x x x x x 4 x
2 x x x 3 x x x 1
x x x 6 x 9 x x x
3 x x x 5 x x x 6
x 4 x x x x x 5 x
x 8 2 x x x 4 7 x
x x x 5 x 2 x x x
require 'set'
class Board
DIGITS = [1, 2, 3, 4, 5, 6, 7, 8, 9]
SIZE = 9
SQ_SIZE = 3
INDEXES = 0..(SIZE - 1)
SQ_INDEXES = 0..(SQ_SIZE - 1)
attr_reader :numbers
def initialize(old_board = nil)
if old_board.nil?
@numbers = Array.new(SIZE) { Array.new(SIZE) }
else
@numbers = old_board.numbers.map { |line| Array.new line }
end
@constraints = nil
@pivots = nil
end
def read(string)
@constraints = nil
@pivots = nil
string.lines.each_with_index do |line, i|
line.split.each_with_index do |char, j|
@numbers[i][j] = (char == 'x') ? nil : char.to_i
end
end
end
def to_s
@numbers.map { |line|
line.map { |i| i || 'x' }.join(' ')
}.join("\n")
end
def constraints
@constraints ||= constraints!
end
def set(i, j, digit)
if @numbers[i][j]
raise "Tried to re-assign position (#{i + 1}, #{j + 1})"
end
@numbers[i][j] = digit
end
def constraints!
constraints = Array.new(SIZE) { Array.new(SIZE) { Set.new(DIGITS) } }
INDEXES.each do |i|
INDEXES.each do |j|
number = @numbers[i][j]
next if number.nil?
INDEXES.each do |k|
constraints[i][k].delete number
constraints[k][j].delete number
end
i_base = (i / SQ_SIZE) * SQ_SIZE
j_base = (j / SQ_SIZE) * SQ_SIZE
SQ_INDEXES.each do |ii|
SQ_INDEXES.each do |jj|
constraints[i_base + ii][j_base + jj].delete number
end
end
constraints[i][j].clear
constraints[i][j] << number
end
end
constraints
end
def pivots
@pivots ||= pivots!
end
def pivots!
constraints = self.constraints
list = []
INDEXES.each do |i|
INDEXES.each do |j|
next unless @numbers[i][j].nil?
priority = constraints[i][j].length
list << [priority, i, j]
end
end
list.reject! { |item| item.first.nil? }
list.sort!
list.map { |item| [item[1], item[2]] }
end
def solve
return self if done?
i, j = *pivots.first
constraints[i][j].each do |digit|
new_board = Board.new self
new_board.set i, j, digit
if answer = new_board.solve
return answer
end
end
return nil
end
def done?
pivots.empty?
end
end
board = Board.new
string = File.read 'puzzle.txt'
board.read string
puts board.solve
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.