Skip to content

Instantly share code, notes, and snippets.

@youjingwong

youjingwong/sample.unsolved.txt

Forked from nextacademy-private/sample.unsolved.txt
Last active August 29, 2015 14:07
Show Gist options

  • Select an option

    Learn more about clone URLs
  • Save youjingwong/cc33db1c3ec42e87afe6 to your computer and use it in GitHub Desktop.

Select an option

Learn more about clone URLs
Save youjingwong/cc33db1c3ec42e87afe6 to your computer and use it in GitHub Desktop.
Download ZIP
Raw
sample.unsolved.txt
096040001100060004504810390007950043030080000405023018010630059059070830003590007
302609005500730000000000900000940000000000109000057060008500006000000003019082040
000075400000000008080190000300001060000000034000068170204000603900000020530200000
300000000050703008000028070700000043000000000003904105400300800100040000968000200
290500007700000400004738012902003064800050070500067200309004005000080700087005109
080020000040500320020309046600090004000640501134050700360004002407230600000700450
608730000200000460000064820080005701900618004031000080860200039050000100100456200
370000001000700005408061090000010000050090460086002030000000000694005203800149500
030500804504200010008009000790806103000005400050000007800000702000704600610300500
000689100800000029150000008403000050200005000090240801084700910500000060060410000
Raw
sudoku.rb
class Sudoku
def initialize(board_string)
@ori_board_array_flat = board_string.split("")
@ori_board_array = @ori_board_array_flat.map { |x| x == "0" ? Array(1..9) : x }
@ori_board_array = Array.new(9) { @ori_board_array.shift(9) }
@attempt = 0
end
#Create temp board for manipulation to preserve original board
def create_temp_board
@board_array = Marshal.load(Marshal.dump(@ori_board_array))
end
#Create mapping of arrays in each 3x3 box
def create_hash_table
hash_table = Hash.new {|h,k| h[k]=[]}
for i in (0...9)
for j in (0...9)
if @board_array[i][j].class != Array
key = "#{i/3}#{j/3}"
hash_table[key] << @board_array[i][j]
end
end
end
hash_table
end
def solve!
start = Time.now
## Compares possible number array with its column, row, and box,
## deleting number
completed = false
until completed##until board is valid
create_temp_board
@attempt += 1
break if @attempt == 10000
unsolved = true
while unsolved##attempt to fill temp board
@hash_table = create_hash_table
eliminate_invalid_numbers
## Iterate through each box, looking for arrays of 1 length,
## which shows that there is 100% possibility of it being the number.
## converts to string.
unsolved = false
min_array_length = 100
placed_value = false #placed value into box
array_found = false
min_array_row = 10
min_array_col = 10
catch :inserted_value do
@board_array.each_with_index do |row, row_num|
row.each_with_index do |value, col_num|
if value.class == Array && value.length == 1
@board_array[row_num][col_num] = value[0].to_s
unsolved = true
placed_value = true
array_found = true
throw :inserted_value #changes one item at a time to prevent mistakes
elsif value.class == Array && value.length < min_array_length
min_array_length = value.length
min_array_row = row_num
min_array_col = col_num
array_found = true
end
end
end
end
#If there is no array with single element, but there are arrays, take one with the minimum length,
# and choose a random element to try
if placed_value == false && array_found
current_array_length = (@board_array[min_array_row][min_array_col].length)
index_of_value = rand(current_array_length)
@board_array[min_array_row][min_array_col] = @board_array[min_array_row][min_array_col][index_of_value].to_s
unsolved = true
end
#If all elements on board are strings.
unless array_found
unsolved = false
end
end
completed = check_solved?
end
(@attempt == 10000)? (puts "Failed to find solution after 10000 attempts.") : (puts "attempts number: #{@attempt}")
finished = Time.now
puts ("Time taken: #{finished - start}")
return @board_array
end
def check_solved?
test_array = @board_array.flatten
test_array.each do |num|
if num == ""
return false
end
end
return true
end
def eliminate_invalid_numbers
@board_array.each_with_index do |row, row_num|
row.each_with_index do |value, col_num|
if value.class == Array
value = compare_del_row(value, row_num)
value = compare_del_col(value, col_num)
value = compare_box(value, row_num, col_num)
@board_array[row_num][col_num] == value
end
end
end
end
def compare_del_row(value, row)
for i in (0...9)
if @board_array[row][i].class == String
value.delete(@board_array[row][i].to_i)
end
end
return value
end
def compare_del_col(value, col)
for i in (0...9)
if @board_array[i][col].class == String
value.delete(@board_array[i][col].to_i)
end
end
return value
end
def compare_box(value, row, col)
@hash_table["#{row/3}#{col/3}"].each do |num|
value.delete(num.to_i)
end
return value
end
def board
puts "-"*21
@board_array.each_with_index do |row, index|
puts "#{row[0]} #{row[1]} #{row[2]} | #{row[3]} #{row[4]} #{row[5]} | #{row[6]} #{row[7]} #{row[8]}"
if index%3 == 2
puts "-"*21
end
end
end
end
# The file has newlines at the end of each line, so we call
# String#chomp to remove them.
board_string = File.readlines('sample.unsolved.txt').first.chomp
game = Sudoku.new(board_string)
# Remember: this will just fill out what it can and not "guess"
game.solve!
puts game.board
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment