Module: Sudoku::Solver

Included in:
Grid
Defined in:
lib/sudoku/solver.rb

Overview

Methodes de resolution des sudokus

Instance Method Summary collapse

Instance Method Details

#missing_col(x) ⇒ Array

Renvoie les nombres manquants dans la colonne

Parameters:

  • x (Fixnum) —

    La colonne à traiter

Returns:

  • (Array) —

    Les nombres manquants



15
16
17
 
# File 'lib/sudoku/solver.rb', line 15

def missing_col x
  Array.new(size){|i| i+1} - col(x)
end

#missing_row(y) ⇒ Array

Renvoie les nombres manquants dans la colonne

Parameters:

  • y (Fixnum) —

    La ligne à traiter

Returns:

  • (Array) —

    Les nombres manquants



22
23
24
 
# File 'lib/sudoku/solver.rb', line 22

def missing_row y
  Array.new(size){|i| i+1} - row(y)
end

#missing_square(x, y) ⇒ Array

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

Parameters:

  • x (Fixnum) —

    La colonne d’une case du carré à traiter

  • y (Fixnum) —

    La rangée d’une case du carré à traiter

Returns:

  • (Array) —

    Les nombres manquants



8
9
10
 
# File 'lib/sudoku/solver.rb', line 8

def missing_square x, y
  Array.new(size){|i| i+1} - square(x,y)
end

#remove_impossible! ⇒ Fixnum

Enleve les nombres qui sont impossibles de la grille

Returns:

  • (Fixnum) —

    le nombre de nombres enlevés



175
176
177
178
179
180
181
182
183
184
 
# 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! ⇒ Fixnum

Resoud le sudoku par backtracking

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés dans la grille



143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
 
# 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) ⇒ Sudoku::Grid

Renvoie un nouveau sudoku reolu par backtracking Si le temps de solution depasse timeout, le solveur est arrete

Parameters:

  • timeout (Fixnum) —

    Le temps maximum en secondes

Returns:

  • (Sudoku::Grid) —

    Le sudoku resolu, ou en partie resolu si le timeout a joue



167
168
169
170
171
 
# 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) ⇒ Fixnum

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

Parameters:

  • x (Fixnum) —

    La colonne à traiter

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés



51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
 
# 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! ⇒ Fixnum

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

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés



121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
 
# 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) ⇒ Fixnum

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

Parameters:

  • y (Fixnum) —

    La ligne à traiter

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés



72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
 
# 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) ⇒ Fixnum

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

Parameters:

  • x (Fixnum) —

    La colonne d’une case du carré à traiter

  • y (Fixnum) —

    La rangée d’une case du carré à traiter

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés



94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
 
# 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! ⇒ Fixnum

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

Returns:

  • (Fixnum) —

    le nombre de nombres ajoutés dans la grille



28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
 
# 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