Skip to content

Instantly share code, notes, and snippets.

@obelisk68
Last active March 25, 2022 04:21
Show Gist options
  • Save obelisk68/c26cccee422f4e794218ef7dd3329bcf to your computer and use it in GitHub Desktop.
Save obelisk68/c26cccee422f4e794218ef7dd3329bcf to your computer and use it in GitHub Desktop.
数独ソルバー
module Sudoku
Size = 81
Length = 9
INDEXS = [0, 3, 6, 27, 30, 33, 54, 57, 60]
.map { |i| [i, i+1, i+2, i+9, i+10, i+ 11, i+18, i+19, i+20] }
class CertainMap
def initialize(ary)
@field = ary
end
attr_reader :field
def make_possible_map
PossibleMap.new(self)
end
def each_certain_number
@field.each_with_index do |num, i|
yield(num, i) if num.nonzero?
end
end
def solved?
@field.none? { |num| num.zero? }
end
def inspect
@field.each_slice(Length).map {|row|
row.map { |i| i.zero? ? "." : i.to_s }.join
}.join("\n")
end
alias :to_s :inspect
end
class PossibleMap
def initialize(certain_map)
@c_map = certain_map
@field = Array.new(Size) { [*1..Length] }
@field.map!.with_index {|e, i|
x = @c_map.field[i]
x == 0 ? e : [x]
}
end
attr_reader :c_map
attr_accessor :field
def inspect
@field.map(&:join).each_slice(Length).map { _1.join(" ") }
end
def each_element(i)
x = i % Length
y = i / Length
(y * Length...(y + 1) * Length).each do |j|
if j != i && @field[j].size != 1
yield @field[j]
end
end
Length.times do |i1|
j = i1 * Length + x
if j != i && @field[j].size != 1
yield @field[j]
end
end
INDEXS[ y / 3 * 3 + x / 3].each do |j|
if j != i && @field[j].size != 1
yield @field[j]
end
end
end
def update1!
changed = false #変更があったか
@c_map.each_certain_number do |num, idx|
each_element(idx) do |e|
f = e.delete(num)
changed = true if f
end
end
@c_map = make_certain_map
changed
end
def update2!
changed = false #変更があったか
(1..Length).each do |kind|
changed = true if update2_sub(kind)
end
@c_map = make_certain_map
changed
end
def update2_sub(kind)
changed = false
all_blocks do |blocks|
e = search_one(blocks, kind)
next unless e
@field[e[1]] = [kind]
changed = true
end
changed
end
#1つの行(列)に「確定しているkind」がない場合、他の「確定している数字」を消す。
#そして、「kindを含むelement」が列に1つだけある場合、その「確定しているkind」が決まる。
def search_one(blocks, kind)
return nil unless blocks.none? { |block| block[0] == [kind] }
bs = blocks.filter_map { |b| !b[0].include?(kind) || b[0].size == 1 ? nil : b }
bs.size == 1 ? bs[0] : nil
end
def all_blocks
Length.times do |y|
yield Length.times.map { [@field[j = y * Length + _1], j] }
end
Length.times do |x|
yield Length.times.map { [@field[j = _1 * Length + x], j] }
end
Length.times do |i|
yield INDEXS[i].map { [@field[_1], _1] }
end
end
def make_certain_map
tmp = @field.map {|e|
case e.size
when 0
raise
when 1
e[0]
else
0
end
}
CertainMap.new(tmp)
end
def solved?
@c_map.solved?
end
def dup
tmp = self.field
pm = PossibleMap.new(@c_map)
pm.field = tmp
pm
end
def min
@field.map.with_index { |e, i| [e, i] }
.reject { _1[0].size == 1 }.min_by { _1[0].size }
end
end
module_function
def solve(init_map)
im = init_map.flat_map { _1.chomp.chars.map(&:to_i) }
cm = CertainMap.new(im)
pm = cm.make_possible_map
update(pm)
puts pm.c_map
pm = try(pm) unless pm.solved?
puts pm.c_map
end
def update(pm)
loop do
f1 = update1(pm)
f2 = update2(pm)
break if !f1 && !f2
end
end
def update1(pm)
f1 = false
loop do
f = pm.update1!
f1 = true if f
break unless f
end
f1
end
def update2(pm)
f2 = false
loop do
f = pm.update2!
f2 = true if f
break unless f
end
f2
end
def try(pm)
return pm if pm.solved?
tmp = pm.dup
e, idx = tmp.min
p [e, idx]
exit
#再帰
end
end
Sudoku.solve(DATA.readlines)
=begin
=end
__END__
004000000
205001800
000800003
090000000
000070060
108005300
030009000
040000200
902050007
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