Skip to content

Instantly share code, notes, and snippets.

@Winslett
Created September 23, 2018 03:24
Show Gist options
  • Save Winslett/017f9e1f548a593e5a84757c754972e8 to your computer and use it in GitHub Desktop.
Save Winslett/017f9e1f548a593e5a84757c754972e8 to your computer and use it in GitHub Desktop.
#!/usr/bin/env ruby
# construct the array of possibilities
def construct_board(board)
unknown_count = 0
board.each_with_index do |row, row_index|
row.each_with_index do |cell_value, column_index|
if cell_value.nil?
board[row_index][column_index] = (1..9).to_a
unknown_count += 1
end
end
end
return board, unknown_count
end
def solve_function(board, prior_unknown_count)
board.each_with_index do |row, row_index|
row.each_with_index do |cell_value, column_index|
if cell_value.is_a?(Integer)
# filter rows
row.each_with_index do |filter_cell_value, filter_column_index|
next if filter_cell_value.is_a?(Integer)
filter_cell_value.delete(cell_value)
end
# filter columns
board.each do |filter_row_values|
next if filter_row_values[column_index].is_a?(Integer)
filter_row_values[column_index].delete(cell_value)
end
# filter blocks
row_block_start, column_block_start = ((row_index / 3.to_f).floor * 3), ((column_index / 3.to_f).floor * 3)
row_block_start.upto(row_block_start + 2) do |filter_row_index|
column_block_start.upto(column_block_start + 2) do |filter_column_index|
next if board[filter_row_index][filter_column_index].is_a?(Integer)
board[filter_row_index][filter_column_index].delete(cell_value)
end
end
end
end
end
unknown_count = 0
guesses = []
# assign for squares where only one possibility exists
board.each_with_index do |row, row_index|
row.each_with_index do |cell, column_index|
if cell.is_a?(Array) && cell.length == 0
raise "Dead end"
elsif cell.is_a?(Array)
guesses << {length: cell.length, row: row_index, column: column_index}
unknown_count += 1
end
end
end
puts [prior_unknown_count, unknown_count].inspect
# guess
if unknown_count == 0
puts "Solved"
board.each do |row|
puts row.join(" ")
end
exit
elsif prior_unknown_count == unknown_count
puts "We are going to start guessing."
guesses.sort_by { |g| g[:length] }.each do |guess|
board[guess[:row]][guess[:column]].each do |guess_value|
guess_board = board
guess_board[guess[:row]][guess[:column]] = guess_value
solve_function(guess_board, unknown_count)
end
end
else
puts "Unknown count: #{unknown_count}"
solve_function(board, unknown_count)
end
end
puzzle = [
[ 5, 3, nil, nil, 7, nil, nil, nil, nil],
[ 6, nil, nil, 1, 9, 5, nil, nil, nil],
[nil, 9, 8, nil, nil, nil, nil, 6, nil],
[ 8, nil, nil, nil, 6, nil, nil, nil, 3],
[ 4, nil, nil, 8, nil, 3, nil, nil, 1],
[ 7, nil, nil, nil, 2, nil, nil, nil, 6],
[nil, 6, nil, nil, nil, nil, 2, 8, nil],
[nil, nil, nil, 4, 1, 9, nil, nil, 5],
[nil, nil, nil, nil, 8, nil, nil, 7, 9]
]
puzzle, unknown_count = construct_board(puzzle)
puts unknown_count.inspect
solve_function(puzzle, unknown_count)
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment