(original) (raw)

############################################################################## ## ## a bug? The change of line 146 from ## print "1" ## to ## print 1 ## changes results of the program ## grey = 0 black = 1 white = -1 vertical = 0 horizontal = 1 def clr(c): if c == grey: return " " elif c == white: return " ." elif c == black: return " B" else: assert False, "illegal color" class Cell(object): __slots__ = ["grid", "coord", "color", "seqs"] def __init__(self, grid, coord): self.grid = grid self.coord = coord self.color = grey self.seqs = [None, None] def paint(self, seqdir, color): if self.color != color: assert self.color == grey, "an attempt to re-paint cell:" + str(self.coord) otherseq = self.seqs[seqdir ^ 1] assert not otherseq.complete, "a complete sequence with grey cells:" + str(self.coord) self.grid.dirty.add(otherseq) self.color = color def __repr__(self): return clr(self.color) class Clue(object): __slots__ = ["size"] def __init__(self, size): self.size = size ###### ## The Sequence ## 'tuple' would be a better word, but it is already taken ## class Sequence(object): __slots__ = ["grid", "orientation", "cells", "clues", "complete"] def __init__(self, grid, orientation, cells, clues): self.grid = grid self.orientation = orientation self.cells = cells self.clues = clues self.complete = False for cell in cells: assert cell.grid == grid, "grid mixup" + str(cell.coord) assert cell.seqs[orientation] == None, "cell belongs to more than one seq of the same orientation: " + str(cell.coord) cell.seqs[orientation] = self def cutoff(self, end): if end > 0: del self.cells[:end] else: del self.cells[end:] def check(self): assert self.clues, "a seq with no clues" filled = sum(clue.size for clue in self.clues) minfill = min(clue.size for clue in self.clues) assert minfill > 0 or (minfill == 0 and len(self.clues) == 1), "illegal clues (zeroes)" assert filled + len(self.clues) <= len(self.cells) + 1, "illegal clues (too big fill)" def fillcomplete(self): expected = sum(clue.size for clue in self.clues) filled = sum(cell.color == black for cell in self.cells) if expected == filled: for cell in self.cells: if cell.color == grey: cell.paint(self.orientation, white) self.complete = True self.grid.incomplete.remove(self) def simplescan(self): assert self.clues, "a seq with no clues" filled = sum(clue.size for clue in self.clues) maxfill = max(clue.size for clue in self.clues) balance = len(self.cells) - filled - len(self.clues) + 1 if balance < maxfill: offset = 0 for clue in self.clues: for ix in range(balance, clue.size): self.cells[offset + ix].paint(self.orientation, black) offset += clue.size + 1 def edges1(self, step): # nota bene: start is used for both cells and clues # therefore, it cannot be len(cells) start = 0 if step > 0 else -1 while self.cells and self.cells[start].color != grey: if self.cells[start].color == white: del self.cells[start] else: ## must be black sz = self.clues[start].size for ix in range(sz): self.cells[start + step*ix].paint(self.orientation, black) if sz < len(self.cells): self.cells[start + step*sz].paint(self.orientation, white) sz += 1 self.cutoff(sz * step) del self.clues[start] def edges2(self, step): # nota bene: start is used for both cells and clues # therefore, it cannot be len(cells) start = 0 if step > 0 else -1 while self.cells: sz = self.clues[start].size assert sz > 0 for ix in range(sz): color = self.cells[start + step*ix].color if color != grey: break if color == white: for iy in range(ix): self.cells[start + step*iy].paint(self.orientation, white) self.cutoff(step * (ix + 1)) self.dumpseq("after white>") continue elif color == black: print 1 for iy in range(ix, sz): self.cells[start + step*iy].paint(self.orientation, black) for iy in range(ix, ix+sz): if iy == len(self.cells): break color = self.cells[start + step*iy].color if color != black: break if color == grey: ## cannot do any more break # iy points either on 1 or beyond the grid for iz in range(iy-sz, iy): self.cells[start + step * iz].paint(self.orientation, black) for iz in range(iy-sz): self.cells[start + step * iz].paint(self.orientation, white) self.cutoff(step * iy) del self.clues[start] if not self.clues: break else: break def dumpseq(self, prompt): pass class Grid(object): __slots__ = ["rows", "cols", "grid", "dirty", "incomplete"] def __init__(self, hclues, vclues): self.rows = len(hclues) self.cols = len(vclues) self.grid = [ [ Cell(self, (r+1, c+1)) for c in xrange(self.cols)] for r in xrange(self.rows)] self.incomplete = set( Sequence(self, horizontal, list(self.grid[r]), [Clue(cl) for cl in hclues[r]]) for r in xrange(self.rows) ) self.incomplete |= set( Sequence(self, vertical, [self.grid[r][c] for r in xrange(self.rows)], [Clue(cl) for cl in vclues[c]]) for c in xrange(self.cols) ) self.dirty = None for r in xrange(self.rows): for c in xrange(self.cols): assert self.grid[r][c].seqs[horizontal] != None and self.grid[r][c].seqs[vertical] != None, "cell does not belong to two seqs:" + str((r, c)) for seq in self.incomplete: seq.check() def dump(self): print " ", "".join(["%2d" % (c+1) for c in range(self.cols)]) for r in range(self.rows): acc = "%2d " % (r+1) for c in range(self.cols): acc += clr(self.grid[r][c].color) print acc def solve(self): self.dirty = self.incomplete.copy() while self.dirty: seq = self.dirty.pop() seq.fillcomplete() if seq.complete: continue seq.simplescan() seq.fillcomplete() if seq.complete: continue seq.edges1(+1) ## we can have no clues at this point ## but we cannot have any black cells with no clues seq.edges1(-1) seq.fillcomplete() if seq.complete: continue seq.simplescan() seq.fillcomplete() if seq.complete: continue seq.edges2(+1) if seq.clues: seq.edges2(-1) seq.dumpseq("edges2 after>") seq.fillcomplete() if seq.complete: continue seq.simplescan() seq.fillcomplete() if seq.complete: continue if self.incomplete: print "try to improve solving algorithm!" else: print "Congratulations: grid solved!" if __name__ == "__main__": g = Grid([(5,1,1), (1,4,1), (2,2), (6,), (1,3,3)], [(1,1), (2,), (1,1), (1,2), (2,2), (3,), (4,), (1,2), (3,), (3,1)] ) g.solve() g.dump()