Siguiente: La Estructura y Ejecución Subir: Introduccion Anterior: Véase También Índice General Índice de Materias
Véase:
~/rubytesting$ cat -n useSudoku.rb 1 #!/usr/bin/env ruby 2 # http://www.websudoku.com/ 3 $LOAD_PATH.unshift 'RPLExamples' 4 require "Sudoku" 5 puts Sudoku.solve Sudoku::Puzzle.new ARGF.readlines
~/rubytesting$ cat -n RPLExamples/sudoku.txt 1 3.4..5.61 2 ....9.8.3 3 .1..8...2 4 4...37.5. 5 .6.9.8.2. 6 .7.54...9 7 1...7..9. 8 7.8.6.... 9 29.4..3.7
~/rubytesting$ ./useSudoku.rb RPLExamples/sudoku.txt 384725961 652194873 917386542 429637158 563918724 871542639 145873296 738269415 296451387
~/rubytesting$ cat -n RPLExamples/Sudoku.rb
1 # http://www.websudoku.com/
2 module Sudoku
3
4 class Puzzle
5
6 ASCII = ".123456789"
7 BIN = "\000\001\002\003\004\005\006\007\010\011"
8
9 def initialize(lines)
10 if (lines.respond_to? :join)
11 s = lines.join
12 else
13 s = lines.dup
14 end
15
16 s.gsub!(/\s/, "")
17
18 raise Invalid, "Grid is the wrong size" unless s.size == 81
19
20 raise Invalid, "Illegal character #{s[i,1]} in puzzle" if i = s.index(/[^123456789\.]/)
21
22 s.tr!(ASCII, BIN) # Translate ASCII characters into bytes
23 @grid = s.unpack('c*') # Now unpack the bytes into an array of numbers
24
25 raise Invalid, "Initial puzzle has duplicates" if has_duplicates?
26 end
27
28 def to_s
29 (0..8).collect{|r| @grid[r*9,9].pack('c9')}.join("\n").tr(BIN,ASCII)
30 end
31
32 def dup
33 copy = super # Make a shallow copy by calling Object.dup
34 @grid = @grid.dup # Make a new copy of the internal data
35 copy # Return the copied object
36 end
37
38 def [](row, col)
39 @grid[row*9 + col]
40 end
41
42 def []=(row, col, newvalue)
43 raise Invalid, "illegal cell value" unless (0..9).include? newvalue
44 @grid[row*9 + col] = newvalue
45 end
46
47 BoxOfIndex = [
48 0,0,0,1,1,1,2,2,2,
49 0,0,0,1,1,1,2,2,2,
50 0,0,0,1,1,1,2,2,2,
51 3,3,3,4,4,4,5,5,5,
52 3,3,3,4,4,4,5,5,5,
53 3,3,3,4,4,4,5,5,5,
54 6,6,6,7,7,7,8,8,8,
55 6,6,6,7,7,7,8,8,8,
56 6,6,6,7,7,7,8,8,8
57 ].freeze
58
59 def each_unknown
60 0.upto 8 do |row| # For each row
61 0.upto 8 do |col| # For each column
62 index = row*9+col # Cell index for (row,col)
63 next if @grid[index] != 0 # Move on if we know the cell's value
64 box = BoxOfIndex[index] # Figure out the box for this cell
65 yield row, col, box # Invoke the associated block
66 end
67 end
68 end
69
70 def has_duplicates?
71 0.upto(8) {|row| return true if rowdigits(row).uniq! }
72 0.upto(8) {|col| return true if coldigits(col).uniq! }
73 0.upto(8) {|box| return true if boxdigits(box).uniq! }
74
75 false # If all the tests have passed, then the board has no duplicates
76 end
77
78 AllDigits = [1, 2, 3, 4, 5, 6, 7, 8, 9].freeze
79
80 def possible(row, col, box)
81 AllDigits - (rowdigits(row) + coldigits(col) + boxdigits(box))
82 end
83
84
85 def rowdigits(row)
86 @grid[row*9,9] - [0]
87 end
88
89 def coldigits(col)
90 result = [] # Start with an empty array
91 col.step(80, 9) {|i| # Loop from col by nines up to 80
92 v = @grid[i] # Get value of cell at that index
93 result << v if (v != 0) # Add it to the array if non-zero
94 }
95 result # Return the array
96 end
97
98 BoxToIndex = [0, 3, 6, 27, 30, 33, 54, 57, 60].freeze
99
100 def boxdigits(b)
101 i = BoxToIndex[b]
102 [
103 @grid[i], @grid[i+1], @grid[i+2],
104 @grid[i+9], @grid[i+10], @grid[i+11],
105 @grid[i+18], @grid[i+19], @grid[i+20]
106 ] - [0]
107 end
108 end # This is the end of the Puzzle class
109
110 class Invalid < StandardError
111 end
112
113 class Impossible < StandardError
114 end
115
116 def Sudoku.scan(puzzle)
117 unchanged = false # This is our loop variable
118
119 until unchanged
120 unchanged = true # Assume no cells will be changed this time
121 rmin,cmin,pmin = nil # Track cell with minimal possible set
122 min = 10 # More than the maximal number of possibilities
123
124 puzzle.each_unknown do |row, col, box|
125 p = puzzle.possible(row, col, box)
126
127 case p.size
128 when 0 # No possible values means the puzzle is over-constrained
129 raise Impossible
130 when 1 # We've found a unique value, so set it in the grid
131 puzzle[row,col] = p[0] # Set that position on the grid to the value
132 unchanged = false # Note that we've made a change
133 else # For any other number of possibilities
134 if unchanged && p.size < min
135 min = p.size # Current smallest size
136 rmin, cmin, pmin = row, col, p # Note parallel assignment
137 end
138 end
139 end
140 end
141
142 return rmin, cmin, pmin
143 end
144
145 def Sudoku.solve(puzzle)
146 puzzle = puzzle.dup
147
148 r,c,p = scan(puzzle)
149
150 return puzzle if r == nil
151
152 p.each do |guess| # For each value in the set of possible values
153 puzzle[r,c] = guess # Guess the value
154
155 begin
156 return solve(puzzle) # If it returns, we just return the solution
157 rescue Impossible
158 next # If it raises an exception, try the next guess
159 end
160 end
161
162 raise Impossible
163 end
164 end