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

# Copyright (C) 2016 Rod Engerstad

import math
import random
from random import randint
from random import shuffle
from itertools import product
import colorsys
import tkinter as tk
import zlib
import base64

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 OpenFileI
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 = ['ER', 'FN', 'HS', 'NP',
                       'HP', 'NT', 'HT', 'FP', 'FT']


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_tooltip(self):
        self.tooltip_text = [
            _('Left-mouse random puzzle, right-mouse next puzzle'),
            _('Left mouse: give hint, right mouse: simple filter'),
            _('Check for errors, correct errors'),
            _('Show solution'),
            ]

    def make_alg_help(self):
        self.alg_text = [_("Exclusion rule: only one of each digit can occur in any polyomino, so once an answer is set all other occurrences of that digit in the same polyomino can be deleted."), _("Forbidden neighbour: adjacent digits cannot be identical (and adjacent includes diagonals); so once an answer is set, any occurences of that digit can be removed from adjacent cells."), _("Hidden single: all polyominos must contain exactly one of each of the digits; if a cell contains the only remaining copy of a digit in a polyomino, that digit must be the answer for that cell, and any other digits in that cell can be deleted."), _("Naked pairs: all polyominos must contain exactly one of each of the digits; if a pair of cells each contain only the same two digits those digits must be the answers for the two cells, and any other occurrences of those digits in the corresponding polyomino can be deleted."), _("Naked triples: all polyominos must contain exactly one of each of the digits; if a trio of cells each contain only the same three digits those digits must be the answers for the three cells, and any other occurrences of those digits in the corresponding polyomino can be deleted."), _("Hidden pairs: all polyominos must contain exactly one of each of the digits; if a pair of cells contain the only copies of two digits in a polyomino, those digits must be the answers for the two cells, and any other digits in those cells can be deleted."), _("Hidden triples: all polyominos must contain exactly one of each of the digits; if three cells contain the only copies of three digits in a polyomino, those digits must be the answers for the three cells, and any other digits in those cells can be deleted."), _("Forbidden pair: if a cell is touching a pair of cells from a neighbouring polyomino and they each only contain the same two digits, then those two digits must be the solution for those two cells and no touching cell can contain them."), _("Forbidden triple: if a cell is touching a trio of cells from a neighbouring polyomino and they each only contain the same three digits, then those three digits must be the solution for those three cells and no touching cell can contain them.")]

    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. If the player right-clicks on the hint button, the program will repeatedly apply a simple filter until it has no effect, clearing the candidates as it goes. Otherwise, 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 and the reasons in green. A further left click will delete the red candidates and unhighlight the green candidates. The program contains 1000 puzzles.")

    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(
            _('Save Puzzle'),
            '',
            '',
            '',
            'save_puzzle'
        ))
        self.menu_items.append(MenuItem(
            _('Load Puzzle'),
            '',
            '',
            '',
            'read_puzzle'
        ))
        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)
        bg = 'white'
        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
        self.grid(row=0, column=0)

    def my_destroy(self):
        self.destroy()

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

    def get_square_colour(self, square_index):
        return self.grid_dic[square_index].colour

    def update_square(self, update):
        """
        set some colours
        """
        operation = update.operation
        cell_id = update.cell_id
        #widget = self.grid_widgets[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_suguru, 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)

    def sg_open_file(self, write, title):
        """
        Use gui to open and file for reading or writing
        """
        self.entry_box.deactivate()
        init_dir = PzlG.app_saves
        filetypes = [('All files', '*')]
        this_file = OpenFileI(self, init_dir, filetypes, write, title)
        self.entry_box.activate()
        return this_file.my_file


class Polyomino(object):
    def __init__(self, shape_id, coords, givens):
        self.shape_id = shape_id
        self.datum_dic = {}
        self.givens_dic = {}
        self.size = len(coords)
        self.solved = False
        self.needed = set([])
        for item in givens:
            key = item[0]
            answer = item[1]
            self.givens_dic[key] = answer
        self.init_needed()
        if len(coords) == 1:
            # deal with polyominos of size 1
            coord = coords[0]
            answer = 1
            datum = Datum(shape_id, coord, answer, self.size)
            self.datum_dic[coord] = datum
            self.givens_dic[coord] = answer
            self.solved = True
        else:
            for coord in coords:
                try:
                    answer = self.givens_dic[coord]
                except KeyError:
                    answer = None
                datum = Datum(shape_id, coord, answer, self.size)
                self.datum_dic[coord] = datum

    def do_single(self):
        self.needed = set([])
        self.solved = True
        for key, datum in list(self.datum_dic.items()):
            datum.do_single()

    def init_needed(self):
        self.needed = set([])
        needed = list(range(self.size))
        self.needed = set(needed)
        for key, answer in list(self.givens_dic.items()):
            self.needed.discard(answer - 1)

    def update_needed(self):
        for key, datum in list(self.datum_dic.items()):
            if datum.guess is not None:
                self.needed.discard(datum.guess)
        if not self.needed:
            self.solved = True

    def set_guess(self, key, answer):
        self.datum_dic[key].set_guess(answer)
        self.datum_dic[key].candidates = set([])
        self.needed.discard(self.datum_dic[key].guess)
        if not self.needed:
            self.solved = True

    def add_given(self, key, answer):
        self.givens_dic[key] = answer


