Class: SudokuSolver

Inherits:
Object
  • Object
show all
Defined in:
lib/sudokusolver.rb

Overview

Throughout this program:

r is a row,    e.g. 'A'
c is a column, e.g. '3'
s is a square, e.g. 'A3'
d is a digit,  e.g. '9'
u is a unit,   e.g. ['A1','B1','C1','D1','E1','F1','G1','H1','I1']
g is a grid,   e.g. 81 non-blank chars, e.g. starting with '.18...7...
values is a hash of possible values, e.g. {'A1'=>'123489', 'A2'=>'8', ...}

Constant Summary collapse

VERSION = 
"1.4"

Instance Attribute Summary collapse

Instance Method Summary collapse

Constructor Details

#initialize ⇒ SudokuSolver

Returns a new instance of SudokuSolver.



31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
 
# File 'lib/sudokusolver.rb', line 31

def initialize() 
  @rows = ('A'..'I').to_a
  @cols = ('1'..'9').to_a 
  @squares = cross(@rows, @cols)  
  @unitlist = Array.new
  cols.each { |c| @unitlist.push(cross(rows, c)) }
  rows.each { |r| @unitlist.push(cross(r, cols)) }    
  for rb in ['ABC','DEF','GHI'] do
    for cb in ['123','456','789'] do
      @unitlist << cross(rb.split(''),cb.split(''))
    end
  end

  @units = Hash.new
  squares.each do |s|
    @units[s] = Array.new
    unitlist.each do |u| 
      u.each do |x| 
        @units[s].push(u) if s == x
      end
    end
  end

  @peers = Hash.new
  squares.each do |s|
    @peers[s] = Array.new
    units[s].each do |u|
      u.each { |s2| @peers[s] << s2 if s2 != s }
    end
  end
  
end

Instance Attribute Details

#cols ⇒ Object (readonly)

Returns the value of attribute cols.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def cols
  @cols
end

#peers ⇒ Object (readonly)

Returns the value of attribute peers.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def peers
  @peers
end

#rows ⇒ Object (readonly)

Returns the value of attribute rows.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def rows
  @rows
end

#squares ⇒ Object (readonly)

Returns the value of attribute squares.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def squares
  @squares
end

#unitlist ⇒ Object (readonly)

Returns the value of attribute unitlist.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def unitlist
  @unitlist
end

#units ⇒ Object (readonly)

Returns the value of attribute units.



18
19
20
 
# File 'lib/sudokusolver.rb', line 18

def units
  @units
end

Instance Method Details

#assign(values, s, d) ⇒ Object

Assign a value to a square in the Sudoku grid: Eliminate all other possible digits from the square by calling the eliminate function (mutually recursive)



81
82
83
84
85
86
87
88
 
# File 'lib/sudokusolver.rb', line 81

def assign(values, s, d)
  values[s].split('').each do |d2|
    unless d2 == d
      return false if eliminate(values, s, d2) == false
    end
  end
  return values
end

#check_solution(solution) ⇒ Object

Verify the Sudoku solution



188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
 
# File 'lib/sudokusolver.rb', line 188

def check_solution(solution)
  values = Hash.new
  for s,d in squares.zip(solution.split(''))
    values[s] = d
  end
  
  unitlist.each do |u|
    tmp = Hash.new
    u.each do |s|
      tmp[values[s]] = true
    end
    return false unless tmp.keys.length == 9
  end
  return true  
end

#cross(a, b) ⇒ Object

Cross-product



21
22
23
24
25
26
27
28
29
 
# File 'lib/sudokusolver.rb', line 21

def cross(a, b)
  cp = Array.new # cross product
  a.each do |x|
    b.each do |y|
      cp << x+y
    end
  end
  return cp
end

#eliminate(values, s, d) ⇒ Object

Remove a possibility from a square. Recursively propagate the constraints: look at the source code for how this is done.



92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
 
# File 'lib/sudokusolver.rb', line 92

def eliminate(values, s, d)
  return values unless values[s].include?(d) ## Already eliminated.

  values[s] = values[s].sub(d,'') # Remove the digit from the string of possibilities
  #  values[s].sub!(d,'') => why doesn't sub!() work?

  return false if values[s].length == 0 # Contradiction: no more values (no more digits can be assigned)

  # Remove digit from all peers
# If the square has only one remaining possibility, that is the assigned value for the square and
# that value must be removed from all that square's peers.
  peers[s].each { |s2| return false unless eliminate(values, s2, values[s]) } if values[s].length == 1

  # Assign the digit to the square if, by elimination
# this is the only square that has the digit as a possibility
  units[s].each do |u|
    dplaces = Array.new
    u.each { |s2| dplaces << s2 if values[s2].include?(d) }
    return false if dplaces.length == 0 # bad
    return false if assign(values, dplaces[0], d) == false if dplaces.length == 1
  end
  return values
end

#parse_grid(g) ⇒ Object

A grid is an 81 character string composed of the digits 0-9 A blank is represented as a period.



66
67
68
69
70
71
72
73
74
75
76
 
# File 'lib/sudokusolver.rb', line 66

def parse_grid(g)
  g = g.chomp
  g = g.split('')
  values = Hash.new
  # Initially any square can be anything.
  squares.each { |s| values[s] = "123456789" }
  for s,d in squares.zip(g)
    return false unless assign(values, s, d) if d =~ /\d/
  end
  return values
end

#print_grid(values) ⇒ Object

Print a text Sudoku grid to STDOUT



147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
 
# File 'lib/sudokusolver.rb', line 147

def print_grid(values)
  return if values == false
  max = 0
  squares.each { |s| max = values[s].length if values[s].length > max }
  width = 1 + max
  a = Array.new
  3.times do |c|
    tmp = ""
    (3*width).times do
      tmp = tmp + '-'
    end
    tmp += "-" if c == 1 
    a.push(tmp)
  end
  line  = "\n" + a.join('+')
  
  tmp = ""
  for r in rows
    for c in cols
      tmp = tmp + values[r+c].center(width)
      if c == '3' or c == '6'
        tmp = tmp + '| '
      end
    end
    tmp = tmp + line if r == 'C' or r == 'F' 
    tmp = tmp + "\n"
  end
  puts tmp + "\n"
  return values
end

#search(values) ⇒ Object

Search if constraint satisfaction does not solve the puzzle



117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
 
# File 'lib/sudokusolver.rb', line 117

def search(values)
  return false if values == false

  solved = true # assumption 
  squares.each do |s|
    unless values[s].length == 1
      solved = false
      break
    end
  end
  return values if solved == true  ## Solved!
    
  min = 10 
  start = nil
  squares.each do |s| # Chose the undetermined square s with the fewest possibilities
    l = values[s].length
    if l > 1 && l < min
      min = l
      start = s
    end
  end

  values[start].split('').each do |d| 
    solution = search(assign(values.clone,start,d))
    return solution unless solution == false
  end
  return false
end

#string_solution(values) ⇒ Object

Transform the solution into an 81 character string



179
180
181
182
183
184
185
 
# File 'lib/sudokusolver.rb', line 179

def string_solution(values)
  solution = ""
  squares.each do |s|
    solution += values[s]
  end
  return solution
end