Class: Sudoku

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

Instance Method Summary collapse

Constructor Details

#initialize(*args) ⇒ Sudoku

Returns a new instance of Sudoku.



20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
 
# File 'lib/phg_sudoku_solver.rb', line 20

def initialize (*args)
  @total_iterations = 0
  @max_iterations = 100000
  @debug = false
  @cells = Array.new(9) { Array.new(9) }

  if args.size==1
    (0..8).each { |row|
      if args[0][row].is_a?(String)
        (0..8).each { |col|
          val = args[0][row][col]
          if /[0-9]/.match(val)
            @cells[row][col] = Cell.new(val.to_i)
          else
            @cells[row][col] = Cell.new()
          end
        }
      end
    }
  elsif args.size==0
    (0..8).each { |row|
      (0..8).each { |col|
        @cells[row][col] = Cell.new()
      }
    }
  end
  unless self.validate_sudoku
    raise Exception.new('Sudoku entered appears to be invalid.')
  end
end

Instance Method Details

#add_possible_value(row, col, val) ⇒ Object 



71
72
73
 
# File 'lib/phg_sudoku_solver.rb', line 71

def add_possible_value(row, col, val)
  @cells[row][col].add_possible_value(val)
end

#check_col_value(row, col, val) ⇒ Object 



286
287
288
289
290
291
292
293
294
295
296
 
# File 'lib/phg_sudoku_solver.rb', line 286

def check_col_value(row, col, val)
  result = true
  (0..8).each { |r|
    if r!=row
      if @cells[r][col].get_fixed_value()==val
        result = false
      end
    end
  }
  result
end

#check_matrix_value(row, col, val) ⇒ Object 



298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
 
# File 'lib/phg_sudoku_solver.rb', line 298

def check_matrix_value(row, col, val)
  result = true
  row_start = (row/3).floor * 3
  col_start = (col/3).floor * 3
  (row_start..row_start+2).each { |y|
    (col_start..col_start+2).each { |x|
      unless row==y and col==x
        if @cells[y][x].get_fixed_value()==val
          result = false
        end
      end
    }
  }
  result
end

#check_row_value(row, col, val) ⇒ Object 



274
275
276
277
278
279
280
281
282
283
284
 
# File 'lib/phg_sudoku_solver.rb', line 274

def check_row_value(row, col, val)
  result = true
  (0..8).each { |current_column|
    if current_column!=col
      if @cells[row][current_column].get_fixed_value()==val
        result = false
      end
    end
  }
  result
end

#compute_possible_values ⇒ Object 



248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
 
# File 'lib/phg_sudoku_solver.rb', line 248

def compute_possible_values

  (0..8).each { |r|
    (0..8).each { |c|
      if @cells[r][c].get_fixed_value()<=0
        @cells[r][c].reset_possible_values()

        (1..9).each { |possible_value|
          if check_row_value(r, c, possible_value) and check_col_value(r, c, possible_value) and check_matrix_value(r, c, possible_value)
            add_possible_value(r, c, possible_value)
          end

        }
        if @cells[r][c].get_possible_values().count==1
          fixed_val = @cells[r][c].get_possible_values()[0]
          @cells[r][c].set_fixed_value(fixed_val)
          print_debug 'Resetting possible values...'
          @cells[r][c].reset_possible_values()
        elsif @cells[r][c].get_possible_values().count>1
          @cells[r][c].set_fixed_value(-1)
        end
      end
    }
  }
end

#copy ⇒ Object 



342
343
344
345
346
347
348
349
350
351
352
353
354
 
# File 'lib/phg_sudoku_solver.rb', line 342

def copy
  s = Sudoku.new()
  (0..8).each { |r|
    (0..8).each { |c|
      copied_cell = @cells[r][c].copy
      s.set_cells(r, c, copied_cell)
    }
  }
  s.set_max_iterations(@max_iterations)
  s.set_total_iterations(@total_iterations)
  s.set_debug(@debug)
  s
end

#count_fixed_cells ⇒ Object 



130
131
132
133
134
135
136
137
138
139
 
# File 'lib/phg_sudoku_solver.rb', line 130

def count_fixed_cells
  fixed_cell_count=0

  @cells.each() do |row|
    row.each() do |cell|
      fixed_cell_count = fixed_cell_count + 1 if cell.get_fixed_value != -1
    end
  end
  fixed_cell_count
end

#dump_known_cells_str ⇒ Object 



464
465
466
467
468
469
470
471
472
473
474
475
476
477
478
479
480
481
482
483
484
485
486
 
# File 'lib/phg_sudoku_solver.rb', line 464

def dump_known_cells_str

  result = '\n'
  for row in (0..8)
    (0..8).each do |col|
      if @cells[row][col].get_fixed_value() > 0
        val = @cells[row][col].get_fixed_value()
      else
        val = ' '
      end
      result+='%3s ' % val
      if col == 2 or col == 5
        result+= '| '
      end
    end
    if row==2 or row==5
      result+= '\n----------------------------------------\n'
    else
      result+= '\n'
    end
  end
  result
end

#dump_to_str ⇒ Object 



437
438
439
440
441
442
443
444
445
446
447
448
449
450
451
452
453
454
455
456
457
458
459
460
461
462
 
# File 'lib/phg_sudoku_solver.rb', line 437

def dump_to_str
  if @debug
    print '\n'
    (0..8).each { |row|
      (0..8).each { |col|
        printf('   %3s     | ' % @cells[row][col].get_fixed_value())
        if col == 2 or col == 5
          print '| '
        end

      }
      print '\n'
      (0..8).each { |col|
        array = @cells[row][col].get_possible_values()
        if array==[]
          array = '--'
        end
        printf(' %10s  ' % array)
        if col == 2 or col == 5
          print '| '
        end
      }
      print '\n\n'
    }
  end
end

#find_col_implied_values ⇒ Object 



177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
 
# File 'lib/phg_sudoku_solver.rb', line 177

def find_col_implied_values
  (1..9).each { |i|
    (0..8).each { |c|
      fixed_count = 0
      variable_count = 0
      temp_row = -1
      temp_col = -1
      (0..8).each { |r|
        if @cells[r][c].get_fixed_value()==i
          fixed_count+=1
        end

        (0..@cells[r][c].get_possible_values().count).each { |j|
          if @cells[r][c].get_possible_values()[j]==i
            variable_count+=1
            temp_row = r
            temp_col = c
          end
        }

      }
      if (fixed_count==0) and (variable_count==1)
        @cells[temp_row][temp_col].set_fixed_value(i)
      end

      if fixed_count>1
        raise('Duplicate fixed value in column check.  Make sure you entered correct values.')
      end
    }
  }
end

#find_matrix_implied_values ⇒ Object 



209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
 
# File 'lib/phg_sudoku_solver.rb', line 209

def find_matrix_implied_values
  # In each sub-matrix we check for implied values (i) one at a time...
  [0, 3, 6].each { |row_start|
    [0, 3, 6].each { |col_start|
      (1..9).each { |i|
        temp_row = 0
        temp_col = 0
        fixed_count = 0
        variable_count = 0
        (row_start..row_start+2).each { |r|
          (col_start..col_start+2).each { |c|

            if @cells[r][c].get_fixed_value()==i
              fixed_count+=1
            end

            (0..@cells[r][c].get_possible_values().count).each { |j|
              if @cells[r][c].get_possible_values()[j]==i
                variable_count+=1
                temp_row = r
                temp_col = c
              end
            }
          }
        }

        if (fixed_count==0) and (variable_count==1)
          @cells[temp_row][temp_col].set_fixed_value(i)
        end

        if fixed_count>1
          raise('Duplicate fixed value in matrix check.  Make sure you entered correct values.')
        end
      }
    }
  }
end

#find_row_implied_values ⇒ Object 



141
142
143
144
145
146
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
 
# File 'lib/phg_sudoku_solver.rb', line 141

def find_row_implied_values

  (1..9).each { |i|
    (0..8).each { |r|
      fixed_count = 0
      variable_count = 0
      temp_row = -1
      temp_col = -1
      (0..8).each { |c|
        # Start by counting up fixed values for the given number i.  (e.g. How many of i do we have?)
        if @cells[r][c].get_fixed_value()==i
          fixed_count+=1
        end

        #  We are checking to see if there is only one i in the possible values for this row.
        #  If so, then we will set the fixed value in the cell contains it.
        (0..@cells[r][c].get_possible_values().count).each { |j|
          if @cells[r][c].get_possible_values()[j]==i
            variable_count+=1
            temp_row = r
            temp_col = c
          end
        }

      }
      if (fixed_count==0) and (variable_count==1)
        @cells[temp_row][temp_col].set_fixed_value(i)
      end

      if fixed_count>1
        raise('Duplicate fixed values in row check.  Make sure you entered correct values.')
      end
    }
  }
end

#get_cells ⇒ Object 



51
52
53
 
# File 'lib/phg_sudoku_solver.rb', line 51

def get_cells
  @cells
end

#get_fixed_value(row, col) ⇒ Object 



59
60
61
 
# File 'lib/phg_sudoku_solver.rb', line 59

def get_fixed_value(row, col)
  @cells[row][col].get_fixed_value()
end

#get_possible_values(row, col) ⇒ Object 



75
76
77
 
# File 'lib/phg_sudoku_solver.rb', line 75

def get_possible_values(row, col)
  @cells[row][col].get_possible_values
end

#get_total_iterations ⇒ Object 



79
80
81
 
# File 'lib/phg_sudoku_solver.rb', line 79

def get_total_iterations
  @total_iterations
end

#print_debug(message) ⇒ Object 



488
489
490
491
492
 
# File 'lib/phg_sudoku_solver.rb', line 488

def print_debug(message)
  if @debug
    puts message + '\n'
  end
end

#recurse ⇒ Object 



314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
340
 
# File 'lib/phg_sudoku_solver.rb', line 314

def recurse
  recurse = copy()
  (2..9).each { |guesses|
    (0..8).each { |r|
      (0..8).each { |c|
        if (recurse.get_possible_values(r, c).count==guesses)  #Staring with cells that have the fewest to solve.
          (0..recurse.get_possible_values(r, c).count).each { |j|
            unless recurse.get_possible_values(r, c)[j].nil?
              print_debug '\nStarting recursion with (%s,%s) set to %s\n' % [r, c, recurse.get_possible_values(r, c)[j]]
              recurse.set_fixed_value(r, c, recurse.get_possible_values(r, c)[j])
              print_debug('Recursion starting...')
              recurse, iterations = recurse.solve
              @total_iterations = @total_iterations + iterations
              if recurse!=nil
                return recurse
              else
                recurse = copy()
              end
            end
          }
        end
      }
    }
  }
  print_debug('Dead end found.\n')
  nil
end

#set_cells(row, col, cell) ⇒ Object 



55
56
57
 
# File 'lib/phg_sudoku_solver.rb', line 55

def set_cells(row, col, cell)
  @cells[row][col]=cell
end

#set_debug(b) ⇒ Object 



433
434
435
 
# File 'lib/phg_sudoku_solver.rb', line 433

def set_debug(b)
  @debug = b
end

#set_fixed_value(row, col, val) ⇒ Object 



63
64
65
 
# File 'lib/phg_sudoku_solver.rb', line 63

def set_fixed_value(row, col, val)
  @cells[row][col].set_fixed_value(val)
end

#set_max_iterations(iterations) ⇒ Object 



12
13
14
 
# File 'lib/phg_sudoku_solver.rb', line 12

def set_max_iterations(iterations)
  @max_iterations=iterations
end

#set_possible_values(row, col, vals) ⇒ Object 



67
68
69
 
# File 'lib/phg_sudoku_solver.rb', line 67

def set_possible_values(row, col, vals)
  @cells[row][col].set_possible_values(vals)
end

#set_total_iterations(iterations) ⇒ Object 



16
17
18
 
# File 'lib/phg_sudoku_solver.rb', line 16

def set_total_iterations(iterations)
  @total_iterations = iterations
end

#solve ⇒ Object 



83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
 
# File 'lib/phg_sudoku_solver.rb', line 83

def solve
  iteration=0
  no_progress_count = 0
  print_debug 'Max Iterations = %s' %  @max_iterations

  while @solved_cell_count!=81
    iteration+=1
    @total_iterations+=1
    print_debug 'Iteration: %s   SolvedCells: %s\n' % [iteration, @solved_cell_count]
    print_debug dump_known_cells_str
    compute_possible_values()

    begin
      if validate_sudoku()
        find_row_implied_values()
        find_col_implied_values()
        find_matrix_implied_values()
      else
        return nil, @total_iterations
      end
    rescue Exception => error
      print_debug '\nValidation Error: %s\n' % error
      @solved_cell_count=count_fixed_cells()
      return nil, @total_iterations
    end

    if @max_iterations > 0 and @total_iterations > @max_iterations
      print_debug 'Total Iterations... %s\n' % @total_iterations
      print_debug 'This is just taking too long\n'
      raise Exception.new('Solution taking too long!\n\n')
    end

    if @solved_cell_count==count_fixed_cells()
      no_progress_count+=1
      if no_progress_count>9
        print_debug ('We''re not making progress here!')
        solution = recurse()
        return solution, @total_iterations
      end
    else
      no_progress_count=0
      @solved_cell_count=count_fixed_cells()
    end
  end
  return self, @total_iterations
end

#validate_column(c) ⇒ Object 



395
396
397
398
399
400
401
402
403
404
405
406
407
408
409
 
# File 'lib/phg_sudoku_solver.rb', line 395

def validate_column(c)

  (1..9).each { |i|
    found_count = 0
    (0..8).each { |r|
      if @cells[r][c].get_fixed_value()==i
        found_count+=1
      end
    }
    if found_count>1
      raise Exception.new('Row invalid.  Canceling')
    end
  }
  true
end

#validate_matrix(r, c) ⇒ Object 



412
413
414
415
416
417
418
419
420
421
422
423
424
425
426
427
428
429
430
 
# File 'lib/phg_sudoku_solver.rb', line 412

def validate_matrix(r, c)
  (1..9).each { |i|
    found_count=0
    row_start = (r/3).floor * 3
    col_start = (c/3).floor * 3
    (row_start..row_start+2).each { |y|
      (col_start..col_start+2).each { |x|
        if @cells[y][x].get_fixed_value()==i
          found_count+=1
        end

      }
    }
    if found_count>1
      raise Exception.new('Matrix invalid! Canceling.')
    end
  }
  true
end

#validate_row(r) ⇒ Object 



378
379
380
381
382
383
384
385
386
387
388
389
390
391
392
 
# File 'lib/phg_sudoku_solver.rb', line 378

def validate_row(r)
  
  (1..9).each { |i|
    found_count=0
    (0..8).each { |c|
      if @cells[r][c].get_fixed_value()==i
        found_count+=1
      end
    }
    if found_count>1
      raise Exception.new('Row invalid %s.  Canceling' % r)
    end
  }
  true
end

#validate_sudoku ⇒ Object 



356
357
358
359
360
361
362
363
364
365
366
367
368
369
370
371
372
373
374
375
376
 
# File 'lib/phg_sudoku_solver.rb', line 356

def validate_sudoku
  results = true
  begin
    (0..8).each { |r|
      validate_row(r)
    }

    (0..8).each { |c|
      validate_column(c)
    }

    [0, 3, 6].each { |r|
      [0, 3, 6].each { |c|
        validate_matrix(r, c)
      }
    }
  rescue Exception => error
    results = false
  end
  results
end