from __future__ import division

from math import sqrt
from operator import attrgetter
import re

from cell import Cell
from constraints import Constraint, Row, Column, Box

symbols = [str(x + 1) for x in range(9)] + [chr(x + 97) for x in xrange(26)]

class GridSizeError(Exception):
    """Exception thrown when an impossible grid size is encountered."""
    pass

class GridIntegrityError(Exception):
    """Exception thrown when a grid's state violates its own constraints.  This
    should only happen if there are bugs in the code itself.
    """
    pass


class Grid(object):
    """Represents a Sudoku grid."""

    ### Utilities

    def _cellidx(self, row, col):
        """Hashes a row and column into a flat array index."""
        return row * self.size + col

    @classmethod
    def _infer_box_size(cls, dimension):
        """Attempts to infer the size of a box, given some dimension of the
        entire grid, i.e. the number of cells per box/row/column.
        
        Returns a tuple of height, width."""
        
        # Most obvious: probably n * n.
        root = int(sqrt(dimension))
        if root ** 2 == dimension:
            return root, root

        # Otherwise, probably n * (n - 1) or n * (n - 2).
        # These puzzles generally have the wide side (n) as the width.
        # This is of course entirely unreliable, but better than nothing..
        #   n^2 - (1|2)n - dimension = 0
        #   Determinant is (1|2)^2 + 4 * dimension and has to be square
        for difference in 1, 2:
            determinant = difference ** 2 + 4 * dimension
            root = int(sqrt(determinant))
            if root ** 2 != determinant:
                continue

            n = (-difference + root) / 2
            if n != int(n):
                continue

            # Success!
            return n - difference, n
        
        # Okay, I don't have a clue.
        raise GridSizeError("Can't infer box height and width for grid size "
                            "%d; please specify them manually" % dimension)

    ### Accessors

    def get_constraints(self, constraint_class=Constraint):
        """Returns constraints of a certain type.  Returns all of them by
        default.
        """

        condition = lambda constraint: isinstance(constraint, constraint_class)
        return filter(condition, self._constraints)

    rows = property(lambda self: self.get_constraints(Row))
    columns = property(lambda self: self.get_constraints(Column))
    boxes = property(lambda self: self.get_constraints(Box))

    box_height = property(attrgetter('_box_height'))
    box_width = property(attrgetter('_box_width'))
    size = property(attrgetter('_size'))
    constraints = property(attrgetter('_constraints'))

    def _is_filled(self):
        for cell in self._cells:
            if cell.value == None:
                return False
        return True
    filled = property(_is_filled)

    ### Constructors

    def __init__(self, box_height=3, box_width=None):
        if not box_width:
            box_width = box_height

        self._box_height = box_height
        self._box_width = box_width
        self._size = box_height * box_width

        self._cells = range(self.size ** 2)
        for row in xrange(self.size):
            for col in xrange(self.size):
                self._cells[self._cellidx(row, col)] \
                    = Cell(self, row, col)

        self._constraints = []
        self.add_default_constraints()

    @classmethod
    def from_matrix(cls, rows, box_height=None, box_width=None):
        """Creates and returns a grid read from a list of lists."""

        if not box_height:
            box_height, box_width = cls._infer_box_size(len(rows))
        elif not box_width:
            box_width = box_height

        self = cls(box_width=box_width, box_height=box_height)

        for row in xrange(self.size):
            for col in xrange(self.size):
                value = rows[row][col]
                if not value:
                    continue
                self.cell(row, col).set(value - 1, normalize=False)

        return self

    @classmethod
    def from_string(cls, grid, box_height=None, box_width=None):
        # XXX sanity check dimensions
        """Creates and returns a grid from a string of symbols.

        Symbols are the digits 1 to 9 followed by the letters of the alphabet.
        Zeroes and periods are assumed to be empty cells.  All other characters
        are ignored.

        Since whitespace is ignored, the string could be all in one line or
        laid out visually in a square, one row per line."""

        # Collapse the string down to just characters we want
        grid = grid.lower()
        grid = re.sub('\\.', '0', grid)
        grid = re.sub('[^0-9a-z]', '', grid)

        # Figure out the length of one side/box
        size = int(sqrt(len(grid)))
        if size ** 2 != len(grid):
            raise GridSizeError("Provided string does not form a square")

        # Set height/width..
        if not box_height:
            box_height, box_width = cls._infer_box_size(size)
        elif not box_width:
            box_width = box_height

        self = cls(box_width=box_width, box_height=box_height)

        for row in xrange(self.size):
            for col in xrange(self.size):
                ch = grid[ self._cellidx(row, col) ]
                if ch == '0':
                    continue
                self.cell(row, col).set(symbols.index(ch), normalize=False)

        return self

    ### Constraints

    def add_constraint(self, constraint):
        self._constraints.append(constraint)
        for cell in constraint.cells:
            cell.add_constraint(constraint)

    def add_default_constraints(self):
        for i in xrange(self.size):
            self.add_constraint(Row(self, i))
            self.add_constraint(Column(self, i))
            self.add_constraint(Box(self, i))

        return

    ### Inspectors

    def cell(self, row, column):
        return self._cells[self._cellidx(row, column)]

    ### Solving

    def normalize_cells(self):
        """Normalizes every cell in the grid.
        
        Returns the number of cell changes."""

        cell_changes = 0
        for cell in self._cells:
            cell_changes += cell.normalize()

        return cell_changes

    def resolve_uniques(self):
        """Searches each group of cells for a value that can only appear in a
        single cell.
        
        Returns the number of cell changes."""

        cell_changes = 0
        for constraint in self.constraints:
            cell_changes += constraint.resolve_uniques()

        return cell_changes

    _solution_steps = [
        normalize_cells,
        resolve_uniques,
    ]

    def solve(self):
        """Attempts to solve the grid by running through various methods of
        elimination one at a time, from simplest to most complex."""

        while True:
            for method in self._solution_steps:
                cell_changes = method(self)

                # If we changed something, start over with simple steps again
                if cell_changes:
                    break

            # If we didn't do anything this round, we're done
            if not cell_changes:
                break