Voici un script ruby pour résoudre de manière élégante les problèmes Sudoku.

sudoku = <<ENDSUDOKU
 .  .  .  1  .  .  .  6  4
 5  .  .  .  7  .  3  .  .
 8  .  2  .  .  .  .  .  .
 .  4  .  .  1  2  5  .  .
 1  .  .  .  .  .  .  .  2
 .  .  5  8  3  .  .  9  .
 .  .  .  .  .  .  4  .  3
 .  .  9  .  2  .  .  .  7
 7  8  .  .  .  1  .  .  .
ENDSUDOKU

class Sudoku
  def initialize(s = nil)
    @a = Array.new(81) # An element for each position on the board
    @cols  = Array.new(9) { Array.new(10, false) }  # A set for each column
    @rows  = Array.new(9) { Array.new(10, false) }  # A set for each row
    @grids = Array.new(9) { Array.new(10, false) }  # A set for each 3x3 grid
    s.split.each_with_index{|n, i| self[i] = n.to_i unless n == '.' } unless s.nil?
  end

  def to_s
    (0..8).map {|i| @a[i*9,9].map {|n| n || "." }.join(" ") }.join("\n") + "\n"
  end

  def solve(i = 0, &block)
    if i == 81
      yield self            # We've reached the end!
    elsif self[i]
      solve(i + 1, &block)  # This square is fixed, so try the next.
    else
      for n in (1..9) do    # Try each possible value for this square.
        if can_set?(i, n)
          self[i] = n
          solve(i + 1, &block)
          self[i] = nil
        end
      end
    end
  end

  def [](i) @a[i]; end

  # Returns true if square i can be set to n without invalidating the sudoku.
  def can_set?(i, n) 
    !(col_at(i)[n] or row_at(i)[n] or grid_at(i)[n])
  end

  def []=(i, n)
    if n.nil?
      m = @a[i]
      col_at(i)[m] = false
      row_at(i)[m] = false
      grid_at(i)[m] = false
    else
      col_at(i)[n] = true
      row_at(i)[n] = true
      grid_at(i)[n] = true
    end
    @a[i] = n
  end

private
  def col_at(i)  @cols[i % 9]; end
  def row_at(i)  @rows[i / 9]; end
  def grid_at(i) @grids[((i % 9) / 3) + ((i / 27) * 3)]; end
end

print Sudoku.new(sudoku).solve {|result| break result.to_s }

Published

Category

ruby

Contact