Skip to content

Instantly share code, notes, and snippets.

@kahdojay
Last active August 29, 2015 14:18
Show Gist options
  • Save kahdojay/6531bbf8d6ad228b4634 to your computer and use it in GitHub Desktop.
Save kahdojay/6531bbf8d6ad228b4634 to your computer and use it in GitHub Desktop.
class Sudoku
def initialize(board_string)
@original_string = board_string
@guess_cache = []
@board = []
board_string.split('').each_slice(9) { |row| @board << row.map {
|num| num.to_i } }
end
def solve!
@board.each_with_index do |row_value, row_index|
row_value.each_with_index do |cell_value, cell_index|
if blank?(cell_value) && get_possibilities(row_index, cell_index).length == 1
row_value[cell_index] = get_possibilities(row_index, cell_index).pop
solve!
end
end
end
guess_coords = find_zeros
until any_zeros? == false
coord = guess_coords.pop
@guess_cache = get_possibilities(coord[0], coord[1])
guess(coord)
end
end
def guess(coord)
if @guess_cache.length > 0
@board[coord[0]][coord[1]] = @guess_cache.pop
solve!
end
return @board if any_zeros? == false
if any_zeros?
reset
end
return if @guess_cache.length == 0
guess
end
def board
@board.flatten.join('')
end
def to_s
puts "______BOARD______"
@board.each {|row| puts row.join(' ')}
end
def blank?(number)
number.eql?(0) ? true : false
end
def get_horizontal(r_index)
@board[r_index]
end
def get_vertical(c_index)
@board.map { |row| row[c_index] }
end
def get_possibilities(r_index, c_index)
valid_numbers = (1..9).to_a
horizontal = valid_numbers - get_horizontal(r_index)
vertical = valid_numbers - get_vertical(c_index)
box = valid_numbers - get_box(r_index, c_index)
horizontal & vertical & box
end
def find_zeros
guess_coordinates = []
@board.each_with_index do |row_value, row_index|
row_value.each_with_index do |cell_value, cell_index|
if cell_value == 0
guess_coordinates << [row_index, cell_index]
end
end
end
guess_coordinates
end
def any_zeros?
return true if self.find_zeros.length > 0
return false if self.find_zeros.length == 0
end
def reset
initialize(@original_string)
end
def get_box(r_index, c_index)
box1 = [@board[0][0], @board[0][1], @board[0][2],
@board[1][0], @board[1][1], @board[1][2],
@board[2][0], @board[2][1], @board[2][2]]
box2 = [@board[0][3], @board[0][4], @board[0][5],
@board[1][3], @board[1][4], @board[1][5],
@board[2][3], @board[2][4], @board[2][5]]
box3 = [@board[0][6], @board[0][7], @board[0][8],
@board[1][6], @board[1][7], @board[1][8],
@board[2][6], @board[2][7], @board[2][8]]
box4 = [@board[3][0], @board[3][1], @board[3][2],
@board[4][0], @board[4][1], @board[4][2],
@board[5][0], @board[5][1], @board[5][2]]
box5 = [@board[3][3], @board[3][4], @board[3][5],
@board[4][3], @board[4][4], @board[4][5],
@board[5][3], @board[5][4], @board[5][5]]
box6 = [@board[3][6], @board[3][7], @board[3][8],
@board[4][6], @board[4][7], @board[4][8],
@board[5][6], @board[5][7], @board[5][8]]
box7 = [@board[6][0], @board[6][1], @board[6][2],
@board[7][0], @board[7][1], @board[7][2],
@board[8][0], @board[8][1], @board[8][2]]
box8 = [@board[6][3], @board[6][4], @board[6][5],
@board[7][3], @board[7][4], @board[7][5],
@board[8][3], @board[8][4], @board[8][5]]
box9 = [@board[6][6], @board[6][7], @board[6][8],
@board[7][6], @board[7][7], @board[7][8],
@board[8][6], @board[8][7], @board[8][8]]
if (0..2).include?(r_index) && (0..2).include?(c_index)
return box1
elsif (0..2).include?(r_index) && (3..5).include?(c_index)
return box2
elsif (0..2).include?(r_index) && (6..8).include?(c_index)
return box3
elsif (3..5).include?(r_index) && (0..2).include?(c_index)
return box4
elsif (3..5).include?(r_index) && (3..5).include?(c_index)
return box5
elsif (3..5).include?(r_index) && (6..8).include?(c_index)
return box6
elsif (6..8).include?(r_index) && (0..2).include?(c_index)
return box7
elsif (6..8).include?(r_index) && (3..5).include?(c_index)
return box8
elsif (6..8).include?(r_index) && (6..8).include?(c_index)
return box9
else
return nil
end
end
end
# Test boards, increasing in difficulty, uncomment one game at a time to test:
# game = Sudoku.new('619030040270061008000047621486302079000014580031009060005720806320106057160400030')
# game = Sudoku.new('310609005500730000000000900000940000000000109000057060008500006000000003019082040')
# game = Sudoku.new('096040001100060004504810390007950043030080000405023018010630059059070830003590007')
# game = Sudoku.new('105802000090076405200400819019007306762083090000061050007600030430020501600308900')
# game = Sudoku.new('005030081902850060600004050007402830349760005008300490150087002090000600026049503')
# game = Sudoku.new('096040001100060004504810390007950043030080000405023018010630059059070830003590007')
# game = Sudoku.new('105802000090076405200400819019007306762083090000061050007600030430020501600308900')
# game = Sudoku.new('005030081902850060600004050007402830349760005008300490150087002090000600026049503')
# game = Sudoku.new('290500007700000400004738012902003064800050070500067200309004005000080700087005109')
# game = Sudoku.new('080020000040500320020309046600090004000640501134050700360004002407230600000700450')
# game = Sudoku.new('608730000200000460000064820080005701900618004031000080860200039050000100100456200')
# game = Sudoku.new('370000001000700005408061090000010000050090460086002030000000000694005203800149500')
# game = Sudoku.new('000689100800000029150000008403000050200005000090240801084700910500000060060410000')
# game = Sudoku.new('030500804504200010008009000790806103000005400050000007800000702000704600610300500')
# game = Sudoku.new('000075400000000008080190000300001060000000034000068170204000603900000020530200000')
# game = Sudoku.new('300000000050703008000028070700000043000000000003904105400300800100040000968000200')
# game = Sudoku.new('302609005500730000000000900000940000000000109000057060008500006000000003019082040')
p "#{game.find_zeros.length} zeros"
game.to_s
game.solve!
game.to_s
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment