Added some real accessors.
[pseudoku.git] / pseudoku / grid / __init__.py
1 from __future__ import division
2
3 from math import sqrt
4 from operator import attrgetter
5 import re
6 from weakref import ref
7
8 from cellgroup import CellConstraint, Row, Column, Box
9
10 symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]
11
12 class GridSizeError(Exception):
13 """Exception thrown when an impossible grid size is encountered."""
14 pass
15
16 class GridIntegrityError(Exception):
17 """Exception thrown when a grid's state violates its own constraints. This
18 should only happen if there are bugs in the code itself.
19 """
20 pass
21
22 class Cell(object):
23 """Represents a single cell/value within a sudoku grid."""
24
25 ### Accessors
26
27 def _get_solved(self):
28 """True iff this cell has been solved."""
29 return len(self._values) == 1
30 solved = property(_get_solved)
31
32 def _get_value(self):
33 """Returns this cell's value, if it has one known."""
34 if self.solved:
35 return self._values[0]
36 return None
37 value = property(_get_value)
38
39 grid = property(lambda self: self._grid())
40 constraints = property(attrgetter('_constraints'))
41
42 def __init__(self, grid, row, column):
43 self._grid = ref(grid)
44 self._row = row
45 self._col = column
46 self._values = range(self.grid.size)
47 self._constraints = []
48 self._normalized = False
49
50 def add_constraint(self, constraint):
51 self._constraints.append(constraint)
52
53 def set(self, value, normalize=True):
54 """Sets the value of this cell. If `normalize` is True or omitted, the
55 grid will be updated accordingly.
56 """
57 self._values = [value]
58 if normalize:
59 self._normalized = False
60 self.normalize()
61
62
63
64 def normalize(self):
65 """Checks to see if this cell has only one possible value left. If
66 so, sets that as its value and eliminates it from every related cell.
67 This method is exhaustive; that repeated calls should have no effect.
68 """
69
70 if self._normalized:
71 # Already done
72 return
73
74 # Set this now just in case of infinite looping
75 self._normalized = True
76
77 if not self.solved:
78 # Don't know the value yet
79 return
80
81 # Elimination time
82 for constraint in self.constraints:
83 for cell in constraint.cells:
84 if cell == self:
85 continue
86 cell.eliminate(self.value)
87
88
89 def eliminate(self, value):
90 """Eliminates the given value as a possibility for this cell."""
91 if value in self._values:
92 self._values.remove(value)
93
94 if len(self._values) == 0:
95 # XXX give me a real exception here
96 raise Exception
97
98 self._normalized = False
99 self.normalize()
100
101
102 class Grid(object):
103 """Represents a Sudoku grid."""
104
105 ### Utilities
106
107 def _cellidx(self, row, col):
108 """Hashes a row and column into a flat array index."""
109 return row * self.size + col
110
111 @classmethod
112 def _infer_box_size(cls, dimension):
113 """Attempts to infer the size of a box, given some dimension of the
114 entire grid, i.e. the number of cells per box/row/column.
115
116 Returns a tuple of height, width."""
117
118 # Most obvious: probably n * n.
119 root = int(sqrt(dimension))
120 if root ** 2 == dimension:
121 return root, root
122
123 # Otherwise, probably n * (n - 1) or n * (n - 2).
124 # These puzzles generally have the wide side (n) as the width.
125 # This is of course entirely unreliable, but better than nothing..
126 # n^2 - (1|2)n - dimension = 0
127 # Determinant is (1|2)^2 + 4 * dimension and has to be square
128 for difference in 1, 2:
129 determinant = difference ** 2 + 4 * dimension
130 root = int(sqrt(determinant))
131 if root ** 2 != determinant:
132 continue
133
134 n = (-difference + root) / 2
135 if n != int(n):
136 continue
137
138 # Success!
139 return n - difference, n
140
141 # Okay, I don't have a clue.
142 raise GridSizeError("Can't infer box height and width for grid size "
143 "%d; please specify them manually" % dimension)
144
145 ### Accessors
146
147 def get_constraints(self, constraint_class=CellConstraint):
148 """Returns constraints of a certain type. Returns all of them by
149 default.
150 """
151
152 condition = lambda constraint: isinstance(constraint, constraint_class)
153 return filter(condition, self._constraints)
154
155 rows = property(lambda self: self.get_constraints(Row))
156 box_height = property(attrgetter('_box_height'))
157 box_width = property(attrgetter('_box_width'))
158 size = property(attrgetter('_size'))
159 constraints = property(attrgetter('_constraints'))
160
161 ### Constructors
162
163 def __init__(self, box_height=3, box_width=None):
164 if not box_width:
165 box_width = box_height
166
167 self._box_height = box_height
168 self._box_width = box_width
169 self._size = box_height * box_width
170
171 self._cells = range(self.size ** 2)
172 for row in xrange(self.size):
173 for col in xrange(self.size):
174 self._cells[self._cellidx(row, col)] \
175 = Cell(self, row, col)
176
177 self._constraints = []
178 self.add_default_constraints()
179
180 @classmethod
181 def from_matrix(cls, rows, box_height=None, box_width=None):
182 """Creates and returns a grid read from a list of lists."""
183
184 if not box_height:
185 box_height, box_width = cls._infer_box_size(len(rows))
186 elif not box_width:
187 box_width = box_height
188
189 self = cls(box_width=box_width, box_height=box_height)
190
191 for row in xrange(self.size):
192 for col in xrange(self.size):
193 value = rows[row][col]
194 if not value:
195 continue
196 self.cell(row, col).set(value - 1, normalize=False)
197
198 return self
199
200 @classmethod
201 def from_string(cls, grid, box_height=None, box_width=None):
202 # XXX sanity check dimensions
203 """Creates and returns a grid from a string of symbols.
204
205 Symbols are the digits 1 to 9 followed by the letters of the alphabet.
206 Zeroes and periods are assumed to be empty cells. All other characters
207 are ignored.
208
209 Since whitespace is ignored, the string could be all in one line or
210 laid out visually in a square, one row per line."""
211
212 # Collapse the string down to just characters we want
213 grid = grid.lower()
214 grid = re.sub('\\.', '0', grid)
215 grid = re.sub('[^0-9a-z]', '', grid)
216
217 # Figure out the length of one side/box
218 size = int(sqrt(len(grid)))
219 if size ** 2 != len(grid):
220 raise GridSizeError("Provided string does not form a square")
221
222 # Set height/width..
223 if not box_height:
224 box_height, box_width = cls._infer_box_size(size)
225 elif not box_width:
226 box_width = box_height
227
228 self = cls(box_width=box_width, box_height=box_height)
229
230 for row in xrange(self.size):
231 for col in xrange(self.size):
232 ch = grid[ self._cellidx(row, col) ]
233 if ch == '0':
234 continue
235 self.cell(row, col).set(symbols.index(ch), normalize=False)
236
237 return self
238
239 ### Constraints
240
241 def add_constraint(self, constraint):
242 self._constraints.append(constraint)
243 for cell in constraint.cells:
244 cell.add_constraint(constraint)
245
246 def add_default_constraints(self):
247 for i in xrange(self.size):
248 self.add_constraint(Row(self, i))
249 self.add_constraint(Column(self, i))
250 self.add_constraint(Box(self, i))
251
252 return
253
254 ### Inspectors
255
256 def cell(self, row, column):
257 return self._cells[self._cellidx(row, column)]
258
259 def is_filled(self):
260 for cell in self._cells:
261 if cell.value == None:
262 return False
263 return True
264
265 ### Solving
266
267 def check(self):
268 """Returns True iff the grid is solved. Raises an exception if an
269 integrity problem is found, such as a value appearing twice in a row.
270 """
271 # TODO remove this; name sucks and concept also sucks
272 return None
273
274
275 def solve(self):
276 """Attempts to solve the grid."""
277 # XXX track how many cells are changed and repeat as appropriate
278
279 # Step 0: Normalize cells, i.e. find any that can only be one value
280 self.normalize_cells()
281
282 # Step 1: Find values that can only go in one cell in a group
283 for group in self.constraints:
284 group.resolve_uniques()
285
286
287 def normalize_cells(self):
288 """Normalizes every cell in the grid."""
289 for cell in self._cells:
290 cell.normalize()