fork(1) download
copy 
  1.  
  2. class Sudoku
  3.   def self.solve(sheet)
  4.     new(sheet).solve.inspect_answers
  5.   end
  6.  
  7.   def initialize(sheet)
  8.     @sheet = sheet.map(&:dup)
  9.     @answers = []
  10.   end
  11.  
  12.   def to_s(sheet = @sheet)
  13.     sheet.map { |r| r.each_slice(3).map(&:join).join('|') }
  14.       .each_slice(3).map { |r| r.join("\n") }.join("\n---+---+---\n")
  15.   end
  16.  
  17.   def inspect_answers
  18.     @answers.map { |a| to_s(a) }.join("\n\n")
  19.   end
  20.  
  21.   def solve
  22.     pt = 0
  23.     fs = undetermineds.map { |r, c| Fiber.new { fiber(r, c) } }
  24.     space_count = fs.size
  25.     case pt
  26.     when -1          then return(self)
  27.     when space_count then @answers << @sheet.map(&:dup); pt -= 1
  28.     else                  pt += fs[pt].resume
  29.     end while 1
  30.   end
  31.  
  32.   private
  33.  
  34.   def undetermineds
  35.     9.times.each_with_object([]) do |r, ary|
  36.       9.times do |c|
  37.         ary << [r, c] if @sheet[r][c].zero?
  38.       end
  39.     end
  40.   end
  41.  
  42.   def fiber(r, c)
  43.     prv = @sheet[r][c]
  44.     loop do
  45.       9.times do |i|
  46.         next unless disjoint?(r, c, i + 1)
  47.         @sheet[r][c] = i + 1
  48.         Fiber.yield(1)
  49.       end
  50.       @sheet[r][c] = prv
  51.       Fiber.yield(-1)
  52.     end
  53.   end
  54.  
  55.   def disjoint?(r, c, n)
  56.     9.times.none? do |i|
  57.       @sheet[i][c] == n ||
  58.       @sheet[r][i] == n ||
  59.       @sheet[r - r % 3 + i % 3][c - c % 3 + i / 3] == n
  60.     end
  61.   end
  62. end
  63.  
  64. puts Sudoku.solve($<.map{|i|i.split.map(&:to_i)})
  65.  
Success #stdin #stdout 0.01s 49632KB
comments (?)
stdin
copy 
1 2 3  4 5 6  7 8 9
4 5 6  7 8 9  1 2 3
7 8 9  1 2 3  4 5 6
2 3 1  9 7 5  _ _ _
5 6 4  8 _ _  _ _ _
8 9 7  6 _ 1  _ _ _
3 1 2  _ _ _  _ _ _
6 4 5  _ _ _  _ _ _
9 7 8  _ _ _  _ _ _
stdout
copy 
123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|917
897|641|235
---+---+---
312|567|894
645|298|371
978|314|562

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|917
897|641|532
---+---+---
312|567|894
645|298|371
978|314|265

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|917
897|641|532
---+---+---
312|567|894
645|398|271
978|214|365

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|235
---+---+---
312|567|894
645|298|317
978|314|562

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|235
---+---+---
312|597|864
645|218|397
978|364|512

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|532
---+---+---
312|567|894
645|298|317
978|314|265

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|532
---+---+---
312|567|894
645|398|217
978|214|365

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|532
---+---+---
312|597|864
645|218|397
978|364|215

123|456|789
456|789|123
789|123|456
---+---+---
231|975|648
564|832|971
897|641|532
---+---+---
312|597|864
645|318|297
978|264|315

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|235
---+---+---
312|597|648
645|218|397
978|364|512

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|235
---+---+---
312|598|647
645|217|398
978|364|512

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|532
---+---+---
312|597|648
645|218|397
978|364|215

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|532
---+---+---
312|597|648
645|318|297
978|264|315

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|532
---+---+---
312|598|647
645|217|398
978|364|215

123|456|789
456|789|123
789|123|456
---+---+---
231|975|864
564|832|971
897|641|532
---+---+---
312|598|647
645|317|298
978|264|315
https://ideone.com/YRslIS
language:
Ruby (ruby 2.5.5)
created:
8 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!