class Datum(object):
    """
    The solver sets guess.
    When the puzzle is solved we copy guess to answer.
    When generating puzzles we stick the generated values in guess.
    When the whole grid has generated values we copy them to answer
    and then set guesses to None so that the solver can again use
    guesses. We randomly reveal answers to use as givens by setting
    guess to answer.
    """
    def __init__(self, shape_id, key, answer, size):
        self.shape_id = shape_id
        self.key = key
        self.index = self.key
        self.func = None
        self.answer = None
        self.guess = None
        self.given = False
        self.neighbours = None
        self.size = size
        self.colour = 'green'
        candidates = list(range(self.size))
        self.candidates = set(candidates)
        if answer is not None:
            self.answer = answer - 1
            self.given = True
            self.guess = self.answer
            self.candidates = set([])

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

    def solved(self):
        ret = False
        if self.guess is not None:
            ret = True
        return ret

    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.func(self.shape_id)

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

    def set_colour(self, colour):
        self.colour = colour

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

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

    def do_single(self):
        #answer = 1
        answer = 0
        self.guess = answer
        self.given = True
        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
                self.func(self.shape_id)
        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.func(self.shape_id)

    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.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 = [0, 0, 3, 5, 6, 7, 8, 9, 10]
        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)

    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):
        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 - 1, y - 1)
        if in_range(neighbour_key):
            neighbour_datum = self.grid_dic[neighbour_key]
            neighbours.append(neighbour_datum)

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

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

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

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

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

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

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

        return neighbours

    """
    def print_grid(self):
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                if self.grid_dic[(x, y)].guess is None:
                    t = 0
                else:
                    t = self.grid_dic[(x, y)].guess
                print t,
            print
        print
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                t = self.grid_dic[(x, y)].shape_id
                print t,
            print
        print
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                datum = self.grid_dic[(x, y)]
                if datum.guess is None:
                    t = ""
                    for candidate in datum.candidates:
                        t += str(candidate)
                    for i in range(len(datum.candidates), 8, 1):
                        t += ' '
                else:
                    t = "   " + str(datum.guess) + "    "
                print t,
            print
        print
    """

    def set_guess(self, datum, guess):
        datum.set_guess(guess)

    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()
            updates.append([key, [1, [datum.guess]]])
        return updates

    def is_finished(self):
        if self.status:
            ret = True
            for shape_id, polyomino in list(self.polyomino_dic.items()):
                if not polyomino.solved:
                    ret = False
                    break
        else:
            ret = False
        return ret

    def add_datum_callback(self):
        for key, 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_needed()

    def forbidden_neighbour(self):
        """
        Prune candidates based on their neighbours
        """
        for key, datum in list(self.grid_dic.items()):
            guess = datum.guess
            if guess is not None:
                cause_candidates = [guess]
                cause_pairs = EditPair(datum, cause_candidates)
                effect_pairs = []
                neighbours = datum.neighbours
                for neighbour in neighbours:
                    if guess in neighbour.candidates:
                        effect_candidates = [guess]
                        effect_pair = EditPair(neighbour,
                                               effect_candidates)
                        effect_pairs.append(effect_pair)
                if effect_pairs:
                    self.editor.add([cause_pairs], effect_pairs,
                                    self.algorithm)

    def exclusion_rule(self):
        """
        If a polyomino has a guess set remove that guess from all
        the polyominos candidates.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for key_0, datum_0 in list(datum_dic.items()):
                    guess = datum_0.guess
                    if guess is not None:
                        cause_candidates = [guess]
                        cause_pairs = EditPair(datum_0, cause_candidates)
                        effect_pairs = []
                        for key_1, datum_1 in list(datum_dic.items()):
                            if key_1 != key_0:
                                candidates = datum_1.candidates
                                if guess in candidates:
                                    effect_candidates = [guess]
                                    effect_pair = EditPair(datum_1,
                                                           effect_candidates)
                                    effect_pairs.append(effect_pair)
                        if effect_pairs:
                            self.editor.add([cause_pairs], effect_pairs,
                                            self.algorithm)

    def hidden_single(self):
        """
        Find datum with unique candidate (hidden_single)
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for key_0, datum_0 in list(datum_dic.items()):
                    others = set([])
                    for key_1, datum_1 in list(datum_dic.items()):
                        if key_1 != key_0:
                            others = others.union(datum_1.candidates)
                    diff = datum_0.candidates.difference(others)
                    if len(diff) == 1:
                        effect_candidates = datum_0.candidates.difference(diff)
                        effect_pair = EditPair(datum_0,
                                               list(effect_candidates))
                        guess = diff.pop()
                        cause_candidates = [guess]
                        cause_pair = EditPair(datum_0,
                                              list(cause_candidates))
                        self.editor.add([cause_pair],
                                        [effect_pair],
                                        self.algorithm)

    def naked_effects(self, datum_dic, keys, cause_candidates,
                      cause_pairs):
        effect_pairs = []
        for key, datum in list(datum_dic.items()):
            if key not in keys:
                candidates = datum.candidates
                effect_candidates = cause_candidates.intersection(candidates)
                if effect_candidates:
                    effect_pair = EditPair(datum, list(effect_candidates))
                    effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def hidden_effects(self, diff, cause_keys,
                       cause_pairs):
        ret = False
        effect_pairs = []
        for key in cause_keys:
            datum = self.grid_dic[key]
            effect_candidates = list(datum.other_candidates(diff))
            if effect_candidates:
                effect_pair = EditPair(datum, list(effect_candidates))
                effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)
            ret = True
        return ret

    def naked_pair(self):
        """
        Find pair of datum, each with the same pair of candidates
        and no others.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic

                for item_0, item_1 in product(list(datum_dic.items()),
                                              list(datum_dic.items())):
                    if item_0 != item_1:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        if c_0 and c_1:
                            c_union = c_0.union(c_1)
                            if len(c_union) == 2:
                                candidates = list(c_union)
                                cp_0 = EditPair(datum_0, candidates)
                                cp_1 = EditPair(datum_1, candidates)
                                cause_pairs = [cp_0,
                                               cp_1]
                                self.naked_effects(datum_dic,
                                                   [key_0, key_1],
                                                   c_union,
                                                   cause_pairs)

    def naked_triple(self):
        """
        Find trio of datum, each with the same trio of candidates
        and no others.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic

                for item_0, item_1, item_2 in product(list(datum_dic.items()),
                                                      list(datum_dic.items()),
                                                      list(datum_dic.items())):
                    if item_0 != item_1 and \
                       item_0 != item_2 and \
                                 item_1 != item_2:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        key_2 = item_2[0]
                        datum_2 = item_2[1]
                        c_2 = datum_2.candidates
                        if c_0 and c_1 and c_2:
                            c_union = c_0.union(c_1.union(c_2))
                            if len(c_union) == 3:
                                candidates = list(c_union)
                                cp_0 = EditPair(datum_0, candidates)
                                cp_1 = EditPair(datum_1, candidates)
                                cp_2 = EditPair(datum_2, candidates)
                                cause_pairs = [cp_0,
                                               cp_1,
                                               cp_2]
                                self.naked_effects(datum_dic,
                                                   [key_0, key_1, key_2],
                                                   c_union,
                                                   cause_pairs)

    def hidden_pair(self):
        """
        Find pair of datum, each with the same pair of candidates
        which do not occur in any others in their polyomino
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for item_0, item_1 in product(list(datum_dic.items()),
                                              list(datum_dic.items())):
                    if item_0 != item_1:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        if c_0 and c_1:
                            c_union = c_0.union(c_1)
                            c_other = set([])
                            for key_3, datum_3 in list(datum_dic.items()):
                                if key_3 != key_0 and \
                                   key_3 != key_1:
                                    c_3 = datum_3.candidates
                                    c_other = c_other.union(c_3)
                            diff = c_union.difference(c_other)
                            if c_other and len(diff) == 2:
                                # there's 2 of them, so they are hidden pairs
                                # and all other candidates can be removed from
                                # their cells
                                cause_0 = EditPair(datum_0, diff)
                                cause_1 = EditPair(datum_1, diff)
                                causes = [cause_0, cause_1]
                                cause_keys = [key_0, key_1]
                                if self.hidden_effects(diff,
                                                       cause_keys,
                                                       causes):
                                    break

    def hidden_triple(self):
        """
        Find trio of datum, each with the same trio of candidates
        which do not occur in any others in their polyomino
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for item_0, item_1, item_2 in product(list(datum_dic.items()),
                                                      list(datum_dic.items()),
                                                      list(datum_dic.items())):
                    if item_0 != item_1 and \
                       item_0 != item_2 and \
                                 item_1 != item_2:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        key_2 = item_2[0]
                        datum_2 = item_2[1]
                        c_2 = datum_2.candidates
                        if c_0 and c_1 and c_2:
                            c_union = c_0.union(c_1.union(c_2))
                            c_other = set([])
                            for key_3, datum_3 in list(datum_dic.items()):
                                if key_3 != key_0 and \
                                   key_3 != key_1 and \
                                            key_3 != key_2:
                                    c_3 = datum_3.candidates
                                    c_other = c_other.union(c_3)
                            diff = c_union.difference(c_other)
                            if c_other and len(diff) == 3:
                                # there's 3 of them, so they are hidden triples
                                # and all other candidates can be removed from
                                # their cells
                                cause_0 = EditPair(datum_0, diff)
                                cause_1 = EditPair(datum_1, diff)
                                cause_2 = EditPair(datum_2, diff)
                                causes = [cause_0, cause_1, cause_2]
                                cause_keys = [key_0, key_1, key_2]
                                if self.hidden_effects(diff,
                                                       cause_keys,
                                                       causes):
                                    break

    def forbidden_pair(self):
        """
        Find pair of datum, each with the same pair of candidates
        and no others and which share neighbours outside a polyomino.
        Such neighbours may be restricted in their candidates.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for item_0, item_1 in product(list(datum_dic.items()),
                                       list(datum_dic.items())):
                    if item_0 != item_1:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        if c_0 and c_1:
                            # get cause candidates
                            cc = c_0.union(c_1)
                            if len(cc) == 2:
                                n_0 = set(datum_0.neighbours)
                                n_1 = set(datum_1.neighbours)
                                # get joint neighbours
                                jn = n_0.intersection(n_1)
                                if jn:
                                    # only want datum from other polyominos
                                    for key, datum in list(datum_dic.items()):
                                        if datum in jn:
                                            jn.remove(datum)
                                if jn:
                                    for e_datum in jn:
                                        e_cands = []
                                        tc = e_datum.candidates
                                        # get effected candidates
                                        if tc:
                                            e_cands = cc.intersection(tc)
                                        if e_cands:
                                            e_cands = list(e_cands)
                                            ccl = list(cc)
                                            cp_0 = EditPair(datum_0, ccl)
                                            cp_1 = EditPair(datum_1, ccl)
                                            cause_pairs = [cp_0, cp_1]
                                            effect_pair = EditPair(e_datum,
                                                                   e_cands)
                                            self.editor.add(cause_pairs,
                                                            [effect_pair],
                                                            self.algorithm)
                                            # to avoid repeats bail out
                                            # (we'll get others later)
                                            break

    def forbidden_triple(self):
        """
        Find trio of datum, each with the same trio of candidates
        and no others and which share neighbours outside a polyomino.
        Such neighbours may be restricted in their candidates.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for item_0, item_1, item_2 in product(list(datum_dic.items()),
                                                      list(datum_dic.items()),
                                                      list(datum_dic.items())):
                    if item_0 != item_1 and \
                       item_0 != item_2 and \
                                 item_1 != item_2:
                        key_0 = item_0[0]
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        key_1 = item_1[0]
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        key_2 = item_2[0]
                        datum_2 = item_2[1]
                        c_2 = datum_2.candidates
                        if c_0 and c_1 and c_2:
                            # get cause candidates
                            cc = c_0.union(c_1.union(c_2))
                            if len(cc) == 3:
                                n_0 = set(datum_0.neighbours)
                                n_1 = set(datum_1.neighbours)
                                n_2 = set(datum_2.neighbours)
                                # get joint neighbours
                                jn = n_0.intersection(n_1.intersection(n_2))
                                if jn:
                                    # only want datum from other polyominos
                                    for key, datum in list(datum_dic.items()):
                                        if datum in jn:
                                            jn.remove(datum)
                                if jn:
                                    for e_datum in jn:
                                        e_cands = []
                                        tc = e_datum.candidates
                                        # get effected candidates
                                        if tc:
                                            e_cands = cc.intersection(tc)
                                        if e_cands:
                                            e_cands = list(e_cands)
                                            ccl = list(cc)
                                            cp_0 = EditPair(datum_0, ccl)
                                            cp_1 = EditPair(datum_1, ccl)
                                            cp_2 = EditPair(datum_2, ccl)
                                            cause_pairs = [cp_0, cp_1, cp_2]
                                            effect_pair = EditPair(e_datum,
                                                                   e_cands)
                                            self.editor.add(cause_pairs,
                                                            [effect_pair],
                                                            self.algorithm)
                                            # to avoid repeats bail out
                                            # (we'll get others later)
                                            break

    def forbidden_quad(self):
        """
        Find quad of datum, each with the same quad of candidates
        and no others and which share neighbours outside a polyomino.
        Such neighbours may be restricted in their candidates.
        """
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                datum_dic = polyomino.datum_dic
                for item_0, item_1, item_2, item_3 in\
                    product(list(datum_dic.items()),
                            list(datum_dic.items()),
                            list(datum_dic.items()),
                            list(datum_dic.items())):
                    key_0 = item_0[0]
                    key_1 = item_1[0]
                    key_2 = item_2[0]
                    key_3 = item_3[0]
                    key_set = set([key_0, key_1, key_2, key_3])
                    if len(key_set) == 4:
                        datum_0 = item_0[1]
                        c_0 = datum_0.candidates
                        datum_1 = item_1[1]
                        c_1 = datum_1.candidates
                        datum_2 = item_2[1]
                        c_2 = datum_2.candidates
                        datum_3 = item_3[1]
                        c_3 = datum_3.candidates
                        if c_0 and c_1 and c_2 and c_3:
                            # get cause candidates
                            cc = c_0.union(c_1.union(c_2.union(c_3)))
                            if len(cc) == 4:
                                n_0 = set(datum_0.neighbours)
                                n_1 = set(datum_1.neighbours)
                                n_2 = set(datum_2.neighbours)
                                n_3 = set(datum_3.neighbours)
                                # get joint neighbours
                                jn = n_0 & n_1 & n_2 & n_3
                                if jn:
                                    # only want datum from other polyominos
                                    for key, datum in list(datum_dic.items()):
                                        if datum in jn:
                                            jn.remove(datum)
                                if jn:
                                    for e_datum in jn:
                                        e_cands = []
                                        tc = e_datum.candidates
                                        # get effected candidates
                                        if tc:
                                            e_cands = cc.intersection(tc)
                                        if e_cands:
                                            e_cands = list(e_cands)
                                            ccl = list(cc)
                                            cp_0 = EditPair(datum_0, ccl)
                                            cp_1 = EditPair(datum_1, ccl)
                                            cp_2 = EditPair(datum_2, ccl)
                                            cp_3 = EditPair(datum_3, ccl)
                                            cause_pairs = [cp_0, cp_1, cp_2, cp_3]
                                            effect_pair = EditPair(e_datum,
                                                                   e_cands)
                                            self.editor.add(cause_pairs,
                                                            [effect_pair],
                                                            self.algorithm)
                                            # to avoid repeats bail out
                                            # (we'll get others later)
                                            break

    def do_hint(self):
        self.editor.set_mode(Sgg.HINT)
        self.algorithm = 0
        self.exclusion_rule()
        if not self.editor.got_data():
            self.algorithm = 1
            self.forbidden_neighbour()
        if not self.editor.got_data():
            self.algorithm = 2
            self.hidden_single()
        if not self.editor.got_data():
            self.algorithm = 3
            self.naked_pair()
        if not self.editor.got_data():
            self.algorithm = 4
            self.hidden_pair()
        if not self.editor.got_data():
            self.algorithm = 5
            self.naked_triple()
        if not self.editor.got_data():
            self.algorithm = 6
            self.hidden_triple()
        if not self.editor.got_data():
            self.algorithm = 7
            self.forbidden_pair()
        if not self.editor.got_data():
            self.algorithm = 8
            self.forbidden_triple()

    def exhaust(self):
        progress = False
        sf_progress = False
        if self.editor.guess_set:
            sf_progress = True
            while sf_progress:
                sf_progress = False
                self.algorithm = 0
                self.exclusion_rule()

                if not self.editor.got_data():
                    self.algorithm = 1
                    self.forbidden_neighbour()
                if self.editor.got_data():
                    progress = True
                    sf_progress = True
                    self.manage_edits(self.algorithm)
        self.editor.guess_set = False
        return progress

    def exhaust_puzzle(self):
        self.check_errors()
        if self.status:
            self.editor.set_mode(Sgg.SOLVE)
            self.editor.guess_set = True
            self.exhaust()
            self.editor.set_mode(Sgg.HINT)

    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 solve_puzzle(self):
        ret = False
        self.editor.mode = Sgg.SOLVE
        self.editor.guess_set = True
        self.zero_algorithm_counts()
        self.difficulty = 0
        sf_progress = True
        while sf_progress:
            sf_progress = self.exhaust()
            if not self.is_finished():
                self.algorithm = 2
                self.hidden_single()
                if not self.editor.got_data():
                    self.algorithm = 3
                    self.naked_pair()
                if not self.editor.got_data():
                    self.algorithm = 4
                    self.hidden_pair()
                if not self.editor.got_data():
                    self.algorithm = 5
                    self.naked_triple()
                if not self.editor.got_data():
                    self.algorithm = 6
                    self.hidden_triple()
                if not self.editor.got_data():
                    self.algorithm = 7
                    self.forbidden_pair()
                if not self.editor.got_data():
                    self.algorithm = 8
                    self.forbidden_triple()
                if self.editor.got_data():
                    sf_progress = True
                    self.manage_edits(self.algorithm)
            else:
                break
        if self.is_finished():
            ret = True
            self.get_difficulty()
        return ret

    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)

    def apply_user_edits(self, datum_index, candidate, mouse_index):
        datum = self.grid_dic[datum_index]
        #datum = self.datum[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])
            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.set_guess(candidate, False)
                    datum.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])

    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 key, datum in list(self.grid_dic.items()):
            self.editor.get_update_ops(datum)
        return self.editor.update_ops

    def packer(self, max_polyomino):

        """
        def print_grid(grid):
            for y in range(Sgg.grid_height):
                for x in range(Sgg.grid_width):
                    t = grid[x, y]
                    print t,
                print
            print
        """

        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
        self.polyomino_dic = {}
        shape_id = 1
        # deal with single cell polyominos first
        for coords in coords_list:
            if len(coords) == 1:
                givens = [[coords[0], 1]]
                polyomino = Polyomino(shape_id, coords, givens)
                polyomino.solved = True
                self.polyomino_dic[shape_id] = polyomino
                shape_id += 1
        done_first = False
        for coords in coords_list:
            if len(coords) != 1:
                if not done_first:
                    # assign values to first multicelled polyomino
                    values = list(range(1, len(coords) + 1))
                    shuffle(values)
                    givens = []
                    for item in range(len(coords)):
                        given = [coords[item], values[item]]
                        givens.append(given)
                    polyomino = Polyomino(shape_id, coords, givens)
                    polyomino.solved = True
                    self.polyomino_dic[shape_id] = polyomino
                    shape_id += 1
                    done_first = True
                else:
                    # here do the rest
                    # first we initialise their polyominos with zero givens
                    # so that needed has all possible values for its size
                    givens = []
                    polyomino = Polyomino(shape_id, coords, givens)
                    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)

    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 shape_id, 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):
        """
        We've filled in all single celled polyominos and 1 multicelled.
        Here we try to fill the rest of the polyominos with values so
        that no identical values touch. Only "strategy" is for each
        polyomino to deal with the most limited datum first. As soon
        as we fail to find a value for a datum we bail out and the caller
        must generate a new arrangement of polyominos.
        """
        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

        # add neighbours to each datum
        self.set_neighbours()
        good = True
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if polyomino.size == 1:
                polyomino.do_single()
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            if not polyomino.solved:
                needed = polyomino.needed
                datum_dic = polyomino.datum_dic
                oks = []
                for key, datum in list(datum_dic.items()):
                    if not datum.solved():
                        # for each datum get a list of its possible answers
                        nbr_values = get_nbr_values(datum)
                        ok = [x for x in needed if x not in nbr_values]
                        oks.append((set(ok), key))
                # sort so we deal with fewest choices first
                oks.sort(key=lambda s: len(s[0]))
                # start a list of the values used so far
                used = []
                for item in oks:
                    key = item[1]
                    values = item[0]
                    while True:
                        try:
                            value = values.pop()
                            if value not in used:
                                # got an unused value, so use it
                                break
                        except KeyError:
                            # no possible answer for this datum so give up
                            good = False
                            break
                    if not good:
                        break
                    # set current value as answer
                    used.append(value)
                    polyomino.set_guess(key, value)
            if not good:
                # no solution found
                break
        if good:
            good = self.check_1s()
        return good

    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 do_polyominos(self):
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            polyomino.givens_dic = {}
            polyomino.solved = False
            datum_dic = polyomino.datum_dic
            # do the polyominos of size 1
            if len(datum_dic) == 1:
                for key, datum in list(datum_dic.items()):
                    polyomino.do_single()

    def prepare_for_solver(self, clues):
        self.reset_guesses()
        self.do_polyominos()
        self.do_givens(clues)
        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)

        for shape_id, polyomino in list(self.polyomino_dic.items()):
            polyomino.init_needed()

    def make_puzzle(self, clues, difficulty):
        self.reset_guesses()
        self.do_givens(clues)
        puzzle = []
        puzzle.append(difficulty)
        puzzle.append(Sgg.grid_width)
        puzzle.append(Sgg.grid_height)
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                t = self.grid_dic[(x, y)].shape_id
                puzzle.append(t)
        for y in range(Sgg.grid_height):
            for x in range(Sgg.grid_width):
                if self.grid_dic[(x, y)].guess is None:
                    t = 0
                else:
                    t = self.grid_dic[(x, y)].guess
                puzzle.append(t)
        return puzzle

    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.
        Do this max_tries times and save the highest
        scoring arrangement as a puzzle.
        """
        answer_keys = []
        min_score = 20
        highest_score = 20
        for tries in range(max_tries):
            self.prepare_for_harden()
            clue_keys = []
            clue_count = 0
            while clue_count < max_clues:
                clue_count += 1
                self.prepare_for_solver(clue_keys)
                key = self.next_key(clue_keys)
                clue_keys.append(key)
                if self.solve_puzzle():
                    # have chosen enough random clues and solved the grid
                    # if highest score, save it
                    if self.difficulty > highest_score:
                        highest_score = self.difficulty
                        answer_keys = clue_keys
                    # force break from loop
                    clue_count = max_clues
        #print 'FINISHED', tries, answer_keys
        if answer_keys:
            # final check!
            self.prepare_for_solver(answer_keys)
            if self.solve_puzzle() and self.difficulty > min_score:
                answer_keys = self.make_puzzle(answer_keys,
                                               self.difficulty)
            else:
                answer_keys = []
        return answer_keys

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

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

    def prepare_for_harden(self):
        self.add_datum_callback()
        self.reset_guesses()
        for shape_id, polyomino in list(self.polyomino_dic.items()):
            polyomino.givens_dic = {}
            polyomino.solved = False
            datum_dic = polyomino.datum_dic
            # solve the polyominos of size 1
            if len(datum_dic) == 1:
                polyomino.solved = True

    def generate(self):

        """
        def print_shape(grid):
            for y in range(Sgg.grid_height):
                for x in range(Sgg.grid_width):
                    t = grid[x, y]
                    print t,
                print
            print
        """

        # print 'Fiddled with the candidate and shape_id
        # values since writing this so it may not work!'
        puzzles = []
        min_puzzles = 1000
        max_tries = 1000
        random.seed(0)
        Sgg.grid_width = 6
        Sgg.grid_height = 6
        max_polyomino = 5
        max_clues = 3 * int(math.sqrt(Sgg.grid_width * Sgg.grid_height))
        count = 0
        good_count = 0
        while True:
            count += 1
            coords_list = self.packer(max_polyomino)
            # coords_list: list of polyominos (x, y) written as lists
            self.filler(coords_list)
            good = self.filler_1()
            if good:
                good_count += 1
                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)

    def get_puzzle(self, puzzle_number):
        """
        Puzzles are stored as two separate grids of
        size Sgg.grid_width * Sgg.grid_height.
        The first contains the polyominos defined by cells
        with the same number, so that polyomino 1 is defined
        by a cluster of cells denoted by 1s, polyomino 2
        by a cluster of 2s, and so on. The next grid
        contains the clues: all non-zero entries are clues.
        So we don't store the solution and have to solve each
        puzzle as it is requested by the user.
        """
        puzzle = self.model_data.get_puzzle(puzzle_number)
        shapes = puzzle[0:]
        answers = puzzle[Sgg.grid_width * Sgg.grid_height:]
        rev_shape_dic = {}
        shape_dic = {}
        item = -1
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            item += 1
            shape_id = shapes[item]

            rev_shape_dic[(x, y)] = shape_id
            try:
                shape = shape_dic[shape_id]
                shape.append((x, y))
            except KeyError:
                shape = [(x, y)]
                shape_dic[shape_id] = shape

        givens_dic = {}
        item = -1
        for y, x in product(list(range(Sgg.grid_height)),
                            list(range(Sgg.grid_width))):
            item += 1
            answer = answers[item]
            if answer != 0:
                shape_id = rev_shape_dic[(x, y)]
                given = ((x, y), answer)
                try:
                    givens = givens_dic[shape_id].append(given)
                except KeyError:
                    givens = [given]
                    givens_dic[shape_id] = givens
        polyominos = []
        for shape_id, coords in list(shape_dic.items()):
            try:
                givens = givens_dic[shape_id]
            except KeyError:
                givens = []
            polyomino = Polyomino(shape_id, coords, givens)
            polyominos.append(polyomino)

        self.grid_dic = {}
        for polyomino in polyominos:
            self.grid_dic.update(polyomino.datum_dic)
            self.polyomino_dic[polyomino.shape_id] = polyomino
        self.set_neighbours()
        self.add_datum_callback()

    def ready_for_user(self):
        """
        We have a completed puzzle in self.datum_dic.
        Here we prepare it for the user.
        """

        def to_hex(int_input):
            symbols = '0123456789abcdef'
            sym_1 = int(int_input / 16)
            sym_2 = int_input % 16
            return symbols[sym_1] + symbols[sym_2]

        def get_n_colours(n_colours):
            """
            Get n_colours colours evenly spaced over the full spectrum
            """
            HSV_tuples = [(x * 1.0 / n_colours, 0.5, 1.0)
                          for x in range(n_colours)]
            hex_out = []
            for rgb in HSV_tuples:
                rgb = [int(x*255) for x in colorsys.hsv_to_rgb(*rgb)]
                myhex = '#' + ("".join([to_hex(x) for x in rgb]))
                hex_out.append(myhex)
            return hex_out

        clue_count = len(self.polyomino_dic)
        self.copy_guesses()
        for key, datum in list(self.grid_dic.items()):
            if not datum.given:
                datum.reset_guess()
        colours = get_n_colours(clue_count)
        shuffle(colours)

        for key, datum in list(self.grid_dic.items()):
            shape_id = datum.shape_id
            colour = colours[shape_id - 1]
            datum.set_colour(colour)

        for shape_id, polyomino in list(self.polyomino_dic.items()):
            polyomino.needed = set(list(range(polyomino.size)))
            if polyomino.size != 1:
                polyomino.solved = False


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 = []
        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):
        puzzle = []
        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]
            puzzle = whole[3:]
        return 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.active = False
        self.coloured_squares = []
        self.screen_shot = ScreenShot(PzlG.app_name, 'dump_',
                                      screen_shot_state)
        self.start_game(None)

    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):
            self.model = Model(self.model_data)
            self.model.get_puzzle(puzzle_number)
            if not self.model.solve_puzzle() or self.model.difficulty < 1:
                bad.append(puzzle_number)
            done += 1
            #print puzzle_number, self.model.difficulty
        #print 'done', done, 'bad', bad, len(bad)
        exit(1)

    def start_game(self, puzzle_number):
        #self.test()
        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)
        # we don't store the solution for built-in puzzles!
        # so get it now using the solver
        self.model.solve_puzzle()
        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.active = True
        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_puzzle':
            self.save_puzzle()
        elif name == 'read_puzzle':
            self.read_puzzle()
        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 == 1:
                if self.model.status:
                    self.model.check_errors()
                    if self.model.status and not self.model.is_finished():
                        if self.model.get_hint_status() != Sgg.APPLY_HINT:
                            if button_index == 1:
                                self.exhaust()
            elif 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
        """
        if self.active:
            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)
            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
                self.uncolour_errors()
                self.model.user_edits.undo()
                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.active:
            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()
        self.active = False

    def exhaust(self):
        """
        Apply simple_filter_exhaustively
        """
        self.model.exhaust_puzzle()
        # now update the view
        board_updates = self.model.get_board_updates()
        self.view.update_squares(board_updates)
        self.screen_shot.snap()
        self.check_finished()

    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)

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

    def save_puzzle(self):
        my_file = self.view.sg_open_file(True, _('Output file'))
        if my_file:
            grid_dic = self.model.grid_dic
            rec = str(self.puzzle_number) + '\n'
            my_file.write(rec)
            for key, datum in list(grid_dic.items()):
                if not datum.candidates:
                    cands = [datum.guess]
                else:
                    cands = list(datum.candidates)
                rec = ''
                rec += str(key[0]) + ','
                rec += str(key[1]) + ','
                for cand in cands:
                    rec += str(cand) + ','
                rec = rec[:-1]
                rec += '\n'
                my_file.write(rec)
            my_file.close()

    def read_puzzle(self):
        file_good = False
        my_file = self.view.sg_open_file(False, _('Input file'))
        if my_file:
            file_good = True
            grid_dic = {}
            self.active = False
            self.view.game_over()
            self.view.entry_box.deactivate()
            self.view.update()
            lines = my_file.read().splitlines()
            try:
                puzzle_number = int(lines[0])
            except ValueError:
                file_good = False
            if file_good:
                lines = lines[1:]
                for line in lines:
                    items = line.split(',')
                    if len(items) < 3 or len(items) > 8:
                        file_good = False
                        break
                    try:
                        key0 = int(items[0])
                    except KeyError:
                        file_good = False
                        break
                    try:
                        key1 = int(items[1])
                    except KeyError:
                        file_good = False
                        break
                    cands = set([])
                    for cand in range(2, len(items)):
                        try:
                            icand = int(items[cand])
                        except KeyError:
                            file_good = False
                            break
                        cands.add(icand)
                    if not file_good:
                        break
                    grid_dic[key0, key1] = cands
                if file_good:
                    self.model = Model(self.model_data)
                    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)
                    # we don't store the solution for built-in puzzles!
                    # so get it now using the solver
                    self.model.solve_puzzle()
                    if not self.model.status:
                        file_good = False
                    else:
                        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.active = True
                        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)
                        self.make_edits(grid_dic)
                        self.fix_problems()
        if not file_good:
            self.start_game(None)

    def make_edits(self, grid_dic):
        """
        grid_dic contains the puzzle state we want to achieve
        so create the corresponding edits.
        """
        mouse_index = 1
        for key, cands in list(grid_dic.items()):
            datum = self.model.grid_dic[key]
            del_cands = set(range(datum.size)).difference(cands)
            for candidate in del_cands:
                self.square_event(key, candidate, mouse_index)

    def fix_problems(self):
        """
        Check each datum and if inconsistent reset guess
        and all its candidates
        """
        for key, datum in list(self.model.grid_dic.items()):
            if datum.is_consistent():
                datum.candidates = set(range(datum.size))
                for candidate in datum.candidates:
                    self.square_event(key, candidate, 2)


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