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

# Copyright (C) 2017 Rod Engerstad

import random
from random import randint
from itertools import product
import colorsys
import Tkinter as tk
import zlib
import base64
import sys

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 Square
from pzl_lib import Egg
from pzl_lib import EditPair
from pzl_lib import UserEdits
from pzl_lib import Editor


class Sgg(object):
    grid_width = None
    grid_height = None
    GIVE_HINT = 0
    APPLY_HINT = 1
    CAUSE = 0
    EFFECT = 1
    SOLVE = 0
    HINT = 1
    ALGORITHM_NAMES = ['0', '1', '2', '3',
                       '4', '5', '6', '7', '8']
    COLOURS = ['#ff7f7f', '#ffcc7f', '#e5ff7f', '#99ff7f', '#7fffb2',
               '#7fffff', '#7fb2ff', '#987fff', '#e57fff', '#ff7fcb']
    symbol_count = None


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.original_square_size = 54
        self.square_size = self.original_square_size
        self.dic = {}
        self.dic['text_colour'] = '#000000'
        self.dic['cause_colour'] = '#00d341'
        self.dic['effect_colour'] = '#ff0000'
        self.dic['button_colour'] = '#82c026'
        self.dic['error_colour'] = '#ff0000'
        self.dic['font_size'] = '1'
        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 = [_("Each unfinished cell need only contain candidates for the unsolved polyominoes that the surround the hole it is part of."), _("Delete candidates which would permit the creation of oversize polyominoes."), _("When a polyomino is complete neighbouring cells cannot have its value."), _("If the total size of the holes touching a polyomino exactly matches the number of cells it needs for completion, they must be part of the polyomino."), _("If a polyomino only touches a single hole and can only reach it via a single cell, that cell must be part of the polyomino. Or if a polyomino only touches a single hole and must include a particular cell in all possible solutions, that cell must be part of the polyomino."), _("If no unfinished polyomino of a particular size can reach a hole cell, the candidates of that size can be deleted.")]


    def make_help(self):
        self.help_text = _("The program starts with a randomly selected puzzle displayed. The possible candidate answers are written in the unsolved squares. These numbers are buttons: left-clicking will delete a candidate, middle-clicking on its position will rewrite it, right-clicking will set it as the answer and delete any other candidates present. 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 number next to the puzzle number is the puzzle difficulty score. The clock ticks every 5 seconds but will be replaced by the algorithm number if a hint is requested. A left click on the hint button will request a single hint. 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. Hints are shown by highlighting the candidates that can be deleted in red. A further left click will delete the red candidates. The program contains 1000 puzzles.")

    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 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(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))


class Board(tk.Frame):
    def __init__(self, parent, settings, grid_dic):
        self.settings = settings
        self.grid_dic = grid_dic
        self.widget_dic = {}
        bg = self.settings.white
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=2,
                          bd=2, bg=bg)
        self.grid(row=0, column=0)
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            key = (x, y)
            datum = self.grid_dic[key]
            widget = Square(self, self.settings,
                            datum, datum.colour,
                            key, y, x)
            self.widget_dic[key] = widget

    def my_destroy(self):
        self.destroy()

    def add_candidate_callback(self, func):
        for _, widget in list(self.widget_dic.items()):
            candidates = widget.candidates
            for candidate in candidates:
                candidate.callback = func

    def get_square_colour(self, square_index):
        datum = self.grid_dic[square_index]
        colour = "#ffffff"
        if datum.guess is not None:
            colour = datum.colour
        return colour

    def update_square(self, update):
        """
        set some colours
        """
        operation = update.operation
        cell_id = update.cell_id
        widget = self.widget_dic[cell_id]
        bg_colour = self.get_square_colour(cell_id)
        update.colour = bg_colour
        if operation == Egg.COLOUR_CANDIDATES_EFFECT:
            # colour effect candidates
            bg_colour = self.settings.dic['effect_colour']
            update.colour = bg_colour
        elif operation == Egg.COLOUR_CANDIDATES_CAUSE:
            # colour cause candidates
            bg_colour = self.settings.dic['cause_colour']
            update.colour = bg_colour
        elif operation == Egg.HIGHLIGHT_ERROR:
            bg_colour = self.settings.dic['error_colour']
            update.colour = bg_colour
        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.datum = None
        self.image_dic = {}
        self.make_image_dic()
        self.image_dic['start'] = [self.images.start_fillomino, 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.datum)

    def update_squares(self, updates):
        for update in updates:
            self.board.update_square(update)

    def add_candidate_callback(self, func):
        self.board.add_candidate_callback(func)

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


class Node(object):
    """
    A node for Djkstra
    """
    def __init__(self, datum, oob):
        self.key = datum.key
        self.neighbours = []
        for neighbour in datum.neighbours:
            if neighbour is not None and neighbour not in oob:
                self.neighbours.append(neighbour.key)
        self.distance = 999999
        self.unvisited = True
        self.predecessor = None


class Dijkstra(object):
    """
    Dijkstra algorithm to find path from start to finish
    avoiding oob (out of bounds)
    """
    def __init__(self, datum_dic, start, finish, oob):
        self.path = []
        self.start_node_key = start
        self.end_node_key = finish
        # node_dic: a dictionary of Nodes indexed on datum.key
        # (only need navigable ones)
        # this is not enough to guarantee a path: there
        # might still be pockets of unreachable passage
        self.node_dic = {}
        for key, datum in list(datum_dic.items()):
            good_datum = False
            for neighbour in datum.neighbours:
                if neighbour not in oob:
                    good_datum = True
                    break
            if good_datum:
                self.node_dic[key] = Node(datum, oob)
        # active_dic a dictionary of nodes indexed on datum.key
        # 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 = {}
        try:
            self.active_dic[
                self.start_node_key] =\
                                       self.node_dic[self.start_node_key]
        except KeyError:
            return
        # check that end node is potentially reachable
        if self.end_node_key in self.node_dic:
            # try to find the path
            self.doit()

    def doit(self):
        success = False
        current_node_key = self.start_node_key
        current_node = self.active_dic[current_node_key]
        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_key = key
                    current_node = value
            if current_node is not None:
                # update distance for all its unvisited neighbours
                for neighbour_key in current_node.neighbours:
                    try:
                        neighbour_node = self.node_dic[neighbour_key]
                        if neighbour_node.unvisited:
                            # first visit so add it to active
                            self.active_dic[neighbour_node.key] = neighbour_node
                            distance = current_node.distance + 1
                            if distance < neighbour_node.distance:
                                neighbour_node.distance = distance
                                neighbour_node.predecessor = current_node_key
                    except KeyError:
                        pass
                # mark current_node visited and remove it from active_nodes
                current_node.unvisited = False
                del self.active_dic[current_node_key]
                if not self.node_dic[self.end_node_key].unvisited:
                    # we've arrived!
                    success = True
                    break
            else:
                # there is no path!
                break
        if success:
            # find path
            path = []
            current_end = self.end_node_key
            while True:
                path.append(current_end)
                if current_end == self.start_node_key:
                    break
                current_end = self.node_dic[current_end].predecessor
            path.reverse()
            self.path = path


class Polyomino(object):
    def __init__(self, shape_id, datums):
        self.shape_id = shape_id
        self.datum_dic = {}
        self.hole = False
        self.size = 0
        for datum in datums:
            self.datum_dic[datum.key] = datum
            if datum.guess is not None:
                self.size = datum.guess + 1
        if self.size == 0:
            self.size = len(datums)
            self.hole = True
        self.complete = False

    def is_hole(self):
        return self.hole

    def add(self, datum):
        self.datum_dic[datum.key] = datum

    def needed(self):
        #if self.hole:
        #    exit(1)
        return self.size - len(self.datum_dic)

    def filled(self):
        return len(self.datum_dic)

    def is_complete(self):
        if not self.hole:
            ret = self.complete
        else:
            ret = False
        return ret

    def update(self):
        """
        A datum in this polyomino has changed
        """
        # check for candidate reset
        self.complete = True
        for _, datum in list(self.datum_dic.items()):
            if datum.guess is None:
                self.complete = False
                # don't need to remove the datum: assign_shape_ids does that
                break
        for key, datum in list(self.datum_dic.items()):
            datum.complete = self.complete

    """
    def print_polyomino(self):
        print
        print self.shape_id
        for key, datum in list(self.datum_dic.items()):
            print key
    """


