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

# Copyright (C) 2019 Rod Engerstad

import sys
import random
import tkinter as tk
import tkinter.colorchooser

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 numberlink_data import ModelData

class Sgg(object):
    """
    Game globals
    """
    GIVE_HINT = 0
    APPLY_HINT = 1
    Left = 'L'
    Right = 'R'
    Up = 'U'
    Down = 'D'

class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.dic = {}
        self.dic['set_colour'] = 'path_1_colour'
        self.dic['path_1_colour'] = '#7FFFD4'
        self.dic['path_2_colour'] = '#7FD4FF'
        self.dic['path_3_colour'] = '#D4FF7F'
        self.dic['path_4_colour'] = '#FF7FD4'
        self.dic['path_5_colour'] = '#7F7FFF'
        self.dic['path_6_colour'] = '#D47FFF'
        self.dic['path_7_colour'] = '#FFD47F'
        self.dic['path_8_colour'] = '#FF7F7F'
        self.dic['path_9_colour'] = '#7FFF7F'
        self.dic['error_colour'] = 'red'

        self.dic['font_size'] = '4'
        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()

    def make_help(self):
        self.help_text = _("The object of the game is to join all the pairs of circled numbers using paths which, in combination, visit every vertex in the grid. No path is allowed to double back on itself to occupy a parallel or anti-parallel adjacent line on the grid. Edges are added using a left mouse click and are removed using right mouse clicks. The jigsaw symbol is a menu for configuring the game. A left click on the PZL numberlink symbol next to it starts a new game by loading a randomly selected puzzle. A right click on this symbol will load the next puzzle. A click on the wand requests a hint. Given the current state of the grid, it can be deduced that the hint vertex is one for which only one or two extensions are possible. If the player can work out which is the correct extending edge they can add it using a left click. Otherwise a further click on the hint button will cause the edge to be revealed.  The hint is shown using a red number (0 if the vertex is not an end). If a hint is requested when the grid contains errors, no hint will be given, the thumb icon turns down and the incorrect edges are displayed. They can be removed using right clicks or by a single click on the thumb icon. At any time clicking the thumb checks the current grid for errors, a second click will remove them. The sad smiley will display the solution. The entry box contains the current puzzle number and can be used to enter puzzle numbers. The number to its right is the puzzle difficulty score. To its right is a clock. The game contains 1000 puzzles ordered by their difficulty score, easiest first.")

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

    def load_menus(self):
        self.menu_items.append(MenuItem(
            _('Grid Spacing'),
            ['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(
            _('Set Colour'),
            [_('path 1'),
             _('path 2'),
             _('path 3'),
             _('path 4'),
             _('path 5'),
             _('path 6'),
             _('path 7'),
             _('path 8'),
             _('path 9'),
             _('Error')],
            'N',
            ['path_1_colour',
             'path_2_colour',
             'path_3_colour',
             'path_4_colour',
             'path_5_colour',
             'path_6_colour',
             'path_7_colour',
             'path_8_colour',
             'path_9_colour',
             'error_colour'],
            'set_colour'
        ))
        self.menu_items.append(MenuItem(
            _('Save Settings'),
            '',
            '',
            '',
            'save_settings'
        ))
        self.menu_items.append(MenuItem(
            _('Help'),
            '',
            '',
            '',
            'help'
        ))
        self.menu_items.append(MenuItem(
            _('About'),
            '',
            '',
            '',
            'about'
        ))

    def do_scaling(self):
        inc = 0.1
        mult = int(self.dic['font_size'])
        factor = 0.8 + mult * inc
        self.square_size = 30
        self.square_size = int(self.square_size * factor)


class CObject(object):
    """
    Canvas lines
    grid coords x, y with 0, 0 at top left
    """

    def __init__(self, canvas, grid_line, v0, v1):
        self.canvas = canvas
        self.grid_line = grid_line
        self.vertex_0 = v0
        self.vertex_1 = v1
        self.coords = (v0.coord, v1.coord)
        self.callback = None
        self.canvas.tag_bind(self.grid_line, "<ButtonRelease-1>", self.command)
        self.canvas.tag_bind(self.grid_line, "<ButtonRelease-3>", self.command)

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

    def command(self, event):
        if event.type == "5":
            mouse_index = event.num
            if mouse_index == 1 or mouse_index == 3:
                if mouse_index == 1:
                    event_code = 1
                elif mouse_index == 3:
                    event_code = 2
                self.callback(event_code, self.coords)


class Board(tk.Frame):
    def __init__(self, parent, settings, model, images):
        self.settings = settings
        self.model = model
        self.vertex_dic = self.model.vertex_dic
        self.images = images
        self.widget_dic = {}
        self.grid_width = None
        self.grid_height = None
        self.canvas_width = None
        self.canvas_height = None
        self.grid_unit = self.settings.square_size
        self.grid_margin = 15
        bg = self.settings.green
        tk.Frame.__init__(self, parent, relief='flat',
                          highlightbackground=self.settings.grey,
                          highlightthickness=2,
                          bd=2, bg=bg)
        self.grid_width = self.model.width
        self.grid_height = self.model.height
        self.canvas_width = 2 * self.grid_margin + self.grid_unit * \
                            (self.grid_width - 1)
        self.canvas_height = 2 * self.grid_margin + self.grid_unit * \
                             (self.grid_height - 1)

        self.tk_focusFollowsMouse()
        bg = self.settings.white
        self.board = tk.Canvas(self, width=self.canvas_width,
                               height=self.canvas_height,
                               bg=bg)

        self.board.grid(row=0, column=0, sticky='NSEW')
        self.grid(row=0, column=0)

    def my_destroy(self):
        self.destroy()

    def add_callbacks(self, func):
        for key, widget in list(self.widget_dic.items()):
            widget.add_callback(func)

    def is_in_path(self, vertex_0, vertex_1):
        in_path = False
        if vertex_0.coord in vertex_1.path_coords:
            in_path = True
        return in_path

    def make_edge_widget(self, v0, v1):
        width = 1
        activefill = '#82c026'
        activewidth = 4
        x2 = self.grid_margin + v0.coord[0] * self.grid_unit
        y2 = self.grid_margin + v0.coord[1] * self.grid_unit
        x3 = self.grid_margin + v1.coord[0] * self.grid_unit
        y3 = self.grid_margin + v1.coord[1] * self.grid_unit

        fill = '#d0dbb9'
        state = 'normal'
        tags = 'link'

        grid_line = self.board.create_line(x2, y2, x3, y3,
                                           width=width,
                                           fill=fill,
                                           tags=tags,
                                           state=state,
                                           activefill=activefill,
                                           activewidth=activewidth)
        # add a path tag for edges in the solution
        if self.is_in_path(v0, v1):
            tag = 'path_' + str(v0.value)
            self.board.addtag_withtag(tag, grid_line)
            tag = 'path'
            self.board.addtag_withtag(tag, grid_line)

        coords = (v0.coord, v1.coord)
        self.widget_dic[coords] = CObject(self.board, grid_line, v0, v1)

        # avoid problems with vertex order

        coordsr = (v1.coord, v0.coord)
        self.widget_dic[coordsr] = self.widget_dic[coords]

    def make_edge_widgets(self):
        for y in range(self.grid_height):
            for x in range(self.grid_width):
                v0 = self.vertex_dic[(x, y)]
                if x + 1 < self.grid_width:
                    v1 = self.vertex_dic[(x+1, y)]
                    self.make_edge_widget(v0, v1)
                if y + 1 < self.grid_height:
                    v1 = self.vertex_dic[(x, y+1)]
                    self.make_edge_widget(v0, v1)

    def draw_solution(self):
        for value in range(1, 10):
            tag = 'path_' + str(value)
            path_tags = self.board.find_withtag(tag)
            path_colour = tag + '_colour'
            colour = self.settings.dic[path_colour]
            for widget in path_tags:
                self.board.itemconfig(widget, fill=colour, width=3)
        self.board.update_idletasks()

    def draw_vertex(self, vertex):
        inc = 10
        x = self.grid_margin + vertex.coord[0] * self.grid_unit
        y = self.grid_margin + vertex.coord[1] * self.grid_unit
        x0 = x - inc
        y0 = y - inc
        x1 = x + inc
        y1 = y + inc
        image = self.images.bridges_number[vertex.value]
        idv = self.board.create_image(x, y, image=image,
                                      tags='vertexn')

    def draw_puzzle(self):
        """
        Draw the grid lines and the circles when the puzzle is loaded.
        """

        for key, vertex in list(self.vertex_dic.items()):
            if vertex.is_end():
                self.draw_vertex(vertex)

        self.make_edge_widgets()
        self.board.tag_raise('vertexn')
        self.update_idletasks()

    def show_edge(self, widget, adding):
        if adding:
            self.board.itemconfig(widget.grid_line, state='normal',
                                  fill='black', width=3)
        else:
            fill = '#d0dbb9'
            self.board.itemconfig(widget.grid_line, state='normal',
                                  fill=fill, width=1)
        self.update_idletasks()

    def board_event(self, event_code, key_in):
        """
        """
        widget_coords = []
        add = False

        try:
            widget = self.widget_dic[key_in]

            if event_code == 1:
                # add edge
                self.show_edge(widget, True)
                widget_coords = widget.coords
                add = True
            elif event_code == 2:
                # delete edge
                self.show_edge(widget, False)
                widget_coords = widget.coords

            self.board.update_idletasks()
        except KeyError:
            pass
        return widget_coords, add

    def show_hint_blob(self, image_index):
        image = self.images.bridges_red_number[image_index]
        coord = self.model.hint[0]
        x = coord[0]
        y = coord[1]
        x = self.grid_margin + x * self.grid_unit
        y = self.grid_margin + y * self.grid_unit
        hid = self.board.create_image(x, y, image=image,
                                      tags='hint')

    def delete_hint_blob(self):
        self.board.delete('hint')

    def apply_hint(self):
        if self.model.hint:
            key_list = sorted(self.model.hint)
            key = tuple(key_list)
            try:
                widget = self.widget_dic[key]
                self.show_edge(widget, True)
                self.delete_hint_blob()
            except KeyError:
                #print 'keyerror', key
                pass

    def colour_error(self, widget, adding):
        if adding:
            self.board.itemconfig(widget.grid_line, state='normal',
                                  fill=self.settings.dic['error_colour'],
                                  width=3)
        else:
            fill = '#d0dbb9'
            self.board.itemconfig(widget.grid_line, state='normal',
                                  fill=fill, width=1)
        self.update_idletasks()

    def colour_errors(self, adding):
        errors = self.model.bad_edges
        for coords in errors:
            widget = self.widget_dic[coords]
            self.colour_error(widget, adding)


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

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

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

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

    def draw_puzzle(self):
        # draw the underlying faint grid lines
        self.board.draw_puzzle()


class NVertex(object):
    """
    A Numberlink vertex

    An end vertex is "used" when it has one edge
    others when they have two used edges.
    """
    def __init__(self, x, y, value):
        self.coord = (x, y)
        self.value = abs(value)
        self.status = True
        self.coords = []
        self.path_coords = []
        self.edges = []
        self.has_end_value = value < 0
        # only one edge can be used if end
        #self.used_edge_count = 0
        self.neighbours = []

    def is_consistent(self):
        self.status = True
        if self.coord in self.coords:
            self.status = False

    def is_used(self):
        return self.coord_count() > 0 or self.is_end()

    def coord_count(self):
        return len(self.coords)

    def good_edge(self, coord):
        ret = False
        if coord in self.path_coords:
            ret = True
        return ret

    def add_edge(self, edge):
        self.edges.append(edge)

    def has_coord(self, coord):
        ret = False
        if coord in self.coords:
            ret = True
        return ret

    def is_end(self):
        return self.has_end_value

    def add_path_coord(self, coord):
        self.path_coords.append(coord)

    def add_coord(self, coord):
        if coord not in self.coords:
            if len(self.coords) < 2:
                self.coords.append(coord)
            #else:
        #        print 'too many coords', self.coord, self.coords
        #else:
        #    print 'attempted duplication', self.coord, coord

    def delete_coord(self, coord):
        if coord in self.coords:
            self.coords.remove(coord)
        #else:
        #    print 'tried to remove absent coord', coord

    def is_satisfied(self):
        # if True cannot be connected to
        ret = False
        if self.is_end():
            if self.coord_count() == 1:
                #if self.used_edge_count == 1:
                ret = True
        else:
            if self.coord_count() == 2:
                #if self.used_edge_count == 2:
                ret = True
        return ret

    def next_coord(self, done):
        """
        previous coords in done
        we want to chain to the next one
        """
        ret = ()
        for coord in self.coords:
            if coord not in done:
                ret = coord
                break
        return ret

    """
    def print_me(self):
        print self.coord, self.has_end_value, self.used_edge_count
    """


class SPath(object):
    """
    A solver path is used by the solver and hints.
    It contains the first and last coordinates of a path
    Using an MVertex function we can chain from left to right.
    """
    def __init__(self, vertex_dic):
        self.vertex_dic = vertex_dic
        self.left = ()
        self.right = ()
        self.coords = set([])
        self.value = None
        self.end_count = 0

    def add_coord(self, coord):
        if coord in self.coords:
            #print 'add_coord duplicate', coord, self.coords
            pass
        else:
            self.coords.add(coord)
            vertex = self.vertex_dic[coord]
            if vertex.is_end():
                self.value = vertex.value
                self.end_count += 1

    def update_coords(self):
        end_count = 0
        if self.left:
            vertex = self.vertex_dic[self.left]
            done = set([])
            while True:
                if vertex.is_end():
                    end_count += 1
                done.add(vertex.coord)
                next_coord = vertex.next_coord(done)
                if not next_coord:
                    break
                else:
                    vertex = self.vertex_dic[next_coord]
            self.coords = done
            self.end_count = end_count

    def coord_count(self):
        return len(self.coords)

    def set_left(self, coord):
        self.left = coord

    def set_right(self, coord):
        self.right = coord

    def update_end(self, new_vertex):
        """
        new_vertex.coord must be 1,1 away from the first or last vertex
        """

        # first?
        if not self.left:
            self.left = new_vertex.coord
            self.right = new_vertex.coord
        else:
            if self.left in new_vertex.coords:
                self.left = new_vertex.coord
            else:
                self.right = new_vertex.coord

    def is_consistent(self):
        ret = True
        done = set([])
        vertex = self.vertex_dic[self.left]
        end_count = 0
        while True:
            if vertex.is_end():
                end_count += 1
            done.add(vertex.coord)
            next_coord = vertex.next_coord(done)
            if not next_coord:
                break
            else:
                vertex = self.vertex_dic[next_coord]
        if self.end_count != end_count:
            #print 'end_count mismatch', self.end_count, end_count
            ret = False
        if self.right not in done:
            #print 'SP not consistent', self.left, self.right, done
            ret = False
        if self.left == self.right and len(self.coords) > 1:
            ret = False
        #if not ret:
        #    self.print_me()
        #    exit(3)
        return ret

    def has_coord(self, coord):
        ret = False
        if coord in self.coords:
            ret = True
        return ret

    def leading_vertex(self, end_index):
        ret = None
        if end_index == 0:
            if self.left:
                ret = self.vertex_dic[self.left]
        elif end_index == 1:
            if self.right:
                ret = self.vertex_dic[self.right]
        return ret

    def has_end(self):
        """
        Need to know if path has at least one end
        """
        return self.left or self.right

    def is_finished(self):
        return self.end_count == 2

    def print_me(self):
        pass
    """
        print 'SPath start', self.left, self.right, self.value, self.end_count, self.coords

        if not self.left:
            return
        done = []
        vertex = self.vertex_dic[self.left]

        while True:
            done.append(vertex.coord)
            print vertex.coord, vertex.coords
            next_coord = vertex.next_coord(done)
            if not next_coord:
                break
            else:
                vertex = self.vertex_dic[next_coord]
    """


class Rat(object):
    """
    A random path generator
    """
    def __init__(self, width, height, used, coord, value):
        self.width = width
        self.height = height
        self.used = used
        self.used.append(coord)
        self.coords = [coord]
        self.value = value
        self.oob = []
        self.directions_tried = {}
        self.direction = ()
        self.direction_prev = ()
        self.coord = coord
        self.finished = False
        self.direction_indices = list(range(4))

    def next_direction(self):
        directions = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        self.direction = ()
        if len(self.directions_tried) < 4:
            if self.direction_prev:
                self.direction = self.direction_prev
                self.directions_tried[self.direction] = True
            else:
                random.shuffle(self.direction_indices)
                for item in self.direction_indices:
                    if directions[item] not in self.directions_tried:
                        self.direction = directions[item]
                        self.directions_tried[self.direction] = True
                        break

    def in_grid(self, x, y):
        return x > -1 and x < self.width and\
            y > -1 and y < self.height

    def get_next_coord(self):
        self.coord = ()
        current = self.coords[-1]
        while True:
            self.next_direction()
            if self.direction:
                next_coord = list(current)
                next_coord[0] += self.direction[0]
                next_coord[1] += self.direction[1]
                if self.in_grid(next_coord[0], next_coord[1]):
                    tmp = tuple(next_coord)
                    if tmp not in self.oob and tmp not in self.used:
                        self.coord = tmp
                        self.directions_tried = {}
                        self.used.append(tmp)
                        self.direction_prev = self.direction
                        break
                    else:
                        self.direction_prev = ()
                else:
                    self.direction_prev = ()
            else:
                self.finished = True
                break

    def update_oob(self):
        oob_directions = {(0, 1): [(-1, -1), (1, -1)],
                          (0, -1): [(-1, 1), (1, 1)],
                          (1, 0): [(-1, -1), (-1, 1)],
                          (-1, 0): [(1, -1), (1, 1)]}
        oob_one = {(0, 1): [(0, -2), (-1, -1), (1, -1), (-1, -2), (1, -2)],
                   (0, -1): [(0, 2), (-1, 1), (1, 1), (-1, 2), (1, 2)],
                   (1, 0): [(-2, 0), (-1, -1), (-1, 1), (-2, -1), (-2, 1)],
                   (-1, 0): [(2, 0), (1, -1), (1, 1), (2, -1), (2, 1)]}

        if self.coord:
            if not self.oob:
                plus = oob_one[self.direction]
                for item in range(5):
                    tmp = list(self.coord)
                    tmp[0] += plus[item][0]
                    tmp[1] += plus[item][1]
                    self.oob.append(tuple(tmp))
            else:
                plus = oob_directions[self.direction]
                for item in range(2):
                    tmp = list(self.coord)
                    tmp[0] += plus[item][0]
                    tmp[1] += plus[item][1]
                    self.oob.append(tuple(tmp))

    def extend(self):
        self.get_next_coord()
        if self.coord:
            self.coords.append(self.coord)
            self.update_oob()

    def count_corners(self):
        """
        A simple puzzle scoring metric
        """
        corners = 0
        directions = []
        for item in range(1, len(self.coords)):
            prev = self.coords[item - 1]
            current = self.coords[item]
            if prev[0] == current[0]:
                directions.append(0)
            else:
                directions.append(1)
        for item in range(1, len(directions)):
            if directions[item - 1] != directions[item]:
                corners += 1
        return corners


class Model(object):
    """
    Numberlink Puzzle.

    Not entirely happy about how this is done.
    We have two types of object: vertices and edges (pairs of adjacent vertices)
    and are storing and updating both as we go along. Normally would prefer
    to store only one object and use it to derive everything else. However,
    we only use vertices for solving and while the stored vertices are always
    correct (ie correspond to vertices in the solution), edges can be placed
    by the user and may be incorrect. The solved vertices are stored in a list
    of objects named spaths.
    Though we set out using Dijkstra type algorithms to find solutions it
    got horribly complicated and offered no obvious way to provide simple
    hints for the user. But we persevered and managed to create puzzles which
    can be solved by simple incremental steps which, once pointed out, should
    be understandable to players. Complicated code deleted.
    """
    def __init__(self, model_data):
        self.model_data = model_data
        self.width = None
        self.height = None
        self.score = None
        self.nvs = []
        self.vertex_dic = {}
        self.status = True
        self.bad_edges = []
        self.errors = []
        self.spaths = []
        self.hint = []
        self.progress = False
        self.path = None
        self.generating = False
        self.rats = []
        self.used = []
        self.rat_count = None

    def check(self):
        return
        for coord, vertex in list(self.vertex_dic.items()):
            if not vertex.status:
                self.status = False
                if not self.generating:
                    PzlG.logger.logger.info("check: bad vertex " +
                                            str(coord))
                    exit(5)
        for spath in self.spaths:
            if not spath.is_consistent():
                #print 'end_count error'
                #spath.print_me()
                self.status = False
                #exit(5)

        for sp0, spath_0 in enumerate(self.spaths):
            for sp1, spath_1 in enumerate(self.spaths):
                if sp1 != sp0:
                    if spath_0.coords.intersection(spath_1.coords):
                        self.status = False

    def get_puzzle(self, puzzle_number):
        puzzle_data = self.model_data.get_puzzle(puzzle_number)
        PzlG.logger.logger.info("get_puzzle " +
                                str(puzzle_number))
        self.width = puzzle_data[1]
        self.height = puzzle_data[2]
        self.score = puzzle_data[0]
        item = 3
        for y in range(self.height):
            for x in range(self.width):
                vertex = NVertex(x, y, puzzle_data[item])
                self.vertex_dic[(x, y)] = vertex
                item += 1
        self.init_spaths()
        self.add_edges()
        self.add_neighbours()

    def init_spaths(self):
        self.spaths = []
        for coord, vertex in list(self.vertex_dic.items()):
            if vertex.is_end():
                new_path = SPath(self.vertex_dic)
                new_path.add_coord(coord)
                new_path.update_end(vertex)
                self.spaths.append(new_path)

    def print_spaths(self):
        for spath in self.spaths:
            spath.print_me()

    def get_neighbours(self, coord):
        x = coord[0]
        y = coord[1]
        neighbours = []
        # up
        if y > 0:
            new_coord = x, y - 1
            neighbours.append(new_coord)
        # down
        if y < self.height - 1:
            new_coord = x, y + 1
            neighbours.append(new_coord)
        # left
        if x > 0:
            new_coord = x - 1, y
            neighbours.append(new_coord)
        # right
        if x < self.width - 1:
            new_coord = x + 1, y
            neighbours.append(new_coord)
        return neighbours

    def add_neighbours(self):
        for y in range(self.height):
            for x in range(self.width):
                vertex = self.vertex_dic[x, y]
                vertex.neighbours = self.get_neighbours((x, y))

    def add_edges(self):
        for y in range(self.height):
            for x in range(self.width):
                value = self.vertex_dic[(x, y)].value
                if y > 0:
                    tmp = self.vertex_dic[(x, y-1)].value
                    if value == tmp:
                        self.vertex_dic[(x, y)].add_edge((x, y-1))
                        self.vertex_dic[(x, y)].add_path_coord((x, y-1))
                if y < self.height - 1:
                    tmp = self.vertex_dic[(x, y+1)].value
                    if value == tmp:
                        self.vertex_dic[(x, y)].add_edge((x, y+1))
                        self.vertex_dic[(x, y)].add_path_coord((x, y+1))
                if x > 0:
                    tmp = self.vertex_dic[(x-1, y)].value
                    if value == tmp:
                        self.vertex_dic[(x, y)].add_edge((x-1, y))
                        self.vertex_dic[(x, y)].add_path_coord((x-1, y))
                if x < self.width - 1:
                    tmp = self.vertex_dic[(x+1, y)].value
                    if value == tmp:
                        self.vertex_dic[(x, y)].add_edge((x+1, y))
                        self.vertex_dic[(x, y)].add_path_coord((x+1, y))

    def update_edges(self, coords, add):
        """
        A user edit is sent as an edge ie a pair of coords, and flag 'add'.
        Add == True means append, False means delete.
        We append it if new or delete it accordingly.

        When adding what we do depends on whether or not the edge is correct.
        If there are no present errors and the edge is correct
        we add it to MVertex.coords
        If there are present errors, whether or not the edge is correct
        we add it to Model.bad_coords
        If the edge is incorrect
        we add it to Model.bad_coords

        When deleting we must delete from the appropriate copy.
        If there are no present errors and the edge is correct
        we delete from MVertex.coords
        If there are errors we delete from Model.bad_coords
        """

        def taxicab_distance(key_0, key_1):
            return int(abs(key_0[0] - key_1[0]) +
                       abs(key_0[1] - key_1[1]))

        # keep edge vertices in order: nearest origin first
        dist_0 = taxicab_distance((0, 0), coords[0])
        dist_1 = taxicab_distance((0, 0), coords[1])
        if dist_0 > dist_1:
            coords = list(reversed(coords))
        if add:
            self.add_edge(coords)
        else:
            self.remove_edge(coords)

    def errors_exist(self):
        return len(self.bad_edges) > 0

    def reset_errors(self):
        self.bad_edges = []

    def is_finished(self):
        ret = True
        for spath in self.spaths:
            if not spath.is_finished():
                ret = False
                break
        return ret

    def is_consistent(self):
        self.status = len(self.bad_edges) == 0
        return self.status

    def get_spath(self, coord_in):
        """
        Find the spath for coord_in.
        """
        ret = None
        for spath in self.spaths:
            if spath.has_coord(coord_in):
                ret = spath
                break
        return ret

    def in_paths(self, paths, coord):
        """
        Is coord in any of paths?
        """
        ret = []
        for path in paths:
            if path.has_coord(coord):
                ret = [path]
                break
        return ret

    def is_u_turn(self, spath, leading_coord, new_coord):
        """
        The only vertex from this path allowed distance 1 away
        from new_vertex is leading_vertex (ie other end of edge)
        For each vertex in path get its immediate neighbours.
        """

        ret = False
        neighbours = self.vertex_dic[new_coord].neighbours
        for neighbour in neighbours:
            if neighbour != leading_coord and\
               spath.has_coord(neighbour):
                ret = True
                break
        return ret

    def complete_paths(self):
        """
        Look for pairs of adjacent vertices from the same path.
        """

        def taxicab_distance(key_0, key_1):
            return int(abs(key_0[0] - key_1[0]) +
                       abs(key_0[1] - key_1[1]))

        ret = []
        for sp0, spath_0 in enumerate(self.spaths):
            if not spath_0.is_finished() and spath_0.value is not None:
                for spath_1 in self.spaths[sp0 + 1:]:
                    if not spath_1.is_finished() and\
                       spath_0.value == spath_1.value:
                        dist = taxicab_distance(spath_0.left, spath_1.left)
                        if dist == 1:
                            ret = [spath_0.left, spath_1.left]
                            break
                        dist = taxicab_distance(spath_0.left, spath_1.right)
                        if dist == 1:
                            ret = [spath_0.left, spath_1.right]
                            break
                        dist = taxicab_distance(spath_0.right, spath_1.left)
                        if dist == 1:
                            ret = [spath_0.right, spath_1.left]
                            break
                        dist = taxicab_distance(spath_0.right, spath_1.right)
                        if dist == 1:
                            ret = [spath_0.right, spath_1.right]
                            break
        return ret

    def try_extending(self):
        """
        Can we extend an existing spath.
        """
        for spath in self.spaths:
            if not spath.is_finished():
                if spath.coord_count() > 1:
                    ret = self.try_extending_00(spath)
                    if ret:
                        self.save_hint(ret)
                        self.progress = True
                        break
                    ret = self.try_extending_01(spath)
                    if ret:
                        self.save_hint(ret)
                        self.progress = True
                        break
                else:
                    ret = self.try_extending_02(spath)
                    if ret:
                        self.save_hint(ret)
                        self.progress = True
                        break
        if not self.progress:
            ret = self.complete_paths()
            if ret:
                self.save_hint(ret)
                self.progress = True
        if not self.progress:
            self.analyse_access()

    def analyse_access(self):
        """
        Examine each unused vertices to see if only one value
        can pass through it.
        """
        for coord, vertex in list(self.vertex_dic.items()):
            if not vertex.is_used():
                # copy the neighbours
                neighbours = list(vertex.neighbours)
                dels = []
                for neighbour in neighbours:
                    if self.vertex_dic[neighbour].is_satisfied():
                        dels.append(neighbour)
                for neighbour in dels:
                    neighbours.remove(neighbour)
                # have now removed any satisfied neighbours
                # now count neighbours for each value path
                neighbour_paths_dic = {}
                for neighbour in neighbours:
                    in_path = self.in_paths(self.spaths, neighbour)
                    if in_path:
                        neighbour_paths_dic.setdefault(in_path[0].value,
                                                       []).append(neighbour)
                if len(neighbours) < 4:
                    # If > 1 neighbours are in same value paths
                    # we can connect to them
                    for key, path_neighbours in\
                        list(neighbour_paths_dic.items()):
                        if key is not None and len(path_neighbours) > 1:
                            # these three vertices must be joined
                            # but we only want to serve up one edge
                            # check if any vertex is in a spath
                            coords = [coord]
                            coords.append(path_neighbours[0])
                            self.save_hint(coords)
                            self.progress = True
                            break
            if self.progress:
                break

    def try_extending_00(self, spath):
        """
        Find all possibilities for each end.
        If only 1, can extend, do it.
        """
        ret = []
        for end_index in range(2):
            new = []
            leading_vertex = spath.leading_vertex(end_index)
            leading_coord = leading_vertex.coord
            # might be an end value
            if not leading_vertex.is_satisfied():
                new_coords = leading_vertex.neighbours
                for new_coord in new_coords:
                    if not self.blocked(spath, leading_vertex,
                                        leading_coord, new_coord):
                        new.append(new_coord)
            if len(new) == 1:
                # only one extension possible, so do it
                new_coord = new[0]
                ret = [leading_coord, new_coord]
                break
        return ret

    def try_extending_01(self, spath):
        """
        Probably a rare event, but check to see if the end is
        only 1 away from a path with the same value.
        If so, do it.
        """

        ret = []
        for end_index in range(2):
            leading_vertex = spath.leading_vertex(end_index)
            leading_coord = leading_vertex.coord
            # might be an end value
            if not leading_vertex.is_satisfied():
                new_coords = leading_vertex.neighbours
                for new_coord in new_coords:
                    spath_1 = self.get_spath(new_coord)
                    if spath != spath_1:
                        if self.vertex_dic[new_coord].is_end() and\
                           self.vertex_dic[new_coord].value ==\
                           spath.value:
                            # must be a join
                            ret = [leading_coord, new_coord]
                            break
                if ret:
                    break

        return ret

    def try_extending_02(self, spath):
        """
        Single valued vertex
        Cannot connect to other valued paths
        or to unvalued paths which surround it.
        """
        ret = []
        vertex = self.vertex_dic[spath.left]
        value = vertex.value
        coord = vertex.coord
        neighbours = list(vertex.neighbours)
        neighbour_paths_dic = {}
        dels = []
        for neighbour in neighbours:
            in_path = self.in_paths(self.spaths, neighbour)
            if in_path:
                if in_path[0].value is None:
                    neighbour_paths_dic.setdefault(in_path[0], []).append(neighbour)
                elif in_path[0].value != value:
                    dels.append(neighbour)
        # remove neighbours from other valued paths
        for neighbour in dels:
            neighbours.remove(neighbour)
        # If > 1 neighbours are in another spath
        # we cannot connect to them
        for key, path_neighbours in list(neighbour_paths_dic.items()):
            if len(path_neighbours) > 1:
                for neighbour in path_neighbours:
                    neighbours.remove(neighbour)

        if len(neighbours) == 1:
            # only one extension possible, so do it
            new_coord = neighbours[0]
            ret = [coord, new_coord]
        return ret

    def blocked(self, spath_0, leading_vertex, leading_coord, new_coord):
        ret = False
        if self.vertex_dic[new_coord].is_satisfied():
            # vertex already used
            ret = True
        elif self.is_u_turn(spath_0, leading_coord,
                            new_coord):
            # would create u-turn
            ret = True

        else:
            spath_1 = self.get_spath(new_coord)
            if spath_1 is not None:

                # ie new_coord is in a path

                if self.is_close_to(spath_0,
                                    leading_vertex,
                                    spath_1):
                    # is loop back
                    ret = True

                elif spath_1.end_count > 0:
                    #elif spath_1.has_end():

                    if spath_1.end_count == 2:
                        #if spath_1.is_finished():
                        # other path complete (shouldn't get here!)
                        ret = True
                    elif spath_0.value is not None and\
                         spath_1.value is not None and\
                         spath_0.value != spath_1.value:
                        # other path has different value
                        ret = True
            elif self.vertex_dic[new_coord].is_end():
                # vertex is unused end
                if spath_0.value is not None and\
                   spath_0.value != self.vertex_dic[new_coord].value:
                    # has different value
                    ret = True
        return ret

    def is_close_to(self, spath_0, end_vertex_0, spath_1):
        """
        Want to forbid join of spaths that are adjacent but
        with different values.
        """
        ret = False
        all_neighbours = {}

        for coord in spath_0.coords:
            vertex = self.vertex_dic[coord]
            if vertex != end_vertex_0:
                for item in vertex.neighbours:
                    all_neighbours.update({item: True})
        for coord in spath_1.coords:
            if coord in all_neighbours:
                ret = True
                break
        return ret

    def blocked_1(self, vertex_0, vertex_1):
        ret = False
        if vertex_1.is_satisfied():
            # vertex already used
            ret = True
        else:
            if vertex_1.is_end():
                if vertex_0.value != vertex_1.value:
                    ret = True
            else:
                # 2019-10-16
                #if vertex_1.used_edge_count == 2:
                #    ret = True
                spath_1 = self.get_spath(vertex_1.coord)
                if spath_1 is not None:
                    if self.is_close_to_1(spath_1, vertex_0.coord):
                        ret = True
        return ret

    def is_close_to_1(self, spath_0, coord_in):
        """
        Want to forbid join of spaths that are adjacent
        """
        ret = False

        for coord in spath_0.coords:
            if coord != spath_0.left and coord != spath_0.right:
                vertex = self.vertex_dic[coord]
                for neighbour in vertex.neighbours:
                    if neighbour == coord_in:
                        ret = True
                        break
            if ret:
                break
        return ret

    def blocked_2(self, coord, new_coord):
        # coord is a would be focus, new_coord is a neighbour
        ret = False
        if self.vertex_dic[new_coord].is_satisfied():

            # vertex already satisfied
            ret = True
        else:
            if self.vertex_dic[new_coord].coord_count() == 1:
                # vertex has one edge
                # need to check that coord would not make u-turn
                spath_1 = self.get_spath(new_coord)
                if spath_1 is not None:
                    if self.is_u_turn(spath_1, new_coord,
                                      coord):
                        # would create u-turn
                        ret = True
        return ret

    def new_foci(self):
        """
        Find new foci. ie vertices that must be traversed
        in particular directions because of lack of choice.
        """
        for coord, vertex in list(self.vertex_dic.items()):
            if vertex.coord_count() == 0:
                # an unused vertex

                neighbours = vertex.neighbours

                if len(neighbours) == 2:
                    if not vertex.is_end():
                        coord_0 = neighbours[0]
                        self.save_hint([coord, coord_0])
                        self.progress = True
                        break
                    else:
                        # end on corner
                        # are neighbours blocked?
                        new = []
                        for neighbour in neighbours:
                            if not self.blocked_2(coord, neighbour):
                                if self.vertex_dic[neighbour].is_end():
                                    if self.vertex_dic[neighbour].value\
                                       == self.vertex_dic[coord].value:
                                        new.append(neighbour)
                                else:
                                    new.append(neighbour)
                        if len(new) == 1:
                            self.save_hint([coord, new[0]])
                            self.progress = True
                            break
                else:

                    # are neighbours blocked?

                    new = []
                    for neighbour in neighbours:
                        if not self.blocked_2(coord, neighbour):
                            new.append(neighbour)
                    if len(new) < 4:
                        if not vertex.is_end():
                            if len(new) == 2:
                                self.save_hint([coord, new[0]])
                                self.progress = True
                                break
                        else:
                            if len(new) == 1:
                                self.save_hint([coord, new[0]])
                                self.progress = True
                                break
                    if vertex.is_end():
                        new = []
                        for neighbour in neighbours:
                            vertex_1 = self.vertex_dic[neighbour]
                            if not self.blocked_1(vertex, vertex_1):
                                new.append(neighbour)
                        if len(new) == 1:
                            self.save_hint([coord, new[0]])
                            self.progress = True
                            break

    def save_hint(self, coords):
        self.hint = coords

    def extend_spath(self, spath, coords):
        if spath.has_coord(coords[0]):
            vertex = self.vertex_dic[coords[0]]
            vertex.add_coord(coords[1])
            spath.add_coord(coords[1])
            vertex = self.vertex_dic[coords[1]]
            vertex.add_coord(coords[0])
            spath.update_end(vertex)
        else:
            vertex = self.vertex_dic[coords[1]]
            vertex.add_coord(coords[0])
            spath.add_coord(coords[0])
            vertex = self.vertex_dic[coords[0]]
            vertex.add_coord(coords[1])
            spath.update_end(vertex)

    def add_edge(self, coords):
        """
        Add user edge defined as pair of coords
        """

        vertex_0 = self.vertex_dic[coords[0]]
        good_edge = vertex_0.good_edge(coords[1])
        if self.errors_exist():
            if coords not in self.bad_edges:
                self.bad_edges.append(coords)
        else:
            if good_edge:
                spath_0 = self.get_spath(coords[0])
                spath_1 = self.get_spath(coords[1])
                if spath_0 is None and spath_1 is None:
                    # new path
                    spath = SPath(self.vertex_dic)
                    vertex = self.vertex_dic[coords[0]]
                    vertex.add_coord(coords[1])
                    spath.add_coord(coords[1])
                    spath.update_end(vertex)
                    vertex = self.vertex_dic[coords[1]]
                    vertex.add_coord(coords[0])
                    spath.add_coord(coords[0])
                    spath.update_end(vertex)
                    self.spaths.append(spath)
                elif spath_0 is not None and spath_1 is not None:
                    jtype = self.get_join_type(spath_0,
                                               spath_1, coords)
                    self.join_spaths(spath_0, spath_1, jtype)
                elif spath_0 is not None:
                    self.check()
                    # extension
                    self.extend_spath(spath_0, coords)
                    self.check()
                elif spath_1 is not None:
                    self.check()
                    # extension
                    self.extend_spath(spath_1, coords)
                    self.check()
            else:
                if coords not in self.bad_edges:
                    self.bad_edges.append(coords)

    def break_spath(self, coords):
        # must split spath but keep all vertices
        spath = self.get_spath(coords[0])

        done = []
        vertex = self.vertex_dic[spath.left]
        while True:
            done.append(vertex.coord)
            next_coord = vertex.next_coord(done)
            if not next_coord:
                break
            else:
                if next_coord in coords:
                    break
                else:
                    vertex = self.vertex_dic[next_coord]
        if next_coord == coords[0]:
            new_0 = [spath.left, coords[0]]
            new_1 = [coords[1], spath.right]
        else:
            new_0 = [spath.right, coords[0]]
            new_1 = [spath.left, coords[1]]
        vertex_0 = self.vertex_dic[coords[0]]
        vertex_1 = self.vertex_dic[coords[1]]
        vertex_0.delete_coord(coords[1])
        vertex_1.delete_coord(coords[0])
        self.spaths.remove(spath)
        spath = SPath(self.vertex_dic)
        spath.set_left(new_0[0])
        spath.set_right(new_0[1])
        spath.update_coords()
        self.spaths.append(spath)
        spath = SPath(self.vertex_dic)
        spath.set_left(new_1[0])
        spath.set_right(new_1[1])
        spath.update_coords()
        self.spaths.append(spath)
        self.check()

    def do_remove_edge(self, spath, del_coord, new_end, direction):
        vertex = self.vertex_dic[new_end]
        vertex.delete_coord(del_coord)
        if direction == Sgg.Left:
            spath.set_left(new_end)
        else:
            spath.set_right(new_end)
        vertex = self.vertex_dic[del_coord]
        vertex.delete_coord(new_end)
        spath.update_coords()
        self.check()

    def remove_edge(self, coords):
        if coords in self.bad_edges:
            self.bad_edges.remove(coords)
        else:
            # good edge to remove?
            spath = self.get_spath(coords[0])
            if spath is not None:
                # internal or end?
                if coords[0] == spath.left:
                    del_coord = coords[0]
                    new_end = coords[1]
                    self.do_remove_edge(spath, del_coord, new_end,
                                        Sgg.Left)
                elif coords[0] == spath.right:
                    del_coord = coords[0]
                    new_end = coords[1]
                    self.do_remove_edge(spath, del_coord, new_end,
                                        Sgg.Right)
                elif coords[1] == spath.left:
                    del_coord = coords[1]
                    new_end = coords[0]
                    self.do_remove_edge(spath, del_coord, new_end,
                                        Sgg.Left)
                elif coords[1] == spath.right:
                    del_coord = coords[1]
                    new_end = coords[0]
                    self.do_remove_edge(spath, del_coord, new_end,
                                        Sgg.Right)
                else:
                    self.break_spath(coords)
            else:
                # user must have right clicked on non-existent edge
                pass

    def update_edges(self, coords, add):
        """
        A user edit is sent as an edge ie a pair of coords, and flag 'add'.
        Add == True means append, False means delete.
        We append it if new or delete it accordingly.

        When adding what we do depends on whether or not the edge is correct.
        If there are no present errors and the edge is correct
        we add it to MVertex.coords
        If there are present errors, whether or not the edge is correct
        we add it to Model.bad_coords
        If the edge is incorrect
        we add it to Model.bad_coords

        When deleting we must delete from the appropriate copy.
        If there are no present errors and the edge is correct
        we delete from MVertex.coords
        If there are errors we delete from Model.bad_coords
        """

        def taxicab_distance(key_0, key_1):
            return int(abs(key_0[0] - key_1[0]) +
                       abs(key_0[1] - key_1[1]))

        # keep edge vertices in order: nearest origin first
        dist_0 = taxicab_distance((0, 0), coords[0])
        dist_1 = taxicab_distance((0, 0), coords[1])
        if dist_0 > dist_1:
            coords = list(reversed(coords))
        if add:
            self.add_edge(coords)
        else:
            self.remove_edge(coords)

    def do_join(self, new_left, new_right, join_0, join_1):
        spath = SPath(self.vertex_dic)
        spath.set_left(new_left)
        spath.set_right(new_right)
        vertex = self.vertex_dic[join_0]
        vertex.add_coord(join_1)
        vertex = self.vertex_dic[join_1]
        vertex.add_coord(join_0)
        spath.update_coords()
        for coord in spath.coords:
            vertex = self.vertex_dic[coord]
            if vertex.is_end():
                spath.value = vertex.value
                break
        return spath

    def join_spaths(self, spath_0, spath_1, jtype):
        """
        Have to make the links, ie update coords for the joining vertices,
        Create new spath set left and right, and possibly value.
        Then delete old spaths.
        """
        left_0 = spath_0.left
        right_0 = spath_0.right
        left_1 = spath_1.left
        right_1 = spath_1.right
        #print 'join_spaths', jtype, left_0, right_0, left_1, right_1
        self.check()
        if jtype == 0:
            spath = self.do_join(right_1, right_0, left_0, left_1)
        elif jtype == 1:
            spath = self.do_join(left_1, right_0, left_0, right_1)
        elif jtype == 2:
            spath = self.do_join(left_0, right_1, left_1, right_0)
        elif jtype == 3:
            spath = self.do_join(left_1, left_0, right_1, right_0)

        try:
            self.spaths.remove(spath_0)
        except ValueError:
            #print 'remove error 0'
            pass
        try:
            self.spaths.remove(spath_1)
        except ValueError:
            #print 'remove error 1'
            pass

        self.spaths.append(spath)
        self.check()

    def get_join_type(self, spath_0, spath_1, coords):
        """
        jtype 0: left_0 == left_1
        jtype 1: left_0 == right_1
        jtype 2: left_1 == right_0
        jtype 3: right_0 == right_1
        """
        if spath_0.left == coords[0]:
            if spath_1.left == coords[1]:
                jtype = 0
            elif spath_1.right == coords[1]:
                jtype = 1
        elif spath_0.right == coords[0]:
            if spath_1.right == coords[1]:
                jtype = 3
            elif spath_1.left == coords[1]:
                jtype = 2
        return jtype

    def add_vertices(self, coords):
        self.check()
        spath_0 = self.get_spath(coords[0])
        spath_1 = self.get_spath(coords[1])
        if spath_0 is None and spath_1 is None:
            # new path
            spath = SPath(self.vertex_dic)
            vertex = self.vertex_dic[coords[0]]
            vertex.add_coord(coords[1])
            spath.add_coord(coords[1])
            spath.update_end(vertex)
            vertex = self.vertex_dic[coords[1]]
            vertex.add_coord(coords[0])
            spath.add_coord(coords[0])
            spath.update_end(vertex)
            self.spaths.append(spath)
            self.check()
        elif spath_1 is None:
            # extension of spath_0
            vertex = self.vertex_dic[coords[0]]
            vertex.add_coord(coords[1])
            spath_0.add_coord(coords[1])
            vertex = self.vertex_dic[coords[1]]
            vertex.add_coord(coords[0])
            spath_0.update_end(vertex)
            self.check()
        elif spath_0 is None:
            # extension of spath_1
            vertex = self.vertex_dic[coords[1]]
            vertex.add_coord(coords[0])
            spath_1.add_coord(coords[0])
            vertex = self.vertex_dic[coords[0]]
            vertex.add_coord(coords[1])
            spath_1.update_end(vertex)
            self.check()
        else:
            # join
            jtype = self.get_join_type(spath_0,
                                       spath_1, coords)
            self.join_spaths(spath_0, spath_1, jtype)

    def is_in_path(self, coords):
        vertex_0 = self.vertex_dic[coords[0]]
        vertex_1 = self.vertex_dic[coords[1]]
        in_path = False
        if vertex_0.coord in vertex_1.path_coords:
            in_path = True
        return in_path

    def check_hint(self):
        if self.hint:
            coords = self.hint
            if not self.is_in_path(coords):
                strargs = ' ' + str(coords[0]) + ',' + str(coords[1]) + ' '
                PzlG.logger.logger.error("give_hint error" + strargs)
                self.hint = []


    def apply_hint(self):
        if self.hint:
            self.check_hint()
            if self.hint:
                self.add_vertices(self.hint)
                self.check()

    def do_hint(self):
        self.hint = []
        self.progress = False
        self.check()
        if self.status:
            self.try_extending()
            if not self.progress:
                self.new_foci()

    def solver_1(self):
        self.progress = False
        self.check()
        if self.status:
            self.try_extending()
            if self.progress:
                self.apply_hint()
            else:
                self.new_foci()
                if self.progress:
                    self.apply_hint()

    def solver(self):
        self.status = True
        self.progress = True
        while self.progress:
            if not self.is_finished():
                self.solver_1()
                if not self.status:
                    break
            else:
                break

    def get_grid(self):
        self.vertex_dic = {}
        for rat_index in range(self.rat_count):
            rat = self.rats[rat_index]
            value = -rat.value
            coord = rat.coords[0]
            x = coord[0]
            y = coord[1]
            vertex = NVertex(x, y, value)
            self.vertex_dic[coord] = vertex
            coord = rat.coords[-1]
            x = coord[0]
            y = coord[1]
            vertex = NVertex(x, y, value)
            self.vertex_dic[coord] = vertex
            value = -value
            for coord in rat.coords[1:-1]:
                x = coord[0]
                y = coord[1]
                vertex = NVertex(x, y, value)
                self.vertex_dic[coord] = vertex
        self.init_spaths()
        self.add_edges()
        self.add_neighbours()

    def find_holes(self):
        holes = []
        for y in range(self.height):
            for x in range(self.width):
                if (x, y) not in self.used:
                    holes.append([(x, y)])
        return holes

    def make_puzzle(self, score):
        puzzle = [score, self.width, self.height]
        for y in range(self.height):
            for x in range(self.width):
                vertex = self.vertex_dic[x, y]
                value = vertex.value
                if vertex.is_end():
                    value = -value
                puzzle.append(value)
        return puzzle

    def diversity_1(self, width, height):
        ret = True
        max_frac = 0.9
        max_frac = 0.99
        x1 = self.width - width + 1
        y1 = self.height - height + 1
        for ys in range(y1):
            for xs in range(x1):
                div_dic = {}
                for y in range(height):
                    for x in range(width):
                        value = self.vertex_dic[xs + x, ys + y].value
                        div_dic.setdefault(value, []).append(value)
                counts = [0] * 10
                for key, item in list(div_dic.items()):
                    counts[key] += len(item)
                counts = sorted(counts)
                frac = (counts[-1] + counts[-2]) / float(width * height)
                if frac > max_frac:
                    ret = False
                    break
            if not ret:
                break
        return ret

    def diversity(self):
        width = 5
        height = 5
        ret = self.diversity_1(width, height)
        if ret:
            width = 4
            height = 7
            ret = self.diversity_1(width, height)
            if ret:
                width = 7
                height = 4
                ret = self.diversity_1(width, height)
        return ret

    def generate(self):
        self.generating = True
        self.width = 9
        self.height = 9
        puzzles = []
        min_puzzles = 50
        seed = 4
        random.seed(seed)
        full_grids = 0
        tries = 0
        while True:
            puzzle_count = len(puzzles)
            tries, full_grids = self.generate_0(tries, full_grids, puzzle_count)
            min_turns = int(1.5 * self.rat_count)
            corners = 0
            for rat in self.rats:
                corners += rat.count_corners()

            if corners >= min_turns:
                puzzle = self.make_puzzle(corners)
                puzzles.append(puzzle)
                #print '>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>> puzzle count', len(puzzles)
                if len(puzzles) == min_puzzles:
                    puzzles = sorted(puzzles)
                    filename = str(seed) + '.txt'
                    with open(filename, "w") as fo:
                        rec = ''
                        for puzzle in puzzles:
                            for item in puzzle:
                                rec += str(item)
                                rec += ','
                        fo.write(rec)
                    exit(8)

    def generate_0(self, tries, full_grids, puzzle_count):
        self.vertex_dic = {}
        self.used = []
        self.rats = []
        self.rat_count = random.randint(self.width - 2, self.width)
        while True:
            tries += 1
            if tries % 1000 == 0:
                pass
                #print '#####################', tries, full_grids, puzzle_count
            self.generate_1()

            if not self.find_holes():
                full_grids += 1
                self.get_grid()
                if self.diversity():
                    self.solver()
                    if self.is_finished():
                        break
        return tries, full_grids

    def generate_1(self):
        self.used = []
        self.rats = []

        for rat_index in range(self.rat_count):
            while True:
                coord = (random.randint(0, self.width - 1),
                         random.randint(0, self.height - 1))
                if coord not in self.used:
                    rat = Rat(self.width, self.height,
                              self.used, coord, rat_index + 1)
                    self.rats.append(rat)
                    break
        busy = True
        while busy:
            busy = False
            for rat_index in range(self.rat_count):
                rat = self.rats[rat_index]
                if not rat.finished:
                    rat.extend()
                    busy = True


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.view = View(root, self.settings)
        self.status = False
        self.active = False
        self.hint_status = Sgg.GIVE_HINT
        self.error_detected = False
        self.puzzle_number = None
        puzzle_number = None
        #if len(sys.argv) > 1:
        #    puzzle_number = int(sys.argv[1])
        self.model = Model(self.model_data)
        self.start_game(puzzle_number)

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

    def test(self):
        bad = []
        for puzzle_number in range(self.model_data.puzzle_count):
            #print '##########################', puzzle_number
            self.model = Model(self.model_data)
            self.model.get_puzzle(puzzle_number)
            self.model.solver()
            if not self.model.is_finished():
                bad.append(puzzle_number)

        #print 'bad', bad, len(bad)
        exit(4)

    def start_game(self, puzzle_number):
        self.hint_status = Sgg.GIVE_HINT
        #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.flasher = Flasher(self.view.clock.box.label,
                               self.master, self.settings)
        self.model.get_puzzle(self.puzzle_number)
        self.view.model = self.model
        self.view.make_board()
        self.view.draw_puzzle()
        self.view.game_on()
        self.view.hint_off()
        self.view.thumbs_up()
        self.add_callbacks()
        self.error_detected = False
        self.active = True
        self.view.entry_box.clear()
        self.view.entry_box.write_box(str(self.puzzle_number))
        self.view.update_score_box(self.model.score)
        self.status = False

    def add_callbacks(self):
        self.view.add_menu_callback(self.service_menu)
        self.view.add_toolbar_callback(self.service_toolbar)
        self.view.entry_box.add_callback(self.get_puzzle_number)
        self.view.board.add_callbacks(self.board_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 == 'set_colour':
            choice = args[1]
            self.set_colour(choice)
        elif name == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

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

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

    def board_event(self, event_code, key):
        if self.active:
            PzlG.logger.logger.info("board_event " +
                                    str(event_code) +
                                    ' ' +
                                    str(key))

            coords, add = self.view.board.board_event(event_code,
                                                      key)
            # update visible_edges
            self.model.update_edges(coords, add)
            if self.hint_status == Sgg.APPLY_HINT:
                # have a hint indicator to remove
                self.view.board.delete_hint_blob()
            self.ready_for_hint()
            self.check_finished()

    def board_event(self, event_code, key):
        if self.active:
            PzlG.logger.logger.info("board_event " +
                                    str(event_code) +
                                    ' ' +
                                    str(key))

            coords, add = self.view.board.board_event(event_code,
                                                      key)
            self.model.update_edges(coords, add)
            if self.hint_status == Sgg.APPLY_HINT:
                # have a hint indicator to remove
                self.view.board.delete_hint_blob()
            self.model.check()
            self.check_finished()

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

    def give_hint(self):
        if self.hint_status == Sgg.GIVE_HINT:
            if self.model.is_consistent():
                # get a hint
                self.model.do_hint()
                if self.model.hint:
                    hint_index = 0
                    tmp = self.model.hint[0]
                    if self.model.vertex_dic[tmp].is_end():
                        hint_index = self.model.vertex_dic[tmp].value
                    self.view.hint_on()
                    self.view.board.show_hint_blob(hint_index)
                    self.hint_status = Sgg.APPLY_HINT
            else:
                self.view.thumbs_down()
                self.colour_errors(True)
                self.error_detected = True
        else:
            # apply the current hint
            #self.screen_shot.snap()
            # update model
            self.model.apply_hint()
            # update board
            self.view.board.apply_hint()
            self.ready_for_hint()

    def check_errors(self):
        # have we already detected 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:
            if self.model.errors_exist():
                self.view.thumbs_down()
                self.error_detected = True
                self.colour_errors(True)

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

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

    def tidy_error(self):
        # Check to see if user has already tidied up.
        if not self.model.is_consistent():
            self.colour_errors(False)

        self.error_detected = False
        self.view.thumbs_up()
        self.colour_errors(False)
        self.model.reset_errors()

    def colour_errors(self, colour):
        self.view.board.colour_errors(colour)

    def show_solution(self):
        if self.hint_status == Sgg.APPLY_HINT:
            # have a hint indicator to remove
            self.view.board.delete_hint_blob()
        # clean up any errors
        self.tidy_error()
        self.view.board.draw_solution()
        self.view.game_over()
        self.view.clock_stop()
        self.active = False

    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_colour(self, choice):
        try:
            bg_colour = self.settings.dic[choice]
            result = tkinter.colorchooser.askcolor(bg_colour)
            if result[1] is not None:
                self.settings.dic[choice] = result[1]
                self.start_game(None)
        except KeyError:
            PzlG.logger.logger.error("set_colour " + choice)
        self.start_game(self.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")
