Skip to content

Instantly share code, notes, and snippets.

Embed
What would you like to do?
数独ソルバー
module Sudoku
class Puzzle
ASCII = ".123456789"
BIN = "\000\001\002\003\004\005\006\007\010\011"
def initialize(lines)
if (lines.respond_to? :join)
s = lines.join
else
s = lines.dup
end
s.gsub!(/\s/, "")
raise Invalid, "Grid is the wrong size" unless s.size == 81
if i = s.index(/[^123456789\.]/)
raise Invalid, "Illegal character #{s[i,1]} in puzzle"
end
s.tr!(ASCII, BIN)
@grid = s.unpack('c*')
raise Invalid, "Initial puzzle has duplicates" if has_duplicates?
end
def to_s
(0..8).collect{|r| @grid[r*9,9].pack('c9')}.join("\n").tr(BIN,ASCII)
end
def dup
copy = super
@grid = @grid.dup
copy
end
def [](row, col)
@grid[row*9 + col]
end
def []=(row, col, newvalue)
unless (0..9).include? newvalue
raise Invalid, "illegal cell value"
end
@grid[row*9 + col] = newvalue
end
BoxOfIndex = [
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 each_unknown
0.upto 8 do |row|
0.upto 8 do |col|
index = row*9+col
next if @grid[index] != 0
box = BoxOfIndex[index]
yield row, col, box
end
end
end
def has_duplicates?
0.upto(8) {|row| return true if rowdigits(row).uniq! }
0.upto(8) {|col| return true if coldigits(col).uniq! }
0.upto(8) {|box| return true if boxdigits(box).uniq! }
false
end
AllDigits = [1, 2, 3, 4, 5, 6, 7, 8, 9].freeze
def possible(row, col, box)
AllDigits - (rowdigits(row) + coldigits(col) + boxdigits(box))
end
private
def rowdigits(row)
@grid[row*9,9] - [0]
end
def coldigits(col)
result = []
col.step(80, 9) {|i|
v = @grid[i]
result << v if (v != 0)
}
result
end
BoxToIndex = [0, 3, 6, 27, 30, 33, 54, 57, 60].freeze
def boxdigits(b)
i = BoxToIndex[b]
[
@grid[i], @grid[i+1], @grid[i+2],
@grid[i+9], @grid[i+10], @grid[i+11],
@grid[i+18], @grid[i+19], @grid[i+20]
] - [0]
end
end #----Puzzle
class Invalid < StandardError
end
class Impossible < StandardError
end
def Sudoku.scan(puzzle)
unchanged = false
until unchanged
unchanged = true
rmin,cmin,pmin = nil
min = 10
puzzle.each_unknown do |row, col, box|
p = puzzle.possible(row, col, box)
case p.size
when 0
raise Impossible
when 1
puzzle[row,col] = p[0]
unchanged = false
else
if unchanged && p.size < min
min = p.size
rmin, cmin, pmin = row, col, p
end
end
end
end
return rmin, cmin, pmin
end
def Sudoku.solve(puzzle)
puzzle = puzzle.dup
r,c,p = scan(puzzle)
return puzzle if r == nil
p.each do |guess|
puzzle[r,c] = guess
begin
return solve(puzzle)
rescue Impossible
next
end
end
raise Impossible
end
end
puts Sudoku.solve(Sudoku::Puzzle.new(DATA.readlines))
__END__
8........
..36.....
.7..9.2..
.5...7...
....457..
...1...3.
..1....68
..85...1.
.9....4..
module Sudoku
Rows = 9.times.map {|i|
(i * 9).upto(i * 9 + 8).to_a
}
Cors = 9.times.map {|i|
i.step(80, 9).to_a
}
make = ->(i) {[i,i+1,i+2,i+9,i+10,i+11,i+18,i+19,i+20]}
Blocks = [0,3,6,27,30,33,54,57,60].map(&make)
module_function
def each_section(*types)
types.each do |type|
type.each do |idxs|
yield idxs.map { @field[_1] }
end
end
end
def delete(a, b)
b.each { a.delete(_1) }
end
def flatten(idx)
ary = @field[idx]
if ary.size == 1
@field[idx] = ary[0]
reduct
end
end
def reduct
each_section(Rows, Cors, Blocks) do |section, _|
integers = section.select { _1.instance_of?(Integer) }
section.each { delete(_1, integers) if _1.instance_of?(Array) }
end
end
def think
loop do
tmp = @field.map(&:dup)
reduct
@field.each_index do
flatten(_1) if @field[_1].instance_of?(Array)
end
break if @field == tmp
end
finish if @field.all? { _1.instance_of?(Integer) }
end
def finish
puts @field.each_slice(9).map(&:join)
exit
end
def select_idxs(field)
[*0...81].select { field[_1].instance_of?(Array) }
.sort_by { field[_1].size }
end
def backtracking(field)
idxs = select_idxs(field)
while (idx = idxs.shift)
field[idx].each do |int|
@field = field.map(&:dup)
@field[idx] = int
think
backtracking(@field)
end
end
end
def check(field, tmp = nil)
each_section(Rows, Cors, Blocks) do |section, _|
f = section.select { _1.instance_of?(Integer) }
.tally.select { |k, v| v >= 2 }.empty?
unless f
p tmp if tmp
p field
raise "error!"
end
end
end
def solve(data)
@field = data.flat_map {
_1.chars.map { |c| c == "." ? (1..9).to_a : c.to_i }
}
think
backtracking(@field)
end
end
Sudoku.solve(DATA.readlines(chomp: true))
__END__
3.61....7
1.....2.9
7..864..1
.....8...
.3..1..9.
.....5...
4..731..5
5.....9.4
8.14....6
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment