sudoku.rb

0_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

1_in1.txt

xxxxxxxxx
xxxxxx5x7
x59x2x6xx
14x7xxx8x
x6xx8xx5x
3xx651xxx
xxx9xxxx1
8xxxx4x9x
xx3xxxx48

2_in2.txt

xxxxxxxxx
xxxxxxx27
4xx6x8xxx
x71xxx3xx
2385x6419
9641xx75x
395x278xx
182x6x974
x468192x5