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

# Copyright (C) 2018 Rod Engerstad


from random import randint

from pzl_lib import PzlG
from pzl_lib import Egg
from pzl_lib import EditPair
from pzl_lib import UserEdits
from pzl_lib import Editor


class Sgg(object):
    simplest_hint = True
    HORIZONTAL = 0
    VERTICAL = 1
    BOX = 2
    CAUSE = 0
    EFFECT = 1
    SOLVE = 0
    HINT = 1
    GIVE_HINT = 0
    APPLY_HINT = 1


class SudokuModel(object):

    SIMPLE_FILTER = 0
    FIRST_ALG = 1

    def __init__(self, model_data):
        self.model_data = model_data
        self.datum = []
        self.row_indexes = []
        self.column_indexes = []
        self.box_indexes = []
        self.errors = []
        self.snapshots = []
        self.unsolved = []
        self.datum_indexes = None
        self.progress = False
        self.status = True
        self.editor = Editor(Sgg.HINT)
        self.user_edits = UserEdits()
        self.hint_status = Sgg.GIVE_HINT
        self.algorithm = -1
        self.algorithm_counts = [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
        self.score = None
        self.puzzle_number = None

    def create_indexes(self):
        """
        Set up useful arrays of datum indexes:
        1. rows
        2. columns
        3. boxes
        """
        box_starts = [0, 3, 6, 27, 30, 33, 54, 57, 60]
        for datum_index in range(0,
                                 81,
                                 9):
            self.row_indexes.append(
                list(range(datum_index,
                           datum_index + 9)))

        for datum_index in range(9):
            self.column_indexes.append(
                list(range(datum_index,
                           81,
                           9)))

        for box_index_1 in range(9):
            temp_list = []
            temp = box_starts[box_index_1]
            for box_index_2 in range(3):
                temp_list.append(temp)
                temp += 1
            temp = box_starts[box_index_1] + 9
            for box_index_2 in range(3):
                temp_list.append(temp)
                temp += 1
            temp = box_starts[box_index_1] + 18
            for box_index_2 in range(3):
                temp_list.append(temp)
                temp += 1
            self.box_indexes.append(temp_list)

    def init_puzzle(self, puzzle_number):
        if puzzle_number is None or puzzle_number < 0 or \
                puzzle_number > self.model_data.puzzle_count - 1:
            puzzle_number = randint(0, self.model_data.puzzle_count - 1)
        self.puzzle_number = puzzle_number
        puzzle_data = self.fetch_selected_puzzle(puzzle_number)
        answers = puzzle_data[1:]
        self.score = puzzle_data[0]
        self.init_datum()
        for datum_index in range(81):
            if answers[datum_index] < 0:
                answer = abs(answers[datum_index])
                given = True
            else:
                answer = answers[datum_index]
                given = False
            self.datum[datum_index].initialise(answer - 1, given)

    def reset(self):
        for datum in self.datum:
            datum.reset()

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

    def get_hint_status(self):
        return self.hint_status

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

    def check_ninemer(self, lists):
        """
        Look for duplicate guesses
        """
        ret = True
        for sub_list in lists:
            seen = []
            for datum_index in sub_list:
                guess = self.datum[datum_index].get_guess()
                if guess is not None:
                    if guess in seen:
                        ret = False
                        self.errors.append(datum_index)
                    else:
                        seen.append(guess)
            if not ret:
                break

    def check_datum(self):
        for datum in self.datum:
            if datum.is_consistent() != 0:
                self.errors.append(datum.index)

    def check_errors(self):
        """
        Look for duplicate guesses and then inconsistent datum
        """
        self.status = True
        self.errors = []
        self.check_ninemer(self.box_indexes)
        self.check_ninemer(self.row_indexes)
        self.check_ninemer(self.column_indexes)
        self.check_datum()
        if self.errors:
            self.status = False

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

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

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

    def get_board_updates(self):
        for datum in self.datum:
            self.editor.get_update_ops(datum)
        return self.editor.update_ops

    def simple_filter_0(self, strip_list):
        """
        If a cell's guess is set and == candidate, remove candidate
        from cell's neighbours in trip_list.
        """
        for datum_index_0 in strip_list:
            datum_0 = self.datum[datum_index_0]
            candidate = datum_0.guess
            if candidate is not None:
                cause_candidates = [candidate]
                cause_pairs = EditPair(datum_0, cause_candidates)
                effect_pairs = []
                for datum_index_1 in strip_list:
                    datum_1 = self.datum[datum_index_1]
                    ret = datum_1.candidate_is_set(candidate)
                    if ret:
                        effect_candidates = [candidate]
                        effect_pair = EditPair(datum_1, effect_candidates)
                        effect_pairs.append(effect_pair)
                if effect_pairs:
                    self.editor.add([cause_pairs], effect_pairs,
                                    self.algorithm)

    def simple_filter(self, direction):
        """
        If a cell's guess is set and == candidate, remove candidate
        from cell's box, row and column neighbours.
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.simple_filter_0(strip_list)
        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.simple_filter_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.simple_filter_0(strip_list)

    def hidden_singles_0(self, strip_list):
        for index_0 in strip_list:
            datum_0 = self.datum[index_0]
            candidates = datum_0.candidates
            strip_candidates = set()
            for index_1 in strip_list:
                if index_1 != index_0:
                    datum_1 = self.datum[index_1]
                    strip_candidates = strip_candidates.union(
                        datum_1.candidates)
            unique = candidates.difference(strip_candidates)
            if len(unique) == 1:
                candidate = unique.pop()
                cause_pairs = EditPair(datum_0, [candidate])
                effect_candidates = list(datum_0.other_candidates([candidate]))
                effect_pairs = EditPair(datum_0, effect_candidates)
                self.editor.add([cause_pairs], [effect_pairs], self.algorithm)

    def hidden_singles(self, direction):
        """
        Find candidates which are only present in a single
        cell in a strip.
        """
        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.hidden_singles_0(strip_list)
        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.hidden_singles_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.hidden_singles_0(strip_list)

    def naked_pairs_1(self, strip_list, datum_dic, candidates,
                      cause_pairs):
        effect_pairs = []
        for index_2 in strip_list:
            if index_2 not in datum_dic:
                datum_2 = self.datum[index_2]
                effect_candidates = []
                for candidate in candidates:
                    ret = datum_2.candidate_is_set(candidate)
                    if ret:
                        effect_candidates.append(candidate)
                if effect_candidates:
                    effect_pair = EditPair(datum_2, effect_candidates)
                    effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def naked_pairs_0(self, strip_list):
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            datum_0 = self.datum[index_0]
            datum_dic = {index_0: True}
            candidates_0 = datum_0.candidates
            if candidates_0:
                for item_1 in range(item_0 + 1, 9):
                    index_1 = strip_list[item_1]
                    datum_1 = self.datum[index_1]
                    candidates_1 = datum_1.candidates
                    if candidates_1:
                        datum_dic[index_1] = True
                        candidates_12 = candidates_0.union(candidates_1)
                        if len(candidates_12) == 2:
                            candidates = list(candidates_12)
                            cause_pairs_0 = EditPair(datum_0, candidates)
                            cause_pairs_1 = EditPair(datum_1, candidates)
                            cause_pairs = [cause_pairs_0, cause_pairs_1]
                            self.naked_pairs_1(strip_list, datum_dic,
                                               candidates,
                                               cause_pairs)
                        del datum_dic[index_1]

    def naked_pairs(self, direction):
        """
        Remove candidates which are the sole remaining candidates
        in exactly 2 cells in the same row or column
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.naked_pairs_0(strip_list)
        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.naked_pairs_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.naked_pairs_0(strip_list)

    def naked_triples_1(self, strip_list, datum_dic, candidates,
                        cause_pairs):
        effect_pairs = []
        for index_2 in strip_list:
            if index_2 not in datum_dic:
                datum_2 = self.datum[index_2]
                effect_candidates = []
                for candidate in candidates:
                    ret = datum_2.candidate_is_set(candidate)
                    if ret:
                        effect_candidates.append(candidate)
                if effect_candidates:
                    effect_pair = EditPair(datum_2, effect_candidates)
                    effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def naked_triples_0(self, strip_list):
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            datum_0 = self.datum[index_0]
            candidates_0 = datum_0.candidates
            if candidates_0:
                datum_dic = {index_0: True}
                for item_1 in range(item_0 + 1, 9):
                    index_1 = strip_list[item_1]
                    datum_1 = self.datum[index_1]
                    candidates_1 = datum_1.candidates
                    if candidates_1:
                        datum_dic[index_1] = True
                        candidates_12 = candidates_0.union(candidates_1)
                        for item_2 in range(item_1 + 1, 9):
                            index_2 = strip_list[item_2]
                            datum_2 = self.datum[index_2]
                            candidates_2 = datum_2.candidates
                            if candidates_2:
                                datum_dic[index_2] = True
                                candidates_123 = candidates_12.union(
                                    datum_2.candidates)
                                if len(candidates_123) == 3:
                                    candidates = list(candidates_123)
                                    cause_pairs_0 = \
                                        EditPair(datum_0, candidates)
                                    cause_pairs_1 = \
                                        EditPair(datum_1, candidates)
                                    cause_pairs_2 = \
                                        EditPair(datum_2, candidates)
                                    cause_pairs = [cause_pairs_0,
                                                   cause_pairs_1,
                                                   cause_pairs_2]
                                    self.naked_triples_1(strip_list,
                                                         datum_dic,
                                                         candidates,
                                                         cause_pairs)
                                del datum_dic[index_2]
                        del datum_dic[index_1]

    def naked_triples(self, direction):
        """
        Remove candidates which are the sole remaining candidates
        in exactly 3 cells in the same row or column
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.naked_triples_0(strip_list)
        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.naked_triples_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.naked_triples_0(strip_list)

    def naked_quads_0(self, strip_list):
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            datum_0 = self.datum[index_0]
            candidates_0 = datum_0.candidates
            if candidates_0:
                datum_dic = {index_0: True}
                for item_1 in range(item_0 + 1, 9):
                    index_1 = strip_list[item_1]
                    datum_1 = self.datum[index_1]
                    candidates_1 = datum_1.candidates
                    if candidates_1:
                        datum_dic[index_1] = True
                        candidates_12 = candidates_0.union(candidates_1)
                        for item_2 in range(item_1 + 1, 9):
                            index_2 = strip_list[item_2]
                            datum_2 = self.datum[index_2]
                            candidates_2 = datum_2.candidates
                            if candidates_2:
                                datum_dic[index_2] = True
                                candidates_123 = candidates_12.union(
                                    datum_2.candidates)
                                for item_3 in range(item_2 + 1,
                                                    9):
                                    index_3 = strip_list[item_3]
                                    datum_3 = self.datum[index_3]
                                    candidates_3 = datum_3.candidates
                                    if candidates_3:
                                        datum_dic[index_3] = True
                                        candidates_1234 = candidates_123.union(
                                            datum_3.candidates)
                                        if len(candidates_1234) == 4:
                                            candidates = list(candidates_1234)
                                            cause_pairs_0 = \
                                                EditPair(datum_0, candidates)
                                            cause_pairs_1 = \
                                                EditPair(datum_1, candidates)
                                            cause_pairs_2 = \
                                                EditPair(datum_2, candidates)
                                            cause_pairs_3 = \
                                                EditPair(datum_3, candidates)
                                            cause_pairs = [cause_pairs_0,
                                                           cause_pairs_1,
                                                           cause_pairs_2,
                                                           cause_pairs_3]
                                            self.naked_triples_1(strip_list,
                                                                 datum_dic,
                                                                 candidates,
                                                                 cause_pairs)
                                        del datum_dic[index_3]
                                del datum_dic[index_2]
                        del datum_dic[index_1]

    def naked_quads(self, direction):
        """
        Remove candidates which are the sole remaining candidates
        in exactly 4 cells in the same row or column
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.naked_quads_0(strip_list)
        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.naked_quads_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.naked_quads_0(strip_list)

    def hidden_pairs_1(self, datum_dic, candidates,
                       cause_pairs):
        effect_pairs = []
        for index_2 in datum_dic:
            datum_2 = self.datum[index_2]
            effect_candidates = list(datum_2.other_candidates(candidates))
            if effect_candidates:
                effect_pair = EditPair(datum_2, effect_candidates)
                effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def hidden_pairs_0(self, strip_list):
        """
        process a strip for hidden pairs
        """
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            datum_0 = self.datum[index_0]
            candidates_0 = datum_0.candidates
            datum_dic = {index_0: True}
            for item_1 in range(item_0 + 1, 9):
                index_1 = strip_list[item_1]
                datum_1 = self.datum[index_1]
                candidates_1 = datum_1.candidates
                pair = candidates_0.union(candidates_1)
                strip_candidates = set()
                datum_dic[index_1] = True
                for index_2 in strip_list:
                    if index_2 not in datum_dic:
                        datum_2 = self.datum[index_2]
                        strip_candidates = strip_candidates.union(
                            datum_2.candidates)
                difference = pair.difference(strip_candidates)
                # difference are the candidates common to
                # datum_0 and datum_1 but not in the rest of the strip
                if len(difference) == 2:
                    # there's 2 of them, so they are hidden pairs
                    # and all other candidates can be removed from
                    # their cells
                    cause_pairs_0 = EditPair(datum_0, difference)
                    cause_pairs_1 = EditPair(datum_1, difference)
                    cause_pairs = [cause_pairs_0, cause_pairs_1]
                    self.hidden_pairs_1(datum_dic,
                                        difference, cause_pairs)
                del datum_dic[index_1]
            item_0 += 1

    def hidden_pairs(self, direction):
        """
        Find pairs of candidates which only occur in two cells
        in a row or column. Remove the other candidates from
        these two cells.
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.hidden_pairs_0(strip_list)

        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.hidden_pairs_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.hidden_pairs_0(strip_list)

    def hidden_triples_1(self, datum_dic, candidates,
                         cause_pairs):
        effect_pairs = []
        for index_2 in datum_dic:
            datum_2 = self.datum[index_2]
            effect_candidates = list(datum_2.other_candidates(candidates))
            if effect_candidates:
                effect_pair = EditPair(datum_2, effect_candidates)
                effect_pairs.append(effect_pair)
        if effect_pairs:
            self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def hidden_triples_0(self, strip_list):
        """
        process a strip for hidden triples
        """
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            datum_0 = self.datum[index_0]
            candidates_0 = datum_0.candidates
            datum_dic = {index_0: True}
            for item_1 in range(item_0 + 1, 9):
                index_1 = strip_list[item_1]
                datum_1 = self.datum[index_1]
                candidates_1 = datum_1.candidates
                pair = candidates_0.union(candidates_1)
                strip_candidates = set()
                datum_dic[index_1] = True
                for item_2 in range(item_1 + 1, 9):
                    index_2 = strip_list[item_2]
                    datum_2 = self.datum[index_2]
                    candidates_2 = datum_2.candidates
                    triple = pair.union(candidates_2)
                    strip_candidates = set()
                    datum_dic[index_2] = True
                    for index_3 in strip_list:
                        if index_3 not in datum_dic:
                            datum_3 = self.datum[index_3]
                            strip_candidates = strip_candidates.union(
                                datum_3.candidates)
                    difference = triple.difference(strip_candidates)
                    # difference are the candidates common to
                    # datum_0, datum_1 and datum_2 but not in the
                    # rest of the strip
                    if len(difference) == 3:
                        # there's 3 of them, so they are hidden triples
                        # and all other candidates can be removed from
                        # their cells
                        cause_pairs_0 = EditPair(datum_0, difference)
                        cause_pairs_1 = EditPair(datum_1, difference)
                        cause_pairs_2 = EditPair(datum_2, difference)
                        cause_pairs = [cause_pairs_0,
                                       cause_pairs_1,
                                       cause_pairs_2]
                        self.hidden_pairs_1(datum_dic,
                                            difference, cause_pairs)
                    del datum_dic[index_2]
                del datum_dic[index_1]

    def hidden_triples(self, direction):
        """
        Find triples of candidates which only occur in three cells
        in a row or column. Remove the other candidates from
        these three cells.
        """

        if direction == Sgg.HORIZONTAL:
            for strip_list in self.row_indexes:
                self.hidden_triples_0(strip_list)

        elif direction == Sgg.VERTICAL:
            for strip_list in self.column_indexes:
                self.hidden_triples_0(strip_list)
        elif direction == Sgg.BOX:
            for strip_list in self.box_indexes:
                self.hidden_triples_0(strip_list)

    def get_box_set(self, strip_list):
        """
        Get the candidates from the 3 squares across a box.
        """
        box_set = self.datum[strip_list[0]].candidates | \
            self.datum[strip_list[1]].candidates | \
            self.datum[strip_list[2]].candidates
        return box_set

    def lc_1_3(self, box_list, effect):
        """
        Within the box strip look for causes of effect.
        """
        cause_pairs = []
        for box_index in range(3):
            datum_index = box_list[box_index]
            datum = self.datum[datum_index]
            cause = datum.candidates.intersection(effect)
            if cause:
                cause_pair = EditPair(datum, cause)
                cause_pairs.append(cause_pair)
        return cause_pairs

    def lc_1_2(self, strip_list, strip_segment, causes_set):
        """
        causes_set contains candidates unique to that box strip.
        Look for those candidates in the rest of the strip (row or column).
        """
        effect_pairs = []
        box_list = strip_list[strip_segment:strip_segment+3]
        for datum_index in strip_list:
            if datum_index not in box_list:
                datum = self.datum[datum_index]
                effect = datum.candidates.intersection(causes_set)
                if effect:
                    effect_pair = EditPair(datum, effect)
                    effect_pairs.append(effect_pair)
        return effect_pairs

    def lc_1_1(self, strip_indexes, box_index, direction,
               set_0, set_1, set_2):
        """
        sets contain the candidates in the 3 box strips.
        strip_indexes are the datum_indexes for the whole strip (row or column)
        If any are unique, send them to lc_1_2
        which looks for effects outside the strips.
        If this finds results, get the cause details using lc_1_3.
        """

        if direction == Sgg.HORIZONTAL:
            strip_index = 3 * int(box_index / 3)
            strip_segment = 3 * int(box_index % 3)
        else:
            strip_index = 3 * int(box_index % 3)
            strip_segment = 3 * int(box_index / 3)

        u_0 = set_0 - set_1 - set_2
        # u_0 contains any candidates unique to one box strip
        if u_0:
            strip_list = strip_indexes[strip_index]
            effect_pairs = self.lc_1_2(strip_list, strip_segment, u_0)
            if effect_pairs:
                effect_set = effect_pairs[0].candidates
                cause_pairs = self.lc_1_3(strip_list[strip_segment:],
                                          effect_set)
                self.editor.add(cause_pairs, effect_pairs, self.algorithm)
        u_0 = set_1 - set_0 - set_2
        if u_0:
            strip_list = strip_indexes[strip_index + 1]
            effect_pairs = self.lc_1_2(strip_list, strip_segment, u_0)
            if effect_pairs:
                effect_set = effect_pairs[0].candidates
                cause_pairs = self.lc_1_3(strip_list[strip_segment:],
                                          effect_set)
                self.editor.add(cause_pairs, effect_pairs, self.algorithm)
        u_0 = set_2 - set_0 - set_1
        if u_0:
            strip_list = strip_indexes[strip_index + 2]
            effect_pairs = self.lc_1_2(strip_list, strip_segment, u_0)
            if effect_pairs:
                effect_set = effect_pairs[0].candidates
                cause_pairs = self.lc_1_3(strip_list[strip_segment:],
                                          effect_set)
                self.editor.add(cause_pairs, effect_pairs, self.algorithm)

    def locked_candidate_1(self):
        """
        If a symbol can only occur in one row or one column of a box
        it cannot occur in those rows or columns outside of the box.
        """

        for box_index in range(9):
            box_list = self.box_indexes[box_index]
            # rows
            row_list = box_list[0:3]
            set_0 = self.get_box_set(row_list)
            row_list = box_list[3:6]
            set_1 = self.get_box_set(row_list)
            row_list = box_list[6:9]
            set_2 = self.get_box_set(row_list)
            self.lc_1_1(self.row_indexes, box_index,
                        Sgg.HORIZONTAL, set_0, set_1, set_2)
            # columns
            column_list = [box_list[0], box_list[3], box_list[6]]
            set_0 = self.get_box_set(column_list)
            column_list = [box_list[1], box_list[4], box_list[7]]
            set_1 = self.get_box_set(column_list)
            column_list = [box_list[2], box_list[5], box_list[8]]
            set_2 = self.get_box_set(column_list)
            self.lc_1_1(self.column_indexes, box_index,
                        Sgg.VERTICAL, set_0, set_1, set_2)

    def lc_2_3(self, inter, box_strip, others):
        """
        others are the box_indexes for the 2 box_strips not in box_strip
        inter is the unique candidates for box_strip (ie not in the other
        2 box_strips).
        """
        effect_pairs = []
        cause_pairs = []
        for item in others:
            datum = self.datum[item]
            effect = inter.intersection(datum.candidates)
            if effect:
                effect_pair = EditPair(datum, effect)
                effect_pairs.append(effect_pair)

                if effect_pairs:
                    for item in box_strip:
                        datum = self.datum[item]
                        cause = inter.intersection(datum.candidates)
                        if cause:
                            cause_pair = EditPair(datum, cause)
                            cause_pairs.append(cause_pair)

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

    def lc_2_2(self, strip_index, strip_indexes, direction,
               set_0, set_1, set_2):
        """
        sets contain the candidates in the 3 box strips.
        strip_indexes are the datum_indexes for the whole strip (row or column)
        """
        # first box strip
        if set_0:
            inter = set_0 - set_1 - set_2
            if inter and len(inter) < len(set_0):
                if direction == Sgg.HORIZONTAL:
                    box_index = 3 * int(strip_index/3)
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][0:3]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)
                else:
                    box_index = int(strip_index/3)
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][0:3]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)

        # middle box strip
        if set_1:
            inter = set_1 - set_0 - set_2
            if inter and len(inter) < len(set_1):
                if direction == Sgg.HORIZONTAL:
                    box_index = 1 + 3 * int(strip_index/3)
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][3:6]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)
                else:
                    box_index = 3 + int(strip_index/3)
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][3:6]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)

        # last box strip
        if set_2:
            inter = set_2 - set_1 - set_0
            if inter and len(inter) < len(set_2):
                if direction == Sgg.HORIZONTAL:
                    box_index = 3 * int(strip_index/3) + 2
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][6:9]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)
                else:
                    box_index = int(strip_index/3) + 6
                    box_indexes = self.box_indexes[box_index]
                    box_strip = strip_indexes[strip_index][6:9]
                    others = [a for a in box_indexes if a not in box_strip]
                    self.lc_2_3(inter, box_strip, others)

    def locked_candidate_2_1(self, strip_indexes, direction):
        """
        Get the candidate sets for each box_strip.
        lc_2_2 finds the unique candidates for each box_strip
        and then checks against the other box_strips that box.
        """
        for strip_index in range(9):
            strip_list = strip_indexes[strip_index]
            box_strip = strip_list[0:3]
            set_0 = self.get_box_set(box_strip)
            box_strip = strip_list[3:6]
            set_1 = self.get_box_set(box_strip)
            box_strip = strip_list[6:9]
            set_2 = self.get_box_set(box_strip)
            self.lc_2_2(strip_index, strip_indexes,
                        direction, set_0, set_1, set_2)

    def locked_candidate_2(self):
        """
        If, for a particular row or column, a symbol can occur in
        only one box, then it cannot occur elsewhere in that box.
        """

        self.locked_candidate_2_1(self.row_indexes, Sgg.HORIZONTAL)
        self.locked_candidate_2_1(self.column_indexes, Sgg.VERTICAL)

    def x_wing_2(self, candidate, strip_list, cause_list):
        """
        Look along a strip for cells not in cause_list
        which contain candidate: they can be deleted
        """
        effect_pairs = []
        for datum_index in strip_list:
            if datum_index not in cause_list:
                datum = self.datum[datum_index]
                if candidate in datum.candidates:
                    effect_pair = EditPair(datum, [candidate])
                    effect_pairs.append(effect_pair)
        return effect_pairs

    def x_wing_1(self, candidate, strip_list):
        """
        Try to find a pair of cells in a strip
        which are the only ones with candidate
        """
        results = []
        for item_0 in range(9):
            index_0 = strip_list[item_0]
            if candidate in self.datum[index_0].candidates:
                for item_1 in range(item_0 + 1, 9):
                    index_1 = strip_list[item_1]
                    if candidate in self.datum[index_1].candidates:
                        strip_candidates = set()
                        for index_2 in strip_list:
                            if index_2 != index_0 and index_2 != index_1:
                                strip_candidates = strip_candidates.union(
                                    self.datum[index_2].candidates)
                        if candidate not in strip_candidates:
                            # candidate only occurs in index_0
                            # and index_1
                            results.append([index_0, index_1, item_0, item_1])
        return results

    def x_wing_0(self, strip_list_0, strip_list_1):
        for candidate in range(9):
            results = []
            for strip_list in strip_list_0:
                results_0 = self.x_wing_1(candidate, strip_list)
                if results_0:
                    # for strip_list candidate only occurs in 2 cells
                    results.append(results_0)
            if len(results) > 1:
                # for these strip_lists candidate only occurs in 2 cells
                # is there a pair on the same orthogonal strips?
                for result_index_0 in range(len(results)):
                    result_0 = results[result_index_0]
                    for result_index_1 in range(result_index_0 + 1,
                                                len(results)):
                        result_1 = results[result_index_1]
                        if result_0[0][2] == result_1[0][2] and \
                                result_0[0][3] == result_1[0][3]:
                            # create cause_list so x_wing_2 can omit them
                            cause_list = []
                            cause_list.append(result_0[0][0])
                            cause_list.append(result_0[0][1])
                            cause_list.append(result_1[0][0])
                            cause_list.append(result_1[0][1])

                            cause_pairs = []
                            for datum_index in cause_list:
                                datum = self.datum[datum_index]
                                cause_pair = EditPair(datum, [candidate])
                                cause_pairs.append(cause_pair)

                            strip_list = strip_list_1[result_0[0][2]]
                            # get any effects this strip
                            effect_pairs_0 = self.x_wing_2(candidate,
                                                           strip_list,
                                                           cause_list)

                            strip_list = strip_list_1[result_1[0][3]]
                            # get any effects this strip
                            effect_pairs_1 = self.x_wing_2(candidate,
                                                           strip_list,
                                                           cause_list)
                            # parcel them up for editing
                            effect_pairs = []
                            for effect_pair in effect_pairs_0:
                                effect_pairs.append(effect_pair)
                            for effect_pair in effect_pairs_1:
                                effect_pairs.append(effect_pair)
                            if effect_pairs:
                                self.editor.add(cause_pairs,
                                                effect_pairs,
                                                self.algorithm)

    def x_wing(self, direction):
        """
        Find single candidates which only occur in the intersection
        of a pair of rows and columns, but which are not possible
        elsewhere in that pair of rows. Remove the candidate from
        elsewhere in those columns.
        """

        if direction == Sgg.HORIZONTAL:
            self.x_wing_0(self.row_indexes, self.column_indexes)
        elif direction == Sgg.VERTICAL:
            self.x_wing_0(self.column_indexes, self.row_indexes)

    def random_answer(self):
        """
        When there's no choice, just pick an answer from the cell
        with the most remaining candidates.
        """
        best = 0
        best_datum = None
        for datum in self.datum:
            candidates_left = len(datum.candidates)
            if candidates_left > best:
                best = candidates_left
                best_datum = datum
        if best_datum is not None:
            cause_pairs = None
            candidate = best_datum.symbol_index
            effect_candidates = \
                list(best_datum.other_candidates([candidate]))
            effect_pairs = EditPair(best_datum, effect_candidates)
            self.editor.add([cause_pairs],
                            [effect_pairs], self.algorithm)

    def apply_all_algs(self):
        directions = [(Sgg.HORIZONTAL, Sgg.VERTICAL, Sgg.BOX),
                      (Sgg.HORIZONTAL, Sgg.VERTICAL), (None)]

        last_algorithm = len(self.algorithms) - 2
        self.editor.guess_set = True
        self.algorithm = SudokuModel.FIRST_ALG
        while True:
            effective = False
            self.progress = False
            self.check_errors()
            if not self.status:
                break
            self.simple_filter_exhaustively()
            self.check_errors()
            if not self.status:
                break

            algorithm_pair = self.algorithms[self.algorithm]
            algorithm = algorithm_pair[0]
            direction_index = algorithm_pair[1]
            if direction_index == 2:
                algorithm()
                effective = self.manage_edits(self.algorithm)
            else:
                for direction in directions[direction_index]:
                    algorithm(direction)
                    effective = self.manage_edits(self.algorithm)
                    if effective:
                        break

            if not effective:
                self.algorithm += 1
                if self.algorithm > last_algorithm:
                    if not self.progress:
                        break
                    self.algorithm = SudokuModel.FIRST_ALG
            else:
                self.algorithm = SudokuModel.FIRST_ALG
            if self.is_finished():
                break

    def do_hint(self):
        directions = [(Sgg.HORIZONTAL, Sgg.VERTICAL, Sgg.BOX),
                      (Sgg.HORIZONTAL, Sgg.VERTICAL), (None)]
        self.progress = False
        self.check_errors()
        if not self.status:
            return
        self.editor.set_mode(Sgg.HINT)
        if not self.is_finished():
            self.algorithm = SudokuModel.SIMPLE_FILTER
            self.simple_filter(Sgg.HORIZONTAL)
            if self.editor.got_data():
                self.progress = True
            else:
                self.simple_filter(Sgg.VERTICAL)
                if self.editor.got_data():
                    self.progress = True
                else:
                    self.simple_filter(Sgg.BOX)
                    if self.editor.got_data():
                        self.progress = True
            if not self.progress:
                if Sgg.simplest_hint:
                    self.algorithm = 0
                    for algorithm_pair in self.algorithms:
                        self.algorithm += 1
                        algorithm = algorithm_pair[0]
                        direction_index = algorithm_pair[1]
                        if direction_index == 2:
                            algorithm()
                            if self.editor.got_data():
                                self.progress = True
                                return
                        else:
                            for direction in directions[direction_index]:
                                algorithm(direction)
                                if self.editor.got_data():
                                    self.progress = True
                                    return
                else:
                    self.algorithm = 0
                    for algorithm_pair in self.algorithms[:-1]:
                        self.algorithm += 1
                        algorithm = algorithm_pair[0]
                        direction_index = algorithm_pair[1]
                        if direction_index == 2:
                            algorithm()
                            if self.editor.got_data():
                                self.progress = True
                        else:
                            for direction in directions[direction_index]:
                                algorithm(direction)
                                if self.editor.got_data():
                                    self.progress = True
                    if not self.progress:
                        self.algorithm += 1
                        self.random_answer()
                        if self.editor.got_data():
                            self.progress = True

    def show_solution(self):
        for datum_index in range(81):
            self.set_guess(self.datum[datum_index],
                           self.datum[datum_index].symbol_index, False)

    def is_finished(self):
        if self.status:
            status = True
            for datum in self.datum:
                if datum.guess is None:
                    status = False
                    break
        else:
            status = False
        return status

    def manage_edits(self, algorithm):
        """
        In order to use the same code to handle solving and
        providing hints, and to satisfy the requirement that
        simple_filter must be applied before the algorithms
        will work we use manage_edits.
        """

        if self.editor.mode == Sgg.SOLVE:
            self.editor.apply()
            count = len(self.editor.changed_datum)

            if count > 0:
                self.progress = True
                self.algorithm_counts[algorithm] += count
            self.editor.reset()
        elif self.editor.mode == Sgg.HINT:
            if self.editor.changed_datum:
                self.progress = True
            else:
                self.progress = False
            self.editor.reset()
        return self.progress

    def simple_filter_exhaustively(self):
        """
        For most of the algorithms to work, it is assumed that
        simple_filter has been applied exhaustively. But we only
        need to apply it if a guess has been set since the last
        time.
        """
        if self.editor.guess_set:
            sf_progress = True
            while sf_progress:
                sf_progress = False
                self.simple_filter(Sgg.HORIZONTAL)
                if self.editor.got_data():
                    sf_progress = True
                self.manage_edits(SudokuModel.SIMPLE_FILTER)
                self.simple_filter(Sgg.VERTICAL)
                if self.editor.got_data():
                    sf_progress = True
                self.manage_edits(SudokuModel.SIMPLE_FILTER)
                self.simple_filter(Sgg.BOX)
                if self.editor.got_data():
                    sf_progress = True
                self.manage_edits(SudokuModel.SIMPLE_FILTER)
        self.editor.guess_set = False

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

    def apply_hint(self):
        if self.progress:
            for edit_pair in self.editor.effects:
                datum_index = edit_pair.datum.index
                candidates = edit_pair.candidates
                datum = self.datum[datum_index]
                for candidate in candidates:
                    guess = datum.del_candidate(candidate)

    def fetch_selected_puzzle(self, puzzle_number):
        """ load a built-in puzzle"""
        return self.model_data.get_puzzle(puzzle_number)

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

    def solve_no_guessing(self):
        solved = False
        unsolved_candidates = 999999
        self.check_errors()
        self.zero_algorithm_counts()
        if self.status:
            self.editor.reset()
            self.editor.set_mode(Sgg.SOLVE)
            while True:
                self.apply_all_algs()
                self.check_errors()
                if not self.status:
                    # shouldn't get here
                    PzlG.logger.logger.error("solve_no_guessing 1")
                    exit(1)
                else:
                    if self.is_finished():
                        solved = True
                        break
                undone = self.get_progress()
                if undone >= unsolved_candidates:
                    break
                else:
                    unsolved_candidates = undone

            if self.status:
                if not solved:
                    # as far as we can go without guessing
                    self.get_unsolved_data()
                    self.check_errors()
                    if not self.status:
                        PzlG.logger.logger.error("solve_no_guessing 2")
                        exit(1)

    def get_progress(self):
        """
        Get a list of the unsolved datum and their candidates.
        """
        undone = 0
        for datum in self.datum:
            if not datum.guess_is_set():
                undone += len(datum.candidates)
        return undone

    def get_unsolved_data(self):
        """
        Get a list of the unsolved datum and their candidates.
        """
        self.unsolved = []
        for datum in self.datum:
            if not datum.guess_is_set():
                pair = datum.index, datum.candidates
                self.unsolved.append(pair)