class Datum(object):
    """
    """
    def __init__(self, key, answer):
        self.shape_id = None
        self.key = key
        self.index = self.key
        self.func = None
        self.answer = None
        self.guess = None
        self.given = False
        self.neighbours = []
        self.shape_id = None
        self.hole_id = None
        self.complete = False
        self.internals = []
        self.unsolved = []
        self.solved = []
        self.colour = '#ffffff'
        self.tmp = None
        self.path = None
        if answer < 0:
            self.answer = -answer - 1
            self.given = True
            self.guess = self.answer
            self.candidates = set([])
        else:
            self.answer = answer - 1
            self.candidates = set(list(range(Sgg.symbol_count)))

    def add_callback(self, func):
        self.func = func

    def make_given(self):
        self.guess = self.answer
        self.given = True
        self.candidates = set([])

    def copy_guess(self):
        self.answer = self.guess

    def unset_guess(self):
        self.guess = None
        self.given = False
        self.set_colour()
        self.func(self.shape_id)

    def reset_guess(self):
        self.guess = None
        self.given = False
        self.candidates = set(list(range(Sgg.symbol_count)))
        self.set_colour()
        self.func(self.shape_id)

    def set_colour(self):
        if self.guess is not None:
            colour_index = self.guess
            self.colour = Sgg.COLOURS[colour_index]
        else:
            self.colour = '#ffffff'

    def set_answer(self):
        self.guess = self.answer
        self.candidates = set([])

    def is_consistent(self):
        """
        guess unset but no candidates left: bit 0
        guess set and candidate(s) True: bit 1
        guess != symbol_index: Error bit 2
        """
        error = 0
        if self.guess is None:
            if self.answer not in self.candidates:
                error = 1
        else:
            if self.candidates:
                error = 2

            if self.answer != self.guess:
                error += 4
        return error

    def del_candidate(self, candidate):
        """
        return guess if deleting last candidate
        """
        ret = -1
        if not self.given:
            if candidate in self.candidates:
                self.candidates.remove(candidate)
            if self.guess is None:
                if len(self.candidates) == 1:
                    candidate = self.candidates.pop()
                    self.set_guess(candidate)
                    ret = candidate
        return ret

    def add_candidate(self, candidate):
        ret = -1
        if not self.given:
            self.candidates.add(candidate)
            if self.guess is not None:
                ret = self.guess
                # next line 2017-06-13
                self.candidates.add(ret)
                self.guess = None
        return ret

    def other_candidates(self, candidate):
        return self.candidates.difference(candidate)

    def candidate_is_set(self, candidate):
        ret = False
        if candidate in self.candidates:
            ret = True
        return ret

    def set_guess(self, guess):
        self.guess = guess
        self.candidates = set()
        self.set_colour()

    def user_set_guess(self, guess):
        self.guess = guess
        self.candidates = set()
        self.set_colour()
        self.func(self.shape_id)

    def is_complete(self):
        return self.complete

    def solved_neighbours(self):
        """
        adjacent cells of different polyominos
        """
        self.solved = []
        for datum in self.neighbours:
            if datum is not None and datum.guess is not None\
               and datum.guess != self.guess:
                self.solved.append(datum)

    def internal_neighbours(self):
        """
        adjacent cells of same polyomino
        """
        self.internals = []
        for datum in self.neighbours:
            if datum is not None and datum.guess is not None\
               and datum.guess == self.guess:
                self.internals.append(datum)

    def unsolved_neighbours(self):
        """
        adjacent hole cells
        """
        self.unsolved = []
        for datum in self.neighbours:
            if datum is not None and datum.guess is None:
                self.unsolved.append(datum)

    def __str__(self):
        return '(%g %g %g)' % (self.key[0], self.key[1], self.shape_id)


class Model(object):

    def __init__(self, model_data):
        self.size_dic = {}
        self.polyomino_dic = {}
        self.grid_dic = {}
        self.model_data = model_data
        self.algorithm_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0]
        self.algorithm_scores = [1, 2, 3, 4, 5, 6, 7, 8, 9]
        self.algorithm = None
        self.hint_status = Sgg.GIVE_HINT
        self.difficulty = None
        self.status = True
        self.errors = []
        self.user_edits = UserEdits()
        self.editor = Editor(Sgg.HINT)
        self.saved_poly_keys = []

    """
    def print_puzzle(self):
        print Sgg.grid_width, Sgg.grid_height
        print 'solution'
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                key = (x, y)
                t = self.grid_dic[key].answer + 1,
                print "%3d" % t,
            print
        print

        ok = True
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                key = (x, y)
                t = self.grid_dic[key].shape_id
                if t is None:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            print 'solved_shape_id'
            for y in range(Sgg.grid_height):
                for x in range(Sgg.grid_width):
                    key = (x, y)
                    t = self.grid_dic[key].shape_id
                    print "%3d" % t,
                print

            print

        print 'guesses'
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                key = (x, y)
                t = 0
                if self.grid_dic[key].guess is not None:
                    t = self.grid_dic[key].guess + 1
                print "%3d" % t,
            print
        print
        print 'completed'
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                key = (x, y)
                t = 0
                if self.grid_dic[key].complete:
                    t = 1
                print "%3d" % t,
            print
        print
        ok = True
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                key = (x, y)
                t = self.grid_dic[key].shape_id
                if t is None:
                    ok = False
                    break
            if not ok:
                break
        if ok:
            print 'shape_id'
            for y in range(Sgg.grid_height):
                for x in range(Sgg.grid_width):
                    key = (x, y)
                    t = self.grid_dic[key].shape_id
                    print "%3d" % t,
                print

            print
    """

    def is_finished(self):
        if self.status:
            ret = True
            for _, polyomino in list(self.polyomino_dic.items()):
                if not polyomino.complete:
                    ret = False
                    break
            if ret:
                try:
                    holes = self.size_dic[0]
                    if self.size_dic[0]:
                        ret = False
                except KeyError:
                    pass
        else:
            ret = False
        return ret

    def add_datum_callback(self):
        for _, datum in list(self.grid_dic.items()):
            datum.add_callback(self.datum_callback)

    def datum_callback(self, shape_id):
        polyomino = self.polyomino_dic[shape_id]
        polyomino.update()

    def set_hint_status(self, status):
        self.hint_status = status

    def get_hint_status(self):
        return self.hint_status

    def zero_algorithm_counts(self):
        length = len(self.algorithm_counts)
        self.algorithm_counts = [0] * length

    def get_difficulty(self):
        difficulty = 0
        for i in range(len(self.algorithm_counts)):
            difficulty += self.algorithm_counts[i] * self.algorithm_scores[i]
        self.difficulty = difficulty

    def check_errors(self):
        self.status = True
        self.errors = []
        for key, datum in list(self.grid_dic.items()):
            status = datum.is_consistent()
            if status != 0:
                self.errors.append(key)
        if self.errors:
            self.status = False

    def set_neighbours(self):
        for key, datum in list(self.grid_dic.items()):
            datum.neighbours = self.get_neighbours(key)

    def get_neighbours(self, key):
        """
             0
            3X1
             2
        """
        def in_range(key):
            ret = True
            x = key[0]
            y = key[1]
            if x < 0 or x >= Sgg.grid_width or \
               y < 0 or y >= Sgg.grid_height:
                ret = False
            return ret

        neighbours = []
        x = key[0]
        y = key[1]

        neighbour_key = (x, y - 1)
        if in_range(neighbour_key):
            neighbour_datum = self.grid_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x + 1, y)
        if in_range(neighbour_key):
            neighbour_datum = self.grid_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x, y + 1)
        if in_range(neighbour_key):
            neighbour_datum = self.grid_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        neighbour_key = (x - 1, y)
        if in_range(neighbour_key):
            neighbour_datum = self.grid_dic[neighbour_key]
        else:
            neighbour_datum = None
        neighbours.append(neighbour_datum)

        return neighbours

    def show_solution(self):
        updates = []
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            key = (x, y)
            datum = self.grid_dic[key]
            datum.set_answer()
            datum.set_colour()
            updates.append([key, [1, [datum.guess]]])
        return updates

    def manage_edits(self, algorithm):
        """
        In order to use the same code to handle solving and
        providing hints, and to satisfy the requirement that
        exhaust must be applied before the algorithms
        will work we use manage_edits.
        """
        if self.editor.mode == Sgg.SOLVE:
            self.editor.apply()
            count = len(self.editor.changed_datum)

            if count > 0:
                self.algorithm_counts[algorithm] += count
        self.editor.reset()

    def apply_user_edits(self, datum_index, candidate, mouse_index):
        datum = self.grid_dic[datum_index]
        candidates = [candidate]
        if candidate is not None and not datum.given:
            # always start a new apply_ops
            self.user_edits.apply_ops = []
            if mouse_index == 1:
                apply_op = Egg.DELETE_CANDIDATES
                # if last but 1 candidate, this is also a set guess
                # so we need to know which candidates to delete
                if len(datum.candidates) == 2:
                    # its a set_guess too
                    candidates = list(datum.candidates)
                edit_pair = EditPair(datum, candidates)
                # do the edit
                guess = datum.del_candidate(candidate)
                if self.user_edits.edits or datum.is_consistent() != 0:
                    self.user_edits.add([edit_pair, apply_op])
                self.user_edits.add_op([edit_pair, apply_op])
                if guess != -1:
                    apply_op = Egg.SET_GUESS
                    edit_pair = EditPair(datum, [guess])
                    if self.user_edits.edits or datum.is_consistent() != 0:
                        self.user_edits.add([edit_pair, apply_op])
                    self.user_edits.add_op([edit_pair, apply_op])
            elif mouse_index == 2:
                # changed order of next lines 2017-06-13
                # so edit_pair includes guess
                guess = datum.add_candidate(candidate)
                apply_op = Egg.ADD_CANDIDATES
                # next 2 lines 2017-06-13
                if guess != -1 and guess != candidate:
                    candidates.append(guess)
                edit_pair = EditPair(datum, candidates)
                # do the edit
                if self.user_edits.edits or datum.is_consistent() != 0:
                    self.user_edits.add([edit_pair, apply_op])
                self.user_edits.add_op([edit_pair, apply_op])
                # added next line 2017-08-06
                self.user_edits.get_shading_ops(datum)
            elif mouse_index == 3:
                if datum.candidate_is_set(candidate):
                    # for display we need to delete the candidates first
                    del_candidates = list(datum.candidates)
                    apply_op = Egg.DELETE_CANDIDATES
                    edit_pair = EditPair(datum, del_candidates)
                    self.user_edits.add_op([edit_pair, apply_op])
                    # do the edit
                    datum.user_set_guess(candidate)
                    apply_op = Egg.SET_GUESS
                    edit_pair = EditPair(datum, [candidate])
                    if self.user_edits.edits or datum.is_consistent() != 0:
                        apply_op = Egg.DELETE_CANDIDATES
                        edit_pair = EditPair(datum, del_candidates)
                        self.user_edits.add([edit_pair, apply_op])
                        apply_op = Egg.SET_GUESS
                        edit_pair = EditPair(datum, [candidate])
                        self.user_edits.add([edit_pair, apply_op])
                    self.user_edits.add_op([edit_pair, apply_op])
                    # added next line 2017-07-31
                    self.user_edits.get_shading_ops(datum)
            self.is_polyomino_complete()

    def get_colour_ops(self):
        self.user_edits.get_colour_ops(self.errors)

    def get_uncolour_ops(self):
        self.user_edits.get_uncolour_ops(self.errors)

    def get_board_updates(self):
        for _, datum in list(self.grid_dic.items()):
            self.editor.get_update_ops(datum)
        return self.editor.update_ops

    def get_puzzle(self, puzzle_number):
        """
        """
        difficulty, puzzle = self.model_data.get_puzzle(puzzle_number)
        self.difficulty = difficulty
        self.grid_dic = {}
        item = -1
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            item += 1
            key = (x, y)
            self.grid_dic[key] = Datum(key, puzzle[item])
        self.set_neighbours()
        return

    def find_route_c(self, start_key, end_key, size):
        """
        Completed cells and cells of different guess and cells
        which do not contain the candidate size - 1
        are treated as obstacles and stuck in out of bounds oob_dic
        """
        def taxicab_distance(key_0, key_1):
            return int(abs(key_0[0] - key_1[0]) +
                       abs(key_0[1] - key_1[1]))

        ret = 999999
        if taxicab_distance(start_key, end_key) <= size:
            bs = size - 1
            oob_dic = {}
            for _, datum in list(self.grid_dic.items()):
                if datum.is_complete()\
                   or (datum.guess is not None and datum.guess != bs)\
                   or (datum.guess is None and bs not in datum.candidates):
                    oob_dic[datum] = True
            dijkstra = Dijkstra(self.grid_dic, start_key, end_key, oob_dic)
            self.path = dijkstra.path
            if self.path:
                ret = len(self.path) - 1
        return ret

    def set_singles_complete(self):
        """
        Any datum of size 1 is complete
        """
        try:
            datums_list = self.size_dic[1]
            for datums in datums_list:
                for datum in datums:
                    datum.complete = True
        except KeyError:
            pass

    def get_size_dic(self):
        """
        Make a list of every datum of each size based on guess,
        those with None in size[0].
        Then merge those with the same size which touch orthogonally
        to produce self.size_dic which consists of lists of touching
        datums indexed on size.
        """
        def is_touching(size_0, size_1):
            ret = False
            for item_0 in size_0:
                key_0 = item_0.key
                x_0 = key_0[0]
                y_0 = key_0[1]
                for item_1 in size_1:
                    key_1 = item_1.key
                    x_1 = key_1[0]
                    y_1 = key_1[1]
                    if x_0 == x_1:
                        if y_0 == y_1 - 1 or y_0 == y_1 + 1:
                            ret = True
                            break
                    elif y_0 == y_1:
                        if x_0 == x_1 - 1 or x_0 == x_1 + 1:
                            ret = True
                            break
                if ret:
                    break
            return ret
        size_dic = {}
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            key = (x, y)
            datum = self.grid_dic[key]
            guess = datum.guess
            if guess is None:
                # datum with no guess, so stick in size[0]
                try:
                    size_dic[0].append([datum])
                except KeyError:
                    size_dic[0] = [[datum]]
            else:
                try:
                    size_dic[guess + 1].append([datum])
                except KeyError:
                    size_dic[guess + 1] = [[datum]]

        # now merge
        for size, datums in list(size_dic.items()):
            progress = True
            while progress:
                progress = False
                size_count = len(datums)
                for i in range(size_count):
                    size_0 = datums[i]
                    for j in range(i + 1, size_count):
                        size_1 = datums[j]
                        if is_touching(size_0, size_1):
                            progress = True
                            tmp_sizes = [size_0 + size_1]
                            for k in range(size_count):
                                if k != i and k != j:
                                    tmp_sizes.append(datums[k])
                            datums = tmp_sizes
                            break
                    if progress:
                        break
            size_dic[size] = datums
        self.size_dic = size_dic

    def assign_shape_ids(self):
        """
        Use size_dic to assign shape_ids and create Polyominoes
        and note them in polyomino_dic.
        Then examine polyominoes to set complete to True
        for completed polyominoes and their datum.
        """
        self.polyomino_dic = {}
        shape_id = -1
        for _, datum_lists in list(self.size_dic.items()):
            for datums in datum_lists:
                shape_id += 1
                poly_list = []
                for datum in datums:
                    datum.shape_id = shape_id
                    poly_list.append(datum)
                poly = Polyomino(shape_id, poly_list)
                self.polyomino_dic[shape_id] = poly
        for shape_id, poly in list(self.polyomino_dic.items()):
            if not poly.is_complete() and poly.size == poly.filled():
                poly.complete = True
                if not poly.hole:
                    for key, datum in list(poly.datum_dic.items()):
                        datum.complete = True

    def is_polyomino_complete(self):
        """
        The problem is that for any polyomino the final hole cell
        that is filled is part of a hole polyomino, but the part
        of the polyomino that is already solved is stored as a
        separate polyomino. So, though we update the hole polyomino
        and mark it as complete we do not know the identity of
        the associated partially complete polyomino and so it does
        not get marked as complete. Most of the time this is handled
        by analyse_for_solver, but for the final moves it is not.
        So here we apply it to be sure!
        """
        self.check_errors()
        if self.status:
            self.analyse_for_solver()

    def analyse_neighbours(self):
        for _, datum in list(self.grid_dic.items()):
            if not datum.is_complete():
                datum.solved_neighbours()
                datum.unsolved_neighbours()
                datum.internal_neighbours()

    def analyse_for_solver(self):
        self.get_size_dic()
        self.analyse_neighbours()
        self.assign_shape_ids()

    def filter_on_neighbours(self):
        """
        filter candidates based on avoiding creating polyominos that
        are too large. For example:
         X
        X1X
         X

        2X
        X2

        3
        3
        X3

        X not same as solved cells

        The patterns of such arrangements are too numerous to
        encode individually so use find_route_c which uses Dijkstra
        to find a shortest route between polyominos while treating cells that
        don't contain the required candidate as obstacles
        """
        cause_pairs = []
        for size, datum_lists in list(self.size_dic.items()):
            if size == 1:
                for datum_list in datum_lists:
                    for datum in datum_list:
                        effect_pairs = []
                        for neighbour in datum.neighbours:
                            if neighbour is not None and\
                               0 in neighbour.candidates:
                                effect_candidates = [0]
                                effect_pair = EditPair(neighbour,
                                                       effect_candidates)
                                effect_pairs.append(effect_pair)
                        if effect_pairs:
                            self.editor.add([cause_pairs], effect_pairs,
                                            self.algorithm)
            elif size > 1:
                len_0 = len(datum_lists)
                for i_0 in range(len_0):
                    datum_list_i = datum_lists[i_0]
                    len_list_i = len(datum_list_i)
                    for datum_i in datum_list_i:
                        effect_pairs = []
                        for j_0 in range(i_0 + 1, len_0):
                            datum_list_j = datum_lists[j_0]
                            len_list_j = len(datum_list_j)
                            for datum_j in datum_list_j:
                                dist = self.find_route_c(datum_i.key,
                                                         datum_j.key, size)
                                if dist == 2 and\
                                   len_list_i + len_list_j >= size:
                                    neighbour = self.grid_dic[self.path[1]]
                                    effect_candidates = [size - 1]
                                    effect_pair = EditPair(neighbour,
                                                           effect_candidates)
                                    effect_pairs.append(effect_pair)
                        if effect_pairs:
                            self.editor.add([cause_pairs], effect_pairs,
                                            self.algorithm)

    def filter_on_finished(self):
        """
        When a polyomino is finished adjacent cells cannot have its value
        """
        finished_polyominos = []
        cause_pairs = []
        for _, polyomino in list(self.polyomino_dic.items()):
            if polyomino.is_complete():
                finished_polyominos.append(polyomino)
        for polyomino in finished_polyominos:
            size = polyomino.size - 1
            effect_pairs = []
            for _, datum in list(polyomino.datum_dic.items()):
                neighbours = datum.neighbours
                for neighbour in neighbours:
                    if neighbour is not None and\
                       size in neighbour.candidates:
                        effect_candidates = [size]
                        effect_pair = EditPair(neighbour,
                                               effect_candidates)
                        effect_pairs.append(effect_pair)
                        if effect_pairs:
                            self.editor.add([cause_pairs], effect_pairs,
                                            self.algorithm)

    def crawl(self, polyomino_in):
        """
        Find all the cells this polyomino could reach
        via holes and other polyominos of the same size.
        extra_potential is what is says.
        poly_ids is a set of all the other polyominoes of size size
        that polyomino_in can reach.
        hole_ids is a set of all the holes that polyomino_in can reach.
        adjacent_holes is a list of the holes which touch polyomino_in.
        multiple_exits is True if there are >1 polyominoes of size size
        touching the holes which touch polyomino_in.
        ie need to know if the polyomino touches only a single hole
        and if that hole touches more than 1 polyomino of the same size.
        Need to know if polyomino can expand in opposite directions.
        Need to know how many holes are in immediate contact with
        the polyomino.
        """
        potential_size = 0
        multiple_exits = False
        polyomino = polyomino_in
        hole_ids = set([])
        poly_ids = set([])
        poly_id = polyomino.shape_id
        size = polyomino.size - 1
        poly_ids.add(poly_id)
        datum_dic = polyomino.datum_dic
        new_hole_ids = self.hole_crawler(datum_dic, poly_ids, size)
        adjacent_holes = list(new_hole_ids)
        extra_holes = new_hole_ids - hole_ids
        loop = 0
        while extra_holes:
            loop += 1
            hole_ids = hole_ids | extra_holes
            # now look for touching polyominos of the same size
            new_poly_ids = set([])
            for hole_id in extra_holes:
                hole_ids.add(hole_id)
                new_poly_ids |= self.polyomino_crawler(hole_id,
                                                       poly_ids,
                                                       size)
            extra_polys = new_poly_ids - poly_ids
            if loop == 1 and len(new_poly_ids) > 1:
                multiple_exits = True
            extra_holes = set([])
            if extra_polys:
                poly_ids = poly_ids | extra_polys
                for extra_poly in extra_polys:
                    polyomino = self.polyomino_dic[extra_poly]
                    datum_dic = polyomino.datum_dic
                    new_hole_ids |= self.hole_crawler(datum_dic,\
                                                      poly_ids, size)
                extra_holes = new_hole_ids - hole_ids
        for n in poly_ids:
            p = self.polyomino_dic[n]
            potential_size += len(p.datum_dic)
        for n in hole_ids:
            p = self.polyomino_dic[n]
            potential_size += len(p.datum_dic)
        extra_potential = potential_size - len(polyomino_in.datum_dic)
        return extra_potential, poly_ids, hole_ids,\
            adjacent_holes, multiple_exits

    def hole_crawler(self, datum_dic, all_hole_ids, size):
        # find all the holes touching polyomino
        hole_ids = set([])
        for _, datum in list(datum_dic.items()):
            neighbours = datum.unsolved
            for neighbour in neighbours:
                if size in neighbour.candidates and\
                   neighbour.shape_id not in all_hole_ids:
                    hole_ids.add(neighbour.shape_id)
        return hole_ids

    def polyomino_crawler(self, hole_id, all_polyomino_ids, size):
        poly_ids = set([])
        # find all the different polyominos of size size touching this hole
        hole_poly = self.polyomino_dic[hole_id]
        for _, datum in list(hole_poly.datum_dic.items()):
            neighbours = datum.solved
            for neighbour in neighbours:
                if neighbour.guess == size\
                   and neighbour.shape_id not in all_polyomino_ids:
                    new_poly_id = neighbour.shape_id
                    poly_ids.add(new_poly_id)
        return poly_ids

    def flood_fill(self, key, old_char, new_char):
        # based on http://inventwithpython.com
        if old_char is None:
            old_char = self.grid_dic[key].tmp
        if self.grid_dic[key].tmp != old_char:
            return
        self.grid_dic[key].tmp = new_char
        x = key[0]
        y = key[1]
        if x > 0:
            key = x - 1, y
            self.flood_fill(key, old_char, new_char)
        if y > 0:
            key = x, y - 1
            self.flood_fill(key, old_char, new_char)
        if x < Sgg.grid_width - 1:
            key = x + 1, y
            self.flood_fill(key, old_char, new_char)
        if y < Sgg.grid_height - 1:
            key = x, y + 1
            self.flood_fill(key, old_char, new_char)

    def analyse_access(self, datum, size):
        """
        If any hole cell is accessible diagonally or in
        opposite directions we cannot know
        if extension is OK. If so return [].
        Also if a hole cell touches a polyomino of the same size
        if extension is OK. If so return [].
        Otherwise the accessibilty of the 4 neighbouring cells.
        """
        poss = [False, False, False, False]
        is_possible = False
        neighbours = datum.neighbours
        dir_index = 0
        for neighbour in neighbours:
            if neighbour is not None and neighbour.guess is None\
               and size in neighbour.candidates:
                poss[dir_index] = True
                is_possible = True
            dir_index += 1
        for neighbour in neighbours:
            if neighbour is not None and neighbour.guess == size\
               and datum.shape_id != neighbour.shape_id:
                is_possible = False
        if is_possible:
            if poss[0] and poss[1] or\
               poss[1] and poss[2] or\
               poss[2] and poss[3] or\
               poss[3] and poss[0] or\
               poss[3] and poss[1] or\
               poss[2] and poss[0]:
                is_possible = False
            if not is_possible:
                poss = []
        return poss

    def get_access_points(self, polyomino, adjacent_holes):
        access_points = set([])
        size = polyomino.size - 1
        for _, datum in list(polyomino.datum_dic.items()):
            neighbours = datum.unsolved
            for neighbour in neighbours:
                if neighbour.shape_id in adjacent_holes and\
                   size in neighbour.candidates:
                    access_points.add(neighbour.key)
        return access_points

    def do_ff(self, access_point, polyomino):
        """
        Use flood-fill like algorithm for measuring holes
        accessible from a single access point next to a polyomino.
        """
        route = set([])
        access_datum = self.grid_dic[access_point]
        size = polyomino.size - 1
        possible = self.analyse_access(access_datum, size)
        if possible:
            # linear or single extension direction open
            capacities = [0, 0, 0, 0]
            hole_id = access_datum.shape_id
            hole_poly = self.polyomino_dic[hole_id]
            directions = 0
            for direction in range(4):
                if possible[direction]:
                    start = access_datum.neighbours[direction]
                    for _, datum in list(self.grid_dic.items()):
                        datum.tmp = None
                    hole_dic = hole_poly.datum_dic
                    for key, datum in list(hole_dic.items()):
                        if size in datum.candidates:
                            datum.tmp = False
                    # block hole
                    access_datum.tmp = None
                    self.flood_fill(start.key, None, 2)
                    poly_id = polyomino.shape_id
                    capacity = 0
                    for key, datum in list(self.grid_dic.items()):
                        if datum.tmp == 2:
                            capacity += 1
                            neighbours = datum.neighbours
                            for neighbour in neighbours:
                                if neighbour is not None and\
                                   neighbour.guess == size and\
                                   neighbour.shape_id != poly_id:
                                    capacity = 999
                                    break
                            if capacity == 999:
                                break
                    capacities[direction] = capacity
                    directions += 1
            if directions == 2:
                needed = polyomino.needed()
                enough = False
                not_enough = False
                for direction in range(4):
                    if capacities[direction] < needed:
                        not_enough = True
                    elif capacities[direction] >= needed:
                        enough = True
                        route.add(access_datum.neighbours[direction].key)
            elif directions == 1:
                needed = polyomino.needed()
                enough = False
                not_enough = False
                for direction in range(4):
                    if capacities[direction] < needed:
                        not_enough = True
                    elif capacities[direction] >= needed:
                        enough = True
                        route.add(access_datum.neighbours[direction].key)
            elif directions > 2:
                route = set([11, 22, 33, 44])
        return route

    def polyomino_expand_11(self, polyomino):
        """
        Check this polyominos expansion possibilities
        """
        cause_pairs = []
        effect_pairs = []
        size = polyomino.size - 1
        extra_potential, poly_ids, hole_ids, adjacent_holes,\
            multiple_exits = self.crawl(polyomino)

        if extra_potential == polyomino.needed():
            # available space exactly matches what is needed
            guess = set([size])
            for hole_id in hole_ids:
                hole_poly = self.polyomino_dic[hole_id]
                for _, datum in list(hole_poly.datum_dic.items()):
                    effect_candidates = datum.other_candidates(guess)
                    effect_pair = EditPair(datum,
                                           effect_candidates)
                    effect_pairs.append(effect_pair)
                    # print 'case 0', datum.key

        if effect_pairs:
            self.editor.add([cause_pairs], effect_pairs,
                            self.algorithm)
        return

    def completes_poly(self, polyomino, poly_ids,
                       access_points):
        """
        If we fill one of the access points, will it complete
        the polyomino?
        """
        ret = []
        for access_point in access_points:
            datum = self.grid_dic[access_point]
            neighbours = datum.neighbours
            touching = set([])
            for neighbour in neighbours:
                if neighbour is not None and neighbour.shape_id in poly_ids:
                    if neighbour.shape_id not in touching:
                        touching.add(neighbour.shape_id)
            found = 0
            for toucher in touching:
                found += len(self.polyomino_dic[toucher].datum_dic)
            if found == polyomino.size - 1:
                ret = access_point
                break
        return ret

    def polyomino_expand_12(self, polyomino):
        """
        Check this polyominoes expansion possibilities.
        If it touches only 1 hole and through only one cell
        that cell must be part of the polyomino.
        If it touches only 1 hole and each contacting cell
        only contacts the hole via one side
        """
        cause_pairs = []
        effect_pairs = []
        needed = polyomino.needed()
        size = polyomino.size - 1
        extra_potential, poly_ids, hole_ids, adjacent_holes,\
            multiple_exits = self.crawl(polyomino)

        if len(adjacent_holes) == 1:
            # only 1 hole. How many access points from the polyomino?
            access_points = self.get_access_points(polyomino, adjacent_holes)
            if len(access_points) == 1:
                # only 1 way into this required hole!
                key = list(access_points)[0]
                datum = self.grid_dic[key]
                guess = set([size])
                effect_candidates = datum.other_candidates(guess)
                effect_pair = EditPair(datum,
                                       effect_candidates)
                effect_pairs.append(effect_pair)
                # print 'case 1', key
            else:
                # first make sure there is no diagonal access from the poly(s)
                diagonal_ok = True
                for key, datum in list(polyomino.datum_dic.items()):
                    possible = self.analyse_access(datum, size)
                    if not possible:
                        diagonal_ok = False
                        break
                if diagonal_ok and needed != 1:
                    # does this complete the polyomino?
                    res = self.completes_poly(polyomino, poly_ids,
                                              access_points)
                    if res:
                        # completes the polyomino
                        datum = self.grid_dic[res]
                        guess = set([polyomino.size - 1])
                        effect_candidates = datum.other_candidates(guess)
                        effect_pair = EditPair(datum,
                                               effect_candidates)
                        effect_pairs.append(effect_pair)
                        # print 'case 2', datum.key
                    else:
                        if len(access_points) == 2:
                            # two access points, but do they both
                            # need to pass through one cell to reach
                            # sufficient space?
                            routes = set([])
                            for ap in access_points:
                                route = self.do_ff(ap, polyomino)
                                if len(route) > 2:
                                    routes = route
                                    break
                                routes = routes  | route
                            routes = access_points.intersection(routes)
                            if len(routes) == 1:
                                datum = self.grid_dic[routes.pop()]
                                guess = set([polyomino.size - 1])
                                effect_candidates = datum.other_candidates(guess)
                                effect_pair = EditPair(datum,
                                                       effect_candidates)
                                effect_pairs.append(effect_pair)
                                # print 'case 3', datum.key

        if effect_pairs:
            self.editor.add([cause_pairs], effect_pairs,
                            self.algorithm)
        return

    def try_expansion_1(self):
        """
        Look for polyominos which must expand into a particular cell
        because of limited scope for expansion in any other direction
        """
        for _, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.is_complete() and not polyomino.is_hole():
                self.polyomino_expand_11(polyomino)
                if self.editor.got_data():
                    break

    def try_expansion_2(self):
        """
        Look for polyominos which must expand into a particular cell
        because of limited scope for expansion in any other direction
        """
        for _, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.is_complete() and not polyomino.is_hole():
                self.polyomino_expand_12(polyomino)
                if self.editor.got_data():
                    break

    def filter_holes(self):
        """
        Each datum need only contain the candidates for the unsolved
        polyominoes the surround the hole it is part of.
        """

        cause_pairs = []
        try:
            holes = self.size_dic[0]
        except KeyError:
            holes = []
        for hole in holes:
            effect_pairs = []
            # get the candidates for the surrounding unsolved polyominoes
            possible_candidates = set([])
            for datum in hole:
                for neighbour in datum.neighbours:
                    if neighbour is not None and\
                       neighbour.guess is not None:
                        poly_id = neighbour.shape_id
                        if not self.polyomino_dic[poly_id].complete:
                            possible_candidates.add(neighbour.guess)
            # now remove the others
            for datum in hole:
                effect_candidates = datum.other_candidates(possible_candidates)
                if effect_candidates:
                    effect_pair = EditPair(datum,
                                           effect_candidates)
                    effect_pairs.append(effect_pair)
            if effect_pairs:
                self.editor.add([cause_pairs], effect_pairs,
                                self.algorithm)

    def filter_on_distance(self):
        """
        Delete candidates that cannot be reached by
        an unfinished polyomino.
        """
        cause_pairs = []
        try:
            holes = self.size_dic[0]
        except KeyError:
            holes = []
        for hole in holes:
            poly_edge_dic = {}
            # which uninished polyominoes border this hole?
            for datum in hole:
                for neighbour in datum.neighbours:
                    if neighbour is not None and\
                       neighbour.guess is not None:
                        shape_id = neighbour.shape_id
                        polyomino = self.polyomino_dic[shape_id]
                        size = polyomino.size
                        if not polyomino.complete:
                            try:
                                poly_edge_dic[size].add(shape_id)
                            except KeyError:
                                poly_edge_dic[size] = set([shape_id])
            for datum in hole:
                keep = set([])
                effect_pairs = []
                for candidate in datum.candidates:
                    size = candidate + 1
                    shape_ids = poly_edge_dic[size]
                    for shape_id in shape_ids:
                        polyomino = self.polyomino_dic[shape_id]
                        datum_dic = polyomino.datum_dic
                        needed = polyomino.needed()
                        for key, _ in list(datum_dic.items()):
                            dist = self.find_route_c(key, datum.key, size)
                            if dist - needed < 1 or dist == 9999:
                                keep.add(candidate)
                effect_candidates = datum.other_candidates(keep)
                if effect_candidates:
                    effect_pair = EditPair(datum,
                                           effect_candidates)
                    effect_pairs.append(effect_pair)
                if effect_pairs:
                    self.editor.add([cause_pairs], effect_pairs,
                                    self.algorithm)
            if effect_pairs:
                return

    def solve_puzzle(self):
        ret = False
        self.editor.mode = Sgg.SOLVE
        self.editor.guess_set = True
        self.zero_algorithm_counts()
        self.difficulty = 0
        self.analyse_for_solver()
        progress = True
        while progress:
            progress = False
            self.check_errors()
            if self.errors:
                break
            if not self.is_finished():
                if not self.editor.got_data():
                    self.algorithm = 0
                    self.filter_holes()
                if not self.editor.got_data():
                    self.algorithm = 1
                    self.filter_on_neighbours()
                if not self.editor.got_data():
                    self.algorithm = 2
                    self.filter_on_finished()
                if not self.editor.got_data():
                    self.algorithm = 3
                    self.try_expansion_1()
                if not self.editor.got_data():
                    self.algorithm = 4
                    self.try_expansion_2()
                if not self.editor.got_data():
                    self.algorithm = 5
                    self.filter_on_distance()
                if self.editor.got_data():
                    progress = True
                    self.manage_edits(self.algorithm)
                    self.analyse_for_solver()
            else:
                break
        if self.is_finished():
            ret = True
            self.get_difficulty()
        return ret

    def do_hint(self):
        self.analyse_for_solver()
        self.editor.set_mode(Sgg.HINT)

        if not self.editor.got_data():
            self.algorithm = 0
            self.filter_holes()
        if not self.editor.got_data():
            self.algorithm = 1
            self.filter_on_neighbours()
        if not self.editor.got_data():
            self.algorithm = 2
            self.filter_on_finished()
        if not self.editor.got_data():
            self.algorithm = 3
            self.try_expansion_1()
        if not self.editor.got_data():
            self.algorithm = 4
            self.try_expansion_2()
        if not self.editor.got_data():
            self.algorithm = 5
            self.filter_on_distance()

    def apply_hint(self):
        if self.editor.got_data():
            for edit_pair in self.editor.effects:
                datum_index = edit_pair.datum.index
                candidates = edit_pair.candidates
                datum = self.grid_dic[datum_index]
                for candidate in candidates:
                    guess = datum.del_candidate(candidate)
            # check polyomino
            self.is_polyomino_complete()

    def ready_for_user(self):
        """
        We have a completed puzzle in self.grid_dic.
        Here we prepare it for the user.
        """
        self.get_size_dic()
        self.assign_shape_ids()
        for _, datum in list(self.grid_dic.items()):
            datum.set_colour()
        self.add_datum_callback()

