Skip to content

Instantly share code, notes, and snippets.

@LolWalid
Created May 27, 2016 16:41
Show Gist options
  • Save LolWalid/093ff7bea4240abe67e15199261f7031 to your computer and use it in GitHub Desktop.
Save LolWalid/093ff7bea4240abe67e15199261f7031 to your computer and use it in GitHub Desktop.
Sudoku Solver in ruby Langage
require 'sudoku'
require 'sudoku_solver'
data = [
[9, 3, 4, 1, 7, 2, 6, 8, 5],
[0, 0, 5, 0, 9, 0, 2, 0, 1],
[8, 0, 0, 0, 4, 0, 0, 0, 0],
[0, 0, 0, 0, 8, 0, 0, 0, 0],
[0, 0, 0, 7, 0, 0, 0, 0, 0],
[0, 0, 0, 0, 2, 6, 0, 0, 9],
[2, 0, 0, 3, 0, 0, 0, 0, 6],
[0, 0, 0, 2, 0, 0, 9, 0, 0],
[0, 0, 1, 9, 0, 4, 5, 7, 0]
]
sudoku = Sudoku.rows(data)
SudokuSolver.new(sudoku).solve
require 'matrix'
# Sudoku
class Sudoku < Matrix
def display
print_tirets
each_with_index do |value, index_row, index_column|
print_pipe if index_column % 3 == 0
print_value(value)
if index_column == (column_count - 1)
print "|\n"
print_tirets if (index_row + 1) % 3 == 0
end
end
end
def valid?
each_with_index do |value, index_row, index_column|
next if valid_value?(value, index_row, index_column)
return false
end
true
end
def valid_value?(value, index_row, index_column, new_value = false)
return true if value == 0
max_count_allowed = new_value ? 1 : 2
row(index_row).count(value) < max_count_allowed &&
column(index_column).count(value) < max_count_allowed &&
count_in_block(value, index_row, index_column) < max_count_allowed
end
def play(value, index_row, index_column)
self[index_row, index_column] = value
end
def next_empty_case
each_with_index do |value, index_row, index_column|
return [index_row, index_column] if value == 0
end
[nil, nil]
end
private
def print_value(value)
if value == 0
print format(' ')
else
print format('%2d ', value)
end
end
def print_tirets
print '---' * (row_count + 1) + "\n"
end
def print_pipe
print '|'
end
def count_in_block(value, index_row, index_column)
block_from_coords(index_row, index_column).to_a.flatten.count(value)
end
def block_from_coords(index_row, index_column)
b = self
r = index_row - index_row % 3
c = index_column - index_column % 3
b.minor(r..(r + 2), c..(c + 2))
end
end
# Sudoku Solver
class SudokuSolver
def initialize(sudoku)
@sudoku = sudoku
end
def solve(position = 0)
@sudoku.display
return true if position == 9 * 9
index_row = position / 9
index_column = position % 9
return solve(position + 1) if @sudoku[index_row, index_column] != 0
(1..9).each do |test_value|
if @sudoku.valid_value?(test_value, index_row, index_column, true)
@sudoku.play(test_value, index_row, index_column)
return true if solve(position + 1)
end
end
@sudoku.play(0, index_row, index_column)
false
end
end
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment