module Sudoku::Solver

Methodes de resolution des sudokus

Public Instance Methods

missing_col(x) click to toggle source

Renvoie les nombres manquants dans la colonne

@param [Fixnum] x La colonne à traiter
@return [Array] Les nombres manquants
# File lib/sudoku/solver.rb, line 15
def missing_col x
  Array.new(size){|i| i+1} - col(x)
end
missing_row(y) click to toggle source

Renvoie les nombres manquants dans la colonne

@param [Fixnum] y La ligne à traiter
@return [Array] Les nombres manquants
# File lib/sudoku/solver.rb, line 22
def missing_row y
  Array.new(size){|i| i+1} - row(y)
end
missing_square(x, y) click to toggle source

Renvoie les nombres manquants dans le carré comprenant la case x,y

@param [Fixnum] x La colonne d'une case du carré à traiter
@param [Fixnum] y La rangée d'une case du carré à traiter
@return [Array] Les nombres manquants
# File lib/sudoku/solver.rb, line 8
def missing_square x, y
  Array.new(size){|i| i+1} - square(x,y)
end
remove_impossible!() click to toggle source

Enleve les nombres qui sont impossibles de la grille

@return (Fixnum) le nombre de nombres enlevés
# File lib/sudoku/solver.rb, line 175
def remove_impossible!
  removes = 0
  each do |x, y, val|
    unless valid_cell? x, y, val
      set x, y, 0 
      removes += 1
    end
  end
  removes
end
solve_backtrack!() click to toggle source

Resoud le sudoku par backtracking @return [Fixnum] le nombre de nombres ajoutés dans la grille

# File lib/sudoku/solver.rb, line 143
def solve_backtrack!
  res = solve_naive!
        
  each do |x, y, cur_val|
    next unless cur_val.zero?
    p = possibilities x, y
    p.each do |val|
      copy = clone
      copy.set x, y, val
      adds = copy.solve_backtrack!
      if copy.complete?
        self.import copy
        return res+adds+1
      end
    end
  end
  
  res
end
solve_backtrack_timeout(timeout) click to toggle source

Renvoie un nouveau sudoku reolu par backtracking Si le temps de solution depasse timeout, le solveur est arrete @param [Fixnum] timeout Le temps maximum en secondes @return [Sudoku::Grid] Le sudoku resolu, ou en partie resolu si le timeout a joue

# File lib/sudoku/solver.rb, line 167
def solve_backtrack_timeout timeout
  res = self.clone
  Thread.new(res){|s| s.solve_backtrack!}.join(timeout)
  res
end
solve_col!(x) click to toggle source

Ajoute un nombre chaque fois que c'est la seule position possible dans la colonne

@param [Fixnum] x La colonne à traiter
@return [Fixnum] le nombre de nombres ajoutés
# File lib/sudoku/solver.rb, line 51
def solve_col! x
  adds = 0
  
  missing_col(x).each do |val|
    pos = []
    size.times do |y|
      next unless get(x,y) == 0
      pos << [x,y] if valid? x, y, val
    end
    if pos.length == 1
      set pos[0][0], pos[0][1], val
      adds += 1
    end
  end
  
  adds
end
solve_naive!() click to toggle source

Utilise solve_uniq_possibilities!, solve_col!, solve_row! et solve_square! tant qu'ils ajoutent des nombres

@return [Fixnum] le nombre de nombres ajoutés
# File lib/sudoku/solver.rb, line 121
def solve_naive!
  res = 0
  
  loop do
    adds = solve_uniq_possibilities!
    size.times do |i|
      adds += solve_col! i
      adds += solve_row! i
      
      x = (i*base) % size
      y = (i/base) * base
      adds += solve_square! x, y
    end
    break if adds.zero?
    res += adds
  end
  
  res
end
solve_row!(y) click to toggle source

Ajoute un nombre chaque fois que c'est la seule position possible dans la ligne

@param [Fixnum] y La ligne à traiter
@return [Fixnum] le nombre de nombres ajoutés
# File lib/sudoku/solver.rb, line 72
def solve_row! y
  adds = 0
  
  missing_row(y).each do |val|
    pos = []
    size.times do |x|
      next unless get(x,y) == 0
      pos << [x,y] if valid? x, y, val
    end
    if pos.length == 1
      set pos[0][0], pos[0][1], val
      adds += 1
    end
  end
  
  adds
end
solve_square!(xx, yy) click to toggle source

Ajoute un nombre chaque fois que c'est la seule position possible dans le carré

@param [Fixnum] x La colonne d'une case du carré à traiter
@param [Fixnum] y La rangée d'une case du carré à traiter
@return [Fixnum] le nombre de nombres ajoutés
# File lib/sudoku/solver.rb, line 94
def solve_square! xx, yy
  xmin = xx - (xx%base)
  ymin = yy - (yy%base)
  adds = 0
  
  missing_square(xx, yy).each do |val|
    pos = []
    base.times do |i|
      base.times do |j|
        x = xmin + i
        y = ymin + j
        next unless get(x,y) == 0
        pos << [x,y] if valid? x, y, val
      end
    end
    if pos.length == 1
      set pos[0][0], pos[0][1], val
      adds += 1
    end
  end
  
  adds
end
solve_uniq_possibilities!() click to toggle source

Ajoute un nombre chaque fois que c'est la seule possibilité

@return [Fixnum] le nombre de nombres ajoutés dans la grille
# File lib/sudoku/solver.rb, line 28
def solve_uniq_possibilities!
  res = 0
  loop do
    adds = 0
    each do |x, y, val|
      next unless val.zero?
      
      p = possibilities x, y
      if p.length == 1
        set x, y, p.first
        adds += 1
      end
      
    end
    break if adds == 0
    res += adds
  end
  res
end