###########################################################################
##############   generation ###############################################

    def packer(self, max_polyomino):

        def make_empty_grid():
            grid = {}
            for y, x in product(list(range(Sgg.grid_height)),
                                list(range(Sgg.grid_width))):
                grid[x, y] = 0
            return grid

        def next_start(grid):
            next_xy = None
            for y, x in product(list(range(Sgg.grid_height)),
                                list(range(Sgg.grid_width))):
                if grid[x, y] == 0:
                    next_xy = x, y
                    break
            return next_xy

        def complete(grid):
            ret = True
            for y, x in product(list(range(Sgg.grid_height)),
                                list(range(Sgg.grid_width))):
                if grid[x, y] == 0:
                    ret = False
                    break
            return ret

        def in_range(key):
            ret = True
            x = key[0]
            y = key[1]
            if x < 0 or x >= Sgg.grid_width or \
               y < 0 or y >= Sgg.grid_height:
                ret = False
            return ret

        def next_cell(grid, polyomino):
            """
            Choose the next cell adjacent to a previous cell
            and trying to make the polyomino irregular in shape.
            """
            def nbrs_ok(polyomino, nbr_0, nbr_1):
                ret = False
                if in_range(nbr_0) and nbr_0 not in polyomino\
                   and in_range(nbr_1) and nbr_1 not in polyomino:
                    ret = True
                return ret
            len_poly = len(polyomino) - 1
            next_key = ()
            reserve = ()
            while True:
                rand = randint(0, len_poly)
                key = polyomino[rand]
                x = key[0]
                y = key[1]
                # up
                y -= 1
                if in_range((x, y)) and grid[(x, y)] == 0:
                    reserve = (x, y)
                    nbr_0 = ((x - 1), y)
                    nbr_1 = ((x + 1), y)
                    if nbrs_ok(polyomino, nbr_0, nbr_1):
                        next_key = (x, y)
                        break
                # right
                x = key[0] + 1
                y = key[1]
                if in_range((x, y)) and grid[(x, y)] == 0:
                    reserve = (x, y)
                    nbr_0 = (x, (y - 1))
                    nbr_1 = (x, (y + 1))
                    if nbrs_ok(polyomino, nbr_0, nbr_1):
                        next_key = (x, y)
                        break
                # down
                x = key[0]
                y = key[1] + 1
                if in_range((x, y)) and grid[(x, y)] == 0:
                    reserve = (x, y)
                    nbr_0 = ((x - 1), y)
                    nbr_1 = ((x + 1), y)
                    if nbrs_ok(polyomino, nbr_0, nbr_1):
                        next_key = (x, y)
                        break
                # left
                x = key[0] - 1
                y = key[1]
                if in_range((x, y)) and grid[(x, y)] == 0:
                    reserve = (x, y)
                    nbr_0 = (x, (y - 1))
                    nbr_1 = (x, (y + 1))
                    if nbrs_ok(polyomino, nbr_0, nbr_1):
                        next_key = (x, y)
                        break
                break
            if not next_key:
                next_key = reserve
            return next_key

        grid = make_empty_grid()
        shape_id = 0
        polyominos = []
        while not complete(grid):
            shape_id += 1
            polyomino = []
            key = next_start(grid)
            grid[key] = shape_id
            polyomino.append(key)
            while True:
                key = next_cell(grid, polyomino)
                if key:
                    grid[key] = shape_id
                    polyomino.append(key)
                    if len(polyomino) == max_polyomino:
                        break
                else:
                    break
            polyominos.append(polyomino)
        return polyominos

    def filler(self, coords_list):
        # coords_list: list of polyominos coordinates written as lists
        ret = True
        self.polyomino_dic = {}
        shape_id = 0
        for coords in coords_list:
            datum_list = []
            value = -len(coords)
            for key in coords:
                datum = Datum(key, value)
                datum_list.append(datum)
            polyomino = Polyomino(shape_id, datum_list)
            self.polyomino_dic[shape_id] = polyomino
            shape_id += 1
        # create grid_dic
        self.grid_dic = {}
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            self.grid_dic.update(polyomino.datum_dic)
        self.set_neighbours()
        self.get_size_dic()
        for size, items in list(self.size_dic.items()):
            for item in items:
                if len(item) != size:
                    ret = False
                    break
            if not ret:
                break
        if ret:
            self.assign_shape_ids()
            self.add_datum_callback()
        return ret

    def check_1s(self):
        """
        Algorithm can place 1s next to single cell polyominos.
        Reject those cases here.
        """
        def get_nbr_values(datum):
            ret = set([])
            for neighbour_datum in datum.neighbours:
                guess = neighbour_datum.guess
                if guess is not None:
                    ret.add(guess)
            return ret

        ret = True
        for _, polyomino in list(self.polyomino_dic.items()):
            if polyomino.size == 1:
                datum_dic = polyomino.datum_dic
                for key, datum in list(datum_dic.items()):
                    nbr_values = get_nbr_values(datum)
                    if 1 in nbr_values:
                        ret = False
                        break
        return ret

    def filler_1(self):
        """
        Check that polyominoes of the same size do not touch.
        (there will be many!)
        """
        good = True
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            datum_dic = polyomino.datum_dic
            size = polyomino.size - 1
            for _, datum in list(datum_dic.items()):
                for neighbour in datum.neighbours:
                    if neighbour is not None and\
                       neighbour.shape_id != shape_id and\
                       neighbour.answer == size:
                        good = False
                        break
                if not good:
                    break
            if not good:
                break
        return good

    def prepare_for_harden(self):
        """
        Choose some clues to get harden started
        """
        frac = 0.4
        clue_count = int(frac * Sgg.grid_width * Sgg.grid_height)
        clue_keys = []
        self.reset_guesses()
        # start using 1 clue from each polyomino (in saved_poly_keys)
        for datum_list in self.saved_poly_keys:
            size = len(datum_list)
            item = randint(0, size - 1)
            key = datum_list[item]
            datum = self.grid_dic[key]
            clue_keys.append(key)
            datum.make_given()
        # now add until reach clue_count clues
        for _ in range(len(clue_keys), clue_count):
            key = self.next_key(clue_keys)
            clue_keys.append(key)
            self.grid_dic[key].make_given()
        return clue_keys

    def harden(self, max_clues, max_tries):
        """
        Have a grid of polyominos complete with answers.
        Unset guesses and then incrementally add clue keys
        until the grid can be solved. (start with 1 clue from each
        polyomino)
        Do this max_tries times and save the highest
        scoring arrangement as a puzzle.
        """
        answer_keys = []
        min_score = 0
        highest_score = -99
        # need to save the solution
        self.saved_poly_keys = []
        for _, polyomino in list(self.polyomino_dic.items()):
            datum_dic = polyomino.datum_dic
            items = []
            for key, datum in list(datum_dic.items()):
                items.append(key)
            self.saved_poly_keys.append(items)
        for _ in range(max_tries):
            clue_keys = self.prepare_for_harden()
            clue_count = len(clue_keys)
            while clue_count < max_clues:
                self.prepare_for_solver()
                if self.solve_puzzle():
                    # have chosen enough random clues and solved the grid
                    if self.difficulty > highest_score:
                        highest_score = self.difficulty
                        answer_keys = clue_keys
                    break
                elif self.status:
                    key = self.next_key(clue_keys)
                    clue_keys.append(key)
                    datum = self.grid_dic[key]
                    datum.make_given()
                    clue_count += 1
                else:
                    break
        if answer_keys:
            # final check!

            self.reset_guesses()
            for key in answer_keys:
                datum = self.grid_dic[key]
                datum.make_given()
            self.prepare_for_solver()
            if self.solve_puzzle():
                self.get_difficulty()
                if self.difficulty > min_score:
                    answer_keys = self.make_puzzle()
            else:
                answer_keys = []
        return answer_keys

    def make_puzzle(self):
        puzzle = [self.difficulty, Sgg.grid_width, Sgg.grid_height]
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            datum = self.grid_dic[x, y]
            value = datum.answer + 1
            if datum.given:
                puzzle.append(-1 * value)
            else:
                puzzle.append(value)
        return puzzle

    def next_key(self, clue_keys):
        while True:
            x = randint(0, Sgg.grid_width - 1)
            y = randint(0, Sgg.grid_height - 1)
            if (x, y) not in clue_keys and \
               self.grid_dic[(x, y)].guess is None:
                return (x, y)

    def prepare_for_solver(self):
        self.get_size_dic()
        self.assign_shape_ids()
        self.add_datum_callback()

    def do_givens(self, clues):
        for key in clues:
            datum = self.grid_dic[key]
            datum.make_given()
            polyomino = self.polyomino_dic[datum.shape_id]
            polyomino.add_given(key, datum.answer)

    def copy_guesses(self):
        for _, datum in list(self.grid_dic.items()):
            datum.copy_guess()

    def reset_guesses(self):
        for _, datum in list(self.grid_dic.items()):
            datum.reset_guess()

    def generate(self):

        puzzles = []
        min_puzzles = 2
        max_tries = 1000
        random.seed(3)
        """
        Sgg.grid_width = 6
        Sgg.grid_height = 6
        max_polyomino = 6
        Sgg.grid_width = 7
        Sgg.grid_height = 7
        max_polyomino = 7
        Sgg.grid_width = 8
        Sgg.grid_height = 8
        max_polyomino = 8
        Sgg.grid_width = 5
        Sgg.grid_height = 5
        max_polyomino = 5
        """
        Sgg.grid_width = 7
        Sgg.grid_height = 7
        max_polyomino = 7
        Sgg.symbol_count = max_polyomino
        frac = 0.55
        max_clues = int(frac * Sgg.grid_width * Sgg.grid_height)
        count = 0
        while True:
            count += 1
            coords_list = self.packer(max_polyomino)
            # coords_list: list of polyominos (x, y) written as lists
            good = False
            if self.filler(coords_list):
                good = self.filler_1()
            if good:
                self.copy_guesses()
                puzzle = self.harden(max_clues, max_tries)
                if puzzle:
                    puzzles.append(puzzle)
                    count = 0
                    if len(puzzles) >= min_puzzles:
                        puzzles = sorted(puzzles)
                        filename = str(Sgg.grid_width) +\
                                   'x' + str(Sgg.grid_height) + '.txt'
                        with open(filename, "w") as fo:
                            counter = 0
                            for puzzle in puzzles:
                                for item in puzzle:
                                    rec = ''
                                    rec += str(item)
                                    rec += ','
                                    counter += 1
                                    if counter % 20 == 0:
                                        rec += '\n'
                                    fo.write(rec)
                                if counter % 20 != 0:
                                    rec = '\n'
                                    fo.write(rec)
                                    counter = 0
                        # print 'Normal termination!'
                        exit(1)


class ModelData(object):
    """
    The built-in puzzles
    """
    def __init__(self):
        self.puzzle_count = 0
        self.puzzles = '\
 '
        self.puzzles = base64.b64decode(self.puzzles)
        self.puzzles = zlib.decompress(self.puzzles)
        self.make_puzzles()

    def make_puzzles(self):
        max_non_score = 19
        puzzles = []
        items = self.puzzles.decode('utf8').split(',')
        this_puzzle = []
        # items = self.puzzles
        for item in items:
            jtem = int(item)
            if jtem > max_non_score:
                # must be a difficulty value
                if this_puzzle:
                    puzzles.append(this_puzzle)
                    this_puzzle = []
            this_puzzle.append(jtem)
        if this_puzzle:
            puzzles.append(this_puzzle)
        self.puzzles = puzzles
        self.puzzle_count = len(self.puzzles)

    def get_puzzle(self, puzzle_index):
        if puzzle_index >= 0 and puzzle_index < self.puzzle_count:
            PzlG.logger.logger.info("puzzle_number " +
                                    str(puzzle_index))
            whole = self.puzzles[puzzle_index]
            difficulty = whole[0]
            Sgg.grid_width = whole[1]
            Sgg.grid_height = whole[2]
            # for our puzzles the max polyomino size == grid_width!
            Sgg.symbol_count = whole[2]
            puzzle = whole[3:]
            return difficulty, puzzle


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.user_edits = None
        self.view = View(root, self.settings)
        self.error_detected = False
        self.puzzle_number = None
        screen_shot_state = False
        self.coloured_squares = []
        self.screen_shot = ScreenShot(PzlG.app_name, 'dump_',
                                      screen_shot_state)
        self.puzzle_number = self.command_line()
        self.start_game(self.puzzle_number)

    def command_line(self):
        puzzle_number = None
        if len(sys.argv) > 1:
            try:
                puzzle_number = int(sys.argv[1])
            except ValueError:
                pass
        return 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):
        done = 0
        bad = []
        for puzzle_number in range(self.model_data.puzzle_count):
        # for puzzle_number in range(85):
            # print '***********************************', puzzle_number
            self.model = Model(self.model_data)
            self.model.get_puzzle(puzzle_number)
            """
            if not self.model.get_size_dic_t():
            bad.append(puzzle_number)
            else:
            done += 1
            """
            if not self.model.solve_puzzle():
                bad.append(puzzle_number)
            else:
                done += 1
        #print 'done', done, 'bad', bad, len(bad)
        exit(1)

    def rescore(self):
        bad = []
        done = 0
        puzzles = []
        for puzzle_number in range(self.model_data.puzzle_count):
            # print '*****************************', puzzle_number
            self.model = Model(self.model_data)
            self.model.get_puzzle(puzzle_number)

            done += 1
            if not self.model.solve_puzzle():
                bad.append(puzzle_number)
            else:
                puzzles.append(self.model.make_puzzle())
        # print 'done', done, 'bad', bad, len(bad)
        puzzles = sorted(puzzles)
        filename = 'nall_puzzles.txt'
        with open(filename, "w") as fo:
            counter = 0
            for puzzle in puzzles:
                for item in puzzle:
                    rec = ''
                    rec += str(item)
                    rec += ','
                    counter += 1
                    if counter % 20 == 0:
                        rec += '\n'
                    fo.write(rec)
                if counter % 20 != 0:
                    rec = '\n'
                    fo.write(rec)
                    counter = 0
        # print 'Normal termination!'
        exit(1)

    def start_game(self, puzzle_number):
        # self.test()
        # self.rescore()
        self.model = Model(self.model_data)
        # self.model.generate()
        self.set_puzzle_number(puzzle_number)
        self.view.clock_init()
        self.view.clock_restart()
        self.view.game_over()
        self.model.get_puzzle(self.puzzle_number)
        self.model.ready_for_user()
        self.ready_for_hint()
        self.view.thumbs_up()
        self.view.datum = self.model.grid_dic
        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.model.set_hint_status(Sgg.GIVE_HINT)
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)

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

    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 == '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 = self.model.editor.algorithm
            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:
                self.check_errors()
                if self.model.status and 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()
                    self.screen_shot.snap()

    def square_event(self, datum_index, candidate, mouse_index):
        """
        Respond to board clicks
        One of the three event servicing functions.
        Mouse index 1 == DELETE
                    2 == REWRITE
                    3 == SET GUESS
        candidate numbers at displayed values - 1
        """
        PzlG.logger.logger.info("square_event " +
                                str(mouse_index) +
                                ' ' +
                                str(datum_index) +
                                ' ' +
                                str(candidate))
        # if necessary abort an active hint
        board_updates = self.model.editor.abort_ops
        self.view.update_squares(board_updates)
        self.model.editor.reset()
        self.model.set_hint_status(Sgg.GIVE_HINT)
        self.model.apply_user_edits(datum_index,
                                    candidate,
                                    mouse_index)

        board_updates = self.model.user_edits.apply_ops
        self.view.update_squares(board_updates)
        # added next 2 lines 2017-08-06
        board_updates = self.model.user_edits.shading_ops
        self.view.update_squares(board_updates)
        self.check_finished()

    def ready_for_hint(self):
        if not self.model.is_finished():
            self.model.editor.reset()
            self.model.set_hint_status(Sgg.GIVE_HINT)
            if self.model.status:
                self.view.hint_off()
                self.view.thumbs_up()
                self.error_detected = False
            # turn on the clock
            self.view.clock.set_show(True)

    def give_hint(self):
        if self.model.get_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.editor.got_data():
                self.view.hint_on()
                board_updates = self.model.editor.show_ops
                self.view.update_squares(board_updates)
            self.view.update_clock_box(self.model.editor.algorithm)
            self.view.clock.set_show(False)
            self.model.set_hint_status(Sgg.APPLY_HINT)
        else:
            self.model.apply_hint()
            board_updates = self.model.editor.apply_ops
            self.view.update_squares(board_updates)
            self.ready_for_hint()
            self.check_finished()

    def check_errors(self):
        if self.error_detected:
            # may have deleted edits
            if self.model.user_edits.edits:
                # we know there's an error already, so now we correct it
                # switched order of next 2 lines 2017-07-31
                self.model.user_edits.undo()
                self.uncolour_errors()
                board_updates = self.model.user_edits.undo_ops
                self.view.update_squares(board_updates)
            self.model.user_edits.reset()
            self.model.check_errors()
            if not self.model.status:
                PzlG.logger.logger.error("check_errors ")
                exit(1)
            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 check_finished(self):
        """
        Check if finished.
        If so, handle buttons, flasher and clock
        """
        if self.model.is_finished():
            # next line added 2017-06-13
            self.show_solution()
            self.screen_shot.snap()
            self.flasher.flash()

    def show_solution(self):
        self.model.show_solution()
        board_updates = self.model.get_board_updates()
        self.view.update_squares(board_updates)
        self.view.hint_off()
        self.view.game_over()
        self.view.clock.set_show(True)
        self.view.clock_stop()

    def colour_errors(self):
        """
        Colour the error squares
        """
        self.model.get_colour_ops()
        board_updates = self.model.user_edits.show_error_ops
        self.view.update_squares(board_updates)

    def uncolour_errors(self):
        """
        Uncolour coloured squares
        """
        self.model.get_uncolour_ops()
        board_updates = self.model.user_edits.unshow_error_ops
        self.view.update_squares(board_updates)
        # added next 2 lines 2017-07-31
        board_updates = self.model.user_edits.shading_ops
        self.view.update_squares(board_updates)

    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")
