Skip to content

Instantly share code, notes, and snippets.

@takuma-saito

takuma-saito/0_sudoku.rb

Last active Oct 21, 2020
Embed
What would you like to do?
sudoku.rb
module Puzzle
class Board
include Enumerable
def initialize(board)
@board = board
end
def rows(row)
@board[row * 9, 9].compact
end
def cols(col)
(0..8).map {|d| @board[d * 9 + col]}.compact
end
BoxToPos = [0, 3, 6, 27, 30, 33, 54, 57, 60].freeze
PosToBox = [
0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2, 0, 0, 0, 1, 1, 1, 2, 2, 2,
3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5, 3, 3, 3, 4, 4, 4, 5, 5, 5,
6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8, 6, 6, 6, 7, 7, 7, 8, 8, 8,
].freeze
def boxes(box)
[0, 1, 2, 9, 10, 11, 18, 19, 20].map {|d| @board[box + d]}.compact
end
AllDigits = [1, 2, 3, 4, 5, 6, 7, 8, 9]
def possible_digits(row, col, idx)
AllDigits - (rows(row) + cols(col) + boxes(BoxToPos[PosToBox[idx]]))
end
def []=(row, col, val)
@board[row * 9 + col] = val
end
def dup
copy = super
@board = @board.dup
copy
end
def to_s
(0..8).map {|i| @board[i*9, 9].map {|x| x.nil? ? " " : x}.join}.join("\n")
end
def each_unknown
@board.each.with_index do |val, idx|
next unless val.nil?
yield(idx/9, idx%9, idx)
end
end
def self.from(io)
chars = io.readlines
.map {|n| n.chomp.chars.map {|x| x === 'x' ? nil : x.to_i}}.flatten
fail unless chars.length === 81 && chars.all? {|c| c.nil? || c.is_a?(Integer)}
new(chars)
end
end
class Invalid < StandardError; end
class Solver
def possible_digits_min(board)
result = nil
board.each_unknown do |row, col, idx| # TODO
digits = board.possible_digits(row, col, idx)
new_result = {row: row, col: col, digits: digits}
case digits.length
when 0
raise Invalid
when 1
return new_result
else
result = new_result if result.nil? || (result[:digits].length > digits.length)
end
end
result
end
def scan(board)
count = 0
loop do
result = possible_digits_min(board)
p result
puts board.to_s
puts '~~~'
fail if (count += 1) > 81
return result if result.nil? || (result[:digits].length != 1)
board[result[:row], result[:col]] = result[:digits].first
end
end
def solve(board)
b = board.dup
result = scan(board)
return board if result.nil?
result[:digits].each do |guess|
board[result[:row], result[:col]] = guess
begin
return solve(board)
rescue Invalid
board = b.dup # TODO
end
end
end
end
end
include Puzzle
puts Solver.new.solve(Board.from($stdin)).to_s
xxxxxxxxx
xxxxxx5x7
x59x2x6xx
14x7xxx8x
x6xx8xx5x
3xx651xxx
xxx9xxxx1
8xxxx4x9x
xx3xxxx48
xxxxxxxxx
xxxxxxx27
4xx6x8xxx
x71xxx3xx
2385x6419
9641xx75x
395x278xx
182x6x974
x468192x5
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.