class Sudoku
require 'pry'
Constants
- BLANK_BOARD
Attributes
difficulty[RW]
removed_values[RW]
solution[RW]
starting_board[RW]
Public Class Methods
new( holes = 40, status_messages = false )
click to toggle source
# File lib/sudoku_wizard.rb, line 18 def initialize( holes = 40, status_messages = false ) start_time = Time.now self.difficulty = holes > 54 ? 54 : holes @status_messages = status_messages puts "Generating Game..." if @status_messages generate_game return if !@status_messages puts "Board Generated in" puts "#{ format_number(@iteration_counter) } Iterations" puts " #{ Time.now - start_time } seconds" end
Public Instance Methods
box_safe(puzzle_matrix, empty_cell, num)
click to toggle source
# File lib/sudoku_wizard.rb, line 96 def box_safe (puzzle_matrix, empty_cell, num) box_start_row = (empty_cell[:row_i] - (empty_cell[:row_i] % 3)) box_start_col = (empty_cell[:col_i] - (empty_cell[:col_i] % 3)) (0..2).to_a.each do |box_row| (0..2).to_a.each do |box_col| return false if puzzle_matrix[box_start_row + box_row][box_start_col + box_col] == num end end return true end
col_safe(puzzle_matrix, empty_cell, num)
click to toggle source
# File lib/sudoku_wizard.rb, line 92 def col_safe (puzzle_matrix, empty_cell, num) !puzzle_matrix.any?{|row| row[ empty_cell[:col_i] ] == num} end
find_next_empty_cell(puzzle_matrix)
click to toggle source
# File lib/sudoku_wizard.rb, line 69 def find_next_empty_cell(puzzle_matrix) # Find the coordinates of the next unsolved cell empty_cell = {row_i:"",col_i:""} for row in puzzle_matrix do next_zero_index = row.find_index(0) empty_cell[:row_i] = puzzle_matrix.find_index(row) empty_cell[:col_i] = next_zero_index return empty_cell if empty_cell[:col_i] end return false end
generate_game()
click to toggle source
# File lib/sudoku_wizard.rb, line 32 def generate_game begin # @start_time = Time.now @iteration_counter = 0 @poke_counter = 0 self.solution = new_solved_board self.starting_board = poke_holes(self.solution.map(&:clone)) rescue => error puts error puts "#{ format_number(@iteration_counter) } iterations, Restarting" if @status_messages generate_game end end
new_solved_board()
click to toggle source
# File lib/sudoku_wizard.rb, line 46 def new_solved_board new_board = BLANK_BOARD.map(&:clone) solve(new_board) new_board end
poke_holes(puzzle_matrix)
click to toggle source
# File lib/sudoku_wizard.rb, line 109 def poke_holes(puzzle_matrix) self.removed_values = [] val = (0...81).to_a.shuffle while self.removed_values.length < self.difficulty next_val = val.pop raise "impossible game" if !next_val row_i = next_val / 9 col_i = next_val % 9 next if (puzzle_matrix[row_i][col_i] == 0) self.removed_values.push({row_i: row_i, col_i: col_i, val: puzzle_matrix[row_i][col_i] }) puzzle_matrix[row_i][col_i] = 0 proposed_board = puzzle_matrix.map(&:clone) puzzle_matrix[row_i][col_i] = self.removed_values.pop[:val] if multiple_solutions?( proposed_board ) end puzzle_matrix end
render(board_name)
click to toggle source
# File lib/sudoku_wizard.rb, line 131 def render(board_name) b = self.send(board_name).map{|row| row.map{|col| col == 0 ? " " : col} } puts " ┏━━━┳━━━┳━━━┱───┬───┬───┲━━━┳━━━┳━━━┓ ┃ #{b[0][0]} ┃ #{b[0][1]} ┃ #{b[0][2]} ┃ #{b[0][3]} │ #{b[0][4]} │ #{b[0][5]} ┃ #{b[0][6]} ┃ #{b[0][7]} ┃ #{b[0][8]} ┃ ┣━━━╋━━━╋━━━╉───┼───┼───╊━━━╋━━━╋━━━┫ ┃ #{b[1][0]} ┃ #{b[1][1]} ┃ #{b[1][2]} ┃ #{b[1][3]} │ #{b[1][4]} │ #{b[1][5]} ┃ #{b[1][6]} ┃ #{b[1][7]} ┃ #{b[1][8]} ┃ ┣━━━╋━━━╋━━━╉───┼───┼───╊━━━╋━━━╋━━━┫ ┃ #{b[2][0]} ┃ #{b[2][1]} ┃ #{b[2][2]} ┃ #{b[2][3]} │ #{b[2][4]} │ #{b[2][5]} ┃ #{b[2][6]} ┃ #{b[2][7]} ┃ #{b[2][8]} ┃ ┡━━━╇━━━╇━━━╋━━━╈━━━╈━━━╋━━━╇━━━╇━━━┩ │ #{b[3][0]} │ #{b[3][1]} │ #{b[3][2]} ┃ #{b[3][3]} ┃ #{b[3][4]} ┃ #{b[3][5]} ┃ #{b[3][6]} │ #{b[3][7]} │ #{b[3][8]} │ ├───┼───┼───╊━━━╋━━━╋━━━╉───┼───┼───┤ │ #{b[4][0]} │ #{b[4][1]} │ #{b[4][2]} ┃ #{b[4][3]} ┃ #{b[4][4]} ┃ #{b[4][5]} ┃ #{b[4][6]} │ #{b[4][7]} │ #{b[4][8]} │ ├───┼───┼───╊━━━╋━━━╋━━━╉───┼───┼───┤ │ #{b[5][0]} │ #{b[5][1]} │ #{b[5][2]} ┃ #{b[5][3]} ┃ #{b[5][4]} ┃ #{b[5][5]} ┃ #{b[5][6]} │ #{b[5][7]} │ #{b[5][8]} │ ┢━━━╈━━━╈━━━╋━━━╇━━━╇━━━╋━━━╈━━━╈━━━┪ ┃ #{b[6][0]} ┃ #{b[6][1]} ┃ #{b[6][2]} ┃ #{b[6][3]} │ #{b[6][4]} │ #{b[6][5]} ┃ #{b[6][6]} ┃ #{b[6][7]} ┃ #{b[6][8]} ┃ ┣━━━╋━━━╋━━━╉───┼───┼───╊━━━╋━━━╋━━━┫ ┃ #{b[7][0]} ┃ #{b[7][1]} ┃ #{b[7][2]} ┃ #{b[7][3]} │ #{b[7][4]} │ #{b[7][5]} ┃ #{b[7][6]} ┃ #{b[7][7]} ┃ #{b[7][8]} ┃ ┣━━━╋━━━╋━━━╉───┼───┼───╊━━━╋━━━╋━━━┫ ┃ #{b[8][0]} ┃ #{b[8][1]} ┃ #{b[8][2]} ┃ #{b[8][3]} │ #{b[8][4]} │ #{b[8][5]} ┃ #{b[8][6]} ┃ #{b[8][7]} ┃ #{b[8][8]} ┃ ┗━━━┻━━━┻━━━┹───┴───┴───┺━━━┻━━━┻━━━┛ " end
row_safe(puzzle_matrix, empty_cell, num)
click to toggle source
# File lib/sudoku_wizard.rb, line 88 def row_safe (puzzle_matrix, empty_cell, num) !puzzle_matrix[ empty_cell[:row_i] ].find_index(num) end
safe(puzzle_matrix, empty_cell, num)
click to toggle source
# File lib/sudoku_wizard.rb, line 82 def safe(puzzle_matrix, empty_cell, num) row_safe(puzzle_matrix, empty_cell, num) && col_safe(puzzle_matrix, empty_cell, num) && box_safe(puzzle_matrix, empty_cell, num) end
solve(puzzle_matrix)
click to toggle source
# File lib/sudoku_wizard.rb, line 52 def solve (puzzle_matrix) empty_cell = find_next_empty_cell(puzzle_matrix) return puzzle_matrix if !empty_cell #If no empty cells, we are done. Return the completed puzzle # Fill in the empty cell for num in (1..9).to_a.shuffle do @iteration_counter += 1 raise "too make buil iterations" if (@iteration_counter > 1_000_000) if safe(puzzle_matrix, empty_cell, num) # For a number, check if it safe to place that number in the empty cell puzzle_matrix[empty_cell[:row_i]][empty_cell[:col_i]] = num # if safe, place number return puzzle_matrix if solve(puzzle_matrix) # Recursively call solve method again. puzzle_matrix[empty_cell[:row_i]][empty_cell[:col_i]] = 0 end end return false #If unable to place a number, return false, trigerring previous iteration to move to next number end
Private Instance Methods
bring_index_to_front(index, array)
click to toggle source
# File lib/sudoku_wizard.rb, line 157 def bring_index_to_front(index, array) starting_point = array.slice(index) array.delete_at(index) array.unshift(starting_point) end
empty_cell_coords(board)
click to toggle source
# File lib/sudoku_wizard.rb, line 203 def empty_cell_coords(board) (0..8).to_a.each_with_object( [] ) do |row, empty_cells| (0..8).to_a.each do |col| next if board[row][col] != 0 empty_cells << {row:row, col:col} end end end
fill_from_array(board, empty_cell_array)
click to toggle source
# File lib/sudoku_wizard.rb, line 180 def fill_from_array(board, empty_cell_array) empty_cell = next_still_empty_cell(board, empty_cell_array) return board if !empty_cell for num in (1..9).to_a.shuffle do @poke_counter += 1 raise "too many pokes: #{@poke_counter}, #{board}, removed: #{@removed_values.length}" if (@poke_counter > 10_000_000) if safe(board, empty_cell, num) board[empty_cell[:row_i]][empty_cell[:col_i]] = num return board if fill_from_array(board, empty_cell_array) board[empty_cell[:row_i]][empty_cell[:col_i]] = 0 end end false end
format_number(integer)
click to toggle source
# File lib/sudoku_wizard.rb, line 215 def format_number(integer) number_of_digits = Math.log(integer, 10).floor + 1 number_of_segments = (number_of_digits / 3.0).ceil int_as_array = integer.to_s.split("") formatted_array = [] index = 1 while index <= number_of_digits do formatted_array.unshift(int_as_array[ index * -1 ] ) formatted_array.unshift("_") if index % 3 == 0 && index != number_of_digits index += 1 end formatted_array.join("") end
multiple_solutions?(board_to_check)
click to toggle source
# File lib/sudoku_wizard.rb, line 165 def multiple_solutions?(board_to_check) possible_solutions = [] empty_cell_array = empty_cell_coords(board_to_check) empty_cell_array.each_with_index do |coord, index| board_clone = board_to_check.map{|row| row.map{|col| col}} empty_cell_array_clone = empty_cell_array.map{|coord| coord} bring_index_to_front(index, empty_cell_array_clone) this_solution = fill_from_array( board_clone, empty_cell_array_clone ) possible_solutions.push(this_solution) return true if possible_solutions.uniq.length > 1 end return false end
next_still_empty_cell(board, empty_cell_array)
click to toggle source
# File lib/sudoku_wizard.rb, line 195 def next_still_empty_cell(board, empty_cell_array) empty_cell_array.each do |coords| next if board[ coords[:row] ][ coords[:col] ] != 0 return {row_i: coords[:row], col_i: coords[:col] } end false end