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

# Copyright (C) 2019 Rod Engerstad

# import sys
import random
import tkinter as tk

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


class Sgg(object):
    """
    Game globals
    """
    GIVE_HINT = 0
    APPLY_HINT = 1

    Left = 'L'
    Right = 'R'
    Up = 'U'
    Down = 'D'
    Empty = 'E'
    White = 'W'
    Black = 'B'
    Unused = 'EEE'
    DEBUG = True
    #DEBUG = False
    alg_usage = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]


class Settings(SettingsB):

    def __init__(self):
        SettingsB.__init__(self)
        self.dic = {}
        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()
        self.make_alg_help()

    def make_alg_help(self):
        self.alg_text = [_("White Parallel (WP). Paths through white circles must pass straight through but turn at the preceeding or following vertex. If an unsolved white circle is next to a solved white circle, the path through the unsolved white circle must be parallel to the path through the solved one."), _("White Continuation (WC). Paths through white circles must pass straight through.  If the path from a white circle extends in only one direction, it must also extend in the opposite direction."), _("Black Blocked (BB). Paths through black circles must turn 90 degrees within the black circle and extend in a straight line for at least two vertices either side. If the path from a black circle is blocked in a particular direction the path must extend in the opposite direction. Blocking means, either it is too close to an edge, or it would illegally intersect another path."), _("Black Extension (BE). Paths through black circles must extend in a straight line for at least 2 vertices. If a path from a black circle has only reached the next vertex, it can be extended one more vertex in the same direction."), _("White Blocked (WB). The path through white circles must pass straight through. If the path cannot pass straight through a white circle for at least one vertex on either side it must take the perpendicular direction."), _("White Turn (WT). Paths through white circles must pass straight through but turn at the preceeding or following vertex. If a White circle has two colinear edges on one side it must have a turn one vertex along in the opposite direction."), _("White Pairs (W2) Paths through white circles must pass straight through but turn at the preceeding or following vertex. The path through a pair of adjacent white circles must either pass directly between the two or both must be crossed in the direction perpendicular to their alignment. If one path is impossible, it must be the other."), _("Black Perpendicular (BP). Paths through black circles must turn 90 degrees within the black circle and extend in a straight line for at least two vertices either side. When a Black circle has an edge in only one direction and one of the perpendicular directions is blocked we know the path must extend in the other."), _("Black and White diagonals (BW). Paths through white circles must pass straight through but turn at the preceeding or following vertex. Paths through black circles must turn 90 degrees within the black circle and extend in a straight line for at least two vertices either side. The combined effect of these two rules means that the path through a black circle with two white circles diagonally adjacent on the same side cannot pass between the two white circles but must go in the opposite direction. Otherwise the path through the white circles would be unable to turn."), _("One Way only (OW). If an end without a circle has only one way to extend because all other paths are blocked, it must be the way."), _("Dead End (DE). If the path can only extend in one direction because all other directions lead to dead ends, that must be the way it goes.")]

    def make_help(self):
        self.help_text = _("The object of the game is to find the unique path which passes through the grid without intersecting itself and while obeying the following special rules for crossing the black and white circles. The path crossing a white circle must pass straight through but it must turn at the previous, or the next vertex, or both. The path crossing a black circle must turn through 90 degrees within the circle and extend in straight lines for at least two vertices both before and after the circle. 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 masyu 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 extension is 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 an orange blob. 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. If a hint is displayed a two letter code for the hint will replace the text of the clock until the hint is applied. 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(
            _('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.callback = None
        self.canvas.tag_bind(self.grid_line, "<ButtonRelease-1>", self.command)
        self.canvas.tag_bind(self.grid_line, "<ButtonRelease-3>", self.command)
        self.coords = (v0.coord, v1.coord)

    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 = model.vertex_dic
        self.images = images
        self.widget_dic = {}
        self.width = None
        self.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.width = self.model.width
        self.height = self.model.height
        self.canvas_width = 2 * self.grid_margin + self.grid_unit *\
                            (self.width - 1)
        self.canvas_height = 2 * self.grid_margin + self.grid_unit *\
                             (self.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'
            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.height):
            for x in range(self.width):
                v0 = self.vertex_dic[(x, y)]
                if x + 1 < self.width:
                    v1 = self.vertex_dic[(x+1, y)]
                    self.make_edge_widget(v0, v1)
                if y + 1 < self.height:
                    v1 = self.vertex_dic[(x, y+1)]
                    self.make_edge_widget(v0, v1)

    def draw_solution(self):
        tag = 'path'
        path_tags = self.board.find_withtag(tag)
        colour = 'black'
        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
        if vertex.is_white():
            fill = 'white'
        else:
            fill = 'black'
        self.board.create_oval(x0, y0, x1, y1, fill=fill,
                               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 not vertex.is_empty():
                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):
        """
        Respong to board event ie user has clicked on the board
        either to add or to remove an edge.
        Return the coords of the vertices at the ends of the edge
        and a code to say it was added or removed.
        """
        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):
        inc = 5
        fill = 'orange'
        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
        x0 = x - inc
        y0 = y - inc
        x1 = x + inc
        y1 = y + inc
        self.board.create_oval(x0, y0, x1, y1, fill=fill,
                               tags='hint')

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

    def apply_hint(self):
        keys = tuple(self.model.hint)
        try:
            widget = self.widget_dic[keys]
            self.show_edge(widget, True)
            self.delete_hint_blob()
        except KeyError:
            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_masyu, 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()

    def update_clock_box(self, algorithm):
        if algorithm is not None:
            name = self.model.alg_names[algorithm]
            self.clock.box.set_text(name)


class MVertex(object):
    """
    A Masyu vertex
    A vertex can be Black, White, Empty or Unused (ie no edges)
    """
    def __init__(self, x, y, codon):
        self.coord = (x, y)
        self.codon = codon
        self.status = True
        self.coords = []
        self.path_coords = []
        self.circle = self.codon[2]
        self.nbr_dic = {}
        self.neighbours = []
        self.set_path(x, y)

    def set_path(self, x, y):
        path_0 = []
        if Sgg.Down in self.codon:
            path_0.append((x, y + 1))
        if Sgg.Up in self.codon:
            path_0.append((x, y - 1))
        if Sgg.Left in self.codon:
            path_0.append((x - 1, y))
        if Sgg.Right in self.codon:
            path_0.append((x + 1, y))
        self.path_coords = path_0

    def get_path_code(self):
        return (self.codon[0], self.codon[1])

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

    def set_empty(self):
        self.codon = self.codon[:2] + Sgg.Empty

    def set_white(self):
        self.codon = self.codon[:2] + Sgg.White

    def set_black(self):
        self.codon = self.codon[:2] + Sgg.Black

    def is_satisfied(self):
        # is this vertex solved? ie can be ignored (also True if empty).
        return not self.path_coords or len(self.coords) > 1

    def is_white(self):
        return self.circle == Sgg.White

    def is_black(self):
        return self.circle == Sgg.Black

    def is_empty(self):
        return self.circle == Sgg.Empty

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

    def is_end(self):
        return len(self.coords) == 1

    def add_coord(self, coord):
        if coord not in self.coords:
            if len(self.coords) < 2:
                self.coords.append(coord)

    def delete_coord(self, coord):
        if coord in self.coords:
            self.coords.remove(coord)

    def update_circle(self):
        self.circle = self.codon[2]

    def is_consistent(self):
        ret = True
        if len(self.coords) > 2:
            self.status = False
            ret = False
        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):
        pass
        #print 'MVertex', self.coord, self.coords
        #print 'coords', self.coords


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

    def add_coord(self, coord):
        if coord in self.coords:
            pass
        else:
            self.coords.add(coord)

    def update_coords(self):
        if self.left:
            vertex = self.vertex_dic[self.left]
            done = set([])
            while True:
                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

    def get_length(self):
        # length is at least the number of vertices
        length = 0
        if self.left:
            length += 1
        if self.right != self.left:
            # when finished ??
            length += 1
        if self.left:
            next_coord = self.vertex_dic[self.left].coord
            if next_coord:
                next_vertex = self.vertex_dic[next_coord]
                if len(next_vertex.coords) == 2:
                    length += 1
        return length

    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]

        while True:
            done.add(vertex.coord)
            next_coord = vertex.next_coord(done)
            if not next_coord:
                break
            else:
                vertex = self.vertex_dic[next_coord]
        if self.right not in done:
            ret = False
        return ret

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

    def has_edge(self, coords):
        """
        Are this pair of coords in this spath?
        We do not know the order
        """
        ret = False
        coord_0 = coords[0]
        coord_1 = coords[1]
        if self.left:
            vertex = self.vertex_dic[self.left]
            done = []
            while True:
                done.append(vertex.coord)
                if vertex.coord in coords:
                    if coord_0 in vertex.coords or coord_1 in vertex.coords:
                        ret = True
                        break
                next_coord = vertex.next_coord(done)
                if not next_coord:
                    break
                else:
                    vertex = self.vertex_dic[next_coord]
        return ret

    def get_ends(self):
        ends = []
        if self.get_length() > 0:
            if self.left:
                ends.append(self.vertex_dic[self.left])
            if self.right:
                ends.append(self.vertex_dic[self.right])
        return ends

    def print_me(self):
        pass
    """
        print 'SPath start', self.left, self.right
        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]
        print 'SPath end', self.left, self.right
        print
    """


class Model(object):
    """
    Masyu Puzzle.
    """
    def __init__(self, model_data):
        self.model_data = model_data
        self.width = None
        self.height = None
        self.score = None
        self.vertex_count = 0
        self.vertex_dic = {}
        self.inter_dic = {}
        self.ends = []
        self.status = True
        self.bad_edges = []
        self.errors = []
        self.spaths = []
        self.hint = []
        self.progress = False
        self.finished = False
        # for generator
        self.dir_dic = {}
        self.shortcuts = []
        self.used_shortcuts = []
        self.counter = 0
        self.coords = []
        self.max_grids = 1
        self.min_mix = 500
        self.freq = 5
        self.algorithm = None
        self.algorithms = [
            (self.white_parallel),
            (self.white_continuation),
            (self.black_blocked),
            (self.black_extension),
            (self.white_blocked),
            (self.white_turn),
            (self.white_two),
            (self.black_perpendicular),
            (self.black_white),
            (self.one_way_only),
            (self.dead_end),
            ]

        # nb following dependent on algorithm order
        self.alg_scores = [2, 1, 2, 1, 1, 2, 4, 3, 4, 3, 3]
        self.alg_names = ['WP', 'WC', 'BB', 'BE', 'WB', 'WT', 'W2', 'BP',
                          'BW', 'OW', 'DE']
        self.alg_score = 0

    def translate(self, amino_acid, codon):
        table = \
                {"A": [Sgg.Left, Sgg.Right, Sgg.White],
                 "B": [Sgg.Left, Sgg.Right, Sgg.Black],
                 "C": [Sgg.Left, Sgg.Right, Sgg.Empty],
                 "D": [Sgg.Up, Sgg.Down, Sgg.White],
                 "E": [Sgg.Up, Sgg.Down, Sgg.Black],
                 "F": [Sgg.Up, Sgg.Down, Sgg.Empty],
                 "G": [Sgg.Left, Sgg.Down, Sgg.White],
                 "H": [Sgg.Left, Sgg.Down, Sgg.Black],
                 "I": [Sgg.Left, Sgg.Down, Sgg.Empty],
                 "J": [Sgg.Left, Sgg.Up, Sgg.White],
                 "K": [Sgg.Left, Sgg.Up, Sgg.Black],
                 "L": [Sgg.Left, Sgg.Up, Sgg.Empty],
                 "M": [Sgg.Right, Sgg.Down, Sgg.White],
                 "N": [Sgg.Right, Sgg.Down, Sgg.Black],
                 "O": [Sgg.Right, Sgg.Down, Sgg.Empty],
                 "P": [Sgg.Right, Sgg.Up, Sgg.White],
                 "Q": [Sgg.Right, Sgg.Up, Sgg.Black],
                 "R": [Sgg.Right, Sgg.Up, Sgg.Empty],
                 "S": [Sgg.Empty, Sgg.Empty, Sgg.Empty]}
        ret = ''
        if amino_acid:
            try:
                ret = table[amino_acid]
            except KeyError:
                ret = []
        elif codon:
            for key, item in list(table.items()):
                back = "".join(list(reversed(item[:2]))) + item[2]
                if "".join(item) == codon or back == codon:
                    ret = key
                    break
        return ret

    def ocheck(self):
        ret = True
        for spath in self.spaths:
            if not spath.is_consistent():
                ret = False
        for coord_0, vertex_0 in list(self.vertex_dic.items()):
            for coord_1 in vertex_0.coords:
                vertex_1 = self.vertex_dic[coord_1]
                if coord_0 not in vertex_1.coords:
                    ret = False
        if not ret and Sgg.DEBUG:
            exit(7)

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

    def inc_coord(self, coord, inc):
        ret = ()
        new_coord = coord[0] + inc[0], coord[1] + inc[1]
        x = new_coord[0]
        y = new_coord[1]
        if self.in_grid_2(x, y):
            ret = new_coord
        return ret

    def get_neighbours(self, coord):
        """
        neighbours are valid neighbours
        nbr_dic is all possible directions, with () for invalid neighbours
        """
        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        distances = [[0, -1], [0, 1], [-1, 0], [1, 0]]
        ddirections = [(Sgg.Up, Sgg.Right), (Sgg.Down, Sgg.Right),
                       (Sgg.Down, Sgg.Left), (Sgg.Up, Sgg.Left)]
        ddistances = [[1, -1], [1, 1], [-1, 1], [-1, -1]]
        nbr_dic = {}
        neighbours = []
        x = coord[0]
        y = coord[1]
        for diri in range(4):
            direction = directions[diri]
            distance = distances[diri]
            new_coord = self.inc_coord(coord, distance)
            if new_coord:
                neighbours.append(new_coord)

            nbr_dic[direction] = new_coord
            if new_coord:
                new_coord = self.inc_coord(new_coord, distance)
            nbr_dic[direction, direction] = new_coord
            direction = ddirections[diri]
            distance = ddistances[diri]
            new_coord = self.inc_coord(coord, distance)
            nbr_dic[direction] = new_coord
            rdir = (direction[1], direction[0])
            nbr_dic[rdir] = new_coord
        return nbr_dic, neighbours

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

    def decode_puzzle(self, puzzle):
        this_puzzle = []
        item = 2
        item = 3
        for y in range(self.height):
            for x in range(self.width):
                acid = puzzle[item]
                if acid != Sgg.Unused:
                    self.vertex_count += 1
                codon = self.translate(acid, '')
                this_puzzle.append(codon)
                item += 1
        return this_puzzle

    def get_puzzle_1(self, puzzle_number):
        puzzle_data = self.model_data.get_puzzle(puzzle_number)
        PzlG.logger.logger.info("get_puzzle " +
                                str(puzzle_number))
        return puzzle_data

    def get_puzzle(self, puzzle_number):
        puzzle_data = self.get_puzzle_1(puzzle_number)
        self.get_puzzle_2(puzzle_data, True)

    def get_puzzle_2(self, puzzle_data, decode):
        self.score = puzzle_data[0]
        self.width = puzzle_data[1]
        self.height = puzzle_data[2]
        if decode:
            data = puzzle_data[:3]
            data += self.decode_puzzle(puzzle_data)
            puzzle_data = data
        item = 3
        for y in range(self.height):
            for x in range(self.width):
                codon = puzzle_data[item]
                vertex = MVertex(x, y, codon)
                self.vertex_dic[(x, y)] = vertex
                item += 1
        self.init_spaths()
        self.add_neighbours()

    def init_spaths(self):
        self.spaths = []

        for coord, vertex in list(self.vertex_dic.items()):
            if not vertex.is_empty():
                new_path = SPath(self.vertex_dic)
                new_path.add_coord(coord)
                new_path.update_end(vertex)
                self.spaths.append(new_path)

    def do_hint(self):
        self.hint = []
        self.progress = False
        if not self.is_finished():
            self.apply_algorithms()

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

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

    def is_finished(self):
        ret = True
        if not self.finished:
            for coord, vertex in list(self.vertex_dic.items()):
                if not vertex.is_satisfied():
                    ret = False
                    break
        if ret:
            self.finished = True
        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 try_directions_1(self, vertex, spath, diri):
        """
        A Black circle is blocked in a direction if it cannot extend
        a distance of 2 vertices. This can occur if
        1. it is close to an edge (rim of grid)
        2. the next vertex is in a spath which has a perpendicular edge
        (doesn't need to be satisfied - one is enough)
        3. the next next vertex is in a spath which has a
        perpendicular edge, and is satisfied, or is unsatisfied but
        from the same spath (unless we are completing the puzzle!).
        from the same spath
        For case 1 we need 2 neighbours.
        For case 2 we check one neighbour.
        For case 3 we need 2 neighbours.

        If this function finds an unblocked direction it returns its coord
        """
        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        reverse_directions = [Sgg.Down, Sgg.Up, Sgg.Right, Sgg.Left]
        perpendicular_directions = [[Sgg.Left, Sgg.Right],
                                    [Sgg.Left, Sgg.Right],
                                    [Sgg.Up, Sgg.Down],
                                    [Sgg.Up, Sgg.Down]]

        ret = []
        direction = directions[diri]
        key_r = reverse_directions[diri]
        key_p = perpendicular_directions[diri]
        coord_d = vertex.nbr_dic[direction]
        coord_dd = vertex.nbr_dic[direction, direction]

        if not coord_d or not coord_dd:
            # off rim
            ret = [True]
        if not ret:
            tmp_vertex = self.vertex_dic[coord_d]
            coord_p_1 = tmp_vertex.nbr_dic[key_p[0]]
            coord_p_2 = tmp_vertex.nbr_dic[key_p[1]]
            if tmp_vertex.has_coord(coord_p_1) or\
               tmp_vertex.has_coord(coord_p_2):
                ret = [True]
        if not ret:
            tmp_vertex = self.vertex_dic[coord_dd]
            coord_p_1 = tmp_vertex.nbr_dic[key_p[0]]
            coord_p_2 = tmp_vertex.nbr_dic[key_p[1]]
            if tmp_vertex.has_coord(coord_p_1) and\
               tmp_vertex.has_coord(coord_p_2):
                ret = [True]
        if not ret and spath is not None and coord_dd:
            tmp_spath = self.get_spath(coord_dd)
            if tmp_spath is not None and\
               spath == tmp_spath and\
               len(self.spaths) > 1:
                tmp_vertex = self.vertex_dic[coord_dd]
                ret = [True]
        if ret:
            # if blocked in direction diri it must extend in the opposite
            new_coord = vertex.nbr_dic[key_r]
            if new_coord and not vertex.has_coord(new_coord):
                ret = [vertex.coord, new_coord]
            else:
                ret = []
        return ret

    def black_blocked_1(self, spath, vertex):
        """
        A Black circle is blocked in a direction if it cannot extend
        a distance of 2 vertices. This can occur if
        1. it is close to an edge (rim of grid)
        2. the next vertex is in a spath which has a perpendicular edge
        (doesn't need to be satisfied - one is enough)
        3. the next next vertex is in a spath which has a
        perpendicular edge, and is satisfied, or is unsatisfied but
        from the same spath
        For case 1 we need 2 neighbours.
        For case 2 we check one neighbour.
        For case 3 we need 2 neighbours.
        """

        ret = []
        if not vertex.is_satisfied() and vertex.is_black():
            for diri in range(4):
                ret = self.try_directions_1(vertex, None, diri)
                if ret:
                    break
        return ret

    def black_blocked(self):
        """
        First edges from black circles.
        If the path is blocked in a particular direction
        the path must extend in the opposite direction.
        Blocking means, either it is too close to an edge,
        or it would illegally intersect another path.
        """

        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for vertex in end_vertices:
                ret = self.black_blocked_1(spath, vertex)
                if ret:
                    self.save_hint(ret)
                    self.progress = True
                    break

    def black_extension(self):
        """
        Extend edges emanating from black circles.
        Paths through black circles must extend in a straight
        line for at least 2 vertices.
        """

        def get_coord(coord_0, coord_1):
            x0 = coord_0[0]
            y0 = coord_0[1]
            x1 = coord_1[0]
            y1 = coord_1[1]
            if x0 == x1:
                if y0 < y1:
                    coord = (coord_0[0], coord_0[1] - 1)
                else:
                    coord = (coord_0[0], coord_0[1] + 1)
            else:
                if x0 < x1:
                    coord = (coord_0[0] - 1, coord_0[1])
                else:
                    coord = (coord_0[0] + 1, coord_0[1])
            return coord

        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for end_index in range(min(len(end_vertices), 2)):
                end_vertex = end_vertices[end_index]
                if end_vertex.is_empty() and not\
                   end_vertex.is_satisfied():
                    vertex_coord = end_vertex.coords[0]
                    if self.vertex_dic[vertex_coord].is_black():
                        new_coord = get_coord(end_vertex.coord, vertex_coord)
                        ret = [end_vertex.coord, new_coord]
                        break
            if ret:
                self.save_hint(ret)
                self.progress = True
                break

    def black_perpendicular(self):
        """
        When a Black circle has an edge in only one direction
        try to find the perpendicular one. If we find blocking in
        one direction we know the path must extend in the other.
        """

        def get_direction(coord_0, coord_1):
            x0 = coord_0[0]
            y0 = coord_0[1]
            x1 = coord_1[0]
            y1 = coord_1[1]
            if x0 == x1:
                if y0 < y1:
                    direction = 2
                else:
                    direction = 2
            else:
                if x0 < x1:
                    direction = 0
                else:
                    direction = 0
            return direction

        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            if len(end_vertices) > 1:
                for endi, vertex in enumerate(end_vertices):
                    if vertex.is_black() and vertex.coords:
                        diri = get_direction(vertex.coord, vertex.coords[0])
                        ret = self.try_directions_1(vertex, spath, diri)
                        if ret:
                            break
                if ret:
                    break
        if ret:
            self.save_hint(ret)
            self.progress = True

    def black_white(self):
        """
        A black circle with two white circles diagonally adjacent on the
        same side must have the loop heading away from that side. If
        not, and it went between the white circles instead, then the
        white circles would be parallel to that section of the loop,
        and make it impossible to complete the black circle.
        """
        dirs = [(Sgg.Up, Sgg.Right), (Sgg.Up, Sgg.Left),
                (Sgg.Down, Sgg.Right), (Sgg.Down, Sgg.Left)]
        pairs = [[0, 2], [2, 3], [3, 1], [1, 0]]
        odirections = [Sgg.Left, Sgg.Up, Sgg.Right, Sgg.Down]
        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for endi, vertex in enumerate(end_vertices):
                if vertex.is_black():
                    for pairi, pair in enumerate(pairs):
                        d1 = dirs[pair[0]]
                        d2 = dirs[pair[1]]
                        nbr_1 = vertex.nbr_dic[d1]
                        nbr_2 = vertex.nbr_dic[d2]
                        if nbr_1 and nbr_2:
                            vertex_1 = self.vertex_dic[nbr_1]
                            vertex_2 = self.vertex_dic[nbr_2]
                            if vertex_1.is_white() and\
                               vertex_2.is_white():
                                odir = odirections[pairi]
                                coord = vertex.nbr_dic[odir]
                                if coord not in vertex.coords:
                                    ret = [vertex.coord, coord]
                                    break
                    if ret:
                        break
            if ret:
                break
        if ret:
            self.save_hint(ret)
            self.progress = True

    def white_threes(self):
        """
        If three or more white circles are orthogonally contiguous and
        collinear, then the loop will need to pass through each of those
        circles perpendicular to the line of circles.

        NB this is not used as w2 does it anyway.
        """
        directions = [Sgg.Left, Sgg.Up, Sgg.Right, Sgg.Down]
        pdirections = [Sgg.Up, Sgg.Left, Sgg.Up, Sgg.Left]
        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for endi, vertex in enumerate(end_vertices):
                if vertex.is_white():
                    for diri, direction in enumerate(directions):
                        d1 = (direction)
                        d2 = (direction, direction)
                        nbr_1 = vertex.nbr_dic[d1]
                        nbr_2 = vertex.nbr_dic[d2]
                        if nbr_1 and nbr_2:
                            vertex_1 = self.vertex_dic[nbr_1]
                            vertex_2 = self.vertex_dic[nbr_2]
                            if vertex_1.is_white() and\
                               vertex_2.is_white():
                                coord = vertex.nbr_dic[pdirections[diri]]
                                if coord not in vertex.coords:
                                    ret = [vertex.coord, coord]
                                    break
                                coord = vertex_1.nbr_dic[pdirections[diri]]
                                if coord not in vertex_1.coords:
                                    ret = [vertex_1.coord, coord]
                                    break
                    if ret:
                        break
            if ret:
                break
        if ret:
            self.save_hint(ret)
            self.progress = True

    def white_blocked_1(self, spath, vertex):
        """
        A White circle is blocked next to rim or by an adjacent path
        """
        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        perpendicular_directions = [[Sgg.Left, Sgg.Right],
                                    [Sgg.Left, Sgg.Right],
                                    [Sgg.Up, Sgg.Down],
                                    [Sgg.Up, Sgg.Down]]
        ret = []
        if not vertex.is_satisfied() and vertex.is_white():
            for diri in range(4):
                direction = directions[diri]

                # open?

                nbr_coord_1 = vertex.nbr_dic[direction]
                if not nbr_coord_1:
                    # nbr off edge in this direction, try perpendicular
                    keys = perpendicular_directions[diri]
                    for key in keys:
                        new_coord = vertex.nbr_dic[key]
                        if not spath.has_edge((vertex.coord, new_coord)):
                            # no edge in this direction, so add it
                            ret = [vertex.coord, new_coord]
                            break
                    if ret:
                        break
                else:
                    tmp_vertex = self.vertex_dic[nbr_coord_1]
                    # nbr in this direction
                    if tmp_vertex.is_satisfied() and not vertex.coords:
                        # nbr is satisfied, but in which direction?
                        keys = perpendicular_directions[diri]
                        for key in keys:
                            new_coord = vertex.nbr_dic[key]
                            if not spath.has_edge((vertex.coord,
                                                   new_coord)):
                                ret = [vertex.coord, new_coord]
                                break
                    if ret:
                        break

        return ret

    def white_blocked(self):
        """
        First edges from white circles.
        The path through white circles must pass straight through.
        Look for blocking by the puzzle rim or by adjacent paths.
        """

        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for end_vertex in end_vertices:
                ret = self.white_blocked_1(spath, end_vertex)
                if ret:
                    self.save_hint(ret)
                    self.progress = True
                    break
            if ret:
                break

    def is_open(self, vertex, direction):
        """
        Is an edge from vertex in direction direction possible?
        Assume no solved from vertex in direction.
        """
        nbr_coord = vertex.nbr_dic[direction]
        ret = (nbr_coord)
        if not nbr_coord:
            ret = ()
        else:
            new_vertex = self.vertex_dic[nbr_coord]
            if len(new_vertex.coords) == 2:
                ret = ()
        return ret

    def is_ok_path(self, sp_0, sp_1):
        """
        sp_0 is spath of current path.
        Would connection to sp_1 create a local loop?
        OK if sp_1 is None or the sp's are different
        or there is only one spath (in which case
        the connection would close the overall path).
        """

        return sp_1 is None or sp_0 != sp_1 or len(self.spaths) == 1

    def white_turn(self):
        """
        Try to extend edges emanating from white circles.
        If White circle has two colinear edges on one side
        it must have a turn one edge along in the opposite direction.
        """

        def get_coords(coord_0, coord_1):
            x0 = coord_0[0]
            y0 = coord_0[1]
            x1 = coord_1[0]
            y1 = coord_1[1]
            if x0 == x1:
                if y0 < y1:
                    direction = Sgg.Down
                    coords = ((coord_0[0], coord_0[1] - 1),
                              (coord_0[0], coord_0[1] - 2))
                else:
                    direction = Sgg.Up
                    coords = ((coord_0[0], coord_0[1] + 1),
                              (coord_0[0], coord_0[1] + 2))
            else:
                if x0 < x1:
                    direction = Sgg.Right
                    coords = ((coord_0[0] - 1, coord_0[1]),
                              (coord_0[0] - 2, coord_0[1]))
                else:
                    direction = Sgg.Left
                    coords = ((coord_0[0] + 1, coord_0[1]),
                              (coord_0[0] + 2, coord_0[1]))
            return coords, direction

        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        perp_dir = [[Sgg.Left, Sgg.Right],
                    [Sgg.Left, Sgg.Right],
                    [Sgg.Up, Sgg.Down],
                    [Sgg.Up, Sgg.Down]]

        ret = []
        for spath in self.spaths:
            # must have at least three vertices
            if spath.get_length() > 1:
                end_vertices = spath.get_ends()
                for end_index in range(2):
                    end_vertex = end_vertices[end_index]
                    if end_vertex.is_empty():
                        vertex = self.vertex_dic[end_vertex.coords[0]]
                        if vertex.is_white():
                            new_coords, direction = get_coords(
                                vertex.coord,
                                end_vertex.coord)
                            if spath.has_edge(new_coords):
                                diri = perp_dir[directions.index(direction)]
                                new_coord_0 = self.is_open(end_vertex, diri[0])
                                new_coord_1 = self.is_open(end_vertex, diri[1])
                                if new_coord_0 and not new_coord_1:
                                    sp = self.get_spath(new_coord_0)
                                    if self.is_ok_path(spath, sp):
                                        ret = [end_vertex.coord, new_coord_0]
                                elif new_coord_1 and not new_coord_0:
                                    sp = self.get_spath(new_coord_1)
                                    if self.is_ok_path(spath, sp):
                                        ret = [end_vertex.coord, new_coord_1]
                            if ret:
                                break
                if ret:
                    break
        if ret:
            self.save_hint(ret)
            self.progress = True

    def one_way_only(self):
        """
        Find ends without circles which have only one way to extend
        because all other paths are blocked.
        """

        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            if len(end_vertices) > 1:
                for vertex in end_vertices:
                    if vertex.is_empty():
                        new_coords = []
                        for diri in range(4):
                            direction = directions[diri]
                            new_coord = self.is_open(vertex, direction)
                            if new_coord:
                                tmp_sp = self.get_spath(new_coord)
                                if self.is_ok_path(spath, tmp_sp):
                                    new_coords.append(new_coord)
                        if len(new_coords) == 1:
                            ret = [vertex.coord, new_coords[0]]
                            break
                if ret:
                    self.save_hint(ret)
                    self.progress = True
                    break

    def explore_grid(self, start_vertex):
        """
        Explore the grid around start_coord to find unused vertices.
        start_vertex is unused and 1 grid unit away from a spath end.
        """
        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        unused = [start_vertex.coord]
        stack = [start_vertex]
        progress = True
        while progress:
            progress = False
            new_stack = []
            for vertex in stack:
                for diri in range(4):
                    direction = directions[diri]
                    nbr_coord = vertex.nbr_dic[direction]
                    if nbr_coord:
                        nbr_vertex = self.vertex_dic[nbr_coord]
                        if nbr_coord not in unused:
                            if not nbr_vertex.coords and\
                               nbr_vertex.is_empty():
                                unused.append(nbr_coord)
                                progress = True
                                new_stack.append(nbr_vertex)
            stack = new_stack
        return unused

    def is_possible_extension(self, spath, coord):
        """
        Can this coord be linked to a solver path other than spath?
        """
        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        ret = []
        vertex = self.vertex_dic[coord]
        for direction in directions:
            nbr_coord = vertex.nbr_dic[direction]
            nbr_spath = self.get_spath(nbr_coord)
            if nbr_spath is not None:
                if nbr_spath != spath:
                    nbr_vertex = self.vertex_dic[nbr_coord]
                    if len(nbr_vertex.coords) < 2:
                        ret.append(nbr_coord)
        return ret

    def no_path_1(self, spath, nbr_coord, extensions):
        """
        nbr_coord is one edge along from the end of a spath
        Using explore_grid we find all unused vertices it can reach.
        Using possible_extension we check if any unused can be linked
        to a different spath
        """

        nbr_vertex = self.vertex_dic[nbr_coord]
        if not nbr_vertex.coords and\
           nbr_vertex.is_empty():
            unused = self.explore_grid(nbr_vertex)
            if unused:
                for hole in unused:
                    if self.is_possible_extension(spath, hole):
                        extensions[nbr_coord] = True
        else:
            nbr_spath = self.get_spath(nbr_coord)
            if nbr_spath is not None and nbr_spath != spath:
                extensions[nbr_coord] = True

    def dead_end(self):
        """
        Check all possible extending paths to check if they can
        be continued. If all but one lead to dead ends, the path
        can only extend one way.
        """

        directions = [Sgg.Up, Sgg.Down, Sgg.Left, Sgg.Right]
        ret = []
        for spath in self.spaths:
            end_vertices = spath.get_ends()
            for end_vertex in end_vertices:
                extensions = {}
                for diri in range(4):
                    direction = directions[diri]
                    nbr_coord = end_vertex.nbr_dic[direction]
                    if nbr_coord:
                        self.no_path_1(spath, nbr_coord,
                                       extensions)
                if len(extensions) == 1:
                    ret = [end_vertex.coord, list(extensions.keys())[0]]
                    break
            if ret:
                self.save_hint(ret)
                self.progress = True
                break

    def extend_1(self, income, visited, extensions):
        """
        Recurse!
        """

        income_vertex = self.vertex_dic[income]
        neighbours = income_vertex.neighbours
        for neighbour in neighbours:
            if neighbour not in visited:
                nbr_vertex = self.vertex_dic[neighbour]
                if not nbr_vertex.is_satisfied():
                    visited.append(neighbour)
                    if len(nbr_vertex.coords) == 1:
                        extensions.append(neighbour)
                    elif nbr_vertex.is_empty():
                        extensions.append(neighbour)
                        # Recurse!
                        self.extend_1(neighbour, visited, extensions)
                    elif not nbr_vertex.coords:
                        # why not recurse after this??
                        extensions.append(neighbour)

    def is_end(self, coord):
        ret = False
        vertex = self.vertex_dic[coord]
        if len(vertex.coords) == 1 or\
           (not vertex.coords and vertex.is_white()):
            ret = True
        return ret

    def white_continuation(self):
        """
        Extend edges emanating from white circles.
        """

        def get_coord(coord_0, coord_1):
            x0 = coord_0[0]
            y0 = coord_0[1]
            x1 = coord_1[0]
            y1 = coord_1[1]
            if x0 == x1:
                if y0 < y1:
                    coord = (coord_0[0], coord_0[1] - 1)
                else:
                    coord = (coord_0[0], coord_0[1] + 1)
            else:
                if x0 < x1:
                    coord = (coord_0[0] - 1, coord_0[1])
                else:
                    coord = (coord_0[0] + 1, coord_0[1])
            return coord

        ret = []

        for spath in self.spaths:
            # must have at least two vertices
            if spath.get_length() > 1:
                end_vertices = spath.get_ends()
                for end_index in range(2):
                    end_vertex = end_vertices[end_index]
                    if end_vertex.is_white():
                        vertex_coord = end_vertex.coords[0]
                        new_coord = get_coord(end_vertex.coord, vertex_coord)
                        if not spath.has_coord(new_coord):
                            ret = [end_vertex.coord, new_coord]
                            break
                if ret:
                    break
        if ret:
            self.save_hint(ret)
            self.progress = True

    def white_two_i1(self, white, inc, bad_coord):
        coord = self.inc_coord(white, inc)
        is_ok = True
        if not coord:
            # reject off grid
            is_ok = False
        else:
            vertex = self.vertex_dic[coord]
            if vertex.is_white():
                # reject white
                is_ok = False
            else:
                if vertex.is_black():
                    if len(vertex.coords) == 1:
                        if vertex.coords[0] == bad_coord:
                            # reject black, bad path
                            is_ok = False
        return is_ok

    def white_two_p1(self, white, inc, bad_coord):
        coord = self.inc_coord(white, inc)
        is_ok = True
        if not coord:
            # reject off grid
            is_ok = False
        else:
            vertex = self.vertex_dic[coord]
            if vertex.is_black():
                if len(vertex.coords) == 1:
                    if vertex.coords[0] == bad_coord:
                        # reject black, bad path
                        is_ok = False
        return is_ok

    def white_two_1(self, white_0, white_1):
        """
        white_0 and white_1 are isolated adjacent whites
        cases:
        vertical alignment
            inline
            parallel
        horizontal alignment
            inline
            parallel
        abcdef
        ghijkl
        mnOpqr
        stUvwx
        yz1234
        567890
        """

        vertical = False
        if white_0[0] == white_1[0]:
            # aligned vertically
            #     O
            #     U
            vertical = True
            # O environment
            inc = (0, -1)
            bad_coord = (0, -2)
            inline_ok = self.white_two_i1(white_0, inc, bad_coord)
            if inline_ok:
                # environment ok, check turn
                bad_coord = (0, 3)
                inc = (0, 2)
                inline_ok = self.white_two_i1(white_0, inc, bad_coord)
            # U environment
            inc = (-1, 0)
            bad_coord = (-2, 0)
            perp_ok = self.white_two_p1(white_0, inc, bad_coord)
            if perp_ok:
                # environment ok, check turn
                inc = (1, 0)
                bad_coord = (2, 0)
                perp_ok = self.white_two_p1(white_0, inc, bad_coord)
        else:
            """
            abcdef
            ghijkl
            mnopqr
            stUVwx
            yz1234
            567890
            """
            # U environment
            bad_coord = (-2, 0)
            inc = (-1, 0)
            inline_ok = self.white_two_i1(white_0, inc, bad_coord)
            if inline_ok:
                # environment ok, check turn
                bad_coord = (3, 0)
                inc = (2, 0)
                inline_ok = self.white_two_i1(white_0, inc, bad_coord)
            # V environment
            bad_coord = (0, -2)
            inc = (0, -1)
            perp_ok = self.white_two_p1(white_0, inc, bad_coord)
            if perp_ok:
                # environment ok, check turn
                bad_coord = (0, 2)
                inc = (0, 1)
                perp_ok = self.white_two_p1(white_0, inc, bad_coord)
        return inline_ok, perp_ok, vertical

    def white_two(self):
        """
        Find and use pairs of adjacent Whites
        A pair of adjacent White circles must be linked inline or
        both passed through in a direction perpendicular to their
        alignment.  Which is it?
        """
        incs = [[0, 1], [1, 0], [1, 0], [0, 1]]
        ret = []
        for spath_0 in self.spaths:
            # must have no vertices and be White
            if spath_0.get_length() == 1:
                end_vertex = self.vertex_dic[spath_0.left]
                if end_vertex.is_white():
                    end_coord = end_vertex.coord
                    # end_coord is White
                    for inc_index, inc in enumerate(incs):
                        blue = self.inc_coord(end_coord, inc)
                        if blue:
                            nbr_coord = blue
                            nbr_vertex = self.vertex_dic[nbr_coord]
                            if nbr_vertex.is_white():
                                spath_1 = self.get_spath(nbr_coord)
                                if spath_1 is not None and\
                                   spath_1.get_length() == 1:
                                    # we have an adjacent pair of
                                    # isolated whites
                                    inline, perp, vert = self.white_two_1(
                                        end_coord,
                                        nbr_coord)
                                    new_coord = ()
                                    if inline and not perp:
                                        if vert:
                                            new_coord = self.inc_coord(
                                                end_coord, (0, -1))
                                        else:
                                            new_coord = self.inc_coord(
                                                end_coord, (-1, 0))
                                    elif perp and not inline:
                                        if vert:
                                            new_coord = self.inc_coord(
                                                end_coord, (-1, 0))
                                        else:
                                            new_coord = self.inc_coord(
                                                end_coord, (0, -1))
                                    if new_coord:
                                        ret = [end_vertex.coord, new_coord]
                                        break
                    if ret:
                        break
        if ret:
            self.save_hint(ret)
            self.progress = True
        return ret

    def white_parallel(self):
        """
        If this vertex is white and an adjacent white is solved and does
        not pass through this vertex, this vertex must be traversed in
        the same direction.
        """

        def get_direction(coords):
            x0 = coords[0][0]
            y0 = coords[0][1]
            x1 = coords[1][0]
            y1 = coords[1][1]
            if x0 == x1:
                direction = 1
            else:
                direction = 0
            return direction

        incs = [(0, 1), (0, -1), (1, 0), (-1, 0)]
        ret = []
        for coord, vertex in list(self.vertex_dic.items()):
            if vertex.is_white() and not vertex.is_satisfied():
                for inc in incs:
                    this_coord = self.inc_coord(coord, inc)
                    if this_coord:
                        this_vertex = self.vertex_dic[this_coord]
                        if this_vertex.is_white() and\
                           this_vertex.is_satisfied():
                            coords = this_vertex.coords
                            direction = get_direction(coords)
                            if direction == 0:
                                new_coord = coord[0]+1, coord[1]
                                if new_coord in vertex.coords:
                                    new_coord = coord[0]-1, coord[1]
                            else:
                                new_coord = coord[0], coord[1]+1
                                if new_coord in vertex.coords:
                                    new_coord = coord[0], coord[1]-1
                            ret = [coord, new_coord]
                            break
                if ret:
                    break
        if ret:
            self.save_hint(ret)
            self.progress = True

    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:
                    # extension
                    self.extend_spath(spath_0, coords)
                elif spath_1 is not None:
                    # extension
                    self.extend_spath(spath_1, coords)
            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)

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

    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()
        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 delete old spaths
        """
        left_0 = spath_0.left
        right_0 = spath_0.right
        left_1 = spath_1.left
        right_1 = spath_1.right

        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:
            pass
        try:
            self.spaths.remove(spath_1)
        except ValueError:
            pass
        self.spaths.append(spath)

    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):
        spath_0 = self.get_spath(coords[0])
        if spath_0 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)
        else:
            # extension or join
            spath_1 = self.get_spath(coords[1])
            if spath_1 is None:
                # extension
                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)
            else:
                # join
                jtype = self.get_join_type(spath_0,
                                           spath_1, coords)
                self.join_spaths(spath_0, spath_1, jtype)

    def apply_hint(self):
        if self.hint:
            coords = self.hint
            self.add_vertices(coords)
        self.algorithm = None

    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
            Sgg.alg_usage[self.algorithm] += 1
            self.alg_score += self.alg_scores[self.algorithm]
            if not self.is_in_path(coords):
                strargs = str(self.algorithm)
                strargs += ' ' + str(coords[0]) + ',' + str(coords[1]) + ' '
                PzlG.logger.logger.error("give_hint " + strargs)
                self.hint = []
                """
                if Sgg.DEBUG:
                    self.print_puzzle1()
                    self.print_grid()
                    self.print_directions()
                    self.print_path()
                    exit(1)
                """

    def apply_algorithms(self):
        self.progress = False
        self.hint = []
        for self.algorithm, algorithm in enumerate(self.algorithms):
            algorithm()
            if self.hint:
                self.check_hint()
                break

    def solver_1(self):
        # get a hint
        self.do_hint()
        if self.hint:
            self.apply_hint()

    def solver(self):
        self.status = True
        self.alg_score = 0
        while True:
            self.solver_1()
            if not self.hint:
                break

    def save_puzzle(self):
        codons = []
        for y in range(self.height):
            for x in range(self.width):
                codon = "".join(self.vertex_dic[(x, y)].codon)
                codons.append(codon)
        return codons

    def update_circles(self):
        for coord, vertex in list(self.vertex_dic.items()):
            vertex.update_circle()

    def make_plough(self):
        coords = []
        width = Sgg.width
        height = Sgg.height
        for y in range(height):
            if y % 2 == 0:
                x0 = width - 1
                xinc = -1
            else:
                x0 = 0
                xinc = 1
            for xi in range(width):
                coords.append((x0, y))
                x0 += xinc
        return coords

    def progress_inter_dic(self):
        for i in range(self.min_mix):
            self.do_back_bite()
            self.get_ends()

    def init_inter_dic(self, coords):
        self.inter_dic = {}
        self.inter_dic[coords[0]] = [(), coords[1]]
        for i in range(1, len(coords) - 1):
            self.inter_dic[coords[i]] = [coords[i - 1], coords[i + 1]]
        self.inter_dic[coords[-1]] = [coords[-2], ()]

    def apply_shortcuts(self):
        """
        Randomly apply shortcuts:
        random_count and random choices
        """
        min_h = 1
        max_h = 4

        if len(self.shortcuts) > min_h:
            random_count = random.randint(min_h,
                                          min(max_h,
                                              len(self.shortcuts) - 1))
            self.used_shortcuts = []
            used = []
            count = 0
            while count < random_count:
                rand = random.randint(0, len(self.shortcuts) - 1)
                if rand not in used:
                    shortcut = self.shortcuts[rand]
                    used.append(rand)
                    used_shortcut = []
                    cut_0 = shortcut[0]
                    cut_1 = shortcut[1]
                    cut_2 = shortcut[2]
                    cut_3 = shortcut[3]

                    used_shortcut.append([(cut_0), self.inter_dic[cut_0][1]])
                    used_shortcut.append([(cut_3), self.inter_dic[cut_3][0]])
                    used_shortcut.append([(cut_1), self.inter_dic[cut_1]])
                    used_shortcut.append([(cut_2), self.inter_dic[cut_2]])
                    self.inter_dic[cut_0][1] = cut_3
                    self.inter_dic[cut_3][0] = cut_0
                    self.inter_dic[cut_1] = [(), ()]
                    self.inter_dic[cut_2] = [(), ()]
                    count += 1
                    self.used_shortcuts.append(used_shortcut)

    def replace_shortcuts(self):

        for shortcuts in self.used_shortcuts:
            shortcut = shortcuts[0]
            self.inter_dic[shortcut[0]][1] = shortcut[1]

            shortcut = shortcuts[1]
            self.inter_dic[shortcut[0]][0] = shortcut[1]

            shortcut = shortcuts[2]
            self.inter_dic[shortcut[0]] = shortcut[1]

            shortcut = shortcuts[3]
            self.inter_dic[shortcut[0]] = shortcut[1]

    """
    def print_puzzle1(self):
        rec = ''
        rec += '99'
        rec += ','
        rec += str(self.width)
        rec += ','
        rec += str(self.height)
        rec += ','
        for y in range(self.height):
            for x in range(self.width):
                tmp = "".join(self.vertex_dic[(x, y)].codon)
                code = self.translate('', tmp)
                rec += "'"
                rec += code
                rec += "'"
                rec += ','
        print rec
    """

    def get_path_1(self):
        self.vertex_count = 0
        path = []

        while True:
            x = random.randint(0, self.width - 1)
            y = random.randint(0, self.height - 1)
            coord = (x, y)
            if self.inter_dic[coord]:
                break
        tmp_dic = {}
        while True:
            if coord and coord not in tmp_dic:
                tmp_dic[coord] = True
                vertex = self.inter_dic[coord]
                coord = vertex[1]
                path.append(coord)
            else:
                break
        self.coords = path
        self.vertex_count = len(path)

    def add_circles(self):
        turns = {
            (Sgg.Left, Sgg.Up): 'A', (Sgg.Left, Sgg.Down): 'B',
            (Sgg.Right, Sgg.Up): 'C', (Sgg.Right, Sgg.Down): 'D',
            (Sgg.Up, Sgg.Left): 'E', (Sgg.Down, Sgg.Left): 'F',
            (Sgg.Up, Sgg.Right): 'G', (Sgg.Down, Sgg.Right): 'H',
            }
        straight = {
            (Sgg.Left, Sgg.Right): 'A', (Sgg.Right, Sgg.Left): 'B',
            (Sgg.Down, Sgg.Up): 'C', (Sgg.Up, Sgg.Down): 'D'
            }

        def next_item(item):
            if item != len(self.coords) - 1:
                item += 1
            else:
                item = 0
            return item

        def prev_item(item):
            if item != 0:
                item -= 1
            else:
                item = len(self.coords) - 1
            return item

        blacks = []
        whites = []
        # add black circles
        for item in range(1, len(self.coords) - 2):
            this_coord = self.coords[item]
            this_dir = self.vertex_dic[this_coord].get_path_code()
            if this_dir in turns:
                p1 = prev_item(item)
                p1c = self.coords[p1]
                p1_dir = self.vertex_dic[p1c].get_path_code()
                n1 = next_item(item)
                n1c = self.coords[n1]
                n1_dir = self.vertex_dic[n1c].get_path_code()
                if p1_dir in straight and n1_dir in straight:
                    blacks.append(item)

        for item in range(0, len(self.coords) - 2):
            this_coord = self.coords[item]
            this_dir = self.vertex_dic[this_coord].get_path_code()
            if this_dir in straight:
                p1 = prev_item(item)
                p1c = self.coords[p1]
                p1_dir = self.vertex_dic[p1c].get_path_code()
                if p1_dir in turns:
                    whites.append(item)
                n1 = next_item(item)
                n1c = self.coords[n1]
                n1_dir = self.vertex_dic[n1c].get_path_code()
                if n1_dir in turns:
                    whites.append(item)
        for item in blacks:
            self.vertex_dic[self.coords[item]].set_black()
        for item in whites:
            self.vertex_dic[self.coords[item]].set_white()

    def gmake_puzzle(self):
        def get_direction(coord_0, coord_1):
            x0 = coord_0[0]
            y0 = coord_0[1]
            x1 = coord_1[0]
            y1 = coord_1[1]
            if x0 == x1:
                if y0 < y1:
                    direction = Sgg.Down
                else:
                    direction = Sgg.Up
            else:
                if x0 < x1:
                    direction = Sgg.Right
                else:
                    direction = Sgg.Left
            return direction

        for y in range(self.height):
            for x in range(self.width):
                codon = Sgg.Unused
                if self.inter_dic[(x, y)][0] and\
                   self.inter_dic[(x, y)][1] and\
                   self.inter_dic[x, y] != [(), ()]:
                    codon = ""
                    this_coord = (x, y)
                    path = self.inter_dic[(x, y)]
                    prev_coord = path[0]
                    next_coord = path[1]
                    direction = get_direction(this_coord, prev_coord)
                    codon += direction
                    direction = get_direction(this_coord, next_coord)
                    codon += direction
                    codon += Sgg.Empty

                vertex = MVertex(x, y, codon)
                self.vertex_dic[(x, y)] = vertex

    def prune_circles(self, puzzle):
        def to_xy(item):
            x = item % self.width
            y = int(item / self.width)
            return (x, y)

        whites = []
        for item in range(3, len(puzzle)):
            if puzzle[item][2] == Sgg.White:
                whites.append(item - 3)
        good = []
        best = []
        for i0, white_0 in enumerate(whites):
            good = []
            self.get_puzzle_2(puzzle, False)
            coord = to_xy(white_0)
            self.vertex_dic[coord].set_empty()
            self.vertex_dic[coord].update_circle()
            self.init_spaths()
            self.add_neighbours()
            self.finished = False
            self.solver()
            if self.is_finished():
                good.append(i0)
                start_1 = i0 + 1
                while True:
                    for i1 in range(start_1, len(whites)):
                        self.get_puzzle_2(puzzle, False)
                        for white_00 in good:
                            item = whites[white_00]
                            coord = to_xy(item)
                            self.vertex_dic[coord].set_empty()
                            self.vertex_dic[coord].update_circle()

                        item = whites[i1]
                        coord = to_xy(item)
                        self.vertex_dic[coord].set_empty()
                        self.vertex_dic[coord].update_circle()
                        self.init_spaths()
                        self.add_neighbours()
                        self.finished = False
                        self.solver()
                        if self.is_finished():
                            good.append(i1)
                            if len(good) > len(best):
                                best = good
                            start_1 = i1 + 1
                    break

        self.get_puzzle_2(puzzle, False)
        for white_00 in best:
            item = whites[white_00]
            coord = to_xy(item)
            self.vertex_dic[coord].set_empty()
            self.vertex_dic[coord].update_circle()
        new_puzzle = [self.alg_score, self.width, self.height]
        for y in range(self.height):
            for x in range(self.width):
                new_puzzle.append("".join(self.vertex_dic[(x, y)].codon))
        return new_puzzle

    def get_ends(self):
        """
        Get ends in a specific order
        """

        self.ends = []
        for coord, path in list(self.inter_dic.items()):
            if not path[0]:
                self.ends.append(coord)
        for coord, path in list(self.inter_dic.items()):
            if not path[1]:
                self.ends.append(coord)

    def get_directions(self):
        """
        Get directions
        """

        def get_direction(coord_0, coord_1):
            direction = Sgg.Left
            if coord_0 and coord_1:
                if coord_0[0] == coord_1[0]:
                    if coord_0[1] < coord_1[1]:
                        direction = Sgg.Down
                    else:
                        direction = Sgg.Up
                else:
                    if coord_0[0] < coord_1[0]:
                        direction = Sgg.Right
            return direction

        self.dir_dic = {}
        for y in range(self.height):
            for x in range(self.width):
                coord_0 = (x, y)
                coord_1 = self.inter_dic[(x, y)][1]
                direction = get_direction(coord_0, coord_1)
                self.dir_dic[x, y] = direction

    def get_shortcuts(self):
        def taxicab_distance(key_0, key_1):
            return int(abs(key_0[0] - key_1[0]) +
                       abs(key_0[1] - key_1[1]))
        opposites_dic = {Sgg.Up: Sgg.Down,
                         Sgg.Down: Sgg.Up,
                         Sgg.Left: Sgg.Right,
                         Sgg.Right: Sgg.Left,
                         Sgg.Empty: Sgg.Empty}
        cuts = []
        max_cut = 3
        vertex = self.ends[0]
        for item in range(self.width * self.height - max_cut):
            direction = self.dir_dic[vertex]
            odir = opposites_dic[direction]
            next_vertex = vertex
            path = [next_vertex]
            for distance in range(max_cut):
                next_vertex = self.inter_dic[next_vertex][1]
                path.append(next_vertex)
                nvd = self.dir_dic[next_vertex]
                if nvd == odir and taxicab_distance(vertex, next_vertex) == 1:
                    cuts.append(path)
            vertex = self.inter_dic[vertex][1]
        dels = []
        for i in range(len(cuts)):
            cuti = cuts[i]
            for cut in cuti:
                for j in range(i+1, len(cuts)):
                    cutj = cuts[j]
                    if cut in cutj:
                        dels.append(j)
        dels = list(reversed(dels))
        for item in dels:
            del cuts[item]
        self.shortcuts = cuts

    def in_grid(self, coord):
        ret = False
        x = coord[0]
        y = coord[1]
        if x > -1 and x < self.width and y > -1 and y < self.height:
            ret = True
        return ret

    def get_path(self, vertex_in, direction):
        directions = [1, 0]
        vertex = self.inter_dic[vertex_in][directions[direction]]
        tmp = []
        while True:
            if vertex in tmp:
                break
            else:
                tmp.append(vertex)
                vertex = self.inter_dic[vertex][direction]
        return tmp

    def check(self):
        """
        Is there a complete path from each end?
        """

        ret = True
        for end_coord in self.ends:
            tmp_dic = {}
            tmp_dic[end_coord] = True
            vertex_pair = self.inter_dic[end_coord]
            if not vertex_pair[0]:
                direction = 1
                vertex = vertex_pair[1]
            else:
                direction = 0
                vertex = vertex_pair[0]

            while True:
                if vertex in tmp_dic:
                    ret = False
                    break
                else:
                    tmp_dic[vertex] = True
                    vertex = self.inter_dic[vertex][direction]
                    if not vertex:
                        if len(tmp_dic) == len(self.inter_dic):
                            break
        """
        if not ret:
            self.print_grid()
            self.status = False
            #print 'error in check'
            exit(4)
        """

        return ret

    def do_back_bite(self):
        """
        chosen_end is connected randomly to an adjacent neighbour
        named new_link.
        new_link now has 3 links and we find which of the original
        links is now part of a cycle
        named cycle_link.
        This link is broken at new_link and cycle_link.
        https://arxiv.org/pdf/cond-mat/0508094.pdf
        Secondary Structures in Long Compact Polymers
        """
        incs = [(1, 0), (-1, 0), (0, 1), (0, -1)]

        while True:
            direction = random.randint(0, 1)
            chosen_end = self.ends[direction]
            poss = []
            for inc in incs:
                new_x = chosen_end[0] + inc[0]
                new_y = chosen_end[1] + inc[1]
                new_coord = new_x, new_y
                if self.in_grid(new_coord) and\
                   new_coord not in self.ends and\
                   new_coord not in self.inter_dic[chosen_end]:
                    poss.append(new_coord)
            if poss:
                break
        choice = random.randint(0, len(poss) - 1)
        new_link = poss[choice]

        # add to chosen_end

        links = self.inter_dic[tuple(chosen_end)]
        if not links[0]:
            self.inter_dic[tuple(chosen_end)] = [new_link, links[1]]
        else:
            self.inter_dic[tuple(chosen_end)] = [links[0], new_link]

        self.inter_dic[new_link].append(tuple(chosen_end))
        cycle_link = self.inter_dic[new_link][direction]
        del self.inter_dic[new_link][direction]

        # now remove link from cycle_link to new_link

        self.inter_dic[cycle_link].remove(tuple(new_link))
        if direction == 0:
            self.inter_dic[cycle_link] = [(), self.inter_dic[cycle_link][0]]
        else:
            self.inter_dic[cycle_link].append(())

        # need to reverse part of path, so get it

        path = self.get_path(cycle_link, direction)

        # not last item

        path.pop()

        # reverse rest

        for item in path:
            vertex = self.inter_dic[item]
            tmp0 = vertex[0]
            tmp1 = vertex[1]
            self.inter_dic[item] = [tmp1, tmp0]

        # set new ends

        self.get_ends()
    """
    def print_grid(self):
        for y in range(self.height):
            for x in range(self.width):
                coords = self.inter_dic[(x, y)]
                rec = "["
                if not coords[0]:
                    rec += '( , ),'
                else:
                    rec += '(' + str(coords[0][0])
                    rec += ','
                    rec += str(coords[0][1]) + '),'
                if not coords[1]:
                    rec += '( , )]'
                else:
                    rec += '(' + str(coords[1][0])
                    rec += ','
                    rec += str(coords[1][1]) + ')]'
                print rec,
            print
        print
        self.print_directions()

    def print_path(self):
        def get_symbol(coords):
            coord_0 = coords[0]
            coord_1 = coords[1]
            symbol = '.'
            if coord_0 and coord_1 and coord_0[0] < coord_1[0]:
                symbol = '>'
            if coord_0 and coord_1 and coord_0[0] > coord_1[0]:
                symbol = '<'
            if coord_0 and coord_1 and coord_0[1] < coord_1[1]:
                symbol = 'v'
            if coord_0 and coord_1 and coord_0[1] > coord_1[1]:
                symbol = '^'
            return symbol
        tmp_dic = {}
        for y in range(self.height):
            for x in range(self.width):
                tmp_dic[(x, y)] = '.'

        for y in range(self.height):
            for x in range(self.width):
                symbol = get_symbol(self.inter_dic[(x, y)])
                tmp_dic[x, y] = symbol

        for y in range(self.height):
            for x in range(self.width):
                print tmp_dic[(x, y)],
            print
        print

    def print_directions(self):
        if self.dir_dic:
            for y in range(self.height):
                for x in range(self.width):
                    direction = self.dir_dic[(x, y)]
                    print direction,
                print
            print
    """

    def join_ends(self):
        end_0 = self.ends[0]
        end_1 = self.ends[1]
        self.inter_dic[end_0][0] = end_1
        self.inter_dic[end_1][1] = end_0

    def check_paths(self):
        """
        Is there a complete path from each end?
        """

        items = 0
        for key, item in list(self.inter_dic.items()):
            if key and item != [(), ()]:
                items += 1
        ret = True
        for end_coord in self.ends:
            tmp_dic = {}
            tmp_dic[end_coord] = True
            vertex_pair = self.inter_dic[end_coord]
            if not vertex_pair[0]:
                direction = 1
                vertex = vertex_pair[1]
            else:
                direction = 0
                vertex = vertex_pair[0]
            c = 0
            while True:
                if vertex in tmp_dic:
                    # print 'cycle found in check'
                    ret = False
                    break
                else:
                    c += 1
                    tmp_dic[vertex] = True
                    if len(tmp_dic) == items:
                        break
                    vertex = self.inter_dic[vertex][direction]
                    if not vertex:
                        if len(tmp_dic) == c:
                            break
        """
        if not ret:
            self.print_grid()
            self.status = False
            print 'error in check_paths'
            exit(6)
        """
        return ret

    def generate_1(self, min_puzzles):
        """
        # we make a plough followed by min_mix generations
        # to mix the paths up before using them regularly.
        """

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

        max_cut_tries = 4
        puzzle_count = 0
        puzzles = []

        self.counter = 0

        while True:
            coords = self.make_plough()
            self.init_inter_dic(coords)
            self.get_ends()

            # inter_dic[x, y] = [(x0, y0), (x1, y1)] where (x0, y0)
            # and (x1, y1) are the adjacent vertices.
            # Once the path is created gmake_puzzle used inter_dic
            # to create vertex_dic[(x, y)] = MVertex(x, y, codon)
            # where codon is a 3-letter code denoting the path in
            # either direction and the circle type for the vertex

            self.progress_inter_dic()
            while True:
                self.do_back_bite()
                self.get_ends()
                if self.counter % self.freq == 0:

                    # Require the ends to be adjacent but not contiguous!

                    if taxicab_distance(self.ends[0],
                                        self.ends[1]) == 1:
                        break
                self.counter += 1
            self.join_ends()

            self.get_directions()

            # Masyu grids have a few empty vertices.
            # Find candidates for removal

            self.get_shortcuts()
            for cut_tries in range(max_cut_tries):
                self.apply_shortcuts()
                self.gmake_puzzle()
                self.replace_shortcuts()
                self.get_ends()
                self.get_path_1()
                self.add_circles()
                self.update_circles()
                self.init_spaths()
                self.add_neighbours()
                self.finished = False
                self.solver()

                if self.is_finished():

                    # this grid is solvable with maximum circles
                    # send it to prune_circles to see how many circles
                    # can be removed whilst retaining solvability

                    puzzle = [self.alg_score, self.width, self.height]
                    puzzle += self.save_puzzle()
                    puzzle = self.prune_circles(puzzle)
                    puzzles.append(puzzle)
                    puzzle_count += 1
                    # print 'puzzle_count', puzzle_count, puzzle
                    break

            if puzzle_count >= min_puzzles:
                break
        return puzzles

    def generate(self):
        self.counter = 0
        min_puzzles = 1000
        self.min_mix = 500
        self.freq = 5
        seed = 1
        #seed = 3
        #seed = 2
        random.seed(seed)
        Sgg.width = 10
        Sgg.height = 10
        self.width = 10
        self.height = 10
        puzzles = self.generate_1(min_puzzles)
        """
        # we make a plough followed by min_mix generations
        # to mix the paths up before using them regularly.
        """
        puzzles = sorted(puzzles)
        filename = str(seed) + '.txt'
        with open(filename, "w") as fo:
            rec = ''
            for puzzle in puzzles:
                for item in range(3):
                    rec += str(puzzle[item])
                    rec += ','
                for item in puzzle[3:]:
                    rec += "'"
                    code = self.translate('', item)
                    rec += str(code)
                    rec += "'"
                    rec += ','
            fo.write(rec)
        exit(8)


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):
            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 Sgg.alg_usage
        # 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)
        # generate
        # 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 == 'save_settings':
            self.settings.preferences.save()
        elif name == 'about':
            self.view.about()
        elif name == 'help':
            self.view.help()

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

        if mouse_index == 2:
            alg_index = self.model.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()
                    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)
            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.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
            # turn on the clock
            self.view.clock.set_show(True)

    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:
                    self.view.hint_on()
                    self.view.board.show_hint_blob()
                    self.view.update_clock_box(self.model.algorithm)
                    self.view.clock.set_show(False)
                    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.model.apply_hint()
            self.view.board.apply_hint()
            self.ready_for_hint()
            self.check_finished()

    def agive_hint(self):
        # version which tries to solve whole puzzle
        while True:
            if self.hint_status == Sgg.GIVE_HINT:
                if self.model.is_consistent():
                    # get a hint
                    self.model.do_hint()
                    if self.model.hint:
                        self.model.apply_hint()
                        # update board
                        self.view.board.apply_hint()
                        self.ready_for_hint()
                    else:
                        self.model.is_finished()
                        break
            else:
                self.view.thumbs_down()
                self.colour_errors(True)
                self.error_detected = True
                break

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


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