#!/usr/bin/python
# -*- coding: utf-8 -*-

# Copyright (C) 2018 Rod Engerstad

import random
from random import randint
import Tkinter as tk
import itertools
from itertools import product
import sys
import time

from nurikabe_data import ModelData
from pzl_lib import PzlG
from pzl_lib import SettingsB
from pzl_lib import Preferences
from pzl_lib import MenuItem
from pzl_lib import Flasher
from pzl_lib import ScreenShot
from pzl_lib import ViewB
from pzl_lib import TextSquare

class Sgg(object):
    """
    Game globals
    """
    grid_width = 6
    grid_height = 6
    cell_count = grid_width * grid_height
    GIVE_HINT = 0
    APPLY_HINT = 1
    DELETE = 4
    HINT = 8

    alg_count = 21
    alg_usage = [0] * alg_count
    ALGORITHM_NAMES = list(range(alg_count))

    WHITE = 9999
    BLACK = 1000
    GREY = 2000

    CURRENT_PUZZLE = []
    progress = False

    generate = False
    max_time = None
    start_time = None
    seed = None


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.original_square_size = 36
        self.square_size = self.original_square_size
        self.dic = {}
        self.dic['font_size'] = '2'
        self.menu_items = []

        self.preferences = Preferences(self.dic)
        self.preferences.load()
        self.load_menus()
        self.count = len(self.menu_items)
        self.set_fonts()
        self.make_help()
        self.make_tooltip()
        self.make_alg_help()

    def make_alg_help(self):
        self.alg_text = [_("If a white can only extend via a single cell, that cell must be white."), _("Black cells must touch other black cells"), _("White cells cannot touch white cells from other clues"), _("Cells which cannot be reached by any clue must be black"), _("This cell must be part of a cluster of whites"), _("This cell is the only possible way to connect a string of black cells"), _("This cell cannot be reached by any clue, so must be black"), _("This cell cannot be reached by any clue, so must be black"), _("This cell must be part of the cluster of whites"), _("This cell cannot be part of the adjacent white cluster so must be black"), _("White cells cannot touch white cells from other clues"), _("White cells cannot touch white cells from other clues"), _("Whichever way the nearby white is finished the cell must be black"), _("This cell cannot be reached by any clue, so must be black"), _("Squares of four blacks are forbidden, so this cell is white"), _("Whichever way the nearby white is finished the cell must be black"), _("Squares of four blacks are forbidden, so this cell is white"), _("Squares of four blacks are forbidden, so this cell is white"), _("White cells cannot touch white cells from other clues"), _("Cells which cannot be reached by any clue must be black"), _("This is a fallback hint, not based on logic!")]
            

    def make_tooltip(self):
        self.tooltip_text = [
            _('Left-mouse random puzzle, right-mouse next puzzle'), _('Give hint, Apply hint'), _('Check for errors, correct errors'), _('Show solution')]

    def make_help(self):
        self.help_text = _("The program starts with a randomly selected puzzle displayed. It shows a grid of cells, some are white and containing numbers, but most are grey which indicates they are unsolved.  Cells touch orthogonally and the cells from one clue must not touch those of another. When the puzzle is complete each clue cell of value N must be part of a cluster of touching white cells of size N and all other cells on the board must be black. The black cells must touch to form a continuous path. This means that from every black cell we can find a route to any other, using only touching black cells. The final rule is that no 2x2 blocks of black cells (squares) are allowed. Players can set cells white with a left mouse click, black with right mouse, and can undo with middle mouse.  In the toolbar the jigsaw symbol contains a menu, the next symbol starts a new game; the wand requests a hint, a second click on the wand will perform the hint operation; the thumb checks if the puzzle contains any errors and a second click will clear the errors; the sad smiley shows the solution; the entrybox shows the current puzzle number and can be used to select a new puzzle number. The clock ticks every 5 seconds but will be replaced by the algorithm number if a hint is requested.  While the hint is active (shown by the wand icon leaning backwards) clicking on the wand with the middle mouse button will cause a pop-up to appear containing a short explanation of the hint. The game contains 500 puzzles, each with grids of 10x10 cells.")

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Font Size'),
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9',
             '10',
             '11',
             '12',
             '13'],
            '',
            ['1',
             '2',
             '3',
             '4',
             '5',
             '6',
             '7',
             '8',
             '9',
             '10',
             '11',
             '12',
             '13'],
            'font_size'
            ))
        """
        self.menu_items.append(MenuItem(
            _('Temp Solver'),
            '',
            '',
            '',
            'temp_solver'
        ))
        """
        self.menu_items.append(MenuItem(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))


class UserEdits(object):
    """
    Actions performed by user stored as datums
    If we get an undo command we simple reset the cell to grey
    """
    def __init__(self):
        self.edits = []

    def add(self, datum):
        self.edits.append(datum)

    def delete(self, datum):
        datum_index = datum.index
        for item in self.edits:
            item_id = item.index
            if item_id == datum_index:
                try:
                    self.edits.remove(item)
                    datum.reset()
                    break
                except ValueError:
                    pass


