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

# Copyright (C) 2021 Rod Engerstad

import random
from random import randint
from random import shuffle
import Tkinter as tk
import colorsys

from targets_data import ModelData
from pzl_lib import PzlG
from pzl_lib import SettingsB
from pzl_lib import Preferences
from pzl_lib import MenuItem
from pzl_lib import Flasher
from pzl_lib import ViewB
from pzl_lib import GreyScales
from pzl_lib import TextSquare


class Sgg(object):
    size = None
    GIVE_HINT = 0
    APPLY_HINT = 1
    TARGET = 'O'
    DASH = '-'
    UNSET = '.'
    alg_scores = [1, 1, 1, 1, 1, 2, 2, 4, 3]
    alg_counts = [0 for i in range(len(alg_scores))]


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.dic = {}
        self.dic['font_size'] = '3'
        self.dic['text_colour'] = 'black'
        self.dic['Autofill_s'] = 'Off'
        self.dic['Autofill_p'] = 'Off'
        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'), _('Give hint, Apply hint'), _('Check for errors, correct errors'), _('Show solution')]

    def make_alg_help(self):
        self.alg_text = [_("Algorithm 0: This cell is in a polyomino with a set Target and so cannot be a Target."), _("Algorithm_1: This cell is in a strip with a set Target and so cannot be a Target."), _("Algorithm_2: All other cells in the polyomino have been ruled out so this one is the Target."), _("Algorithm_3: This cell is touched by a Target cell and so cannot be a Target."), _("Algorithm_4: This cell is the last one in a strip and so must be a Target."), _("Algorithm_5: This cell is in a polyomino which provides all the cells for a different strip and so cannot be a Target."), _("Algorithm_6: A polyomino only has cells in one strip so must provide its Target. This cell is from a different polyomino in the strip and so cannot be a Target."), _("Algorithm_7: A group of polyominoes lie entirely in a set of adjacent strips. These strips can only contain their Targets, and cells from other polyominoes cannot be Targets."), _("Algorithm_8: This cell touches or blocks all the cells in a different polyomino and so cannot be a Target.")]

    def make_help(self):
        self.help_text = _("A completed puzzle has a Target (O) in every row, column and polyomino. Targets cannot touch orthogonally or diagonally. The aim is to find the Targets. A right click sets a Target (O). A left click sets a Dash (-) to rule out a Target. Middle mouse deletes either. The jigsaw puzzle icon contains a menu used for configuring the program. A left click on the next icon to the right selects a random puzzle, a right click the next puzzle in sequence. The wand requests a hint, a second click on the wand will perform the hint operation. The thumb checks if the puzzle contains errors and a second click will clear any errors. The sad smiley shows the solution. The entrybox shows the current puzzle number and can be used to select a new puzzle number. There are 1000 built-in puzzles, 200 each of sizes 5, 6, 7, 8, 9. The number to the right of the puzzle number is the difficulty rating of the puzzle, and to its right a clock.  When a hint is requested its algorithm number will replace the clock and middle mouse on the wand icon will summarise the algorithm. The menu can be used to switch on and off two autofill functions and to set the font size. Autofill strip places dashes thoughout the row and column when a Target is set. Autofill polyomino places dashes in the rest of a polyomino when its Target is set.")

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Autofill strips'),
            [_('On'), _('Off')],
            '',
            ['On', 'Off'],
            'Autofill_s'
        ))
        self.menu_items.append(MenuItem(
            _('Autofill polyominoes'),
            [_('On'), _('Off')],
            '',
            ['On', 'Off'],
            'Autofill_p'
        ))
        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, model):
        self.settings = settings
        self.model = model
        grid_dic = model.grid_dic
        self.grid_widgets = []
        bg = self.settings.green
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=2,
                          bd=2, bg=bg)

        fg = self.settings.dic['text_colour']

        cell_index = 0
        for y in range(Sgg.size):
            for x in range(Sgg.size):
                guess = grid_dic[x, y].guess
                if guess == Sgg.UNSET:
                    text = ' '
                elif guess == Sgg.DASH:
                    text = '.'
                else:
                    text = 'O'

                bg = grid_dic[x, y].colour
                cell = TextSquare(self, self.settings, cell_index, fg,
                                  bg, text)
                cell.grid(row=y, column=x)
                cell.grid_propagate(0)
                self.grid_widgets.append(cell)
                cell_index += 1
        self.grid(row=0, column=0)

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

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

    def do_cell_update(self, key, text, fg, bg):
        widget_index = key[0] + key[1] * Sgg.size
        widget = self.grid_widgets[widget_index]
        update = [text, fg, bg]
        widget.my_update(update)
        self.update_idletasks()

    def apply_user_click(self, text, cell_index):
        key = (cell_index % Sgg.size, cell_index // Sgg.size)
        fg = self.settings.dic['text_colour']
        bg = self.model.grid_dic[key].colour
        self.do_cell_update(key, text, fg, bg)

    def mint(self):
        hint = self.model.hint[0]
        x = hint[0][0]
        y = hint[0][1]
        key = (x, y)
        guess = hint[1]
        bg = self.model.grid_dic[key].colour
        fg = self.settings.dic['text_colour']
        return key, guess, bg, fg

    def show_hint(self):
        """
        Show a hint on the grid.
        """
        if self.model.hint:
            key, guess, bg, fg = self.mint()
            text = '?'
            self.do_cell_update(key, text, fg, bg)

    def apply_hint(self):
        """
        Remove hint symbol from grid and reveal answer
        """
        if self.model.hint:
            key, guess, bg, fg = self.mint()
            self.do_cell_update(key, guess, fg, bg)

    def unshow_hint(self):
        """
        Remove hint symbol from grid
        """
        if self.model.hint:
            key, guess, bg, fg = self.mint()
            text = ' '
            self.do_cell_update(key, text, fg, bg)

    def show_errors(self):
        fg = self.settings.dic['text_colour']
        for key in self.model.errors:
            bg = self.model.grid_dic[key].colour
            text = 'X'
            self.do_cell_update(key, text, fg, bg)

    def unshow_errors(self):
        fg = self.settings.dic['text_colour']
        for key in self.model.errors:
            bg = self.model.grid_dic[key].colour
            text = ' '
            self.do_cell_update(key, text, fg, bg)


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

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

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

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

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


class Poly(object):
    def __init__(self, poly_id, datums):
        self.poly_id = poly_id
        self.datums = datums
        self.size = len(datums)
        self.row_indexes = set([])
        self.col_indexes = set([])
        self.finished = False

    def has_set_key(self, datum):
        ret = False
        for datum in self.datums:
            if not datum.is_set():
                ret = True
                break
        return ret

    def update_rows_cols(self):
        """
        Make sets of the row and column indexes currently
        used by this poly.
        rows has the y values, cols the x values.
        """
        self.row_indexes = set([])
        self.col_indexes = set([])
        for datum in self.datums:
            if not datum.is_set():
                self.row_indexes.add(datum.key[1])
                self.col_indexes.add(datum.key[0])

    def is_finished(self):
        return self.finished

    """
    def print_me(self):
        print self.poly_id, self.finished
        for datum in self.datums:
            print datum.key
        print
    """


class Datum(object):
    """
    A cell in the grid, has poly and colour
    """
    def __init__(self, poly_id, key):
        self.poly_id = abs(poly_id)
        self.answer = Sgg.DASH
        if poly_id < 0:
            self.answer = Sgg.TARGET
        self.key = key
        self.func = None
        self.guess = Sgg.UNSET
        self.neighbours = set([])
        self.size = None
        self.colour = 'green'

    def set_guess(self, guess):
        if guess == Sgg.TARGET:
            self.guess = Sgg.TARGET
        else:
            self.guess = Sgg.DASH

    def guess_correct(self, guess):
        return guess == self.answer

    def is_wrong(self):
        return self.is_set() and self.guess != self.answer

    def is_finished(self):
        return self.is_set() and self.guess == self.answer

    def is_set(self):
        return self.guess != Sgg.UNSET

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

    # def __str__(self):
    #    return str(self.poly_id)


class Model(object):
    """
    grid_dic[x, y] is the Datum at (x, y)
    poly_dic(poly_id) is a list of poly_id's Datum indexes (x, y)
    Each solving algorithm finds all possible guesses for the current
    state of the puzzle and returns them as a list. Only the solver used during
    puzzle generation uses all the guesses for each algorithm, because
    it makes it twice as fast; but the other functions use only the first
    in the list.
    """
    def __init__(self, model_data):
        self.size = None
        self.score = None
        self.finished = False
        self.model_data = model_data
        self.poly_dic = {}
        self.grid_dic = {}
        self.target_keys = []
        self.hint = []
        self.errors = []
        self.algorithm = None
        self.algorithms = [
            (self.alg_0),
            (self.alg_1),
            (self.alg_2),
            (self.alg_3),
            (self.alg_4),
            (self.alg_5),
            (self.alg_6),
            (self.alg_7),
            (self.alg_8),
            ]
        self.alg_counts = [0] * len(self.algorithms)

    def check_errors(self):
        self.errors = []
        for key, datum in list(self.grid_dic.items()):
            if datum.is_wrong():
                # print 'error', key, datum
                self.errors.append(key)

    def zero_alg_counts(self):
        self.alg_counts = [0] * len(self.algorithms)

    def apply_algorithms(self):
        """
        Try all algorithms. If one succeeds, return.
        """
        self.hint = []
        for self.algorithm, algorithm in enumerate(self.algorithms):
            algorithm()
            if self.hint:
                break

    def apply_hint(self):
        """
        Add a hint to the grid.
        hint = [key, guess]
        """
        if self.hint:
            hint = self.hint[0]
            key = hint[0]
            guess = hint[1]
            self.grid_dic[key].set_guess(guess)
            self.update_poly(key)
            self.alg_counts[self.algorithm] += 1
            self.check_finished()

    def apply_hints(self):
        """
        Add a hint to the grid.
        hint = [key, guess]
        """
        for hint in self.hint:
            key = hint[0]
            guess = hint[1]
            self.grid_dic[key].set_guess(guess)
            self.update_poly(key)
            self.alg_counts[self.algorithm] += 1

        self.check_finished()

    def check_hint(self):
        hint = self.hint[0]
        key = hint[0]
        return self.grid_dic[key].guess_correct(hint[1])

    def do_hint(self):
        """
        If not finished try all algorithms. If one succeeds, return.
        """
        self.hint = []
        if not self.is_finished():
            self.apply_algorithms()
            if self.hint:
                hint = self.hint[0]
                if not self.check_hint():
                    # error detected
                    PzlG.logger.logger.error("solve error! (" +
                                             str(hint[0][0]) + ',' +
                                             str(hint[0][1]) + ')' + ' ' +
                                             str(hint[1]))
                    # self.print_me(3)
                    self.hint = []

    def solver_1(self):
        """
        Keep trying and applying all algorithms until finished or failed.
        """
        score = 0
        self.zero_alg_counts()
        progress = True
        while progress:
            progress = False
            self.do_hint()
            if self.hint:
                progress = True
                self.apply_hint()

        self.check_finished()
        if self.is_finished():
            for i, count in enumerate(self.alg_counts):
                Sgg.alg_counts[i] += count
                score += Sgg.alg_scores[i] * count
        return self.is_finished(), score

    def solver(self):
        """
        Keep trying and applying all algorithms until finished or failed.
        """
        score = 0
        self.zero_alg_counts()
        progress = True
        while progress:
            progress = False
            self.do_hint()
            if self.hint:
                progress = True
                self.apply_hint()

        self.check_finished()
        if self.is_finished():
            for i, count in enumerate(self.alg_counts):
                Sgg.alg_counts[i] += count
                score += Sgg.alg_scores[i] * count
        return self.is_finished(), score

    def solver(self):
        """
        Keep trying and applying all algorithms until finished or failed.
        """
        score = 0
        self.zero_alg_counts()
        progress = True
        while progress:
            progress = False
            self.hint = []
            if not self.is_finished():
                self.apply_algorithms()
            if self.hint:
                progress = True
                self.apply_hints()

        self.check_finished()
        if self.is_finished():
            for i, count in enumerate(self.alg_counts):
                Sgg.alg_counts[i] += count
                score += Sgg.alg_scores[i] * count
        return self.is_finished(), score

    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.size or \
               y < 0 or y >= Sgg.size:
                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 set(neighbours)

    def strip_done(self, xory, key):
        """
        Is there already a TARGET in this strip?
        """
        ret = False
        if xory == 'x':
            x = key[0]
            y = key[1]
            for x in range(self.size):
                if self.grid_dic[x, y].guess == Sgg.TARGET:
                    ret = True
                    break
        else:
            x = key[0]
            y = key[1]
            for y in range(self.size):
                if self.grid_dic[x, y].guess == Sgg.TARGET:
                    ret = True
                    break
        return ret

    def get_puzzle(self, puzzle_number):
        """
        Get grid_dic[x, y] of Datum for this puzzle
        Get poly_dic[poly_id] of Poly for this puzzle
        """
        puzzle = self.model_data.get_puzzle(puzzle_number)
        self.score = puzzle[0]
        self.size = puzzle[1]
        Sgg.size = self.size
        item = 2
        self.grid_dic = {}
        self.poly_dic = {}
        self.target_keys = []
        t_dic = {}
        for y in range(self.size):
            for x in range(self.size):
                poly_id = puzzle[item]
                datum = Datum(poly_id, (x, y))
                self.grid_dic[x, y] = datum
                t_dic.setdefault(abs(poly_id), []).append(datum)
                if poly_id < 0:
                    self.target_keys.append((x, y))
                item += 1
        # make poly_dic
        for poly_id, datums in list(t_dic.items()):
            self.poly_dic[poly_id] = Poly(poly_id, datums)

        self.set_neighbours()
        self.prepare_colours()
        return puzzle

    def prepare_colours(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.7, 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

        colour_count = len(self.poly_dic)
        colours = get_n_colours(colour_count)
        shuffle(colours)

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

    def poly_from_datum(self, datum):
        poly_id = datum.poly_id
        return self.poly_dic[poly_id]

    def alg_0(self):
        """
        Are there any polys with TARGET set but more UNSETS?
        Algorithm 0: This cell is in a polyomino with a set Target
        and so cannot be a Target
        """
        for key, datum in list(self.grid_dic.items()):
            if datum.guess == Sgg.TARGET:
                poly = self.poly_from_datum(datum)
                if not poly.is_finished():
                    for datum_1 in poly.datums:
                        if not datum_1.is_set():
                            self.hint.append([datum_1.key, Sgg.DASH])

    def alg_1(self):
        """
        Are there any strips with TARGET set but more UNSETS?
        Algorithm_1: This cell is in a strip with a set Target
        and so cannot be a Target.
        """
        for y in range(self.size):
            for x in range(self.size):
                datum = self.grid_dic[x, y]
                if datum.guess == Sgg.TARGET:
                    for y_0 in range(self.size):
                        datum_0 = self.grid_dic[x, y_0]
                        if not datum_0.is_set():
                            self.hint.append([datum_0.key, Sgg.DASH])

                    for x_0 in range(self.size):
                        datum_0 = self.grid_dic[x_0, y]
                        if not datum_0.is_set():
                            self.hint.append([datum_0.key, Sgg.DASH])

    def alg_2(self):
        """
        Are there any polys with only 1 cell left?
        Algorithm_2: All other cells in the polyomino have
        been ruled out so this one is the Target.
        """
        for poly_id, poly in list(self.poly_dic.items()):
            if not poly.is_finished():
                done = []
                for datum in poly.datums:
                    if datum.is_set():
                        done.append(datum)
                if len(done) == len(poly.datums) - 1:
                    # got one
                    for datum in poly.datums:
                        if datum not in done:
                            self.hint.append([datum.key, Sgg.TARGET])

    def alg_3(self):
        """
        Are there any TARGETS touching UNSETS?
        Algorithm_3: This cell is touched by a Target cell
        and so cannot be a Target.
        """
        for y in range(self.size):
            for x in range(self.size):
                datum = self.grid_dic[x, y]
                if datum.guess == Sgg.TARGET:
                    for neighbour in datum.neighbours:
                        if not neighbour.is_set():
                            self.hint.append([neighbour.key, Sgg.DASH])

    def alg_4(self):
        """
        Is there a strip with only 1 cell left?
        Algorithm_4: This cell is the last one in a strip
        and so must be a Target.
        """
        for y in range(self.size):
            undone = []
            for x in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    undone.append(datum)
            if len(undone) == 1:
                self.hint.append([undone[0].key, Sgg.TARGET])

        for x in range(self.size):
            undone = []
            for y in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    undone.append(datum)
            if len(undone) == 1:
                self.hint.append([undone[0].key, Sgg.TARGET])

    def alg_5(self):
        """
        If all the cells in a strip are from a single poly
        that poly must provide the TARGET for the strip and so
        all its cells in other strips can be deleted.
        Algorithm_5: This cell is in a polyomino which provides all the
        cells for a different strip and so cannot be a Target.
        """
        for y in range(self.size):
            t_dic = {}
            for x in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    poly_id = datum.poly_id
                    t_dic.setdefault(poly_id, []).append((x, y))

            if len(t_dic) == 1:
                # 1 poly covers the whole strip
                poly_id = list(t_dic.keys())[0]
                poly = self.poly_dic[poly_id]
                for datum in poly.datums:
                    key = datum.key
                    if key[1] != y and not datum.is_set():
                        # datum is in poly but in a different strip
                        self.hint.append([key, Sgg.DASH])

        for x in range(self.size):
            t_dic = {}
            for y in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    poly_id = datum.poly_id
                    t_dic.setdefault(poly_id, []).append((x, y))

            if len(t_dic) == 1:
                # 1 poly covers the whole strip
                poly_id = list(t_dic.keys())[0]
                poly = self.poly_dic[poly_id]
                for datum in poly.datums:
                    key = datum.key
                    if key[0] != x and not datum.is_set():
                        # datum is in poly but in a different strip
                        self.hint.append([key, Sgg.DASH])

    def alg_6(self):
        """
        Are there any polys with cells in a single strip?
        Algorithm_6: A polyomino only has cells in one strip so must
        provide its Target. This cell is from a different polyomino
        in the strip and so cannot be a Target.
        """
        for poly_id, poly in list(self.poly_dic.items()):
            if not poly.is_finished():
                xs = set([])
                ys = set([])
                for datum in poly.datums:
                    if not datum.is_set():
                        xs.add(datum.key[0])
                        ys.add(datum.key[1])
                if len(xs) == 1:
                    # got one
                    x = xs.pop()
                    for y in range(self.size):
                        datum = self.grid_dic[x, y]
                        if datum.poly_id != poly_id and not datum.is_set():
                            self.hint.append([datum.key, Sgg.DASH])

                elif len(ys) == 1:
                    # got one
                    y = ys.pop()
                    for x in range(self.size):
                        datum = self.grid_dic[x, y]
                        if datum.poly_id != poly_id and not datum.is_set():
                            self.hint.append([datum.key, Sgg.DASH])

    def alg_7(self):
        """
        Find polys which are confined to a set of strips and so must
        contain the TARGETS for the strips. Any cells from other polys
        in these strips cannot be TARGETS.
        Look for a continuous section of strips which contains
        a set of poly's which do not occur in other strips and
        that the length of the section is equal to the number
        of these polys. The section lengths are called spans
        and we try several sizes.
        """
        # get sets of rows and columns used by each poly
        for poly_id, poly in list(self.poly_dic.items()):
            poly.update_rows_cols()

        # try spans of sizes spans
        max_span = self.size - 2
        spans = list(range(2, max_span))

        # do horizontal strips
        # make a list of sets of poly_ids for each vertical strip
        strips = []
        for y in range(self.size):
            strip = set([])
            for x in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    strip.add(datum.poly_id)
            strips.append(strip)

        for span in spans:
            # get set of all poly_ids for sections of width span

            for row in range(self.size - span + 1):
                all_poly_ids = set([])
                for i in range(span):
                    strip = strips[row + i]
                    all_poly_ids = all_poly_ids.union(strip)

                ys = set(list(range(row, row + span)))
                # collect poly_ids which also use external rows
                dels = set([])
                for poly_id in all_poly_ids:
                    poly = self.poly_dic[poly_id]
                    for y in poly.row_indexes:
                        if y not in ys:
                            dels.add(poly.poly_id)

                # if the number of remaining poly_ids == span
                # these alone polys must be used for this span

                if len(all_poly_ids - dels) == span:
                    for poly_id in dels:
                        for datum in self.poly_dic[poly_id].datums:
                            if datum.key[1] in ys and not datum.is_set():
                                self.hint.append([datum.key, Sgg.DASH])

        # do vertical strips
        # make a list of sets of poly_ids for each horizontal strip
        strips = []
        for x in range(self.size):
            strip = set([])
            for y in range(self.size):
                datum = self.grid_dic[x, y]
                if not datum.is_set():
                    strip.add(datum.poly_id)
            strips.append(strip)

        for span in spans:
            # get set of all poly_ids for sections of width span

            for col in range(self.size - span + 1):
                all_poly_ids = set([])
                for i in range(span):
                    strip = strips[col + i]
                    all_poly_ids = all_poly_ids.union(strip)

                xs = set(list(range(col, col + span)))
                # collect poly_ids which also use external cols
                dels = set([])
                for poly_id in all_poly_ids:
                    poly = self.poly_dic[poly_id]
                    for x in poly.col_indexes:
                        if x not in xs:
                            dels.add(poly.poly_id)

                # if the number of remaining poly_ids == span
                # these alone polys must be used for this span
                if len(all_poly_ids - dels) == span:
                    for poly_id in dels:
                        for datum in self.poly_dic[poly_id].datums:
                            if datum.key[0] in xs and not datum.is_set():
                                self.hint.append([datum.key, Sgg.DASH])

    def alg_8(self):
        """
        If a cell touches all the cells of a different polyomino it
        cannot contain a TARGET.
        If those from the other poly that do not touch the cell are all
        in the same strip they too cannot contain a TARGET.
        """

        for poly_id_0, poly_0 in list(self.poly_dic.items()):
            if not poly_0.is_finished():
                for datum_0 in poly_0.datums:
                    if not datum_0.is_set():
                        for poly_id_1, poly_1 in list(self.poly_dic.items()):
                            if poly_id_0 != poly_id_1 and\
                               not poly_1.is_finished():
                                datum_1s = set([])
                                for datum_1 in poly_1.datums:
                                    if not datum_1.is_set():
                                        datum_1s.add(datum_1)
                                left = datum_1s - datum_0.neighbours
                                if not left:
                                    # datum_0 touches all the cells in poly_1
                                    self.hint.append([datum_0.key, Sgg.DASH])

                                """
                                even if datum_0 does not touch all it may still
                                be in the same strip as all those not touching
                                """

                                dc = 0
                                for datum in left:
                                    key = datum.key
                                    if key[0] == datum_0.key[0] or\
                                       key[1] == datum_0.key[1]:
                                        dc += 1

                                if dc == len(left):
                                    # datum_0 touches the cells in poly_1
                                    # or is in the same strip
                                    self.hint.append([datum_0.key, Sgg.DASH])
    """
    def print_me(self, task):
        if task == 0:
            for y in range(self.size):
                for x in range(self.size):
                    print self.grid_dic[x, y].poly_id,
                print
            print
        elif task == 2:
            for y in range(self.size):
                for x in range(self.size):
                    print self.grid_dic[x, y].guess,
                print
            print
        elif task == 3:
            for y in range(self.size):
                for x in range(self.size):
                    if self.grid_dic[x, y].guess != Sgg.DASH and\
                       self.grid_dic[x, y].guess != Sgg.TARGET:
                        print self.grid_dic[x, y].poly_id,
                    else:
                        print self.grid_dic[x, y].guess,
                print
            print
    """

    def check_finished(self):
        self.finished = True
        for key in self.target_keys:
            if not self.grid_dic[key].is_finished():
                self.finished = False
                break

    def is_finished(self):
        return self.finished

    def undo_errors(self):
        for key in self.errors:
            self.grid_dic[key].guess = Sgg.UNSET
        self.errors = []

    def apply_user_click(self, mouse_index, key):
        """
        User has clicked at coord key
        """
        guesses = [0, Sgg.DASH, Sgg.UNSET, Sgg.TARGET]
        guess = guesses[mouse_index]
        self.grid_dic[key].set_guess(guess)

        # now update the poly

        self.update_poly(key)
        self.check_finished()

    def update_poly(self, key):
        poly_id = self.grid_dic[key].poly_id
        poly = self.poly_dic[poly_id]
        finished = True
        for datum in poly.datums:
            if not datum.is_set():
                finished = False
                break
        poly.finished = finished

    def generate(self):
        """
        Generate. Targets first, then grow polys around them.
        """
        seed = 6
        random.seed(seed)
        puzzles = []
        max_puzzles = 5
        min_size = 5
        max_size = 9
        for self.size in range(min_size, max_size + 1):
            Sgg.size = self.size
            self.generate_1(puzzles, max_puzzles)
        self.save_puzzles(puzzles)
        exit(1)

    def generate_1(self, puzzles, max_puzzles):
        min_score = self.size * self.size * 85.0 / 64.0
        trials = 0
        trial = 0
        puzzle_count = 0
        while puzzle_count < max_puzzles:
            trial += 1
            trials += 1
            while True:
                polys = [[] for p in range(self.size)]
                grid_dic = self.init_grid()
                xys = self.get_target_pos()
                self.add_targets(grid_dic, polys, xys)
                self.fill_grid(grid_dic, polys)
                if self.grid_ok(grid_dic):
                    break
            self.make_grid(grid_dic)
            result, score = self.solver()

            if self.is_finished() and score >= min_score:
                puzzle = self.save_puzzle(grid_dic, score)
                puzzles.append(puzzle)
                puzzle_count += 1
                # print '>>>>>>>>>>>>>>>>>>>>>>', puzzle_count, trial, trials
                # self.print_grid_4(grid_dic)
                trial = 0

    def save_puzzle(self, grid_dic, score):
        puzzle = [score, self.size]
        for y in range(self.size):
            for x in range(self.size):
                puzzle.append(grid_dic[x, y])
        return puzzle

    def save_puzzles(self, puzzles):
        puzzles = sorted(puzzles)
        filename = 'wapuzzles.txt'
        with open(filename, "w") as fo:
            rec = ''
            for puzzle in puzzles:
                for item in puzzle:
                    rec += str(item)
                    rec += ','
            fo.write(rec)

    def init_grid(self):
        grid_dic = {}
        for y in range(self.size):
            for x in range(self.size):
                grid_dic[x, y] = 0
        return grid_dic

    def add_targets(self, grid_dic, polys, xys):
        for i, key in enumerate(xys):
            grid_dic[key] = -(i + 1)
            polys[i].append(key)

    def choose_poly(self, poly_indexes):
        item = poly_indexes[randint(0, len(poly_indexes) - 1)]
        return item

    def choose_new_cell(self, grid_dic, key):
        directions = [(0, -1), (1, 0), (0, 1), (-1, 0)]
        shuffle(directions)
        ret = ()
        x_in = key[0]
        y_in = key[1]
        for dir1 in directions:
            x_inc = dir1[0]
            y_inc = dir1[1]
            x = x_in + x_inc
            y = y_in + y_inc
            if x > -1 and x < self.size and\
               y > -1 and y < self.size and\
               not grid_dic[x, y]:
                ret = (x, y)
                break
        return ret

    def grid_ok_9(self, grid_dic):
        ret = True
        polys = [0 for pos in range(self.size)]
        for y in range(self.size):
            for x in range(self.size):
                pos = abs(grid_dic[x, y])
                polys[pos - 1] += 1
        for pos in polys:
            if pos < 2:
                ret = False
                break
        return ret

    def grid_ok(self, grid_dic):
        if self.size == 9:
            return self.grid_ok_9(grid_dic)
        ret = True
        t_dic = {}
        for y in range(self.size):
            for x in range(self.size):
                key = (x, y)
                poly_id = abs(grid_dic[key])
                t_dic.setdefault(poly_id, []).append((x, y))

        for poly_id, poly in list(t_dic.items()):
            xmin = 99
            xmax = -99
            ymin = 99
            ymax = -99
            for key in poly:
                xmin = min(xmin, key[0])
                xmax = max(xmax, key[0])
                ymin = min(ymin, key[1])
                ymax = max(ymax, key[1])
            if xmax - xmin < 1 or ymax - ymin < 1:
                ret = False
                break
        return ret

    def fill_grid(self, grid_dic, polys):
        """
        Having seeded the grid with TARGETS, randomly grow the polys.
        Try to vary the sizes.
        First chose the number of small polys (1 - 4), then grow them
        all with 5 to 1 chance of extending a large one.
        """
        small_count = 2
        if self.size == 8:
            small_count = random.randint(2, 4)
        elif self.size == 9:
            small_count = random.randint(2, 5)
        poly_indexes = []
        for i in range(small_count):
            poly_indexes.append(i)
        for j in range(i + 1, len(polys)):
            poly_indexes.append(j)
            poly_indexes.append(j)
            poly_indexes.append(j)
            poly_indexes.append(j)
            poly_indexes.append(j)

        done = len(polys)
        while done < self.size * self.size:
            poly_index = self.choose_poly(poly_indexes)
            poly = polys[poly_index]
            shuffle(poly)
            for key in poly:
                new_key = self.choose_new_cell(grid_dic, key)
                if new_key:
                    grid_dic[new_key] = poly_index + 1
                    poly.append(new_key)
                    done += 1
                    break
    """
    def print_grid_4(self, grid_dic):
        for y in range(self.size):
            for x in range(self.size):
                print grid_dic[x, y],
            print
    """

    def make_grid(self, grid_dic):
        self.grid_dic = {}
        self.poly_dic = {}
        self.target_keys = []
        t_dic = {}
        for y in range(self.size):
            for x in range(self.size):
                poly_id = grid_dic[x, y]
                datum = Datum(poly_id, (x, y))
                self.grid_dic[x, y] = datum
                t_dic.setdefault(abs(poly_id), []).append(datum)
                if poly_id < 0:
                    self.target_keys.append((x, y))
        # make poly_dic
        for poly_id, datums in list(t_dic.items()):
            self.poly_dic[poly_id] = Poly(poly_id, datums)

        self.set_neighbours()

    def get_target_pos(self):
        success = False
        while not success:
            tries = 0
            keys = []
            done = []
            for x in range(self.size):
                while len(done) < self.size and tries < 20:
                    tries += 1
                    y = random.randint(0, self.size - 1)
                    if y not in done:
                        key = (x, y)
                        good = True
                        for item in keys:
                            if (x, y - 1) == item or\
                               (x + 1, y - 1) == item or\
                               (x + 1, y) == item or\
                               (x + 1, y + 1) == item or\
                               (x, y + 1) == item or\
                               (x - 1, y + 1) == item or\
                               (x - 1, y) == item or\
                               (x - 1, y - 1) == item:
                                good = False
                                break
                        if good:
                            keys.append((x, y))
                            done.append(y)
                            break

                if len(keys) == self.size:
                    success = True
                    break
        shuffle(keys)
        return keys


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

    def __init__(self, root):
        self.settings = Settings()
        self.master = root
        self.flasher = None
        self.model_data = ModelData()
        self.model = None
        self.hint_status = Sgg.GIVE_HINT
        self.active = False
        self.error_detected = False
        self.puzzle_number = None
        self.exposed = {}
        self.view = View(root, self.settings)
        puzzle_number = None
        self.start_game(puzzle_number)

    def test(self):
        # print 'test'
        new_puzzles = []
        done = 0
        bad = []
        for puzzle_number in range(self.model_data.puzzle_count):
            self.model = Model(self.model_data)
            puzzle = self.model.get_puzzle(puzzle_number)
            if not self.model.solver_1()[0]:
                bad.append(puzzle_number)
            done += 1
        """
            print puzzle_number
        print 'done', done, 'bad', bad, len(bad)
        print Sgg.alg_counts
        tot = float(sum(Sgg.alg_counts))
        for alg in Sgg.alg_counts:
            print 100.0 * alg / tot
        """
        exit(1)

    def sort(self):
        """
        Can be used to merge or rescore puzzles.
        """
        # print 'sort'
        new_puzzles = []
        done = 0
        bad = []
        for puzzle_number in range(self.model_data.puzzle_count):
            self.model = Model(self.model_data)
            puzzle = self.model.get_puzzle(puzzle_number)
            result, score = self.model.solver_1()
            if not score:
                bad.append(puzzle_number)
            else:
                new_puzzle = [score] + puzzle[1:]
                new_puzzles.append(new_puzzle)
            done += 1
        """
            print puzzle_number
        print 'done', done, 'bad', bad, len(bad)
        print Sgg.alg_counts
        self.model.save_puzzles(new_puzzles)
        """
        exit(1)

    def start_game(self, puzzle_number):
        """
        Prepare for a game or generate puzzles
        """
        self.model = Model(self.model_data)
        # self.model.generate()
        # self.test()
        # self.sort()
        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)
        PzlG.logger.logger.info("start_game with puzzle number " +
                                str(self.puzzle_number))
        self.view.thumbs_up()
        self.view.model = self.model
        self.view.make_board()
        self.add_callbacks()
        self.ready_for_hint()
        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.score)
        self.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        self.active = True
        self.hint_status = Sgg.GIVE_HINT

    def add_callbacks(self):
        """
        Set up callbacks
        """
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.entry_box.add_callback(self.get_puzzle_number)
        self.view.board.add_callback(self.cell_event)

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

        strargs = ''
        for item in args:
            strargs += ' ' + item
        PzlG.logger.logger.info("service_menu " + strargs)
        name = args[0]
        if name == 'font_size':
            self.set_font_size()
        elif name == '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):
        """
        Respond to Toolbar choices
        """
        PzlG.logger.logger.info("service_toolbar " +
                                str(button_index) +
                                ' ' +
                                str(mouse_index))

        if mouse_index == 2:
            alg_index = None
            if self.model.hint:
                alg_index = self.model.hint[0]
                alg_index = self.model.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:
                if not self.model.is_finished():
                    self.give_hint()
            elif button_index == 2:
                if not self.model.is_finished():
                    self.check_errors()
            elif button_index == 3:
                if not self.model.is_finished():
                    self.show_solution()

    def cell_event(self, cell_index, mouse_index):
        """
        left mouse add zero
        middle mouse delete
        right mouse add one
        """
        if self.active:
            key = (cell_index % Sgg.size, cell_index // Sgg.size)
            PzlG.logger.logger.info("cell_event " +
                                    str(mouse_index) +
                                    ' ' +
                                    str(key))
            # need to remove any active hint

            if self.model.hint:
                self.view.hint_off()
                self.view.board.unshow_hint()
                self.model.hint = []
                self.hint_status = Sgg.GIVE_HINT

            if mouse_index == 1:
                # player has left clicked on this cell
                # ie wants to add a DASH
                self.model.apply_user_click(mouse_index, key)
                text = Sgg.DASH
                self.view.board.apply_user_click(text, cell_index)
                self.view.clock.set_show(True)
            elif mouse_index == 2:
                # player has middle clicked on this cell
                # ie wants to delete
                self.model.apply_user_click(mouse_index, key)
                text = ' '
                self.view.board.apply_user_click(text, cell_index)
            elif mouse_index == 3:
                # player has right clicked on this cell
                # ie wants to add a TARGET
                self.model.apply_user_click(mouse_index, key)
                text = Sgg.TARGET
                self.view.board.apply_user_click(text, cell_index)
                self.auto_strips(key)
                self.auto_poly(key)
                self.view.clock.set_show(True)
            self.check_finished()
            self.model.check_errors()

    def auto_strips(self, key_in):
        if self.settings.dic['Autofill_s'] == 'On':
            fg = self.settings.dic['text_colour']
            guess = Sgg.DASH
            for x in range(self.model.size):
                key = (x, key_in[1])
                if key != key_in:
                    self.model.grid_dic[key].set_guess(guess)
                    self.model.update_poly(key)
                    bg = self.model.grid_dic[key].colour
                    self.view.board.do_cell_update(key, guess, fg, bg)
            for y in range(self.model.size):
                key = (key_in[0], y)
                if key != key_in:
                    self.model.grid_dic[key].set_guess(guess)
                    self.model.update_poly(key)
                    bg = self.model.grid_dic[key].colour
                    self.view.board.do_cell_update(key, guess, fg, bg)

    def auto_poly(self, key_in):
        if self.settings.dic['Autofill_p'] == 'On':
            fg = self.settings.dic['text_colour']
            guess = Sgg.DASH
            poly_id = self.model.grid_dic[key_in].poly_id
            poly = self.model.poly_dic[poly_id]
            for datum in poly.datums:
                key = datum.key
                if key != key_in:
                    self.model.grid_dic[key].set_guess(guess)
                    self.model.update_poly(key)
                    bg = self.model.grid_dic[key].colour
                    self.view.board.do_cell_update(key, guess, fg, bg)

    def ready_for_hint(self):
        """
        If the puzzle not finished, check for errors
        and if found show them.
        Otherwise set hint mode the GIVE_HINT and set the display.
        """
        if not self.model.is_finished():
            self.model.check_errors()
            if self.model.errors:
                self.show_errors()
                self.error_detected = True
            else:
                self.hint_status = Sgg.GIVE_HINT
                self.view.hint_off()
                self.view.thumbs_up()
                self.error_detected = False
            self.view.clock.set_show(True)
            self.model.hint = []

    def give_hint(self):
        """
        If in GIVE_HINT mode check for errors.
          If found show them to user
          Else find a hint, display it and change hint mode
        Else apply the hint, prepare for next and check if finished.
        """
        if self.hint_status == Sgg.GIVE_HINT:
            self.model.check_errors()
            if self.model.errors:
                self.view.thumbs_down()
                self.show_errors()
                self.error_detected = True
            else:
                self.error_detected = False
                self.model.do_hint()
                if self.model.hint:
                    self.view.hint_on()
                    self.view.board.show_hint()
                    self.view.update_clock_box(self.model.algorithm)
                    self.view.clock.set_show(False)
                    self.hint_status = Sgg.APPLY_HINT
        else:
            hint = self.model.hint[0]
            PzlG.logger.logger.info("apply hint (" +
                                    str(hint[0][0]) + ',' +
                                    str(hint[0][1]) + ')' + ' ' +
                                    str(hint[1]))

            self.view.board.apply_hint()
            self.model.apply_hint()
            if hint[1] == Sgg.TARGET:
                self.auto_strips(hint[0])
                self.auto_poly(hint[0])
            self.ready_for_hint()
            self.check_finished()

    def check_errors(self):
        """
        If an error already known, sort it out.
        Otherwise check for errors.
        """
        if self.error_detected:
            # we know there's an error already, so now we correct it
            self.tidy_error()
            self.ready_for_hint()
        else:
            self.model.check_errors()
            if self.model.errors:
                self.view.thumbs_down()
                self.error_detected = True
                self.show_errors()

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

    def show_solution(self):
        fg = self.settings.dic['text_colour']
        for y in range(self.model.size):
            for x in range(self.model.size):
                datum = self.model.grid_dic[x, y]
                text = ' '
                if datum.answer == Sgg.TARGET:
                    text = 'O'
                self.view.board.do_cell_update((x, y), text,
                                               fg, datum.colour)

        self.view.game_over()
        self.view.clock_stop()
        self.active = False

    def show_errors(self):
        """
        Colour the error cells
        """
        self.view.board.show_errors()

    def tidy_error(self):
        """
        update view and undo errors
        """

        # do the display first
        self.view.board.unshow_errors()
        self.model.undo_errors()
        self.error_detected = False
        self.view.thumbs_up()

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

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

    def set_puzzle_number(self, puzzle_number):
        """
        Select or set random 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


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