class Datum(object):
    """
    Data item for a cell

    white is conventionally drawn white (0) and form walls
    black is conventinally drawn black (1) and form the stream
    """
    def __init__(self, datum_index, value):
        self.index = datum_index
        self.row = None
        self.column = None
        self.status = True
        self.size = None
        self.guess = None
        self.clue_cell = False
        self.owner = None
        self.reached_by = []
        if value == 0:
            self.colour = Sgg.WHITE
        elif value == 1:
            self.colour = Sgg.BLACK
        else:
            # a clue cell
            self.colour = Sgg.WHITE
            self.size = abs(value)
            self.clue_cell = True
            self.guess = Sgg.WHITE
            self.reached_by = [datum_index]
        self.neighbours_55 = []
        self.neighbours_sq = []
        self.neighbours_gg = []
        self.gneighbours = []
        self.set_row_and_column()
        self.set_neighbours()

    def set_guess(self, guess):
        self.guess = guess
        self.status = True
        if guess == Sgg.BLACK:
            self.reached_by = []
        if self.guess != self.colour:
            self.status = False

    def reset(self):
        self.status = True
        self.guess = None
        self.owner = None
        self.reached_by = []

    def remove_reacher(self, reacher):
        if reacher in self.reached_by:
            Sgg.progress = True
            if self.guess == Sgg.WHITE:
                if len(self.reached_by) > 1 and self.index != reacher:
                    self.reached_by.remove(reacher)
            else:
                self.reached_by.remove(reacher)

    def set_reached_by(self, reached_by):
        self.reached_by = reached_by
        Sgg.progress = True

    def set_owner(self, owner):
        """
        If a cell is white it cannot have a white cell from
        another clue touching laterally or vertically.
        Here we denote which clue "owns" these cells.
        If more than one cell claims ownership the cell
        must be BLACK
        """
        ret = None
        if self.owner is None:
            self.owner = owner
            Sgg.progress = True
        elif self.owner != owner:
            if self.guess is None:
                ret = self.index
                Sgg.progress = True
        return ret

    def is_navigable(self, owner):
        """
        an individual datum is possibly navigable if it is not BLACK
        and if owned is owned by owner
	OR if finding paths between Blacks we send None as owner
        """
        ret = True
        if owner is None:
            if self.guess == Sgg.WHITE:
                ret = False
        else:
            if self.guess == Sgg.BLACK or \
                (self.owner is not None and self.owner != owner):
                ret = False

        return ret

    def touches(self, datum_index):
        ret = False
        if datum_index in self.neighbours_gg:
            ret = True
        return ret

    def is_correct(self, value):
        ret = True
        if self.colour != value:
            ret = False
        return ret

    def is_consistent(self):
        if self.guess != None:
            ret = (self.guess == self.colour)
        else:
            ret = True
        if not ret:
            PzlG.logger.logger.info("inconsistent datum " + str(self.index))
        return ret


    def set_row_and_column(self):
        self.row = self.index / Sgg.grid_width
        self.column = self.index % Sgg.grid_width

    def is_owned(self):
        ret = True
        if self.owner is None:
            ret = False
        return ret

    def set_neighbours(self):
        """
        Set the neighbours
            gg
             0
           3 . 1
             2

        _sq
           7 0 1
           6 . 2
           5 4 3

        _55
        opabc
        n701d
        m682e
        l543f
        kjihg

        """
        self.neighbours_55 = []
        self.neighbours_sq = []
        self.neighbours_gg = []

        # up 0
        nbr_index = self.index - Sgg.grid_width
        if nbr_index > -1:
            self.neighbours_gg.append(nbr_index)
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # up right 1
        nbr_index = self.index - Sgg.grid_width + 1
        if nbr_index > -1 and (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # right 2
        nbr_index = self.index + 1
        if (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_gg.append(nbr_index)
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # down right 3
        nbr_index = self.index + Sgg.grid_width + 1
        if nbr_index < Sgg.cell_count and\
           (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # down 4
        nbr_index = self.index + Sgg.grid_width
        if nbr_index < Sgg.cell_count:
            self.neighbours_gg.append(nbr_index)
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # down left 5
        nbr_index = self.index + Sgg.grid_width - 1
        if nbr_index < Sgg.cell_count and self.index % Sgg.grid_width != 0:
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # left 6
        nbr_index = self.index - 1
        if self.index % Sgg.grid_width != 0:
            self.neighbours_gg.append(nbr_index)
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # up left 7
        nbr_index = self.index - Sgg.grid_width - 1
        if nbr_index > -1 and self.index % Sgg.grid_width != 0:
            self.neighbours_sq.append(nbr_index)
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_sq.append(None)
            self.neighbours_55.append(None)

        # up 2 a
        nbr_index = self.index - 2 * Sgg.grid_width
        if nbr_index > -1:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)
        # b
        nbr_index = self.index - 2 * Sgg.grid_width + 1
        if nbr_index > -1 and (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # c
        nbr_index = self.index - 2 * Sgg.grid_width + 2
        if nbr_index > -1 and\
           (self.index + 1) % Sgg.grid_width != 0 and\
           (self.index + 2) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # d
        nbr_index = self.index - Sgg.grid_width + 2
        if nbr_index > -1 and\
           (self.index + 1) % Sgg.grid_width != 0 and\
           (self.index + 2) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        """
        _55
        opabc
        n701d
        m682e
        l543f
        kjihg
        """
        # e
        nbr_index = self.index + 2
        if (self.index + 1) % Sgg.grid_width != 0 and\
           (self.index + 2) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # f
        nbr_index = self.index + Sgg.grid_width + 2
        if nbr_index < Sgg.cell_count and\
           (self.index + 2) % Sgg.grid_width != 0 and\
           (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # g
        nbr_index = self.index + 2 * Sgg.grid_width + 2
        if nbr_index < Sgg.cell_count and\
           (self.index + 1) % Sgg.grid_width != 0 and\
           (self.index + 2) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # h
        nbr_index = self.index + 2 * Sgg.grid_width + 1
        if nbr_index < Sgg.cell_count and\
           (self.index + 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # i
        nbr_index = self.index + 2 * Sgg.grid_width
        if nbr_index < Sgg.cell_count:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # j
        nbr_index = self.index + 2 * Sgg.grid_width - 1
        if nbr_index < Sgg.cell_count and\
           self.index % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # k
        nbr_index = self.index + 2 * Sgg.grid_width - 2
        if nbr_index < Sgg.cell_count and\
           self.index % Sgg.grid_width != 0 and\
           (self.index - 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        """
        _55
        opabc
        n701d
        m682e
        l543f
        kjihg
        """
        # l
        nbr_index = self.index + Sgg.grid_width - 2
        if nbr_index < Sgg.cell_count and\
           self.index % Sgg.grid_width != 0 and\
           (self.index - 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # m
        nbr_index = self.index - 2
        if nbr_index > -1 and\
           self.index % Sgg.grid_width != 0 and\
           (self.index - 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # n
        nbr_index = self.index - Sgg.grid_width - 2
        if nbr_index > -1 and\
           self.index % Sgg.grid_width != 0 and\
           (self.index - 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # o
        nbr_index = self.index - 2 * Sgg.grid_width - 2
        if nbr_index > -1 and\
           self.index % Sgg.grid_width != 0 and\
           (self.index - 1) % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)

        # p
        nbr_index = self.index - 2 * Sgg.grid_width - 1
        if nbr_index > -1 and\
           self.index % Sgg.grid_width != 0:
            self.neighbours_55.append(nbr_index)
        else:
            self.neighbours_55.append(None)
        self.neighbours_55.append(self.index)

    def __str__(self):
        return str(self.guess) + ' '


class Black(object):
    """
    Data for one set of black cells
    Each cell is a Datum.
    """
    next_id = 0
    def __init__(self):
        self.index = Black.next_id
        Black.next_id += 1
        self.cells = set([])
        self.delete = False

    def add(self, new_cells):
        # add a new list of datum
        Sgg.progress = True
        for new_cell in new_cells:
            self.cells.add(new_cell)

    def contains_index(self, datum_index):
        ret = False
        for datum in self.cells:
            if datum.index == datum_index:
                ret = True
                break
        return ret

    def for_deletion(self):
        Sgg.progress = True
        self.delete = True

    def merge(self, black):
        Sgg.progress = True
        self.cells = self.cells.union(black.cells)

    def items(self):
        return self.cells


class White(object):
    """
    Data for one set of white cells or clue.
    Each cell is a Datum. The clue_index is datum.index.
    A cell is connected to a clue_cell if
    it touches it or touches a chain of whites that do.
    An orphan cell is always unconnected but if we know its
    clue we can set clue_cell accordingly. Then we say it
    "contains_clue".
    """
    next_id = 0
    def __init__(self, datum):
        self.datum_index = datum.index
        self.index = White.next_id
        White.next_id += 1
        self.cells = set([datum])
        self.linear = False
        self.size = datum.size
        self.contains_clue_cell = False
        if datum.size is not None:
            self.clue_index = datum.index
            self.connected = True
        else:
            self.clue_index = None
            self.connected = False
        self.finished = False
        self.surrounded = False
        self.delete = False
        # should this be done here?
        if len(self.cells) == self.size:
            self.finished = True
            self.connected = True

    def is_consistent(self):
        ret = True
        if not self.cells:
            ret = False
        return ret

    def add(self, new_cell):
        Sgg.progress = True
        self.cells.add(new_cell)
        if len(self.cells) == self.size:
            self.finished = True
            self.connected = True

    def add_clue_cell(self, clue_index):
        Sgg.progress = True
        self.clue_index = clue_index
        self.contains_clue_cell = True
        for cell in self.cells:
            cell.set_owner(clue_index)
            cell.set_reached_by([clue_index])
        if len(self.cells) == self.size:
            self.finished = True
            self.connected = True

    def merge(self, white):
        Sgg.progress = True
        self.cells = self.cells.union(white.cells)
        if len(self.cells) == self.size:
            self.finished = True
            self.connected = True
        # take the strongest settings for the rest
        if self.size is None and white.size is not None:
            self.size = white.size
            self.clue_index = white.clue_index
            # check reached_bys
            for cell in self.cells:
                cell.set_reached_by([self.clue_index])
        if self.connected or white.connected:
            self.connected = True

    def items(self):
        return self.cells

    def is_connected(self):
        return self.connected

    def is_finished(self):
        return self.finished

    def is_surrounded(self):
        return self.surrounded

    def contains_clue(self):
        return self.contains_clue_cell

    def contains_index(self, datum_index):
        ret = False
        for datum in self.cells:
            if datum.index == datum_index:
                ret = True
                break
        return ret

    def touches(self, datum_index):
        ret = False
        for datum in self.cells:
            if datum.touches(datum_index):
                ret = True
                break
        return ret

    def for_deletion(self):
        Sgg.progress = True
        self.delete = True

    def contacts(self, datum_index):
        ret = False
        if self.contains_index(datum_index) or\
           self.touches(datum_index):
            ret = True
        return ret


class Container(object):
    """
    A collection of objects
    """

    def __init__(self):
        self.contents = set([])

    def add(self, item):
        self.contents.add(item)

    def delete(self):
        self.contents = set([x for x in self.contents if not x.delete])
        Sgg.progress = True

    def items(self):
        return self.contents

class Node(object):
    """
    A node for Djkstra
    """
    def __init__(self, datums, datum, clue_cell, oob):
        self.index = datum.index
        self.neighbours = []
        for neighbour in datum.gneighbours:
            if datums[neighbour].is_navigable(clue_cell) and \
               neighbour not in oob:
                self.neighbours.append(neighbour)
            else:
                pass
        self.distance = 999999
        self.unvisited = True
        self.predecessor = None
        self.predecessors = []


class Dijkstra(object):
    """
    Dijkstra algorithm to find path from start to finish
    """
    def __init__(self, datums, start, finish, clue_cell, oob,
                 get_paths):
        self.path = []
        self.success = False
        self.get_paths = get_paths
        self.distance = None
        self.start_node_index = start
        self.end_node_index = finish
        # node_dic: a dictionary of Nodes indexed on datum.index
        # (only need navigable ones)
        # ie exclude BLACKs and those with no neighbours or which
        # are owned by other clues.
        # this is not enough to guarantee a path:
        # unknowns may be BLACK, but it tells if a cell is
        # definitely unreachable

        # next case add Jan 2018!
        if start == finish:
            self.distance = 0
            self.path = []
            return

        self.node_dic = {}
        for datum in datums:
            good_datum = False
            if datum.is_navigable(clue_cell) and \
               datum.index not in oob:
                for neighbour in datum.neighbours_gg:
                    if datums[neighbour].is_navigable(clue_cell) and \
                       neighbour not in oob:
                        good_datum = True
                        break
            if good_datum:
                self.node_dic[datum.index] = Node(datums,
                                                  datum,
                                                  clue_cell,
                                                  oob)

        # check that end nodes are potentially reachable
        if self.end_node_index in self.node_dic and \
           self.start_node_index in self.node_dic:
            # active_dic a dictionary of nodes indexed on datum.index
            # at the beginning it contains only the start node but
            # we add each node as we meet it. When weve dealt with all
            # a nodes neighbours we remove it from active_dic
            self.active_dic = {}
#            for key, value in self.active_dic.iteritems():
            self.active_dic[self.start_node_index] = \
                                                     self.node_dic[self.start_node_index]
            # try to find the path
            self.doit()

    def doit(self):
        current_node_index = self.start_node_index
        current_node = self.active_dic[current_node_index]
        current_node.distance = 0
        while True:
            # find active node with shortest distance
            # only active nodes can be part of the path
            current_node = None
            shortest_distance = 999999
            for key, value in list(self.active_dic.items()):
                if value.distance < shortest_distance:
                    shortest_distance = value.distance
                    current_node_index = key
                    current_node = value

            if current_node is not None:
                # update distance for all its unvisited neighbours
                for neighbour_index in current_node.neighbours:
                    try:
                        neighbour_node = self.node_dic[neighbour_index]
                        if neighbour_node.unvisited:
                            # first visit so add it to active
                            self.active_dic[neighbour_node.index] = neighbour_node
                            distance = current_node.distance + 1
                            if self.get_paths:
                                if distance <= neighbour_node.distance:
                                    neighbour_node.distance = distance
                                    neighbour_node.predecessors.append(current_node_index)
                            else:
                                if distance < neighbour_node.distance:
                                    neighbour_node.distance = distance
                                    neighbour_node.predecessor = \
                                                                 current_node_index

                    except KeyError:
                        pass
                # mark current_node visited and remove it from active_nodes
                current_node.unvisited = False
                del self.active_dic[current_node_index]
                if not self.node_dic[self.end_node_index].unvisited:
                    # we've arrived!
                    self.success = True
                    break
            else:
                # there is no path!
                break

        self.do_path()

    def do_path(self):
        if self.success:
            if self.get_paths:
                path = []
                # find path
                distance = 0
                current_end = self.end_node_index
                while True:
                    path.extend(self.node_dic[current_end].predecessors)
                    distance += 1
                    if current_end == self.start_node_index:
                        break
                    current_end = self.node_dic[current_end].predecessors[0]
                self.distance = distance
                self.path = path
            else:
                # find distance
                path = []
                distance = 0
                current_end = self.end_node_index
                while True:
                    path.append(current_end)
                    distance += 1
                    if current_end == self.start_node_index:
                        break
                    current_end = self.node_dic[current_end].predecessor

                path.reverse()
                self.path = path
                self.distance = distance


class Pattern(object):
    """
    A pattern
    name:        a name for the pattern
    search_type: which datums to look through, Sgg.WHITE, Sgg.BLACK, Sgg.GREY
    set_type:    the value to be set for a hit, Sgg.WHITE, Sgg.BLACK
    set_position the position to set if we find a match
    opens:       cells which must be open
    whites:      cells which must be white
    blacks       cells which must be black (or off the board?)
            case = [centre, required_opens, required_blacks,
                    required_whites, exclusive_whites, essential_blacks,
                    set_position,
                    [set_type], [search_type]]
    """
    def __init__(self, name, pattern):
        self.template = [
            ['q', 'r', 'c', 'd', 'e'],
            ['p', '7', '0', '1', 'f'],
            ['o', '6', '8', '2', 'g'],
            ['n', '5', '4', '3', 'h'],
            ['m', 'l', 'k', 'j', 'i']]

        self.pattern = pattern
        self.name = name
        self.search_type = []
        self.set_type = []
        self.opens = []
        self.blacks = []
        self.whites = []
        self.set_position = ['8']
        self.exclusive_whites = []
        self.essential_blacks = []
        self.get_cases()

    def get_search_type(self):
        """
        """
        search_codes = ['V', 'w']
        search_type = '.'
        for row_index in range(len(self.pattern)):
            row = self.pattern[row_index]
            column_index = 0
            for column in row:
                for type_index in range(len(search_codes)):
                    if column == search_codes[type_index]:
                        search_type = column
                        break
                column_index += 1
        return search_type

    def get_set_type(self):
        """
        Z = open and the cell which will be set white if the pattern matches
        z = open and the cell which will be set black if the pattern matches
        V = open and the cell which will be set white if the pattern matches
        WHITE = 9999
        BLACK = 1000
        GREY = 2000
        """
        set_codes = ['Z', 'z', 'V']
        set_types = [Sgg.WHITE, Sgg.BLACK, Sgg.WHITE]
        set_type = None
        found = []
        for row_index in range(len(self.pattern)):
            row = self.pattern[row_index]
            column_index = 0
            for column in row:
                for type_index in range(len(set_codes)):
                    if column == set_codes[type_index]:
                        found.append(type_index)
                column_index += 1
        found = sorted(found)
        if found:
            set_type = set_types[found[0]]
        # gives precedent to earliest in list
        return set_type

    def get_case(self, codes):
        case = []
        for row_index in range(len(self.pattern)):
            row = self.pattern[row_index]
            column_index = 0
            for column in row:
                if column in codes:
                    case.append(self.template[row_index][column_index])
                column_index += 1
        return case

    def get_set_position(self):
        # if we have z or Z then it is the position to set
        codes = ['z', 'Z']
        pos = [0, 0]
        for row_index in range(len(self.pattern)):
            row = self.pattern[row_index]
            column_index = 0
            for column in row:
                if column in codes:
                    pos = self.template[row_index][column_index]
                    break
                column_index += 1
        return pos

    def get_cases(self):
        blacks = ['b']
        vital_blacks = ['B']
        whites = ['w', 'u', 'v', 'V']
        exclusive_whites_codes = ['w', 'u', 'v', 'V']
        opens = ['.', 'z', 'Z']
        self.blacks = self.get_case(blacks)
        self.essential_blacks = self.get_case(vital_blacks)
        self.opens = self.get_case(opens)
        self.whites = self.get_case(whites)
        self.exclusive_whites = self.get_case(exclusive_whites_codes)
        self.set_position = self.get_set_position()
        self.set_type = self.get_set_type()
        self.search_type = self.get_search_type()

    """
    def print_pattern(self):
        print
        for row in self.pattern:
            print row

    def print_me(self):
        print 'print_me'
        print 'name', self.name
        print 'search_type', self.search_type
        print 'set_type', self.set_type
        print 'opens', self.opens
        print 'blacks', self.blacks
        print 'whites', self.whites
        print 'set_position', self.set_position
        print 'exclusive_whites', self.exclusive_whites
        print 'essential_blacks', self.essential_blacks
    """


class NPattern(object):
    """Receives a pattern defined as text.
    Calculates all symmetirc versions of the pattern,
    removing duplicates, and then creates an individual
    search pattern (using Pattern) for each case.

    """

    def __init__(self, text):
        self.name = text[0]
        self.text = text[1:]
        self.centre = []
        self.pattern = []
        self.patterns = []
        """
        self.neighbour_codes = [
            ['q', 'r', 'c', 'd', 'e'],
            ['p', '7', '0', '1', 'f'],
            ['o', '6', '8', '2', 'g'],
            ['n', '5', '4', '3', 'h'],
            ['m', 'l', 'k', 'j', 'i']]
        """
        self.neighbour_codes = [['7', '0', '1'],
                                ['6', '8', '2'],
                                ['5', '4', '3']]
        self.search_patterns = []
        self.to_tuples()
        self.rotate()
        self.flip()

        self.prune_duplicates()
        self.make_search_patterns()

    def make_search_patterns(self):
        self.search_patterns = []
        count = 0
        for pattern in self.patterns:
            search_pattern = Pattern(self.name + str(count), pattern)
            self.search_patterns.append(search_pattern)
            count += 1

    def to_tuples(self):
        for line in self.text:
            row = tuple(line)
            self.pattern.append(row)

    def rotate(self):
        """
        We rotate the neighbour positions and the pattern
        self.neighbour_codes = [['7', '0', '1'],
                                ['6', '8', '2'],
                                ['5', '4', '3']]

        rotate_90 codes:
        ('5', '6', '7')
        ('4', '8', '0')
        ('3', '2', '1')
        """
        rotated_90 = list(zip(*self.pattern[::-1]))
        rotated_180 = list(zip(*rotated_90[::-1]))
        rotated_270 = list(zip(*rotated_180[::-1]))

        self.patterns.append(self.pattern)
        self.patterns.append(rotated_90)
        self.patterns.append(rotated_180)
        self.patterns.append(rotated_270)

    def flip(self):
        """
        701
        682
        543

        flip h
        107
        286
        345
        ie 2 6, 6 2

        flip v
        543
        682
        701
        ie 0 4, 4 0
        """

        flip_h = []
        flip_v = []
        rows = len(self.pattern)
        columns = len(self.pattern[0])
        if columns > 1:
            for row in self.pattern:
                flip_h.append(tuple(reversed(row)))
        if rows > 1:
            for row_index in range(rows - 1, -1, -1):
                new_row = []
                row = self.pattern[row_index]
                for column_index in range(columns):
                    new_row.append(row[column_index])
                flip_v.append(new_row)
        self.patterns.append(flip_h)
        self.patterns.append(flip_v)

        rows = len(self.pattern)
        columns = len(self.pattern[0])
        if rows == columns:
            # flip_d1 is r90 + flip_h
            rotated_90 = list(zip(*self.pattern[::-1]))
            flip_d1 = []
            for row in rotated_90:
                flip_d1.append(list(reversed(row)))

            # flip_d1 is r90 + flip_v
            flip_d2 = []
            for row_index in range(rows - 1, -1, -1):
                new_row = []
                row = rotated_90[row_index]
                for column_index in range(columns):
                    new_row.append(row[column_index])
                flip_d2.append(new_row)

            self.patterns.append(flip_d1)
            self.patterns.append(flip_d2)

    def prune_duplicates(self):
        for index_1 in range(len(self.patterns)):
            for index_2 in range(index_1 + 1,
                                 len(self.patterns)):
                if self.patterns[index_2] == self.patterns[index_1]:
                    self.patterns[index_2] = []

        final_patterns = []
        for pattern in self.patterns:
            if pattern:
                final_patterns.append(pattern)
        self.patterns = final_patterns

    """
    def print_pattern(self, pattern):
        print
        for row in pattern:
            print row

    def print_patterns(self):
        print 'print_patterns'
        for pattern in self.patterns:
            for row in pattern:
                print row
            print
    """


class Model(object):
    """

    """
    def __init__(self, settings, model_data):
        self.settings = settings
        self.model_data = model_data
        self.datum = []
        self.blacks = Container()
        self.whites = Container()
        self.unfinished_whites = []
        self.orphan_whites = []
        self.new_blacks = set([])
        self.unknowns = set([])
        self.status = True
        self.finished = False
        self.progress = True
        self.alg_count = Sgg.alg_count
        self.alg_usage = [0] * self.alg_count
        self.puzzle_number = None
        self.puzzle_data = []
        self.user_edits = UserEdits()
        self.search_patterns = []
        self.hints = []
        self.for_removal = []
        self.errors = []
        self.neighbour_dic = {
            '0': 0, '1': 1, '2': 2, '3': 3, '4': 4, '5': 5, '6': 6,
            '7': 7, 'c': 8, 'd': 9, 'e': 10, 'f': 11, 'g': 12,
            'h': 13, 'i': 14, 'j': 15, 'k': 16, 'l': 17, 'm': 18,
            'n': 19, 'o': 20, 'p': 21, 'q': 22, 'r': 23, '8': 24}
        """
        qrcde
        p701f
        o682g
        n543h
        mlkji

        """
        pattern_0 = 'near_whites_2', 'aaaaa', 'aauaa', 'aazva', 'aaaaa', 'aaaaa'
        pattern_1 = 'near_whites_1', 'aaaaa', 'aaaaa', 'auzva', 'aaaaa', 'aaaaa'
        pattern_2 = 'next_white_nw', 'auaaa', 'az.aa', 'a.waa', 'aaaaa', 'aaaaa'
        pattern_3 = 'black_hole', 'aaaaa', 'aabaa', 'abzba', 'aabaa', 'aaaaa'
        pattern_4 = 'black_squares', 'aaaaa', 'aaaaa', 'aaZBa', 'aaBBa', 'aaaaa'
        pattern_5 = 'last_white', 'aaaaa', 'aaaaa', 'aaV.a', 'aa.za', 'aaaaa'
        pattern_7 = 'black_pairs', 'aaaaa', 'aBBaa', 'a..aa', 'aaaaa', 'aaaaa'
        pattern_6 = 'black_singles', 'aabaa', 'aB.ba', 'b.Z.a', 'abaaa', 'aaaaa'
        self.text_patterns = [
            pattern_0,
            pattern_1,
            pattern_2,
            pattern_3,
            pattern_4,
            pattern_5,
            pattern_6,
            pattern_7]

        self.get_search_patterns()

    def get_search_patterns(self):
        self.search_patterns = []
        for text_pattern in self.text_patterns:
            patterns = NPattern(text_pattern).search_patterns
            self.search_patterns.append(patterns)

    def __str__(self):
        out = ''
        item = -1
        for y in range(Sgg.grid_height):
            string = str(y * Sgg.grid_width)
            out += string.rjust(4) + ' '
            for _ in range(Sgg.grid_width):
                item += 1
                o = str(self.datum[item])
                out += o
            out += '\n'
        return out

    def set_puzzle_number(self, puzzle_number):
        if puzzle_number is None or puzzle_number < 0 or \
                puzzle_number > self.model_data.puzzle_count - 1:
            puzzle_number = randint(0, self.model_data.puzzle_count - 1)
        self.puzzle_number = puzzle_number

    def update_alg_usage(self, alg):
        if alg < self.alg_count:
            self.alg_usage[alg] += 1
            Sgg.alg_usage[alg] += 1

    def init_types(self):
        """
        New puzzle: get list of whites and unknowns
        """
        for datum in self.datum:
            if datum.size != None:
                white = White(datum)
                self.whites.add(white)
                self.set_ownership(datum.index, datum.index)
            else:
                self.unknowns.add(datum.index)
        self.unfinished_whites = []
        self.orphan_whites = []
        whites = list(self.whites.items())
        for white in whites:
            if not white.is_finished():
                if white.is_connected():
                    clue_index = white.clue_index
                    for datum in list(white.items()):
                        datum.set_owner(clue_index)
                    self.unfinished_whites.append(white)

    def add_whites(self, hints):
        for hint in hints:
            datum_index = hint[0]
            self.add_white(datum_index)

    def get_unknowns(self, datum):
        unknowns = []
        nbrs = datum.neighbours_gg
        for nbr in nbrs:
            if self.datum[nbr].guess is None:
                unknowns.append(nbr)
        return unknowns

    def set_ownership(self, datum_index, clue_index):
        """
        New white. Claim ownership of vertical and lateral neighbours
        """
        datum = self.datum[datum_index]
        ret = datum.set_owner(clue_index)
        if ret is not None:
            self.new_blacks.add(ret)
        nbrs = datum.neighbours_gg
        for neighbour in nbrs:
            ret = self.datum[neighbour].set_owner(clue_index)
            if ret is not None:
                self.new_blacks.add(ret)

    def prune_reached_bys(self, clue_index):
        alg = 6
        for datum in self.datum:
            if clue_index in datum.reached_by and datum.guess is None:
                self.for_removal.append([datum.index, clue_index, alg])

    def handle_removal(self):
        hints = []
        while self.for_removal and not hints:
            job = self.for_removal.pop()
            datum = self.datum[job[0]]
            clue_index = job[1]
            alg = job[2]
            reached_by = datum.reached_by
            if not reached_by:
                pass
            elif clue_index not in reached_by:
                pass
            else:
                datum.remove_reacher(clue_index)
                if not datum.reached_by:
                    # new black cell
                    hint = [datum.index, Sgg.BLACK, alg]
                    hints.append(hint)
                    break
        return hints

    def add_white(self, new_white_index):
        """
        Handle a new white.
        It may join an existing set of whites which include clues
        or a set of orphan whites, or join sets of both.
        If it results in a finished white we can remove it from
        all reached_bys.
        """

        if not self.datum[new_white_index].is_correct(Sgg.WHITE):
            #print 'Bad value for datum', new_white_index, 'WHITE'
            self.status = False
            #print Sgg.CURRENT_PUZZLE
            return
        whites = list(self.whites.items())
        new = True
        for white in whites:
            if white.contains_index(new_white_index):
                new = False
        if new:
            Sgg.progress = True
            self.unknowns.discard(new_white_index)

            # try unconnected (orphan) whites

            # the cell lists for all those that touch are merged
            # and the original Whites deleted from Whites
            # later we add the new White to the Whites
            new_white = White(self.datum[new_white_index])
            for_deletion = False
            for white in whites:
                if not white.is_connected() and white.touches(new_white_index):
                    # touches this set of whites, so add and
                    # mark this member for deletion
                    new_white.merge(white)
                    white.for_deletion()
                    self.orphan_whites.remove(white)
                    for_deletion = True

            # now check if new_white_index touches any clued whites

            in_white = None
            for white in whites:
                if white.is_connected() and white.touches(new_white_index):
                    in_white = white
                    break

            if in_white is not None:
                # new_white_index touches a clued white so add it
                in_white.merge(new_white)
                #claim the surrounding cells
                self.set_ownership(new_white_index, in_white.clue_index)
                # update reachby
                self.datum[new_white_index].set_reached_by([in_white.clue_index])
                if in_white.finished:
                    self.prune_reached_bys(in_white.clue_index)
                    self.unfinished_whites.remove(in_white)
            else:
                # doesn't touch any clued whites so add it as an orphan
                self.whites.add(new_white)
                self.orphan_whites.append(new_white)

            if for_deletion:
                self.whites.delete()

    def add_blacks(self, hints):
        """
        given a list of new blacks in hints
        add them to self.blacks
        1. new black
        2. add to existing black
        3. join self.blacks (up to 4)
        """

        blacks = list(self.blacks.items())
        for_deletion = False
        for hint in hints:
            datum_index = hint[0]
            datum = self.datum[datum_index]
            if not datum.is_correct(Sgg.BLACK):
                #print 'Bad value for datum', datum_index, 'BLACK'
                self.status = False
                #print Sgg.CURRENT_PUZZLE
                return
            skip = False
            for black in blacks:
                if black.contains_index(datum_index):
                    skip = True
                    break
            if not skip:
                self.unknowns.discard(datum_index)

                nbrs = datum.neighbours_gg
                # for each neighbour of datum
                # check each Black and save matches in touchers
                touchers = set([])
                for nbr in nbrs:
                    for black in blacks:
                        if black.contains_index(nbr):
                            touchers.add(black)
                new_black = Black()
                new_black.add([datum])
                for toucher in touchers:
                    new_black.merge(toucher)
                    for_deletion = True
                    toucher.for_deletion()
                # add new to blacks
                self.blacks.add(new_black)

        if for_deletion:
            self.blacks.delete()

    def assign_parent(self, white):
        """
        Check reached_bys to try to assign parents to this white
        """
        clue_index = None
        for datum in list(white.items()):
            reached_by = datum.reached_by
            if len(reached_by) == 1:
                clue_index = list(reached_by)[0]
                white.add_clue_cell(clue_index)
                break
        return clue_index

    def assign_parents(self):
        progress = False
        whites = self.orphan_whites
        for white in whites:
            if not white.contains_clue():
                parent = self.assign_parent(white)
                if parent is not None:
                    progress = True
        return progress

    def check_errors(self):
        self.status = True
        self.errors = []
        for datum in self.datum:
            if not datum.is_consistent():
                self.status = False
                self.errors.append(datum)

    def check_finished(self):
        self.finished = True
        if self.unknowns:
            self.finished = False

    def is_finished(self):
        return self.finished

    def do_hint(self):
        if not self.is_consistent():
            self.status = False
        if not self.status:
            return
        self.check_finished()
        if not self.is_finished():
            self.apply_algorithms()

    def is_consistent(self):
        """
        Is the data consistent?
        clues should only contain incomplete sets of whites
        ditto whites
        blacks should contain all blacks until there is only one
        black
        completed_whites + whites + unknowns + blacks = grid_size
        also check that no element in unknowns is in whites,
        completed_whites or blacks
        """

        consistent = False
        self.check_errors()
        if self.status:
            consistent = True
        return consistent
        """
            blacks = self.blacks.items()
            whites = self.whites.items()
            for white in whites:
                if not white.is_consistent():
                    print 'inconsistent White', white.index
                    white.print_me()
                    consistent = False
                    break
            if consistent:
                for unknown in self.unknowns:
                    for black in blacks:
                        if black.contains_index(unknown):
                            print 'unknown', unknown, 'in black', black
                            consistent = False
                    for white in whites:
                        if white.contains_index(unknown):
                            print 'unknown', unknown, 'in whites', white
                            consistent = False
            if consistent:
                cells = set([])
                for white in whites:
                    my_cells = white.cells
                    if cells.intersection(my_cells):
                        print 'shared cells', cells, my_cells
                        consistent = False
                        break
                    else:
                        cells = cells.union(my_cells)
            if consistent:
                for datum in self.datum:
                    if datum.guess == Sgg.WHITE:
                        datum_index = datum.index
                        found = False
                        for white in whites:
                            if white.contains_index(datum_index):
                                if found:
                                    print 'datum in more than one White!', datum_index
                                    for w in whites:
                                        w.print_me()
                                    consistent = False
                                    break
                                else:
                                    found = True
                        if consistent:
                            if not found:
                                pass
                                #print 'datum not in any White!', datum_index
                                #return False
            if consistent:
                for datum in self.datum:
                    if datum.guess == Sgg.BLACK:
                        datum_index = datum.index
                        found = False
                        for black in blacks:
                            if black.contains_index(datum_index):
                                if found:
                                    print 'datum in more than one Black!', datum_index
                                    for w in blacks:
                                        w.print_me()
                                    consistent = False
                                    break
                                else:
                                    found = True
                        if consistent:
                            if not found:
                                pass
                                #print 'datum not in any Black!', datum_index
        if not consistent:
            print 'aaaaaaaaargggggggggh!!'
            print Sgg.ops
            print Sgg.CURRENT_PUZZLE
            exit(1)
        return consistent
        """

    def get_puzzle(self, puzzle_number):
        self.puzzle_number = puzzle_number
        puzzle = self.model_data.get_puzzle(puzzle_number)
        Sgg.grid_width = puzzle[0]
        Sgg.grid_height = puzzle[1]
        Sgg.cell_count = Sgg.grid_width * Sgg.grid_height
        self.puzzle_data = puzzle[2:]
        self.datum = []
        for cell in range(Sgg.cell_count):
            self.datum.append(Datum(cell, self.puzzle_data[cell]))

        self.init_types()
        self.init_ranges()
        self.refine_ranges()

    def init_ranges(self):
        for white in list(self.whites.items()):
            size = white.size
            clue_index = white.clue_index
            white_datum = self.datum[clue_index]
            for datum in self.datum:
                if datum.guess is None:
                    reached_by = datum.reached_by
                    if self.in_range(white_datum, datum, size):
                        reached_by.append(clue_index)

    def refine_ranges_1(self):

        def taxicab_distance(datum_0, datum_1):
            return int(abs(datum_0.row - datum_1.row) +
                       abs(datum_0.column - datum_1.column))

        clue_dic = {}
        # get all unsolved squares
        all_squares = self.get_unsolved_4s()

        # get dictionary of squares only reached by a single clue
        for square in all_squares:
            clue_indexes = set([])
            for cell_index in square:
                reached_by = self.datum[cell_index].reached_by
                if len(reached_by) > 1:
                    clue_indexes = set([])
                    break
                elif len(reached_by) == 1:
                    clue_indexes.add(reached_by[0])
            if len(clue_indexes) == 1:
                clue_index = clue_indexes.pop()
                try:
                    clue_dic[clue_index].append(square)
                except KeyError:
                    clue_dic[clue_index] = [square]

        # get dictionary of most distant squares (based on row and column)
        new_clue_dic = {}
        for clue_index, squares in list(clue_dic.items()):
            min_column = [9999, None]
            max_column = [-9999, None]
            min_row = [9999, None]
            max_row = [-9999, None]
            for square in squares:
                for cell_index in square:
                    datum = self.datum[cell_index]
                    column = datum.column
                    row = datum.row
                    if column < min_column[0]:
                        min_column[0] = column
                        min_column[1] = square
                    if column > max_column[0]:
                        max_column[0] = column
                        max_column[1] = square
                    if row < min_row[0]:
                        min_row[0] = row
                        min_row[1] = square
                    if row > max_row[0]:
                        max_row[0] = row
                        max_row[1] = square
            new_clue_dic[clue_index] = [min_column, max_column,
                                        min_row, max_row]
        # get closest cell to clue in each square
        tmp_dic = {}
        for clue_index, stuff in list(new_clue_dic.items()):
            clue_datum = self.datum[clue_index]
            tmp_dic[clue_index] = []
            for item in stuff:
                square = item[1]
                min_distance = [999, None]
                for cell_index in square:
                    datum = self.datum[cell_index]
                    distance = taxicab_distance(clue_datum, datum)
                    if distance < min_distance[0]:
                        min_distance[0] = distance
                        min_distance[1] = cell_index
                tmp_dic[clue_index].append(min_distance[1])
            tmp_dic[clue_index] = [set(tmp_dic[clue_index]), None]
        new_clue_dic = tmp_dic

        # get max range for each clue

        for clue_index, stuff in list(new_clue_dic.items()):
            clue_datum = self.datum[clue_index]
            max_distance = -999
            for cell_index in stuff[0]:
                datum = self.datum[cell_index]
                max_distance = max(max_distance,
                                   taxicab_distance(clue_datum, datum))
            stuff[1] = clue_datum.size - max_distance - 1

        # clue cannot reach further than stuff[1] from each cell in stuff[0]
        # so work out the range_box this describes
        tmp_dic = {}
        for clue_index, stuff in list(new_clue_dic.items()):
            min_c = 9999
            max_c = -9999
            min_r = 9999
            max_r = -9999
            new_list = list(stuff[0])
            new_list.append(clue_index)
            for cell_index in new_list:
                cell = self.datum[cell_index]
                min_c = min(min_c, cell.column)
                max_c = max(max_c, cell.column)
                min_r = min(min_r, cell.row)
                max_r = max(max_r, cell.row)
            min_c -= stuff[1]
            max_c += stuff[1]
            min_r -= stuff[1]
            max_r += stuff[1]
            tmp_dic[clue_index] = [min_c, max_c, min_r, max_r]
        return tmp_dic

    def refine_ranges(self):
        progress = True
        count = 0
        while progress:
            count += 1
            progress = False
            clue_dic = self.refine_ranges_1()
            for clue_index, limits in list(clue_dic.items()):
                for datum in self.datum:
                    reached_by = datum.reached_by
                    if clue_index in reached_by:
                        if datum.column < limits[0] or\
                           datum.column > limits[1] or\
                           datum.row < limits[2] or\
                           datum.row > limits[3]:
                            datum.remove_reacher(clue_index)
                            progress = True

    def reset_range(self, datum):
        reached_by = []
        for white in self.unfinished_whites:
            clue_datum = self.datum[white.clue_index]
            if self.in_range(datum, clue_datum, white.size):
                reached_by.append(white.clue_index)
        datum.reached_by = reached_by

    def in_range(self, datum_0, datum_1, size):
        """
        return True if distance between 2 datum is < size
        """

        def taxicab_distance(datum_0, datum_1):
            return int(abs(datum_0.row - datum_1.row) +
                       abs(datum_0.column - datum_1.column))

        ret = False
        if size > taxicab_distance(datum_0, datum_1):
            ret = True
        return ret

    def get_white_with_clue(self, clue_index):
        white_parent = None
        for white in self.unfinished_whites:
            if white.clue_index == clue_index:
                # found parent
                white_parent = white
                break
        return white_parent

    def set_gneighbours(self, clue_cell):
        """
        For Dijkstra we need neighbours of clue_cells and unknowns
        """
        for datum in self.datum:
            datum.gneighbours = []
            if datum.is_navigable(clue_cell):
                for neighbour in datum.neighbours_gg:
                    if self.datum[neighbour].is_navigable(clue_cell):
                        datum.gneighbours.append(neighbour)

    def update_gneighbours(self, datum_in, clue_cell):
        """
        For Dijkstra we need neighbours of clue_cells and unknowns
        """
        nbrs = datum_in.neighbours_gg
        datum_in.gneighbours = []
        if datum_in.is_navigable(clue_cell):
            for neighbour in nbrs:
                if self.datum[neighbour].is_navigable(clue_cell):
                    datum_in.gneighbours.append(neighbour)
        for nbr in nbrs:
            datum = self.datum[nbr]
            datum.gneighbours = []
            if datum.is_navigable(clue_cell):
                for neighbour in datum.neighbours_gg:
                    if self.datum[neighbour].is_navigable(clue_cell):
                        datum.gneighbours.append(neighbour)

    def add_hints(self, hint):
        if hint:
            if not self.is_consistent():
                self.status = False
                return
            if hint[1] == Sgg.BLACK:
                self.add_blacks([hint])
            else:
                self.add_whites([hint])
            if not self.is_consistent():
                self.status = False
                return

    def apply_hint(self):
        hint = self.hints[0]
        self.add_hints(hint)
        return [hint[0]]

    def delete_hint(self):
        self.hints = []

    def black_extension(self):
        """
        Find Blacks with only 1 way to extend
        and which need to extend (ie which are otherwise only
        connected to a dead end).
        """
        alg = 1
        hints = []
        new_blacks = set([])
        blacks = list(self.blacks.items())
        for black in blacks:
            unknowns = []
            black_cells = list(black.items())
            for black_cell in black_cells:
                unknown = self.get_unknowns(black_cell)
                if unknown:
                    unknowns.append(unknown)
            if len(unknowns) == 1 and len(unknowns[0]) == 1 and \
                    len(blacks) > 1:
                # only one way to go and > 1 list of blacks
                new_blacks.add(unknowns[0][0])
        for new_black in new_blacks:
            hint = (new_black, Sgg.BLACK, alg)
            hints.append(hint)
        return hints

    def white_extension(self):
        """
        Find whites in self.whites which can only extend one way
        Get all the unknowns for each white_dic.
        If there is only 1 then that is the way to go.
        """
        alg = 0
        hints = []
        new_whites = set([])
        for white in self.unfinished_whites:
            unknowns = set([])
            for datum in list(white.items()):
                unknown = set(self.get_unknowns(datum))
                unknowns = unknowns.union(unknown)
            if len(unknowns) == 1:
                unknown = unknowns.pop()
                new_whites.add(unknown)
        for white in self.orphan_whites:
            unknowns = set([])
            for datum in list(white.items()):
                unknown = set(self.get_unknowns(datum))
                unknowns = unknowns.union(unknown)
            if len(unknowns) == 1:
                unknown = unknowns.pop()
                new_whites.add(unknown)
        for new_white in new_whites:
            if self.datum[new_white].guess is None:
                hint = [new_white, Sgg.WHITE, alg]
                hints.append(hint)
        return hints

    def surround_completed(self):
        """
        For newly completed whites make a list of the surrounding
        cells that must be black.
        """
        alg = 2
        hints = []
        new_blacks = set([])
        whites = list(self.whites.items())
        for white in whites:
            if not white.is_surrounded() and white.is_finished():
                white_cells = list(white.items())
                for white_cell in white_cells:
                    nbrs = white_cell.neighbours_gg
                    for nbr in nbrs:
                        nbr_datum = self.datum[nbr]
                        if nbr_datum not in white_cells and \
                           nbr_datum.guess is None and \
                           nbr not in new_blacks:
                            new_blacks.add(nbr)

        for black_index in new_blacks:
            hint = [black_index, Sgg.BLACK, alg]
            hints.append(hint)
        return hints

    def check_1(self, datum, cases, target):
        is_ok = True
        nbrs = datum.neighbours_55
        for nbr in cases:
            nbr_index = self.neighbour_dic[nbr]
            if nbr_index is None:
                is_ok = False
                break
            else:
                nbr_index = nbrs[nbr_index]
                if nbr_index is not None:
                    nbr_datum = self.datum[nbr_index]
                    if nbr_datum.guess is not target:
                        is_ok = False
                        break
                else:
                    is_ok = False
                    break
        return is_ok

    def check_2(self, datum, cases, target):
        # allows off board as True
        is_ok = True
        nbrs = datum.neighbours_55
        for nbr in cases:
            nbr_index = self.neighbour_dic[nbr]
            if nbr_index is None:
                # off board
                pass
            else:
                nbr_index = nbrs[nbr_index]
                if nbr_index is not None:
                    nbr_datum = self.datum[nbr_index]
                    if nbr_datum.guess is not target:
                        is_ok = False
                        break
        return is_ok

    def get_clue_index(self, datum_index):
        ret = None
        for white in list(self.whites.items()):
            if white.contains_index(datum_index):
                ret = white.clue_index
                break
        return ret

    def check_exclusive_whites(self, datum, cases):
        target = Sgg.WHITE
        is_ok = True
        nbrs = datum.neighbours_55
        owners = set([])
        for nbr in cases:
            nbr_index = self.neighbour_dic[nbr]
            if nbr_index is None:
                pass
            else:
                nbr_index = nbrs[nbr_index]
                if nbr_index is not None:
                    nbr_datum = self.datum[nbr_index]
                    if nbr_datum.guess == target:
                        owners.add(self.get_clue_index(nbr_index))
                else:
                    is_ok = False
                    break
        if None in owners or len(owners) < len(cases):
            is_ok = False
        return is_ok

    def apply_pattern_1(self, opens, blacks, whites, exclusive_whites,
                        essential_blacks, set_position, set_type, alg):
        hints = []
        for datum_index in self.unknowns:
            datum = self.datum[datum_index]
            # check open cells
            is_ok = True
            if opens:
                is_ok = self.check_1(datum, opens, None)
            if is_ok:
                # check black cells
                if blacks:
                    is_ok = self.check_2(datum, blacks, Sgg.BLACK)
                if is_ok:
                    # check whites cells
                    if whites:
                        is_ok = self.check_1(datum, whites, Sgg.WHITE)
                    if is_ok:
                        # check exclusive whites
                        if exclusive_whites:
                            is_ok = self.check_exclusive_whites(datum,
                                                                exclusive_whites)
                        if is_ok:
                            # check essential_blacks
                            if essential_blacks:
                                is_ok = self.check_1(datum, essential_blacks,
                                                     Sgg.BLACK)
            if is_ok:
                if set_type is not None:
                    nbr_index = self.neighbour_dic[set_position]
                    position_index = datum.neighbours_55[nbr_index]
                    if position_index > -1 and position_index < Sgg.cell_count:
                        hint = [position_index, set_type, alg]
                        hints.append(hint)
                        break
                else:
                    hints = self.check_access(datum_index, opens, alg)
                    if hints:
                        break
        return hints

    def apply_pattern_2(self, opens, blacks, whites, exclusive_whites,
                        essential_blacks, set_position, set_type,
                        search_type, alg):
        hints = []
        for white in self.unfinished_whites:
            extender = self.whites_1(white, search_type)
            is_ok = False
            if extender:
                datum = extender[0][0]
                # check open cells
                is_ok = True
                if opens:
                    is_ok = self.check_1(datum, opens, None)
                if is_ok:
                    if blacks:
                        is_ok = self.check_2(datum, blacks, Sgg.BLACK)
                    if is_ok:
                        # check whites cells
                        if whites:
                            is_ok = self.check_1(datum, whites, Sgg.WHITE)
                        if is_ok:
                            # check exclusive whites
                            if exclusive_whites:
                                is_ok = self.check_exclusive_whites(datum,
                                                                    exclusive_whites)
                            if is_ok:
                                # check essential_blacks
                                if essential_blacks:
                                    is_ok = self.check_1(datum,
                                                         essential_blacks,
                                                         Sgg.BLACK)
            if is_ok:
                nbr_index = self.neighbour_dic[set_position]
                position_index = datum.neighbours_55[nbr_index]
                if position_index > -1 and position_index < Sgg.cell_count:
                    hint = [position_index, set_type, alg]
                    hints.append(hint)
                    break
        return hints

    def whites_1(self, white, search_type):
        """
        Can this WHITE only extend from 1 and only in two directions.
        If so return the cell_index, otherwise []
        """
        ret = []
        unknowns = []

        if (search_type == 'V' and white.size - len(white.cells) == 1)\
           or search_type == 'w':
            for datum in list(white.items()):
                unknown = self.get_unknowns(datum)
                if unknown:
                    unknowns.append([datum, unknown])
            if len(unknowns) == 1 and len(unknowns[0][1]) == 2:
                # only 1 cell can extend, and only in 2 directions
                ret = unknowns
        return ret

    def apply_pattern_family(self, pattern_family, alg):
        search_type = pattern_family[0].search_type
        hints = []
        if search_type == '.':
            for pattern in pattern_family:
                opens = pattern.opens
                blacks = pattern.blacks
                essential_blacks = pattern.essential_blacks
                whites = pattern.whites
                exclusive_whites = pattern.exclusive_whites
                set_position = pattern.set_position
                set_type = pattern.set_type
                hints = self.apply_pattern_1(opens, blacks, whites,
                                             exclusive_whites,
                                             essential_blacks,
                                             set_position, set_type, alg)
                if hints:
                    break
        else:
            for pattern in pattern_family:
                opens = pattern.opens
                blacks = pattern.blacks
                essential_blacks = pattern.essential_blacks
                whites = pattern.whites
                exclusive_whites = pattern.exclusive_whites
                set_position = pattern.set_position
                set_type = pattern.set_type
                hints = self.apply_pattern_2(opens, blacks, whites,
                                             exclusive_whites,
                                             essential_blacks,
                                             set_position, set_type,
                                             search_type, alg)
                if hints:
                    break
        return hints

    def white_reaches_1(self, clued_white, datum):
        """
        Can this clued white reach this datum?
        """
        ret = True
        size = clued_white.size
        for white_datum in list(clued_white.items()):
            if not self.in_range(datum,
                                 white_datum,
                                 size):
                ret = False
                break
        return ret

    def white_reaches_2(self, clued_white, datum, bad):
        """
        Can this clued white reach this datum?
        """
        ret = False
        size = clued_white.size
        clue_index = clued_white.clue_index
        for white_datum in list(clued_white.items()):
            dijkstra = Dijkstra(self.datum,
                                datum.index,
                                white_datum.index,
                                clue_index,
                                bad,
                                False)
            distance = dijkstra.distance
            if distance is not None and \
               size >= distance:
                ret = True
                break
        return ret

    def get_children(self, clued_white):
        """
        Look for all orphan whites that share clue_index
        """
        children = []
        if clued_white is not None:
            clue_index = clued_white.clue_index
            for orphan_white in self.orphan_whites:
                if orphan_white.clue_index == clue_index:
                    children.append(orphan_white)
        return children

    def expansion_0(self, my_index, clue_index, good, done, needed):
        """
        RECURSION!!!
        """
        len_good = len(good)
        if len_good > needed:
            return
        done.add(my_index)
        datum = self.datum[my_index]
        if datum.is_navigable(clue_index):
            good.add(my_index)
            nbrs = datum.neighbours_gg
            for nbr in nbrs:
                if nbr not in done:
                    self.expansion_0(nbr, clue_index, good, done, needed)
            if len(good) > needed or len(good) == len_good:
                # return if got enough or made no progress
                return

    def expansion_1(self):
        """
        Examine expansion potential in all 4 directions and their total.
        Keep looking until enough cells accumulated.
        """
        nbr_indexes = [0, 2, 4, 6]
        alg = 4
        hints = []
        for white in self.unfinished_whites:
            needed = white.size
            clue_index = white.clue_index
            white_opens = []
            hint_datum = []
            for white_cell in list(white.items()):
                opens = [set([]), set([]), set([]), set([])]
                hint_datum.append(white_cell.index)
                for direction in range(4):
                    nbri = nbr_indexes[direction]
                    done = set([])
                    good = set([])
                    for datum in list(white.items()):
                        done.add(datum.index)
                    # get datum for this direction
                    datum_index = white_cell.neighbours_sq[nbri]
                    # get neighbours for this direction
                    if datum_index is not None and\
                       datum_index not in done and\
                       self.datum[datum_index].is_navigable(clue_index):
                        self.expansion_0(datum_index, clue_index, good, done, needed)
                        opens[direction] = good
                white_opens.append(opens)

            needed = white.size - len(white.cells)
            all_opens = set([])
            for openi in white_opens:
                for openj in openi:
                    all_opens.update(openj)

            if len(all_opens) == needed:
                for datum_index in hint_datum:
                    datum = self.datum[datum_index]
                    nbrs = datum.neighbours_sq
                    for i in range(4):
                        nbr_index = nbr_indexes[i]
                        nbr = nbrs[nbr_index]
                        if nbr is not None and nbr in all_opens:
                            hint = [nbr, Sgg.WHITE, alg]
                            hints.append(hint)
                            break
                    if hints:
                        break
            else:
                # is 1 cell required. ie are all the others
                # combined insufficient?
                tots = []
                for openi in white_opens:
                    tot = 0
                    for openj in openi:
                        tot += len(openj)
                    tots.append(tot)
                # tots are the total expansion possibilities for each cell
                # in this white
                count = 0
                white_index = None
                total = 0
                for tot_index in range(len(tots)):
                    if tots[tot_index] < needed:
                        total += tots[tot_index]
                    else:
                        # adequate
                        count += 1
                        white_index = tot_index
                if count == 1 and total < needed:
                    # only white_index adequate and total of rest inadequate
                    # check the directions and capacities for white_index
                    opens = white_opens[white_index]
                    this_datum_index = hint_datum[white_index]
                    count = 0
                    new_tot = 0
                    for i in range(4):
                        if len(opens[i]) < needed - total:
                            count += 1
                            new_tot += len(opens[i])
                        else:
                            count_index = i
                    if count == 3 and new_tot < needed - total:
                        # need to expand from this cell
                        this_datum = self.datum[this_datum_index]
                        nbr = this_datum.neighbours_sq[nbr_indexes[count_index]]
                        hint = [nbr, Sgg.WHITE, alg]
                        hints.append(hint)
                        break
            if hints:
                break
        return hints

    def check_access(self, datum_index, opens, alg):
        offsets = {'0': -Sgg.grid_width,
                   '2': 1,
                   '4': Sgg.grid_width,
                   '6': -1}
        hints = []
        offset = opens[0]
        if offset == '8':
            offset = opens[1]
        datum_1 = self.datum[datum_index]
        datum_2 = self.datum[datum_index + offsets[offset]]
        datum_1_index = datum_1.index
        datum_2_index = datum_2.index
        if datum_1.is_owned() or datum_2.is_owned():
            pass
        child_dic = {}
        for clued_white in self.unfinished_whites:
            child_dic[clued_white] = self.get_children(clued_white)

        reached_1 = set([])
        bad = [datum_2_index]
        datum = datum_1
        # try all clues
        for clued_white in self.unfinished_whites:
            if self.white_reaches_1(clued_white, datum):
                self.set_gneighbours(clued_white.clue_index)
                children = child_dic[clued_white]
                if not children:
                    if self.white_reaches_2(clued_white, datum, bad):
                        reached_1.add(clued_white)
                else:
                    if self.is_reachable(clued_white,
                                         children,
                                         datum, bad):
                        reached_1.add(clued_white)

        reached_2 = set([])
        datum = datum_2
        bad = [datum_1_index]
        # try all clues
        for clued_white in self.unfinished_whites:
            if self.white_reaches_1(clued_white, datum):
                self.set_gneighbours(clued_white.clue_index)
                children = child_dic[clued_white]
                if not children:
                    if self.white_reaches_2(clued_white, datum, bad):
                        reached_2.add(clued_white)
                else:
                    if self.is_reachable(clued_white,
                                         children,
                                         datum, bad):
                        reached_2.add(clued_white)

        if not reached_1 and reached_2:
            hint = [datum_2_index, Sgg.WHITE, alg]
            hints.append(hint)
        elif not reached_2 and reached_1:
            hint = [datum_1_index, Sgg.WHITE, alg]
            hints.append(hint)
        return hints

    def is_reachable(self, clued_white, children, datum, bad):
        ret = True
        size = clued_white.size
        clue_index = clued_white.clue_index
        all_white_cells = set([])
        for child in children:
            for cell in list(child.items()):
                all_white_cells.add(cell.index)
        for cell in list(clued_white.items()):
            all_white_cells.add(cell.index)

        for cell_index in all_white_cells:
            cell = self.datum[cell_index]
            if not self.in_range(cell, datum, size):
                ret = False
                break
        if ret:
            # find path
            for cell_index in all_white_cells:
                dijkstra = Dijkstra(self.datum,
                                    datum.index,
                                    cell_index,
                                    clue_index,
                                    bad,
                                    False)
                distance = dijkstra.distance
                if distance is not None and \
                   size >= distance:
                    pass
                else:
                    ret = False
                    break
        return ret

    def unite_1(self, clued_white, orphan_white):
        """
        What is the minimum number of cells required to join
        these two whites?
        """

        def taxicab_distance(datum_0, datum_1):
            return int(abs(datum_0.row - datum_1.row) +
                       abs(datum_0.column - datum_1.column))

        ret = []
        new_cell_index = None
        min_distance = 99
        clue_index = clued_white.clue_index
        clued_white_cells = list(clued_white.items())
        orphan_white_cells = list(orphan_white.items())
        for clued_item in clued_white_cells:
            for orphan_item in orphan_white_cells:
                distance = taxicab_distance(clued_item, orphan_item) - 1
                if distance <= min_distance:
                    dijkstra = Dijkstra(self.datum,
                                        clued_item.index,
                                        orphan_item.index,
                                        clue_index,
                                        [],
                                        False)
                    distance = dijkstra.distance
                    if distance is not None:
                        if distance - 2 < min_distance:
                            min_distance = distance - 2
                            new_cell_index = dijkstra.path[1]
                            ret = [clued_item, orphan_item, min_distance]
                        elif distance == min_distance:
                            # maybe no solution
                            ret = []
        if ret:
            missing_cell_count = clued_white.size\
                                 - len(orphan_white_cells)\
                                 - len(clued_white_cells)
            if min_distance == missing_cell_count:
                # must check that this cell blocks all alternative
                # paths or makes them overlong.
                bad = [new_cell_index]
                for clued_item in clued_white_cells:
                    for orphan_item in orphan_white_cells:
                        dijkstra = Dijkstra(self.datum,
                                            clued_item.index,
                                            orphan_item.index,
                                            clue_index,
                                            bad,
                                            False)
                        distance = dijkstra.distance
                        if distance is not None and\
                           distance - 2 == missing_cell_count:
                            # an alternative path
                            new_cell_index = None
                            break
                    if new_cell_index is None:
                        break
            else:
                new_cell_index = None
        return new_cell_index

    def unite_2(self, clued_white, child):
        """
        Simple case: if parent has only 2 ways to extend
        and one makes the path to the child too long we
        can extend in the other direction. Ditto for child
        to parent.
        """
        ret = None
        size = clued_white.size
        clue_index = clued_white.clue_index
        unknowns = set([])
        for datum in list(clued_white.items()):
            unknown = set(self.get_unknowns(datum))
            unknowns = unknowns.union(unknown)
        if len(unknowns) == 2:
            good_unknown = []
            for unknown in unknowns:
                good = set([])
                for child_cell in child.cells:
                    child_index = child_cell.index
                    dijkstra = Dijkstra(self.datum,
                                        unknown,
                                        child_index,
                                        clue_index,
                                        [],
                                        False)
                    distance = dijkstra.distance
                    if distance is not None:
                        if distance < size:
                            good.add(unknown)
                        else:
                            good = set([])
                    else:
                        good = set([])
                if good:
                    # all children reached
                    good_unknown.append(unknown)
            if len(good_unknown) == 1:
                # only 1 unknown reaches all children
                ret = good_unknown[0]
        return ret

    def unite_families(self):
        """
        For parents with children find essential internal cells
        """
        alg = 8
        hints = []
        for clued_white in self.unfinished_whites:
            clue_index = clued_white.clue_index
            children = self.get_children(clued_white)
            if children and len(children) == 1:
                self.set_gneighbours(clue_index)
                new_cell = self.unite_2(clued_white, children[0])
                if new_cell is not None:
                    hint = [new_cell, Sgg.WHITE, alg]
                    hints.append(hint)
                    break
                new_cell = self.unite_1(clued_white, children[0])
                if new_cell is not None:
                    hint = [new_cell, Sgg.WHITE, alg]
                    hints.append(hint)
                    break
            elif children and len(children) > 1:
                polyominoes,\
                    white_cells = self.get_possible_polyominoes_1(clued_white)
                new_polyominoes = []
                for polyomino in polyominoes:
                    new_polyomino = []
                    for cell_index in polyomino:
                        if cell_index not in white_cells:
                            new_polyomino.append(cell_index)
                    new_polyominoes.append(new_polyomino)
                polyominoes = new_polyominoes
                common = set(polyominoes[0])
                for polyomino in polyominoes[1:]:
                    common.intersection_update(polyomino)
                if common:
                    hint = [common.pop(), Sgg.WHITE, alg]
                    hints.append(hint)
                    break
        return hints

    def unreachable_d(self):
        """
        Refine reached_bys for parents with children when
        only 1 cell required to join!
        """
        alg = 9
        hints = []
        for clued_white in self.unfinished_whites:
            clue_index = clued_white.clue_index
            children = self.get_children(clued_white)
            if len(children) == 1 and len(children[0].cells) == 1:
                child = children[0]
                needed = clued_white.size - len(clued_white.cells)\
                         - len(child.cells)
                if needed == 1:
                    linkers = []
                    # parent and orphan must touch diagonally
                    for parent_cell in clued_white.cells:
                        nbrs = parent_cell.neighbours_sq
                        for child_cell in child.cells:
                            child_cell_index = child_cell.index
                            if nbrs[1] == child_cell_index:
                                linkers = [nbrs[0], nbrs[2]]
                            elif nbrs[3] == child_cell_index:
                                linkers = [nbrs[4], nbrs[2]]
                            elif nbrs[5] == child_cell_index:
                                linkers = [nbrs[4], nbrs[6]]
                            elif nbrs[7] == child_cell_index:
                                linkers = [nbrs[0], nbrs[6]]
                            if linkers:
                                break
                        if linkers:
                            for parent_cell in clued_white.cells:
                                parent_cell_index = parent_cell.index
                                linkers.append(parent_cell_index)
                            for child_cell in child.cells:
                                child_cell_index = child_cell.index
                                linkers.append(child_cell_index)
                            break
                    if linkers:
                        for datum in self.datum:
                            if datum.guess is None and\
                               datum.index not in linkers:
                                reached_by = datum.reached_by
                                if clue_index in reached_by:
                                    self.for_removal.append([datum.index,
                                                             clue_index, alg])
        return hints

    def unreachable_e(self):
        """
        Refine reached_bys for parents with and without children
        """
        alg = 7
        hints = []
        bad = []
        for clued_white in self.unfinished_whites:
            clue_index = clued_white.clue_index
            all_white_cells = set([])
            for cell in list(clued_white.items()):
                all_white_cells.add(cell.index)
            children = self.get_children(clued_white)
            for child in children:
                for cell in list(child.items()):
                    all_white_cells.add(cell.index)
            if children:
                # we know they reach one another
                # we want the maximum distance between cells
                max_distance = -99
                self.set_gneighbours(clued_white.clue_index)
                white_cells = list(all_white_cells)
                length = len(white_cells)
                for index_0 in range(length):
                    datum_index_0 = white_cells[index_0]
                    for index_1 in range(index_0 + 1, length):
                        datum_index_1 = white_cells[index_1]
                        dijkstra = Dijkstra(self.datum,
                                            datum_index_0,
                                            datum_index_1,
                                            clue_index,
                                            bad,
                                            False)
                        distance = dijkstra.distance
                        if distance is not None:
                            max_distance = max(max_distance, distance)
                            for item in dijkstra.path:
                                all_white_cells.add(item)
                max_reach = clued_white.size - max_distance
            else:
                max_reach = clued_white.size - len(all_white_cells)
            min_c = 9999
            max_c = -9999
            min_r = 9999
            max_r = -9999
            for cell_index in all_white_cells:
                cell = self.datum[cell_index]
                min_c = min(min_c, cell.column)
                max_c = max(max_c, cell.column)
                min_r = min(min_r, cell.row)
                max_r = max(max_r, cell.row)
            min_c -= max_reach
            max_c += max_reach
            min_r -= max_reach
            max_r += max_reach
            for datum in self.datum:
                reached_by = datum.reached_by
                if clue_index in reached_by:
                    if datum.column < min_c or\
                       datum.column > max_c or\
                       datum.row < min_r or\
                       datum.row > max_r:
                        self.for_removal.append([datum.index, clue_index, alg])
                        break
        return hints

    def unreachable_g(self):
        """
        Refine reached_bys for all clued whites
        """
        progress = False
        alg = 19
        hints = []
        bad = []
        reached_by_dic = {}
        for datum in self.datum:
            for datum_index in datum.reached_by:
                try:
                    reached_by_dic[datum_index].append(datum.index)
                except KeyError:
                    reached_by_dic[datum_index] = [datum.index]
        # this enables us to deal with all the reached_bys for a clue together
        for clue_index, reached in list(reached_by_dic.items()):
            white = self.get_white_with_clue(clue_index)
            if white is not None:
                size = white.size
                self.set_gneighbours(clue_index)
                for datum_index in reached:
                    for_removal = False
                    for white_datum in list(white.items()):
                        white_index = white_datum.index
                        dijkstra = Dijkstra(self.datum,
                                            white_index,
                                            datum_index,
                                            clue_index,
                                            bad,
                                            False)
                        distance = dijkstra.distance
                        if distance is None or distance > size:
                            for_removal = True
                            break
                    if for_removal:
                        self.for_removal.append([datum_index, clue_index, alg])
                        progress = True
                        break
                if progress:
                    break
        return hints

    def check_linkers(self):
        """
        Define a linker as an unfinished cell which touches > 1 whites
        linked_whites are those whites
        if linked_whites contains > 1 clue_index
          linker is black
        elif linked_whites contains clue_index and size <= linker size
          linker is black
        """
        alg = 18
        hints = []
        for datum in self.datum:
            if datum.guess is None:
                touching_whites = set([])
                for white in list(self.whites.items()):
                    if white.contacts(datum.index):
                        touching_whites.add(white)
                clued = []
                white_size = None
                size = 1
                for white in touching_whites:
                    size += len(white.cells)
                    if white.is_connected():
                        clued.append(white)
                        white_size = white.size
                if len(clued) > 1 or (len(clued) == 1 and size > white_size):
                    hint = [datum.index, Sgg.BLACK, alg]
                    hints.append(hint)
                    break
        return hints

    def black_c_nbrs(self, c_index):
        """
        c_index is a connector index for a chain of blacks.
        Return a set of its neighbours which are unsolved or black.
        Later we discard blacks from its own chain.
        """
        outs = set([])
        c_datum = self.datum[c_index]
        nbrs = c_datum.neighbours_gg
        for nbr in nbrs:
            nbr_datum = self.datum[nbr]
            if nbr_datum.guess is None:
                outs.add(nbr)
            elif nbr_datum.guess == Sgg.BLACK:
                outs.add(nbr)
        return outs


    def contains_type(self, collection, wanted):
        ret = False
        for item in collection:
            if self.datum[item].guess is wanted:
                ret = True
                break
        return ret

    def black_connectivity_1(self):
        hints = []
        alg = 5
        connectors_dic = {}
        max_connectors = 5
        if self.blacks:
            for black_chain in list(self.blacks.items()):
                connectors = set([])
                for black in list(black_chain.items()):
                    unknowns = self.get_unknowns(black)
                    for unknown in unknowns:
                        connectors.add(unknown)
                if len(connectors) == 2:
                    c_list = list(connectors)
                    outs_0 = self.black_c_nbrs(c_list[0])
                    outs_1 = self.black_c_nbrs(c_list[1])
                    for black in list(black_chain.items()):
                        outs_0.discard(black.index)
                        outs_1.discard(black.index)

                    if not outs_0 and outs_1:
                        # has only 2 connectors and this one
                        # touches only unsolved so it must be black
                        # as the black chain must link in 2 places
                        hint = [c_list[1], Sgg.BLACK, alg]
                        hints.append(hint)
                        break
                    elif not outs_1 and outs_0:
                        # has only 2 connectors and this one
                        # touches only unsolved so it must be black
                        # as the black chain must link in 2 places
                        hint = [c_list[0], Sgg.BLACK, alg]
                        hints.append(hint)
                        break
                    elif outs_1 and outs_0:
                        cd0 = self.datum[c_list[0]]
                        if cd0.touches(c_list[1]):
                            if self.contains_type(outs_0, Sgg.BLACK) and\
                               not self.contains_type(outs_1, Sgg.BLACK) and\
                               len(outs_1) == 1:
                                # has 2 connectors which touch and only this
                                # one touches a different black and the
                                # other has no other unknown neighbours
                                hint = [c_list[0], Sgg.BLACK, alg]
                                hints.append(hint)
                                break
                            elif self.contains_type(outs_1, Sgg.BLACK) and\
                               not self.contains_type(outs_0, Sgg.BLACK) and\
                               len(outs_0) == 1:
                                # has 2 connectors which touch and only this
                                # one touches a different black and the
                                # other has no other unknown neighbours
                                hint = [c_list[1], Sgg.BLACK, alg]
                                hints.append(hint)
                                break
                elif len(connectors) == 1:
                    # single connector, so it must connect
                    hint = [connectors.pop(), Sgg.BLACK, alg]
                    hints.append(hint)
                    break
                # build dic of connectors for each black chain
                connectors_dic[black_chain] = connectors
            if not hints and len(connectors_dic) < max_connectors\
               and len(self.unknowns) < Sgg.cell_count / 3.0:
                hints = self.black_connectivity_2(connectors_dic)
        return hints

    def expansion_2(self, my_index, clue_index, good, done):
        """
        RECURSION!!!
        """
        len_good = len(good)
        done.add(my_index)
        datum = self.datum[my_index]
        if datum.is_navigable(clue_index):
            good.add(my_index)
            nbrs = datum.neighbours_gg
            for nbr in nbrs:
                if nbr not in done:
                    self.expansion_2(nbr, clue_index, good, done)
            if len(good) == len_good:
                # return if made no progress
                return

    def expansion_3(self, my_index, combination, done):
        """
        RECURSION!!!
        """
        len_done = len(done)
        done.add(my_index)
        datum = self.datum[my_index]
        nbrs = datum.neighbours_gg
        for nbr in nbrs:
            if nbr not in done and nbr in combination:
                self.expansion_3(nbr, combination, done)
            if len(done) == len_done:
                # return if made no progress
                return

    def get_polyominoes(self, cell_indexes, size, whites):
        polyominoes = []
        for combination in itertools.combinations(cell_indexes, size):
            # combination must include all white cells
            is_ok = True
            for white in whites:
                if white not in combination:
                    is_ok = False
                    break
            if is_ok:
                for item in combination:
                    done = set([])
                    self.expansion_3(item, combination, done)
                    if len(done) != size:
                        is_ok = False
                        break
                if is_ok:
                    polyominoes.append(combination)
        return polyominoes

    def get_bad_blacks(self):
        bad_blacks = set([])
        if self.blacks:
            for black_chain in list(self.blacks.items()):
                for black in list(black_chain.items()):
                    bad_blacks.add(black.index)
        return bad_blacks

    def get_white_cells(self, clued_white):
        all_white_cells = []
        # add the clue_cell
        for white in list(clued_white.items()):
            all_white_cells.append(white.index)
        children = self.get_children(clued_white)
        for child in children:
            for cell in list(child.items()):
                all_white_cells.append(cell.index)
        return all_white_cells, children

    def get_perimeter(self, white_cells, needed):
        """
        Find the rectangle which must contain this white.
        """
        x_values = [999, -999]
        y_values = [999, -999]
        for cell_index in white_cells:
            datum = self.datum[cell_index]
            x_values[0] = min(x_values[0], datum.column)
            y_values[0] = min(y_values[0], datum.row)
            x_values[1] = max(x_values[1], datum.column)
            y_values[1] = max(y_values[1], datum.row)
        x_values[0] -= needed
        x_values[1] += needed
        y_values[0] -= needed
        y_values[1] += needed
        return x_values, y_values

    def get_local_cells(self, x_values, y_values, clue_index):
        """
        Collect all the unsolved cells in this area
        """
        unknowns = []
        for cell_index in self.unknowns:
            datum = self.datum[cell_index]
            x = datum.column
            y = datum.row
            if x >= x_values[0] and x <= x_values[1] and\
               y >= y_values[0] and y <= y_values[1] and\
               datum.is_navigable(clue_index):
                unknowns.append(cell_index)
        return unknowns

    def get_possible_polyominoes_1(self, clued_white):
        """
        Get the possible polyominoes for this clued_white.
        """
        clue_index = clued_white.clue_index
        size = clued_white.size
        white_cells, children = self.get_white_cells(clued_white)
        needed = size - len(white_cells)
        # if children must need >= 1 cell to join
        if children:
            needed -= 1
        # the extra cells needed could be added in any direction
        x_values, y_values = self.get_perimeter(white_cells, needed)
        unknowns = self.get_local_cells(x_values, y_values, clue_index)
        all_cells = set(unknowns) | set(white_cells)
        polyominoes = self.get_polyominoes(all_cells,
                                           size,
                                           white_cells)
        return polyominoes, white_cells

    def get_possible_polyominoes(self):
        white_poly_dic = {}
        # create a dictionary which contains the number
        # of cells in all unfinished whites
        for clued_white in self.unfinished_whites:
            clue_index = clued_white.clue_index
            polyominoes,\
                white_cells = self.get_possible_polyominoes_1(clued_white)
            white_poly_dic[clue_index] = polyominoes
        return white_poly_dic

    def get_these_whites(self, white_poly_dic, these_connectors):
        # which whites polyominoes contain these_connectors
        whites = set([])
        for white, polyominoes in list(white_poly_dic.items()):
            for polyomino in polyominoes:
                for connector in these_connectors:
                    if connector in polyomino:
                        whites.add(white)
        return whites

    def compare_connectors(self, connectors_dic, connectors,
                           white_polyominoes, this_black, bad_blacks):
        """
        Only one white can obstruct the connectivity for this black
        and we have all its polyominoes in white_polyominoes, and its
        connectors in connectors.
        We test each connector for this black and count how many
        connectors from other blacks it can reach.
        For each connector we set each possible polyomino as an obstruction.
        We accummulate all connectors which are blocked by all polyominoes.
        If only 1 connector is unblocked it must be black.
        """
        new_blacks = []
        blocked = set([])
        for connector_i in connectors:
            good_c = 0
            for black, connectors_j in list(connectors_dic.items()):
                if black != this_black:
                    for connector_j in connectors_j:
                        for polyomino in white_polyominoes:
                            if connector_i not in polyomino and\
                               connector_j not in polyomino:
                                bad = set(polyomino) | bad_blacks
                                dijkstra = Dijkstra(self.datum,
                                                    connector_i,
                                                    connector_j,
                                                    None,
                                                    bad,
                                                    False)
                                distance = dijkstra.distance
                                if distance is not None:
                                    good_c += 1
            if good_c == 0:
                # this connector is blocked by all possible polyominoes
                blocked.add(connector_i)
        new_black = connectors - blocked
        if len(new_black) == 1:
            new_blacks = [new_black.pop()]
        return new_blacks

    def black_connectivity_2(self, connectors_dic):
        self.set_gneighbours(None)
        white_poly_dic = {}
        hints = []
        alg = 5
        bad_blacks = self.get_bad_blacks()
        white_poly_dic = self.get_possible_polyominoes()
        # is there a black which is only affected by one white?
        for black, connectors in list(connectors_dic.items()):
            whites = self.get_these_whites(white_poly_dic, connectors)
            if len(whites) == 1:
                white_polyominoes = white_poly_dic[whites.pop()]
                new_blacks = self.compare_connectors(connectors_dic,
                                                     connectors,
                                                     white_polyominoes,
                                                     black, bad_blacks)
                if new_blacks:
                    hint = [new_blacks[0], Sgg.BLACK, alg]
                    hints.append(hint)
                    break
        return hints

    def probe_blacks_3(self, datum, direction):
        """
        _sq
           7 0 1
           6 . 2
           5 4 3

           . . .
           B B B

           o1o2o3
           b1b2b3

        incoming datum is o2
        """

        directions = [[6, 2, 4], [6, 2, 0], [0, 4, 2], [0, 4, 6]]
        ret = False
        nbrs = datum.neighbours_sq
        my_directions = directions[direction]
        o1 = nbrs[my_directions[0]]
        o3 = nbrs[my_directions[1]]
        b2 = nbrs[my_directions[2]]

        if o1 is not None and o3 is not None and b2 is not None:
            o1d = self.datum[o1]
            o3d = self.datum[o3]
            b2d = self.datum[b2]
            if o1d.guess is None and o3d.guess is None and\
               b2d.guess == Sgg.BLACK:
                b1 = o1d.neighbours_sq[my_directions[2]]
                b3 = o3d.neighbours_sq[my_directions[2]]
                if b1 is not None and b3 is not None and\
                   self.datum[b1].guess == Sgg.BLACK and\
                   self.datum[b3].guess == Sgg.BLACK:
                    ret = True
        return ret

    def probe_blacks_2(self, datum):
        """
        directions:
        3 vertical, black to left
        2 vertical, black to right
        1 horizontal black above
        0 horizontal black below
          datum is unknown
        """
        ret = False
        for direction in range(4):
            ret = self.probe_blacks_3(datum, direction)
            if ret:
                break
        return ret

    def probe_blacks_1(self):
        for unknown in self.unknowns:
            if self.probe_blacks_2(self.datum[unknown]):
                pass

    def probe_blacks(self):
        """
        Three blacks in a row adjacent to 3 unknows:
                  bbb
                  ...
        If the middle unknown is black then the cells either side
        must be white:
                  bbb
                  wbw
        So if they cannot be white the middle unknown is white.
        Cases
                  bbb
                  ...

                  ...
                  bbb

                   b.
                   b.
                   b.

                   .b
                   .b
                   .b

        """
        hints = []
        self.probe_blacks_1()
        return hints

    def do_blacks(self):
        alg = 3
        hints = []
        for unknown in self.unknowns:
            datum = self.datum[unknown]
            if not datum.reached_by:
                hint = [unknown, Sgg.BLACK, alg]
                hints.append(hint)
                break
        return hints

    def cheat(self):
        alg = 20
        hints = []
        for unknown in self.unknowns:
            answer = self.datum[unknown].colour
            hint = [unknown, answer, alg]
            hints.append(hint)
            break
        return hints

    def apply_algorithms(self):

        self.check_finished()
        if self.is_finished():
            return
        if not self.is_consistent():
            self.status = False
            return

        while True:
            self.assign_parents()
            self.apply_algorithms_1()
            if self.hints:
                break
            if not self.for_removal:
                break
        if not self.hints and not self.for_removal:
            self.hints = self.cheat()

    def apply_algorithms_1(self):
        if not self.hints and self.for_removal:
            self.hints = self.handle_removal()

        if not self.hints and not self.for_removal:
            self.hints = self.do_blacks()

        if not self.hints and not self.for_removal:
            self.hints = self.surround_completed()

        if not self.hints and not self.for_removal:
            self.hints = self.black_extension()

        if not self.hints and not self.for_removal:
            self.hints = self.white_extension()

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[0]
            self.hints = self.apply_pattern_family(pattern_family, 10)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[4]
            self.hints = self.apply_pattern_family(pattern_family, 14)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[7]
            self.hints = self.apply_pattern_family(pattern_family, 17)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[1]
            self.hints = self.apply_pattern_family(pattern_family, 11)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[5]
            self.hints = self.apply_pattern_family(pattern_family, 15)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[2]
            self.hints = self.apply_pattern_family(pattern_family, 12)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[3]
            self.hints = self.apply_pattern_family(pattern_family, 13)

        if not self.hints and not self.for_removal:
            pattern_family = self.search_patterns[6]
            self.hints = self.apply_pattern_family(pattern_family, 16)

        if not self.hints and not self.for_removal:
            self.hints = self.expansion_1()

        if not self.hints and not self.for_removal:
            self.hints = self.black_connectivity_1()

        if not self.hints and not self.for_removal:
            self.hints = self.unreachable_e()

        if not self.hints and not self.for_removal:
            self.hints = self.unite_families()

        if not self.hints and not self.for_removal:
            self.hints = self.unreachable_g()

        #if not self.hints:
        #    self.hints = self.probe_blacks()

        if not self.hints and not self.for_removal:
            self.hints = self.check_linkers()

        if not self.hints and not self.for_removal:
            self.hints = self.unreachable_d()

        Sgg.progress = False
        return

    def for_test_apply_algorithms(self):
        max_tries = 20
        self.check_finished()
        if self.is_finished():
            return
        if not self.is_consistent():
            self.status = False
            return
        tries = -1
        while True:
            tries += 1
            order = list(range(4, 21))
            random.shuffle(order)
            while order:
                alg = order.pop()
                self.assign_parents()
                self.apply_algorithms_1(alg)
                if self.hints:
                    break
                if tries > max_tries and not self.for_removal:
                    break
            if self.hints:
                break
            if tries > max_tries and not self.for_removal:
                break
        #if not self.hints and not self.for_removal:
        #    self.hints = self.cheat()

    def for_test_apply_algorithms_1(self, alg):
        if not self.hints and self.for_removal:
            self.hints = self.handle_removal()

        if not self.hints and not self.for_removal:
            self.hints = self.do_blacks()

        if not self.hints and not self.for_removal:
            self.hints = self.surround_completed()

        if not self.hints and not self.for_removal:
            self.hints = self.black_extension()

        if not self.hints and not self.for_removal:
            self.hints = self.white_extension()

        if not self.hints and not self.for_removal:
            if alg == 10:
                pattern_family = self.search_patterns[0]
                self.hints = self.apply_pattern_family(pattern_family, 10)
            elif alg == 14:
                pattern_family = self.search_patterns[4]
                self.hints = self.apply_pattern_family(pattern_family, 14)
            elif alg == 17:
                pattern_family = self.search_patterns[7]
                self.hints = self.apply_pattern_family(pattern_family, 17)
            elif alg == 11:
                pattern_family = self.search_patterns[1]
                self.hints = self.apply_pattern_family(pattern_family, 11)
            elif alg == 15:
                pattern_family = self.search_patterns[5]
                self.hints = self.apply_pattern_family(pattern_family, 15)
            elif alg == 12:
                pattern_family = self.search_patterns[2]
                self.hints = self.apply_pattern_family(pattern_family, 12)
            elif alg == 13:
                pattern_family = self.search_patterns[3]
                self.hints = self.apply_pattern_family(pattern_family, 13)
            elif alg == 16:
                pattern_family = self.search_patterns[6]
                self.hints = self.apply_pattern_family(pattern_family, 16)
            elif alg == 4:
                self.hints = self.expansion_1()
            elif alg == 5:
                self.hints = self.black_connectivity_1()
            elif alg == 8:
                self.hints = self.unite_families()
            elif alg == 7:
                self.hints = self.unreachable_e()
            elif alg == 19:
                self.hints = self.unreachable_g()
            elif alg == 18:
                self.hints = self.check_linkers()
            elif alg == 9:
                self.hints = self.unreachable_d()

        Sgg.progress = False
        return

    def solver(self):
        status = False
        self.progress = True
        while self.progress:
            self.progress = False
            self.apply_algorithms()
            if not self.status:
                return False
            if self.is_finished():
                #self.print_grid()
                status = True
                break
            if self.hints:
                hint = self.hints[0]
                self.apply_hint()
                self.datum[hint[0]].set_guess(hint[1])

                self.update_alg_usage(hint[2])

                self.hints = []
                #self.print_grid()
            if not Sgg.progress and not self.for_removal:
                break
            else:
                self.progress = True
        return status

    def solver_1(self):
        status = False
        self.progress = True
        while self.progress:
            self.progress = False
            self.apply_algorithms()
            if not self.status:
                return False
            if self.is_finished():
                #print 'finished'
                #self.print_grid()
                status = True
                break
            if self.hints:
                hint = self.hints[0]
                self.apply_hint()
                self.datum[hint[0]].set_guess(hint[1])

                self.update_alg_usage(hint[2])
                self.hints = []
                #self.print_grid()
            if not Sgg.progress and not self.for_removal:
                break
            else:
                self.progress = True
        return status

    def apply_user_click(self, action, datum_index):
        """
        All user actions are stored in Datum as guess.
        If bad status we accummulate edits
        """
        ret = []
        datum = self.datum[datum_index]
        self.check_errors()
        if action is Sgg.WHITE:
            datum.set_guess(Sgg.WHITE)
            if self.status and datum.is_consistent() and\
               datum.colour == Sgg.WHITE:
                self.add_whites([[datum.index, Sgg.WHITE]])
            else:
                if self.user_edits is None:
                    self.user_edits = UserEdits()
                self.user_edits.add(datum)
            ret = [datum.index]
        elif action is Sgg.BLACK:
            datum.set_guess(Sgg.BLACK)
            if self.status and datum.is_consistent() and\
               datum.colour == Sgg.BLACK:
                self.add_blacks([[datum.index, Sgg.BLACK]])
            else:
                if self.user_edits is None:
                    self.user_edits = UserEdits()
                self.user_edits.add(datum)
            ret = [datum.index]
        elif action is Sgg.DELETE:
            if datum.guess == Sgg.BLACK or datum.guess == Sgg.WHITE:
                datum.reset()
                self.reset_range(datum)
                if datum in self.user_edits.edits:
                    self.user_edits.delete(datum)
                ret = [datum.index]
        return ret

    def undo_user_edits(self):
        updates = []
        for datum in self.user_edits.edits:
            updates.append(datum.index)
            datum.reset()
            self.reset_range(datum)
        self.user_edits = None
        return updates

    def do_links(self, datum):
        """
        If we turn datum white will its linked cells
        still be linked?
        Possible links between 0-2, 2-4, 4-6, 6-0,
        and 0-4 and 2-6.
        The last 2 require dijkstra, but we may be able to avoid
        it for the others.
        """
        def check_pairwise(nbr0, nbr2, nbr1):
            """
            If the link between nbr0 and nbr2 does not need dijkstra
            if
            """
            is_ok = False
            if nbr0 is None:
                is_ok = True
            if nbr2 is None:
                is_ok = True
            if not is_ok:
                if self.datum[nbr0].guess == Sgg.BLACK and\
                   self.datum[nbr2].guess == Sgg.BLACK:
                    # datum is link between 0 and 2
                    if nbr1 is not None and\
                       self.datum[nbr1].guess == Sgg.BLACK:
                        # they are still linked via 1
                        is_ok = True
                else:
                    # at least one is not black so ok
                    is_ok = True
            return is_ok

        pairs = [[0, 2], [2, 4], [4, 6], [6, 0], [0, 4], [2, 6]]
        ret = True
        done = [False, False, False, False, True, True]
        nbrs = datum.neighbours_sq
        done[0] = check_pairwise(nbrs[0], nbrs[2], nbrs[1])
        done[1] = check_pairwise(nbrs[2], nbrs[4], nbrs[3])
        done[2] = check_pairwise(nbrs[4], nbrs[6], nbrs[5])
        done[3] = check_pairwise(nbrs[6], nbrs[0], nbrs[7])
        if nbrs[0] is not None and\
           self.datum[nbrs[0]].guess == Sgg.BLACK and\
           nbrs[4] is not None and\
           self.datum[nbrs[4]].guess == Sgg.BLACK:
            done[4] = False
        if nbrs[2] is not None and\
           self.datum[nbrs[2]].guess == Sgg.BLACK and\
           nbrs[6] is not None and\
           self.datum[nbrs[6]].guess == Sgg.BLACK:
            done[5] = False

        # are there alternative paths?
        if False in done:
            bad = [datum.index]
            #self.set_gneighbours(None)
            for i in range(6):
                if not done[i]:
                    pair = pairs[i]
                    ret = True
                    dijkstra = Dijkstra(self.datum,
                                        nbrs[pair[0]],
                                        nbrs[pair[1]],
                                        None,
                                        bad,
                                        False)
                    distance = dijkstra.distance
                    if distance is None:
                        ret = False
                if not ret:
                    break
        return ret

    def get_black_4s(self):
        """
        Check for black squares
        """
        cases = [[2, 3, 4], [4, 5, 6], [0, 6, 7], [0, 1, 2]]
        squares = []
        for datum in self.datum:
            if datum.guess == Sgg.BLACK:
                nbrs = datum.neighbours_sq
                for case in cases:
                    square = []
                    for item in case:
                        nbr = nbrs[item]
                        if nbr is not None and\
                           self.datum[nbr].guess == Sgg.BLACK:
                            square.append(nbr)
                    if len(square) == 3:
                        square.append(datum.index)
                        squares.append(square)
        return squares

    def get_white_4s(self):
        """
        Check for white squares
        """
        cases = [[2, 3, 4], [4, 5, 6], [0, 6, 7], [0, 1, 2]]
        squares = []
        for datum in self.datum:
            if datum.guess == Sgg.WHITE:
                nbrs = datum.neighbours_sq
                for case in cases:
                    square = []
                    for item in case:
                        nbr = nbrs[item]
                        if nbr is not None and\
                           self.datum[nbr].guess == Sgg.WHITE:
                            square.append(nbr)
                    if len(square) == 3:
                        square.append(datum.index)
                        squares.append(square)
        return squares

    def get_unsolved_4s(self):
        """
        Check for unsolved squares
        """
        cases = [[2, 3, 4], [4, 5, 6], [0, 6, 7], [0, 1, 2]]
        squares = []
        for datum in self.datum:
            if datum.guess is None:
                nbrs = datum.neighbours_sq
                for case in cases:
                    square = []
                    for item in case:
                        nbr = nbrs[item]
                        if nbr is not None and\
                           self.datum[nbr].guess is None:
                            square.append(nbr)
                    if len(square) == 3:
                        square.append(datum.index)
                        squares.append(square)
        return squares

    def expansion_4(self, my_index, good, done):
        """
        RECURSION!!!
        Measure a collection of adjacent white cells
        """
        len_good = len(good)
        done.add(my_index)
        datum = self.datum[my_index]
        if datum.guess == Sgg.WHITE:
            good.add(my_index)
            nbrs = datum.neighbours_gg
            for nbr in nbrs:
                if nbr not in done:
                    self.expansion_4(nbr, good, done)
            if len(good) == len_good:
                # return if made no progress
                return

    def count_whites(self, datum, max_white):
        """
        If this cell is made white will it make
        a White that is too big?
        """
        ret = True
        nbrs = datum.neighbours_gg
        whites = []
        for nbr in nbrs:
            if self.datum[nbr].guess == Sgg.WHITE:
                whites.append(nbr)
        for white in whites:
            good = set([])
            done = set([])
            self.expansion_4(white, good, done)
            if len(good) > max_white:
                ret = False
                break
        return ret

    def count_whites_1(self, datum):
        """
        If this cell is made white how big a White will it make?
        """
        size = 0
        nbrs = datum.neighbours_gg
        whites = []
        for nbr in nbrs:
            if self.datum[nbr].guess == Sgg.WHITE:
                whites.append(nbr)
        for white in whites:
            good = set([])
            done = set([])
            self.expansion_4(white, good, done)
            size = max(size, len(good))
        return size

    def count_whites_2(self, max_white):
        ret = True
        for cell_index in range(Sgg.cell_count):
            datum = self.datum[cell_index]
            # if not making whites too big
            if not self.count_whites(datum, max_white):
                ret = False
                break
        return ret

    def get_whites(self):
        whites = []
        for cell_index in range(Sgg.cell_count):
            datum = self.datum[cell_index]
            if datum.guess == Sgg.WHITE:
                found = False
                for white in whites:
                    for w in white:
                        if self.datum[w].touches(cell_index):
                            white.append(cell_index)
                            found = True
                            break
                    if found:
                        break
                if not found:
                    whites.append([cell_index])
        new_whites = []
        for white in whites:
            new_whites.append(set(white))
        whites = new_whites
        progress = True
        c = 0
        while progress:
            c += 1
            if c > 30:
                exit(1)
            progress = False
            for white_0 in whites:
                for w_0 in white_0:
                    for white_1 in whites:
                        if white_1 != white_0:
                            for w_1 in white_1:
                                if self.datum[w_0].touches(w_1):
                                    # assume they all touch
                                    white_00 = white_0 | white_1
                                    whites.remove(white_1)
                                    whites.remove(white_0)
                                    whites.append(white_00)
                                    progress = True
                                    break
                        if progress:
                            break
                    if progress:
                        break
                if progress:
                    break
        return whites

    def generate_1(self):
        whites = []
        # fill grid with black cells
        self.datum = []
        for cell_index in range(Sgg.cell_count):
            datum = Datum(cell_index, 1)
            datum.set_guess(Sgg.BLACK)
            self.datum.append(datum)
        order = list(range(Sgg.cell_count))
        random.shuffle(order)
        max_white = 4
        self.set_gneighbours(None)
        for cell_index in order:
            datum = self.datum[cell_index]
            # if not making whites too big
            if self.count_whites(datum, max_white):
                # and links OK
                if self.do_links(datum):
                    datum.set_guess(Sgg.WHITE)
                    self.update_gneighbours(datum, None)
        #self.print_grid()
        max_white = 6
        finished = False
        progress = True
        while progress:
            squares = self.get_black_4s()
            if not squares:
                if self.count_whites_2(max_white):
                    whites = self.get_whites()
                    finished = True
                    break
            progress = False
            for square in squares:
                # which cell, if white, would make the smallest White?
                smallest = 99
                smallest_index = None
                for cell_index in square:
                    datum = self.datum[cell_index]
                    size = self.count_whites_1(datum)
                    if size < smallest:
                        size = smallest
                        smallest_index = cell_index
                datum = self.datum[smallest_index]
                if self.do_links(datum):
                    datum.set_guess(Sgg.WHITE)
                    self.update_gneighbours(datum, None)
                    progress = True
                #self.print_grid()
        if finished:
            squares = self.get_white_4s()
            #squares = []
            if squares:
                whites = []
        return whites

    def ginit(self):
        self.datum = []
        self.blacks = Container()
        self.whites = Container()
        self.unfinished_whites = []
        self.orphan_whites = []
        self.new_blacks = set([])
        self.unknowns = set([])
        self.status = True
        self.finished = False
        self.alg_usage = [0] * self.alg_count
        self.hints = []

    def fiddle_clue_indexes(self, undone):
        def touches(cell_1, cell_2):
            ret = False
            nbr = cell_1 - Sgg.grid_width + 1
            if nbr % Sgg.grid_width != 0 and cell_2 == nbr:
                ret = True
            else:
                nbr = cell_1 + Sgg.grid_width + 1
                if nbr % Sgg.grid_width != 0 and cell_2 == nbr:
                    ret = True
                else:
                    nbr = cell_1 + Sgg.grid_width - 1
                    if cell_1 % Sgg.grid_width != 0 and cell_2 == nbr:
                        ret = True
                    else:
                        nbr = cell_1 - Sgg.grid_width - 1
                        if cell_1 % Sgg.grid_width != 0 and cell_2 == nbr:
                            ret = True
            return ret

        pairs = []
        progress = True
        while progress:
            progress = False
            for white_1 in undone:
                for item_1 in white_1:
                    for white_2 in undone:
                        if white_2 != white_1:
                            for item_2 in white_2:
                                if touches(item_1, item_2):
                                    pair = [white_1, item_1]
                                    pairs.append(pair)
                                    pair = [white_2, item_2]
                                    pairs.append(pair)
                                    undone.remove(white_1)
                                    undone.remove(white_2)
                                    progress = True
                                    break
                        if progress:
                            break
                    if progress:
                        break
                if progress:
                    break
        return undone, pairs

    def fiddle_clue_indexes_2(self, whites):
        """
        Rearrange white cell lists so that cells with only
        one white neighbour are first in the list.
        Assuming that whites with clues in those positions
        will be more easily solved.
        """
        def touches(cell_1, cell_2):
            ret = False
            nbr = cell_1 - Sgg.grid_width
            if cell_2 == nbr:
                ret = True
            else:
                nbr = cell_1 + Sgg.grid_width
                if cell_2 == nbr:
                    ret = True
                else:
                    nbr = cell_1 + 1
                    if nbr % Sgg.grid_width != 0\
                       and cell_2 == nbr:
                        ret = True
                    else:
                        nbr = cell_1 - 1
                        if cell_1 % Sgg.grid_width != 0\
                           and cell_2 == nbr:
                            ret = True
            return ret

        new_whites = []
        sizes = []
        for white in whites:
            sizes.append(len(white))
            new_list = []
            for item_1 in white:
                count = 0
                for item_2 in white:
                    if item_2 != item_1:
                        if touches(item_1, item_2):
                            count += 1
                if count == 1:
                    new_list.append(item_1)
            new_whites.append(new_list)
        return new_whites, sizes

    def generate_2(self, whites_in, tries):
        # 1 == BLACK, 0 == WHITE, -n = clue
        whites = list(whites_in)
        all_whites = []
        for white in whites_in:
            for cell in white:
                all_whites.append(cell)
        ones = []
        for white in whites_in:
            if len(white) == 1:
                ones.append(white)
                whites.remove(white)
        whites, pairs = self.fiddle_clue_indexes(whites)
        fixed = [1] * Sgg.cell_count
        for white in all_whites:
            fixed[white] = 0
        for white in ones:
            fixed[list(white)[0]] = -1
        for pair in pairs:
            fixed[pair[1]] = -len(pair[0])
        whites, sizes = self.fiddle_clue_indexes_2(whites)
        for items in product(*whites):
            tries += 1
            data = []
            for cell in range(Sgg.cell_count):
                data.append(fixed[cell])

            wi = -1
            for item in items:
                wi += 1
                lenw = sizes[wi]
                data[item] = -lenw
            Sgg.CURRENT_PUZZLE = data
            self.ginit()
            for cell in range(Sgg.cell_count):
                self.datum.append(Datum(cell, data[cell]))
            self.init_types()
            self.init_ranges()
            self.refine_ranges()
            status = self.solver()
            if status:
                break
        if not status:
            data = []
        return data, tries

    def generate(self):
        """
        Make a grid of blacks.
        Try removing blacks in random order until all have been tried
        """
        random.seed(Sgg.seed)
        Sgg.grid_width = 10
        Sgg.grid_height = 10
        Sgg.cell_count = Sgg.grid_width * Sgg.grid_height
        puzzles = []
        Sgg.start_time = time.time()
        trials = 0
        tries = 0
        good_whites = 0
        while True:
            trials += 1
            whites = self.generate_1()
            if whites:
                delta_time = int(time.time() - Sgg.start_time)
                if delta_time > Sgg.max_time:
                    break
                good_whites += 1
                data, tries = self.generate_2(whites, tries)
                if data:
                    puzzle = []
                    puzzle.append(Sgg.grid_width)
                    puzzle.append(Sgg.grid_height)
                    for item in data:
                        puzzle.append(item)
                    puzzles.append(puzzle)
                    #print 'puzzle count', len(puzzles), trials, good_whites, tries
        filename = 'puzzles_' + str(Sgg.seed) + '.txt'
        with open(filename, "w") as fo:
            rec = ''
            for puzzle in puzzles:
                for item in puzzle:
                    rec += str(item)
                    rec += ','
            fo.write(rec)
        exit(1)

    """
    def print_grid(self):
        item = -1
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                item += 1
                sym = '+'
                if self.datum[item].guess == Sgg.WHITE:
                    sym = '.'
                print sym,
            print
        print
    """


class Board(tk.Frame):
    def __init__(self, parent, settings, model):
        self.settings = settings
        self.model = model
        self.grid_widgets = []
        bg = self.settings.green
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=2,
                          bd=2, bg=bg)

        square_index = 0
        for row in range(Sgg.grid_height):
            for column in range(Sgg.grid_width):
                #datum = datum_dic[square_index]
                output = self.get_update(square_index, -1)
                text = output[0]
                fg = output[1]
                bg = output[2]
                square = TextSquare(self, self.settings, square_index, fg,
                                    bg, text)
                square.grid(row=row, column=column)
                square.grid_propagate(0)
                self.grid_widgets.append(square)
                square_index += 1
        self.grid(row=0, column=0)

    def my_destroy(self):
        for widget in self.grid_widgets:
            widget.my_destroy()
        self.destroy()

    def add_callback(self, func):
        for widget in self.grid_widgets:
            widget.callback = func

    def get_update(self, square_index, job):
        """
        whole cell white
        whole cell black
        whole cell grey
        set clue (white with black number)
        hint (orange with ?)
        error (whole cell red)
        12 hint
        13 hint off
        14 undo error
        15 set error red
        return [symbol, fg, bg]
        """
        numbers = [' ', '1', '2', '3', '4', '5', '6', '7', '8', '9']
        hint = '?'
        grey = '#A9AAA9'
        red = self.settings.red
        update = []
        if job == -1:
            cell = self.model.datum[square_index]
            if cell.size is not None:
                update = [numbers[cell.size], 'black', 'white']
            elif cell.guess == Sgg.WHITE:
                update = [numbers[0], 'white', 'white']
            elif cell.guess == Sgg.BLACK:
                update = [numbers[0], 'black', 'black']
            else:
                update = [numbers[0], grey, grey]
        elif job > -1 and job < 10:
            update = [numbers[job], 'white', grey]
        elif job == 12:
            update = [hint, 'black', 'orange']
        elif job == 13:
            update = [' ', 'black', grey]
        elif job == 14:
            update = [' ', 'black', grey]
        elif job == 15:
            if self.model.datum[square_index].guess == Sgg.BLACK:
                bg = 'black'
            else:
                bg = 'white'
            update = ['X', red, bg]
        return update

    def update_squares(self, changes):
        """
        changes is a list of datums that have changed.
        """
        for square_index in changes:
            self.update_square(square_index, -1)

    def update_square(self, square_index, job):
        """
        Update cell square_index with a known operation (job)
        """
        update = self.get_update(square_index, job)
        widget = self.grid_widgets[square_index]
        widget.my_update(update)


class View(ViewB):
    """
    Stick blobs on the screen and respond to callbacks
    """

    def __init__(self, master, settings):
        ViewB.__init__(self, master, settings)
        self.model = None
        self.image_dic = {}
        self.make_image_dic()
        self.image_dic['start'] = [self.images.start_nurikabe, 0, True]
        self.do_layout(self)
        self.entry_box.activate()

    def make_board(self):
        """
        draw the squares
        """

        if self.board is not None:
            self.board.my_destroy()
        self.board = Board(self.top_frame, self.settings,
                           self.model)

    def update_clock_box(self, algorithm):
        value = '  '
        if algorithm is not None:
            value = Sgg.ALGORITHM_NAMES[algorithm]
        self.clock.box.set_text(value)


class Controller(object):
    """
    Set up and control
    """

    def __init__(self, root):
        self.settings = Settings()
        self.master = root
        self.flasher = None
        self.model_data = ModelData()
        self.model = None
        self.hint_status = Sgg.GIVE_HINT
        self.status = False
        self.active = False
        self.error_detected = False
        self.puzzle_number = None
        self.exposed = {}
        screen_shot_state = False
        self.screen_shot = ScreenShot(PzlG.app_name,
                                      'dump_',
                                      screen_shot_state)
        self.view = View(root, self.settings)
        puzzle_number = None
        """
        if len(sys.argv) > 1:
            if Sgg.generate:
                Sgg.seed = int(sys.argv[1])
                Sgg.max_time = int(sys.argv[2])
            else:
                puzzle_number = int(sys.argv[1])
        """
        self.start_game(puzzle_number)

    def set_puzzle_number(self, puzzle_number):
        if puzzle_number is None or puzzle_number < 0 or \
                puzzle_number > self.model_data.puzzle_count - 1:
            puzzle_number = randint(0, self.model_data.puzzle_count - 1)
        self.puzzle_number = puzzle_number

    def test(self):
        max_trial = 1
        bad = []

        for trial in range(max_trial):
            for puzzle_number in range(self.model_data.puzzle_count):
                #print '>>>>>>', puzzle_number
                if puzzle_number not in bad:
                    self.model = Model(self.settings, self.model_data)
                    self.model.get_puzzle(puzzle_number)
                    success = self.model.solver_1()
                    if not success:
                        bad.append(puzzle_number)
                #print Sgg.alg_usage
        """
        PzlG.logger.logger.info("test " + str(done) + ' bad ' +
                                " ".join(str(x) for x in bad))
        good = []
        for puzzle_number in range(self.model_data.puzzle_count):
            if puzzle_number not in bad:
                puzzle = self.model.model_data.get_puzzle(puzzle_number)
                good += puzzle
        print good
        """
        #print 'remaining', self.model_data.puzzle_count - len(bad)
        exit(1)

    def start_game(self, puzzle_number):
        #self.test()
        self.set_puzzle_number(puzzle_number)
        self.view.clock_init()
        self.view.clock_restart()
        self.view.game_over()
        self.model = Model(self.settings, self.model_data)
        if Sgg.generate:
            self.model.generate()
        self.model.get_puzzle(self.puzzle_number)
        self.view.thumbs_up()
        self.view.model = self.model
        self.view.make_board()
        self.add_callbacks()
        self.view.game_on()
        self.error_detected = False
        self.view.entry_box.clear()
        self.view.entry_box.write_box(str(self.puzzle_number))
        #self.view.update_score_box(self.model.difficulty)
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        self.status = False
        self.active = True
        self.hint_status = Sgg.GIVE_HINT

    def add_callbacks(self):
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.entry_box.add_callback(self.get_puzzle_number)
        self.view.board.add_callback(self.square_event)

    def service_menu(self, *args):
        """
        Respond to menu choices
        """

        strargs = ''
        for item in args:
            strargs += ' ' + item
        PzlG.logger.logger.info("service_menu " + strargs)
        name = args[0]
        if name == 'font_size':
            self.set_font_size()
        elif name == 'temp_solver':
            #self.model.solver()
            self.temp_solver()
        elif name == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

    def service_toolbar(self, button_index, mouse_index):
        PzlG.logger.logger.info("service_toolbar " +
                                str(button_index) +
                                ' ' +
                                str(mouse_index))

        if mouse_index == 2:
            alg_index = None
            if self.model.hints:
                alg_index = self.model.hints[0][2]
            self.view.do_tooltip(button_index, alg_index)
        elif mouse_index == 3:
            if button_index == 0:
                self.puzzle_number += 1
                self.start_game(self.puzzle_number)
        elif mouse_index == 1:
            if button_index == 0:
                self.start_game(None)
            elif button_index == 1:
                if not self.model.is_finished():
                    self.give_hint()
                    self.screen_shot.snap()
            elif button_index == 2:
                if not self.model.is_finished():
                    self.check_errors()
            elif button_index == 3:
                if not self.model.is_finished():
                    self.show_solution()

    def square_event(self, datum_index, mouse_index):
        """
        left mouse white
        middle mouse delete
        right mouse black
        """

        if self.active:
            PzlG.logger.logger.info("square_event " +
                                    str(mouse_index) +
                                    ' ' +
                                    str(datum_index))
            # need to remove any active hint
            if self.model.hints:
                self.view.hint_off()
                #if self.model.hint:
                hint_datum_index = self.model.hints[0][0]
                self.view.board.update_square(hint_datum_index, 13)
                self.model.hints = []
            self.hint_status = Sgg.GIVE_HINT

            changes = []
            if mouse_index == 1:
                # player has left clicked on this cell
                # ie wants to set it white
                changes = self.model.apply_user_click(Sgg.WHITE,
                                                      datum_index)
            elif mouse_index == 2:
                # player has middle clicked on this cell
                # ie wants to delete
                changes = self.model.apply_user_click(Sgg.DELETE,
                                                      datum_index)
            elif mouse_index == 3:
                # player has right clicked on this cell
                # ie wants to make it black
                changes = self.model.apply_user_click(Sgg.BLACK,
                                                      datum_index)
            if changes:
                # send list of changed cells to board
                self.view.board.update_squares(changes)
            self.check_finished()

    def ready_for_hint(self):
        if not self.model.is_finished():
            self.hint_status = Sgg.GIVE_HINT
            self.model.delete_hint()
            if self.model.status:
                self.view.hint_off()
                self.view.thumbs_up()
                self.error_detected = False
            self.view.clock.set_show(True)

    def temp_solver(self):
        self.hint_status = Sgg.GIVE_HINT
        while True:
            if self.hint_status == Sgg.GIVE_HINT:
                self.model.apply_algorithms()
                if self.model.status and self.model.hints:# or Sgg.progress:
                    self.view.hint_on()
                    hint = self.model.hints[0]
                    datum_index = hint[0]
                    colour = hint[1]
                    alg = hint[2]
                    self.model.update_alg_usage(alg)
                    self.model.datum[datum_index].set_guess(colour)
                    self.view.board.update_square(datum_index, 12)
                    self.view.update_clock_box(alg)
                    self.view.clock.set_show(False)
                    self.hint_status = Sgg.APPLY_HINT
                elif not Sgg.progress and not self.model.for_removal:
                    self.hint_status = Sgg.GIVE_HINT
                    return
                elif self.model.is_finished():
                    return
                elif not self.status:
                    return
            else:
                if self.model.hints:
                    self.apply_hint()
                    self.ready_for_hint()
                    self.check_finished()
                self.hint_status = Sgg.GIVE_HINT

    def give_hint(self):
        if self.hint_status == Sgg.GIVE_HINT:
            self.model.do_hint()
            if not self.model.status:
                self.view.thumbs_down()
                self.colour_errors()
                self.error_detected = True
            elif self.model.hints:
                self.view.hint_on()
                hint = self.model.hints[0]
                datum_index = hint[0]
                colour = hint[1]
                alg = hint[2]
                self.model.update_alg_usage(alg)
                self.model.datum[datum_index].set_guess(colour)
                self.view.board.update_square(datum_index, 12)
                self.view.update_clock_box(alg)
                self.view.clock.set_show(False)
            self.hint_status = Sgg.APPLY_HINT
        else:
            if self.model.hints:
                self.apply_hint()
                self.ready_for_hint()
                self.check_finished()
            self.hint_status = Sgg.GIVE_HINT


    def check_errors(self):
        if self.error_detected:
            # may have deleted edits
            if self.model.user_edits is not None:
                # we know there's an error already, so now we correct it
                self.tidy_error()
            self.model.check_errors()
            if not self.model.status:
                PzlG.logger.logger.error("errors_check ")
                return
            self.ready_for_hint()
        else:
            self.model.check_errors()
            if not self.model.status:
                self.view.thumbs_down()
                self.error_detected = True
                self.colour_errors()

    def show_solution(self):
        self.active = False
        for datum_index in range(Sgg.cell_count):
            datum = self.model.datum[datum_index]
            if datum.size is None:
                changes = self.model.apply_user_click(datum.colour,
                                                      datum_index)
                self.view.board.update_squares(changes)

        self.view.game_over()
        self.view.clock_stop()

    def check_finished(self):
        """
        Check if finished.
        If so, handle buttons, flasher and clock
        """
        self.model.check_finished()
        if self.model.is_finished():
            self.active = False
            self.view.game_over()
            self.view.clock.set_show(True)
            self.view.clock_stop()
            self.flasher.flash()

    def apply_hint(self):
        changes = self.model.apply_hint()
        if changes:
            # send list of changed cells to board
            self.view.board.update_squares(changes)

    def colour_errors(self):
        """
        Colour the error squares and note their indexes for uncolouring.
        """
        job = 15
        for datum in self.model.errors:
            self.view.board.update_square(datum.index, job)

    def tidy_error(self):
        """
        update view and undo errors
        """
        job = 14
        updates = self.model.undo_user_edits()
        for update in updates:
            self.view.board.update_square(update, job)
        self.model.errors = []
        self.model.delete_hint()
        self.model.status = True
        self.error_detected = False
        self.view.thumbs_up()

    def set_font_size(self):
        self.settings.do_scaling()
        self.start_game(self.puzzle_number)

    def get_puzzle_number(self, text):
        if text.find('XYZZY') != -1:
            self.view.xyzzy()
            self.view.entry_box.clear()
        else:
            try:
                puzzle_number = int(text)
                self.start_game(puzzle_number)
                self.screen_shot.snap()
            except ValueError:
                self.view.entry_box.clear()


INITIALISE = PzlG()
if __name__ == '__main__':
    try:
        ROOT = tk.Tk()
        ROOT.withdraw()
        APP = Controller(ROOT)
        ROOT.mainloop()
        PzlG.logger.logger.info("Stop program")
    except:
        PzlG.logger.logger.info("Failure!")
        PzlG.logger.logger.exception("Unhandled exception during main")
