import functools import os, sys import copy import numpy as np import re import itertools import operator import time, datetime import multiprocessing as mp import queue from contextlib import contextmanager nnn = 0 # Constraint functions: def FirstCellIsGreaterThanSumOfRest(*cells): return cells[0] > sum(cells[1:]) def FirstCellIsSumOfRest(*cells): return cells[0] == sum(cells[1:]) def FirstCellIsSumOfRestModSecond(*cells): return cells[0] == sum(cells[2:]) % cells[1] def FirstCellIsNotSumOfRest(*cells): return cells[0] != sum(cells[1:]) def First2CellsAreSumOfRest(*cells): return (cells[0] * 10 + cells[1]) == sum(cells[2:]) def NumbersIncrease(*cells): return functools.reduce(lambda a, b: a and b, map(lambda a, b: a < b, cells[:-1], cells[1:])) def FirstDoesNotAppearsInRestOfSet(*cells): return cells[1:].count(cells[0]) == 0 def FirstAppearsOnceInRestOfSet(*cells): return cells[1:].count(cells[0]) == 1 def FindNextOfSecondModFirstInRestOfSet(*cells): if NextOfSecondModFirstAppearsOnceInRestOfSet(*cells): return cells[2:].index(cells[1] % cell[0] + 1) + 2 else: return None def NextOfSecondModFirstAppearsOnceInRestOfSet(*cells): return (cells[2:].count(cells[1] % cell[0] + 1) == 1) def PreviousOfSecondModFirstAppearsOnceInRestOfSet(*cells): return (cells[2:].count((cells[1] - 2) % cell[0] + 1) == 1) def PreviousAndNextOfThirdPlusMinusSecondModFirstAppearsOnceInRestOfSet(*cells): return (cells[3:].count((cells[2] + cells[1] - 1) % cells[0] + 1) == 1) and (cells[3:].count((cells[2] - cells[1] - 1) % cells[0] + 1) == 1) def PreviousAndNextOfThirdPlusMinusSecondModFirstAppearsOnceOrTwiceInRestOfSet(*cells): return (cells[3:].count((cells[2] + cells[1] - 1) % cells[0] + 1) <= 2) and (cells[3:].count((cells[2] - cells[1] - 1) % cells[0] + 1) <= 2) def AllDifferent(*cells): return len(cells) == len(set(cells)) def IndexedThermo(*cells): cell1 = cells[0] cell2 = cells[-1] if cell1 == cell2: return False if cell1 < cell2: thermocells = cells[cell1-1:cell2] else: thermocells = cells[::-1][cell2-1:cell1] return functools.reduce(lambda a, b: a and b, map(lambda a, b: a < b, thermocells[:-1], thermocells[1:])) # Set generation functions: def ParamOriginAndKnightsMoves(xym, xyd, xy0): x0, y0 = xy0 return [xym, xyd,] + list(filter(lambda xy: (0 < xy[0] < 10) and (0 < xy[1] < 10), ((x0, y0), (x0-2, y0-1), (x0-2, y0+1), (x0+2, y0-1), (x0+2, y0+1), (x0-1, y0-2), (x0-1, y0+2), (x0+1, y0-2), (x0+1, y0+2)))) def OriginAndKnightsMoves(xy0): x0, y0 = xy0 return list(filter(lambda xy: (0 < xy[0] < 10) and (0 < xy[1] < 10), ((x0, y0), (x0-2, y0-1), (x0-2, y0+1), (x0+2, y0-1), (x0+2, y0+1), (x0-1, y0-2), (x0-1, y0+2), (x0+1, y0-2), (x0+1, y0+2)))) def KnightsMoves(xy0): x0, y0 = xy0 return list(filter(lambda xy: (0 < xy[0] < 10) and (0 < xy[1] < 10), ((x0-2, y0-1), (x0-2, y0+1), (x0+2, y0-1), (x0+2, y0+1), (x0-1, y0-2), (x0-1, y0+2), (x0+1, y0-2), (x0+1, y0+2)))) # Generic functions def prod(array): return functools.reduce(operator.mul, array) def C(n, c): return prod(range(c+1, n+1)) // n def B(b): return 'T' if b else 'f' # Puzzle definition class SquareSudokuPuzzle: class Status: global_progress = False progress_step = False finished = False solved = False failed = False timedout = False removal_steps = 0 exploratory_steps = 0 recursion_level = 0 max_possibles = 0 min_possibles = 0 def __init__(self, rootsize = 3, title = "", givens = {}, constraints = {}, clues = {}, debug = 0, debug_step = 0): self.debug = debug self.debug_step = debug_step self.status = self.Status() self.rootsize = rootsize self.size = rootsize ** 2 self.digits = set(range(1, self.size + 1)) self.columns = self.digits self.rows = self.digits self.boxes = self.digits self.sumalldiff = (self.size * (self.size + 1)) // 2 self.status.max_possibles = self.size self.status.min_possibles = self.size self.solutions_filename = '' rc0 = { b: ( 1 + ((b - 1) // rootsize) * rootsize, 1 + ((b - 1) % rootsize) * rootsize ) for b in self.boxes } self.puzzle = { 'Information': { 'Title': title, 'BoardType': 'Square Sudoku', 'RootSize': rootsize, 'BoardSize': self.size, }, 'Board': {(r, c): set(self.digits) for r in self.rows for c in self.columns}, 'AllSets': { 'Rows': { 'Constraints': [AllDifferent,], 'Sets': {r: [(r, c) for c in self.columns] for r in self.rows}, }, 'Columns': { 'Constraints': [AllDifferent,], 'Sets': {c: [(r, c) for r in self.rows] for c in self.columns}, }, 'Boxes': { 'Constraints': [AllDifferent,], 'Sets': {b: [(rc0[b][0]+r, rc0[b][1]+c) for r in range(rootsize) for c in range(rootsize)] for b in self.boxes}, }, }, 'Givens': {}, } self.info = self.puzzle['Information'] self.board = self.puzzle['Board'] self.givens = self.puzzle['Givens'] self.title = self.info['Title'] # Add givens and fill in the grid if givens: if isinstance(givens, dict): self.givens = givens else: # Assume a string # Translate string to dictionary for n, d in enumerate(re.sub('[^0-9a-zA-Z.]', '', re.sub('#.*\n', '', givens))): if d != '.': r = 1 + n // self.size c = 1 + n % self.size self.givens.update({(r, c): int(d)}) for cell, digit in self.givens.items(): self.board[cell] = {digit,} # Initial singles are the givens, but not the clues self.singles = copy.deepcopy(self.givens) # Add clues (determined or not) to the board if any if clues: #self.puzzle['Clues'] = clues self.board.update(clues) self.givens.update(clues) # TODO: handle undetermined clues # Add constraints if constraints: self.puzzle['AllSets'].update(constraints) # Build constraints inventory, always, as there are always standard constraints self.__BuildConstraintsInventory() # TODO: in due course make this OO, with self registration depending on constraints # though that presumes tailored/targetted solving strategies. self.strategies = [ self.AllDifferentStrategy2_SiftGroups, self.FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference, self.StoredSuccessfulStrategiesStrategy4_FilterOverlappingSets_with_AlwaysInDigits, self.FirstCellIsSumOfRestStrategy5_ReductionOfPossibles, self.ThermoStrategy8_ReducePossibles, self.GenericTrialAndErrorPerConstraintStrategy98_Systematic, ] def OriginAndKnightsMoves(self, xy0): x0, y0 = xy0 return list(filter(lambda xy: (0 < xy[0] <= self.size) and (0 < xy[1] <= self.size), ((x0, y0), (x0-2, y0-1), (x0-2, y0+1), (x0+2, y0-1), (x0+2, y0+1), (x0-1, y0-2), (x0-1, y0+2), (x0+1, y0-2), (x0+1, y0+2)))) def IndexedThermosValidation(self, *cells): for r in self.rows: c1 = cells[r-1] c2 = cells[r+self.size-1] if c1 > c2: c1 = self.size + 1 - c1 c2 = self.size + 1 - c2 for c in range(c1, c2+1): r1 = cells[c+self.size*2-1] r2 = cells[c+self.size*3-1] if r1 > r2: r1 = self.size + 1 - r1 r2 = self.size + 1 - r2 if r1 <= r <= r2: return False return True def IndexedThermosColumnsValidation(self, c, cells): for r in self.rows: c1 = cells[r-1] c2 = cells[r+self.size-1] if c1 == 0 or c2 == 0: continue if c1 > c2: c1 = self.size + 1 - c1 c2 = self.size + 1 - c2 if c1 <= c <= c2: r1 = cells[c+self.size*2-1] r2 = cells[c+self.size*3-1] if r1 == 0 or r2 == 0: return True if r1 > r2: r1 = self.size + 1 - r1 r2 = self.size + 1 - r2 if r1 <= r <= r2: return False return True def OrthogonallyAdjacentCells(self, xy0): x0, y0 = xy0 return list(filter(lambda xy: (0 < xy[0] <= self.size) and (0 < xy[1] <= self.size), ((x0, y0), (x0, y0-1), (x0, y0+1), (x0+1, y0), (x0-1, y0)))) def OrthogonallyAdjacentBoxes(self, xy0): x0, y0 = xy0 return list(filter(lambda xy: (0 < xy[0] <= self.rootsize) and (0 < xy[1] <= self.rootsize), ((x0, y0), (x0, y0-1), (x0, y0+1), (x0+1, y0), (x0-1, y0)))) def __AddConstraint(self, allsetsid, constraintid, setid, constraint, s): n_all_constraints = len(self.all_constraints) if allsetsid not in self.crossref: self.crossref[allsetsid] = {} self.crossref[allsetsid][setid] = n_all_constraints if allsetsid in ('Rows', 'Columns', 'Boxes', 'DisjointSets'): if constraint is AllDifferent: if allsetsid not in self.all_different_9cell_crossref: self.all_different_9cell_crossref[allsetsid] = {} self.all_different_9cell_crossref[allsetsid][setid] = n_all_constraints if allsetsid not in self.puzzle['AllSets']: self.puzzle['AllSets'][allsetsid] = {} self.puzzle['AllSets'][allsetsid]['Sets'] = {} if setid not in self.puzzle['AllSets'][allsetsid]['Sets']: self.puzzle['AllSets'][allsetsid]['Sets'][setid] = s self.all_constraints.append({ 'AllSetsID': allsetsid, 'ConstraintsID': constraintid, 'SetID': setid, 'n': n_all_constraints, 'Constraint': constraint, 'Set': s, 'SetSize': len(s), 'Deterministic': False, 'NumberOfConstraintsPerCell': 0, # we want this high (more 'tension') 'NumberOfLinkedConstraints': 0, # we want this low (less complexity) 'SolvabilityScore': 0, }) if constraint is not None: for cell in s: if cell not in self.cell_constraints: self.cell_constraints[cell] = [] self.cell_constraints[cell].append({ 'n': n_all_constraints, 'Constraint': constraint, 'Set': s, }) def __BuildConstraintsInventory(self): self.cell_constraints = {} self.all_constraints = [] self.crossref = {} self.all_different_9cell_crossref = {} # Make a structured inventory of all constraints for cell in self.board: self.cell_constraints[cell] = [] for allsetsid, allsets in self.puzzle['AllSets'].items(): for constraintid, constraint in enumerate(allsets['Constraints']): if self.debug >= 3: print(f'self.__AddConstraint({allsetsid}, {constraintid}, ?, {constraint}, ?) Sets = {allsets["Sets"]}') for setid, s in allsets['Sets'].items(): if self.debug >= 3: print(f'self.__AddConstraint({allsetsid}, {constraintid}, {setid}, {constraint}, {s})') self.__AddConstraint(allsetsid, constraintid, setid, constraint, s) # Establish groups of rows and columns for Strategy 3, to help find small regions # with small subsets that can be calculated to be constrained to an interesting sum. for allsetsid in ['Rows', 'Columns']: if allsetsid in self.all_different_9cell_crossref: for g1, cn1 in list(self.all_different_9cell_crossref[allsetsid].items())[:-1]: for g2, cn2 in list(self.all_different_9cell_crossref[allsetsid].items())[g1:]: self.__AddConstraint("Groups", None, f'{allsetsid} {g1}..{g2}' , None, list(set.union(*( set(self.all_constraints[self.all_different_9cell_crossref[allsetsid][g]]['Set']) for g in range(g1, g2+1) ))) ) # Prepare for groups of adjacent boxes allboxes = {} nallboxes = {} alladjacentboxes = {} self.boxaliases = {} for n, rc in enumerate(self.puzzle['AllSets']['Boxes']['Sets'][1]): # Counting boxes from 0 for simple power of 2 arythmetics allboxes[n] = rc nallboxes[rc] = n alladjacentboxes[n] = self.OrthogonallyAdjacentBoxes(rc) # Calculate which combinations of boxes form regions of orthogonally adjacent boxes for ncombi in range(1, 2**self.size): checkalladjacent = {n: False for n in allboxes if (2**n) & ncombi} if len(checkalladjacent) >= 2: n0 = list(checkalladjacent.keys())[0] checkalladjacent[n0] = True progress = True while progress: progress = False for n in checkalladjacent: if checkalladjacent[n]: for rc in alladjacentboxes[n]: nc = nallboxes[rc] if nc in checkalladjacent: if not checkalladjacent[nc]: checkalladjacent[nc] = True progress = True alladjacent = True for n in checkalladjacent: if not checkalladjacent[n]: alladjacent = False break if alladjacent: # Cross ref boxes are numbered from 1, not 0, so we need to add 1 (twice) self.boxaliases[ncombi] = f'Boxes {[n+1 for n in checkalladjacent]}' self.__AddConstraint("Groups", None, self.boxaliases[ncombi], None, list(set.union(*( set(self.all_constraints[self.all_different_9cell_crossref['Boxes'][g+1]]['Set']) for g in checkalladjacent ))) ) def __ComputeSolvabilityAndEffectiveSets(self): for n, c in enumerate(self.all_constraints): c.update({ 'ConstraintSatisfied': False, 'ConstraintRedundant': False, 'Subsets': [], 'Supersets': [], 'OverlappingSets': [], 'EffectiveSet': [c for c in c['Set'] if len(self.board[c]) > 1], }) # The effective set is the subset of the constraint cells that still have degrees of freedom for n, c in enumerate(self.all_constraints): # TODO: decide whether this if has a rightful place # preventing the inventory of subsets... for groups of rows, columns or boxes # This was a bug fix where strategy 1 sifting sifted too aggressively, but the bug might be somewhere else #if c['Constraint'] is not None: cells = c['Set'] eset1 = set(c['EffectiveSet']) linkedconstraints = [] for cell in eset1: for linked_contraint in self.cell_constraints[cell]: if linked_contraint not in linkedconstraints: linkedconstraints.append(linked_contraint) cpc = sum(len(self.cell_constraints[cell]) for cell in cells) / len(cells) nlc = 1 + len(linkedconstraints) sos = 3*cpc + nlc if c['Constraint'] == FirstCellIsSumOfRest: sp = self.Possibles(cells) if sp: p = self.board[c['Set'][0]] if len(p) == 1: givens = set(cell for cell in cells[1:] if len(self.board[cell]) == 1) if len(givens) < len(cells) - 1: sum_givens = self.SumGivens(givens) sos += 2 + 30 * len(cells) * ((list(p)[0]-sum_givens)/(len(cells)-len(givens)-1) - 5)**2 + 10 / prod(len(s) for s in sp) elif c['Constraint'] == NumbersIncrease: sos += 30 sos = sos / len(cells) c.update({ 'NumberOfConstraintsPerCell': cpc, 'NumberOfLinkedConstraints': nlc, 'SolvabilityScore': sos, }) for n2, c2 in list(enumerate(self.all_constraints))[n+1:]: # TODO: decide whether this if has a rightful place #if c2['Constraint'] is not None: # Test areas (cell coverage), overlaps... eset2 = set(c2['EffectiveSet']) if eset1.issubset(eset2): if eset1 != eset2: if c['Constraint'] is not None: c2['Subsets'].append(n) if c2['Constraint'] is not None: c['Supersets'].append(n2) if eset2.issubset(eset1): if eset1 != eset2: if c2['Constraint'] is not None: c['Subsets'].append(n2) if c['Constraint'] is not None: c2['Supersets'].append(n) if eset2 & eset1: if c2['Constraint'] is not None: c['OverlappingSets'].append(n2) if c['Constraint'] is not None: c2['OverlappingSets'].append(n) allsumsubsets = set() for n2 in c['Subsets']: if self.all_constraints[n2]['Constraint'] == FirstCellIsSumOfRest and len(self.board[self.all_constraints[n2]['Set'][0]]) == 1: allsumsubsets = allsumsubsets | set(self.all_constraints[n2]['EffectiveSet']) if allsumsubsets == set(c['EffectiveSet']): c.update({'ConstraintRedundant': True,}) # Note: DO NOT SORT all_constraints, otherwise it breaks the numbering system & recursion solving self.constraints_all_different = [c for c in self.all_constraints if c['Constraint'] == AllDifferent and c['Constraint'] is not None] self.constraints_knight_tour = [c for c in self.all_constraints if c['Constraint'] == PreviousAndNextOfThirdPlusMinusSecondModFirstAppearsOnceOrTwiceInRestOfSet and c['Constraint'] is not None] self.constraints_not_all_different = [c for c in self.all_constraints if c['Constraint'] != AllDifferent and c['Constraint'] is not None] self.constraints_all_different.sort(key = lambda x: (not x['Deterministic'], -x['SolvabilityScore'])) self.constraints_not_all_different.sort(key = lambda x: (not x['Deterministic'], -x['SolvabilityScore'])) def __str__(self): digitloc = { d: ( (d - 1) // self.rootsize, (d - 1) % self.rootsize ) for d in self.digits } s = time.strftime("%F %X", time.localtime(time.time())) s += '\n' if self.title: s += self.title if self.status.recursion_level: s += f' (depth {self.status.recursion_level})' s += '\n' if self.status.max_possibles <= 1: for r in self.rows: if r > 1 and (r - 1) % self.rootsize == 0: d = "─" sep = "┼" for c in self.columns: if c > 1 and (c - 1) % self.rootsize == 0: s += sep s += d s += '\n' for c in self.columns: if c > 1 and (c - 1) % self.rootsize == 0: s += '│' if len(self.board[(r, c)]) == 1: s += f'{list(self.board[(r, c)])[0]}' else: s += '☼' s += '\n' else: for r in self.rows: if r > 1 and (r - 1) % self.rootsize == 0: d = "─" sep = "┼" else: d = " " sep = "│" if r > 1: for c in self.columns: s += d if c > 1 and (c - 1) % self.rootsize == 0: s += sep + d s += d * self.rootsize s += d + '\n' for digitStep in range(self.rootsize): for c in self.columns: s += ' ' if c > 1 and (c - 1) % self.rootsize == 0: s += '│ ' for digitSmall in range(self.rootsize): d = digitStep * self.rootsize + digitSmall + 1 if d in self.board[(r, c)]: s += f'{d}' else: s += '.' s += '\n' if self.status.removal_steps: s += f'Removal steps: {self.status.removal_steps}\n' if self.status.exploratory_steps: s += f'Exploratory steps: {self.status.exploratory_steps}\n' return s def print_cell_set_line(self, cells): print(self.__str_cells_line__(cells)) def print_cell_set_square(self, cells): print(self.__str_cells_square__(cells)) def __str_cells_line__(self, cells): digitloc = { d: ( (d - 1) // self.rootsize, (d - 1) % self.rootsize ) for d in self.digits } if len(cells) == 0: return '\n\n' if len(cells) > self.size: return self.__str_cells_square__(cells) s = '' max_possibles = 0 for c in cells: npossibles = len(self.board[c]) if npossibles > max_possibles: max_possibles = npossibles if max_possibles <= 1: for r, c in cells: s += f' {r},{c}' s += '\n' for c in cells: if self.board[c]: s += f' {list(self.board[c])[0]} ' else: s += f' ☼ ' else: for r, c in cells: s += f' {r},{c}' s += '\n' for c in cells: s += f' ━━━' s += '\n' for digitStep in range(self.rootsize): for c in cells: if self.rootsize == 2: s += ' ' s += ' ' for digitSmall in range(self.rootsize): d = digitStep * self.rootsize + digitSmall + 1 if d in self.board[c]: s += f'{d}' else: s += '⋅' s += '\n' for r, c in cells: if r == 0: s += f'{r},{c}: {self.board[(r, c)]}\n' s += '\n' return s def __str_cells_square__(self, cells): digitloc = { d: ( (d - 1) // self.rootsize, (d - 1) % self.rootsize ) for d in self.digits } s = '\n' if self.title: s += self.title if self.status.recursion_level: s += f' (depth {self.status.recursion_level})' s += '\n' if self.status.max_possibles <= 1: for r in self.rows: if r > 1 and (r - 1) % self.rootsize == 0: d = "─" sep = "┼" for c in self.columns: if c > 1 and (c - 1) % self.rootsize == 0: s += sep s += d s += '\n' for c in self.columns: if c > 1 and (c - 1) % self.rootsize == 0: s += '│' if len(self.board[(r, c)]) == 1: if (r, c) in cells: s += f'{list(self.board[(r, c)])[0]}' else: s += '‐' else: s += '☼' s += '\n' else: for r in self.rows: if r > 1 and (r - 1) % self.rootsize == 0: d = "─" sep = "┼" else: d = " " sep = "│" if r > 1: for c in self.columns: s += d if c > 1 and (c - 1) % self.rootsize == 0: s += sep + d s += d * self.rootsize s += d + '\n' for digitStep in range(self.rootsize): for c in self.columns: s += ' ' if c > 1 and (c - 1) % self.rootsize == 0: s += '│ ' for digitSmall in range(self.rootsize): d = digitStep * self.rootsize + digitSmall + 1 if d in self.board[(r, c)]: if (r, c) in cells: s += f'{d}' else: s += '‐' else: if (r, c) in cells: s += '⋅' else: s += ' ' s += '\n' if self.status.removal_steps: s += f'Removal steps: {self.status.removal_steps}\n' if self.status.exploratory_steps: s += f'Exploratory steps: {self.status.exploratory_steps}\n' s += '\n' return s def print_indexed_thermos(self): print(self.__str_indexed_thermos__()) def __str_indexed_thermos__(self): s = time.strftime("%F %X", time.localtime(time.time())) s += '\n' if self.title: s += self.title if self.status.recursion_level: s += f' (depth {self.status.recursion_level})' s += '\n' colindex = list(self.columns) colsep = [] for c in colindex[-1:1:-1]: if (c-1) % self.rootsize == 0: colsep.insert(0, [c-1, c, f'{c-1}-{c}']) colindex.insert(c-1, colsep[0][2]) display = {ri: {ci: ' ' for ci in colindex} for ri in colindex} for r in self.rows: for cs in colsep: display[r][cs[2]] = '│' for rs in colsep: for c in self.columns: display[rs[2]][c] = '─' for rs in colsep: for cs in colsep: display[rs[2]][cs[2]] = '┼' cells = [list(self.board[cell])[0] if len(self.board[cell]) == 1 else 0 for cell in self.indexedthermos_c['Set']] ch = '\033[32m' cv = '\033[35m' ce = '\033[31m' cn = '\033[0m' HT = [ch+'●'+cn, ch+'━'+cn, ch+'╸'+cn, ch+'╺'+cn, ch+'┿'+cn] VT = [cv+'●'+cn, cv+'┃'+cn, cv+'╹'+cn, cv+'╻'+cn, cv+'╂'+cn] EE = ce+'×'+cn for r in self.rows: c1 = cells[r-1] c2 = cells[r+self.size-1] if c1 and c2: if c1 > c2: c1 = self.size + 1 - c1 c2 = self.size + 1 - c2 display[r][c2] = HT[0] display[r][c1] = HT[3] for c in range(c1+1, c2): display[r][c] = HT[1] else: display[r][c1] = HT[0] display[r][c2] = HT[2] for c in range(c1+1, c2): display[r][c] = HT[1] for c in self.columns: r1 = cells[c+self.size*2-1] r2 = cells[c+self.size*3-1] if r1 and r2: if r1 > r2: r1 = self.size + 1 - r1 r2 = self.size + 1 - r2 if display[r2][c] == ' ': display[r2][c] = VT[0] else: display[r2][c] = EE if display[r1][c] == ' ': display[r1][c] = VT[3] else: display[r1][c] = EE for r in range(r1+1, r2): if display[r][c] == ' ': display[r][c] = VT[1] else: display[r][c] = EE else: if display[r1][c] == ' ': display[r1][c] = VT[0] else: display[r1][c] = EE if display[r2][c] == ' ': display[r2][c] = VT[2] else: display[r2][c] = EE for r in range(r1+1, r2): if display[r][c] == ' ': display[r][c] = VT[1] else: display[r][c] = EE for r in self.rows: for cs in colsep: if display[r][cs[0]] in HT and display[r][cs[1]] in HT and not (display[r][cs[0]] == HT[0] and display[r][cs[1]] == HT[0]): display[r][cs[2]] = HT[4] for rs in colsep: for c in self.columns: if display[rs[0]][c] in VT and display[rs[1]][c] in VT and not (display[rs[0]][c] == VT[0] and display[rs[1]][c] == VT[0]): display[rs[2]][c] = VT[4] s += '\n'.join(''.join(display[r][c] for c in colindex) for r in colindex) return s def PrintSuccessfulSets(self, constraint): print(f'\nConstraint {constraint["n"]}:') self.print_cell_set_line(constraint['Set']) if 'SuccessfulSets' in constraint: ssets = constraint['SuccessfulSets'] print(f' Successful Sets ({len(ssets)}):') for s in ssets: print(f' {s}') #print(f' {}') def CheckSolveLevel(self): self.status.max_possibles = 0 self.status.min_possibles = self.size len_possibles = set(len(possibles) for possibles in self.board.values()) self.status.max_possibles = max(len_possibles) self.status.min_possibles = min(len_possibles) self.status.solved = self.status.max_possibles == 1 and self.status.min_possibles == 1 self.status.failed = self.status.min_possibles == 0 self.status.finished = self.status.solved or self.status.failed if self.status.solved: # Double-check self.CheckConstraints() return self.status.max_possibles def CheckFinished(self): self.CheckSolveLevel() if self.debug >= 2: print(f'maxpos={self.status.max_possibles} minpos={self.status.min_possibles} self.status.solved: {self.status.solved} self.status.failed: {self.status.failed} self.status.finished: {self.status.finished}') return self.status.finished def CheckConstraint(self, nc): c = self.all_constraints[nc] cells = c['Set'] if 'SuccessfulSets' in c: successful_sets = c['SuccessfulSets'] else: constraint_check = c['Constraint'] if constraint_check is not None and 0 < self.nSetPossibles(cells) < 100: try: successful_sets = {s for s in self.SetPossibles(cells) if constraint_check(*s)} except: self.print_cell_set_line(cells) print(self.nSetPossibles(cells)) print(self.SetPossibles(cells)) raise else: successful_sets = None if successful_sets is not None and len(successful_sets) == 0: self.status.solved = False self.status.failed = True c['failed'] = True return False return True def CheckConstraints(self): Result = True for n, c in enumerate(self.all_constraints): Result = Result and self.CheckConstraint(n) return Result def SumGivens(self, cells): return sum(list(self.board[c])[0] for c in cells if len(self.board[c]) == 1) def Possibles(self, cells): return tuple(self.board[c] for c in cells) def nSetPossibles(self, cells): if len(cells) == 0: return 0 return np.prod([len(t) for t in self.Possibles(cells)]) def SetPossibles(self, cells): sp = self.Possibles(cells) if min(len(digits) for digits in sp) == 0: return set() else: return set(itertools.product(*sp)) def FilterStoredSuccessfulStrategies(self, cell, level = 0): if self.debug >= 2: print(f'\nFilterStoredSuccessfulStrategies start {cell}') for constraint in self.cell_constraints[cell]: if self.debug >= 2: self.PrintSuccessfulSets(constraint) if 'SuccessfulSets' in constraint: sets_to_remove = set() cellnum = constraint['Set'].index(cell) for s in constraint['SuccessfulSets']: if s[cellnum] not in self.board[cell]: sets_to_remove = sets_to_remove | s if sets_to_remove: # if a possible digit has been removed from a cell, remove all # successful sets that contain that digit for that set. if self.debug >= 2: print(f'\nPROGRESS {self.status.recursion_level} FSS.{level} FilterStoredSuccessfulStrategies A') print(f' exclude sets {cell}=({cellnum} in set): {constraint["SuccessfulSets"]} => ', end='') constraint['SuccessfulSets'] -= sets_to_remove self.status.removal_steps += 1 self.status.global_progress = True if self.debug >= 2: print(f'{constraint["SuccessfulSets"]}') sys.stdout.flush() # check if the remaining successful sets further constrain the other cells in the set # and if so, recurse sets = constraint['SuccessfulSets'] possibles = set() for cellnumo, other in enumerate(constraint['Set']): if other != cell: possibles = self.board[other] newpossibles = set(s[cellnumo] for s in sets) if len(possibles & newpossibles) < len(possibles): if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} FSS.{level} FilterStoredSuccessfulStrategies B') print(f' exclude {other}=({cellnumo} in set): {self.board[other]} => ', end='') self.board[other] = possibles & newpossibles self.status.removal_steps += 1 if self.debug >= 2: print(f'{self.board[other]}') self.FilterStoredSuccessfulStrategies(other, level + 1) if self.CheckFinished(): break if self.CheckFinished(): break if self.debug >= 2: print(f'\nFilterStoredSuccessfulStrategies end {cell}') def AllDifferentStrategy1_SiftSingles(self): for cell, digit in self.singles.items(): self.board[cell] = {digit,} for constraint in self.cell_constraints[cell]: if constraint['Constraint'] == AllDifferent: if self.debug >= 2: print(f'\nCell: {cell}: {digit}, constraint: {constraint}') self.status.progress_step = False for other in constraint['Set']: if other != cell and digit in self.board[other]: if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} AllDifferentStrategy1_SiftSingles') print(f' exclude {other}: {self.board[other]} => ', end='') self.board[other] -= {digit,} self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[other]}') self.FilterStoredSuccessfulStrategies(other) if self.status.progress_step and self.debug >= 2: print(self) sys.stdout.flush() if self.CheckFinished(): break if self.status.finished: break return self.status def AllDifferentStrategy1_ScanForSingles(self): if not self.status.finished: # Scan for singles self.singles = {} for cell, possibles in self.board.items(): if len(possibles) == 1: if cell not in self.givens: self.singles.update({cell: list(possibles)[0]}) self.progress = True if len(self.singles) > 0: self.givens.update(self.singles) self.CheckFinished() return self.status def AllDifferentStrategy2_SiftGroups(self): for n, c in enumerate(self.constraints_all_different): # Check pairs, triples... a.k.a. tuples ''' For each "AllDifferent" constraint, iterate over all possible combinations of groups of cells within that set for a given number of groups (between 2 and the number of cells in the set less 1). Compute the union of possible values within that group, if that number is equal to the number of cells scanned, then we have a tuple and therefore we can eliminate any value of the tuple found in the cells of this set outside the current group. ''' cells = c['Set'] DigitGroups = [self.board[cell] for cell in cells] self.status.progress_step = True while self.status.progress_step: self.status.progress_step = False for groupcount in range(2, len(cells))[::-1]: for OneCombinationOfGroups in itertools.combinations(DigitGroups, groupcount): Group = set() for g in OneCombinationOfGroups: Group = Group | g if len(Group) == groupcount: Others = set() for g2 in DigitGroups: if g2 not in OneCombinationOfGroups: Others = Others | g2 if len(Others & Group) > 0: if self.debug >= 2: print(f'\nCell groups: {OneCombinationOfGroups} ({groupcount}), constraint: {c}') for other in cells: if self.board[other] not in OneCombinationOfGroups and self.board[other] & Group: if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} AllDifferentStrategy2_SiftGroups') print(f' exclude {other}: {self.board[other]} => ', end='') self.board[other] -= Group self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[other]}') self.FilterStoredSuccessfulStrategies(other) if self.debug >= 2: print(self) sys.stdout.flush() if self.CheckFinished(): break if self.status.finished: break if self.status.finished: break return self.status def FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference(self): ''' For every constraint of type "FirstCellIsSumOfRest" (e.g. arrow or cage) if the sum is known (fixed), either as a given or by previous solving steps, then look for other similar constraints with the same parent set. If several sets with fixed sum restrict the remaining cells of the parent set sufficiently (maybe a single cell, or a multi-cell with an interesting sum: low or high), then compute the cell value or add a new constraint which will be looked at at the next global iteration. ''' # "Good Sums" are sums of a number of cells below a low number or above a high number # as they have few combinations. # We use these values to filter the new constraints to add and not generate # useless constraints needlessly. goodsums = { n: [sum(range(n+1)), 0, 0, sum(range(self.size+1-n, self.size+1))] for n in range(1, self.size+1) } goodsums = { n: [goodsums[n][0], min(goodsums[n][0] + self.rootsize, goodsums[n][3]), max(goodsums[n][0], goodsums[n][3] - self.rootsize), goodsums[n][3]] for n in range(1, self.size+1) } # "nextclue" is the index for the next clue or sum to be added should we create a # new constraint. nextclue = 0 for r, c in self.board: if r == 0: if c > nextclue: nextclue = c nextclue += 1 self.status.progress_step = False # First find all sets with a sum constraint (first cell only for now) # ((two cell sums may require separate processing)) # these sets will be used to [revent re-trying what has already been tried. if self.debug >= 2: print('All Sum sets:') allsumsets = [] for c in self.constraints_not_all_different: if c['Constraint'] == FirstCellIsSumOfRest: allsumsets.append(set(c['Set'][1:])) if self.debug >= 2: print(f' {allsumsets[-1]}') if set(c['Set'][1:]) != set(c['EffectiveSet']): allsumsets.append(set(c['EffectiveSet'])) if self.debug >= 2: print(f' {allsumsets[-1]}') if self.debug >= 2: print('') # Parent list: # 1. all self.size regions that must contain different digits # 2. all combinations of rows, columns or boxes # 3. all regions which have a known sum parent_list = [(self.sumalldiff, c, set(c['Set'])) for c in self.constraints_all_different if len(c['Set']) == self.size] parent_list += [(self.sumalldiff * len(c['Set']) // self.size, c, set(c['Set'])) for c in self.all_constraints if c['Constraint'] == None] parent_list += [(list(c['Set'][0])[0], c, set(c['Set'][1:])) for c in self.constraints_not_all_different if c['Constraint'] == FirstCellIsSumOfRest and len(self.board[c['Set'][0]]) == 1] for parentsum, c, parent in parent_list: if len(parent) >= 2: sumsubsets = [] # Find the cells that have a single possible value (i.e. the cells that are already resolved) # compute their sum. parent_givens = set(cell for cell in parent if len(self.board[cell]) == 1) sum_givens = self.SumGivens(parent) # Find subsets (sub regions) of unresolved values with a known sum, keep these subsets in 'sumsubsets' for subsetnumber in c['Subsets']: subsetconstraint = self.all_constraints[subsetnumber] subsetconstraintsumpossibles = self.board[subsetconstraint['Set'][0]] if (subsetconstraint['Constraint'] == FirstCellIsSumOfRest and len(subsetconstraintsumpossibles) == 1 and len(subsetconstraint['EffectiveSet']) >= 1 and not subsetconstraint['ConstraintRedundant'] ): newitem = (subsetnumber, list(subsetconstraintsumpossibles)[0] - self.SumGivens(subsetconstraint['Set'][1:]), subsetconstraint['EffectiveSet']) if newitem not in sumsubsets: sumsubsets.append(newitem) if len(sumsubsets) >= 1: # If there is at least one subset, calculate the union of all subsets combiregion = set.union(*(set(subset[2]) for subset in sumsubsets)) combisum = sum(subset[1] for subset in sumsubsets) if self.debug >= 2: print('\n########################################################\nFirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference\nParent set:') if c['Constraint'] != None: self.print_cell_set_line(parent) self.print_cell_set_square(parent) print('Parent givens:') self.print_cell_set_line(parent_givens) print(f'Parent sum subsets: (n={len(sumsubsets)})') for s in sumsubsets: print(f' {s}') for s2 in sumsubsets: if s != s2: intersection = set(s[2]) & set(s2[2]) if intersection: print(f' intersects with {s2}:\t{intersection}') print('') if len(combiregion) < len(parent): # By default, but only if subsets do not overlap, we have one big region, check if it does the job. sumsubsetscombinations = [[(-1, combisum, combiregion),],] if sum(len(sr[2]) for sr in sumsubsets) != len(combiregion): # If subsets overlap, remove all the subsets that have a potential overlap, # calculate the base region free of overlaps, and add combinations of potentially # overlapping subsets as options to check subsetstofloat = set() for sn, s in enumerate(sumsubsets): for sn2, s2 in enumerate(sumsubsets): if s != s2: intersection = set(s[2]) & set(s2[2]) if intersection: subsetstofloat = subsetstofloat | {sn, sn2} sumsubsets2 = [] if subsetstofloat: for sn in sorted(subsetstofloat, reverse = True): sumsubsets2.append(sumsubsets[sn]) del sumsubsets[sn] if sumsubsets and sumsubsets2: combiregion = set.union(*(set(subset[2]) for subset in sumsubsets)) combisum = sum(subset[1] for subset in sumsubsets) sumsubsetscombinations = ([(-1, combisum, combiregion), *combi] for ngroups in range(1, len(sumsubsets2) + 1) for combi in itertools.combinations(sumsubsets2, ngroups)) # Only change sumsubsetscombinations if we have subsets to include if self.debug >= 2: print(f'Sum subset combinations count = {C(len(sumsubsets2), ngroups)}') for nc, combi in enumerate(sumsubsetscombinations): # For each combination that is smaller than the parent region... combiregion2 = set.union(*(set(subset[2]) for subset in combi)) combisum2 = sum(subset[1] for subset in combi) if len(combiregion2) < len(parent): if sum(len(sr[2]) for sr in combi) == len(combiregion2): # if the subsets do not overlap complement = parent - combiregion2 - parent_givens if complement not in allsumsets: # and complement - parent_givens: # And the remaining cells do not form an existinng region with a known sum # Then, if there is only one remaining cell, we now know its value # If there are two or more remaining cells, we know their sum # In both cases we can move forward. sumcomplement = parentsum - combisum2 - sum_givens lc = len(complement) if 0 < lc < self.size: if self.debug >= 2: print(f'Combi {nc}: {combiregion2}\nComplement: {complement}') print(f'Sum complement: {sumcomplement} ({lc} cells <= {(self.size // 2)}) ({goodsums[lc][0]}<= X <={goodsums[lc][1]}? or {goodsums[lc][2]}<= X <={goodsums[lc][3]}?)') if lc == 1 and sumcomplement in self.digits: other = list(complement)[0] if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference') print(f' set single cell complement {complement}: {self.board[other]} => ', end='') self.board[other] = {sumcomplement, } self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[other]}') self.FilterStoredSuccessfulStrategies(other) elif 2 <= lc < (self.size // 2) and (goodsums[lc][0] <= sumcomplement <= goodsums[lc][1] or goodsums[lc][2] <= sumcomplement <= goodsums[lc][3]): clue = {(0, nextclue): {sumcomplement,}} self.board.update(clue) self.givens.update(clue) self.__AddConstraint("Calculated", "-", nextclue, FirstCellIsSumOfRest, ((0, nextclue),) + tuple(complement)) allsumsets.append(complement) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference') print(f' Add new constraint: {self.all_constraints[-1]}') nextclue += 1 self.__ComputeSolvabilityAndEffectiveSets() elif sumcomplement < goodsums[lc][0] or goodsums[lc][3] < sumcomplement: #for other in complement: # self.board[other] = set() #self.status.global_progress = True #self.status.progress_step = True #self.status.failed = True #self.status.finished = True if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference') print(f' Impossible sum: {sumcomplement}') continue if self.status.progress_step: break # Try and find a region a few cells bigger than the parent region if lc <= (self.size // 2 + 1): overlappingsets = {} for cell in complement: for cc in self.cell_constraints[cell]: ccsumpossibles = self.board[cc['Set'][0]] rcc = self.all_constraints[cc['n']] if (cc['Constraint'] == FirstCellIsSumOfRest and len(ccsumpossibles) == 1 and len(rcc['EffectiveSet']) >= 1 and not rcc['ConstraintRedundant'] ): scc = set(rcc['EffectiveSet']) inside = scc & parent outside = scc - parent if outside: if tuple(scc) not in overlappingsets: overlappingsets[tuple(scc)] = (ccsumpossibles, tuple(inside), tuple(outside)) if overlappingsets: if self.debug >= 2: print(f'Combi {nc}: {combiregion2}\nComplement: {complement}') print(f' {len(overlappingsets)} overlappingsets:') for scc, sccprops in overlappingsets.items(): print(f' {scc}: {sccprops}') #print(f' {}') #combioverlapping if self.debug >= 2: print(f'\n') if self.status.progress_step: break def StoredSuccessfulStrategiesStrategy4_FilterOverlappingSets_with_AlwaysInDigits(self): self.status.progress_step = False for c in self.constraints_not_all_different: if 'SuccessfulSets' in c: successful_sets = c['SuccessfulSets'] for cn2 in c['OverlappingSets']: if self.all_constraints[cn2]['Constraint'] == AllDifferent: # Reduce SuccessfulSets over the overlapping region, find if some digits always appear set2 = self.all_constraints[cn2]['Set'] overlapping = tuple(cellnum for cellnum, cell in enumerate(c['Set']) if cell in set2) alwaysinset = set.intersection(*({s[n] for n in overlapping} for s in successful_sets)) if alwaysinset: # If there are any digits common to all options in the overlapping set, # then check in non overlapping cells for remval if relevant. for cell in set2: if cell not in c['Set']: if self.board[cell] & alwaysinset: if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} StoredSuccessfulStrategiesStrategy4_FilterOverlappingSets_with_AlwaysInDigits') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] - alwaysinset self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') self.FilterStoredSuccessfulStrategies(cell) if self.CheckFinished(): break def FirstCellIsSumOfRestStrategy5_ReductionOfPossibles(self): self.status.progress_step = False for c in self.constraints_not_all_different: if c['Constraint'] == FirstCellIsSumOfRest: s = c['Set'] contained = False for sup in c['Supersets']: if self.all_constraints[sup]['Constraint'] == AllDifferent: contained = True break if contained and len(self.board[s[0]]) == 1: givens = set(cell for cell in s[1:] if len(self.board[cell]) == 1) sumpossibles = list(self.board[s[0]])[0] - self.SumGivens(givens) setpossibles = set(s[1:]) - givens if setpossibles: possibles = set.union(*(self.board[cell] for cell in setpossibles)) reduced = tuple(set(combi) for combi in itertools.combinations(possibles, len(setpossibles)) if sum(combi) == sumpossibles ) if len(reduced) > 0: reduced = set.union(*reduced) else: reduced = set() if len(reduced) < len(possibles): # Magic happens for cell in setpossibles: if self.board[cell] & (self.digits - reduced): if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} FirstCellIsSumOfRestStrategy5_ReductionOfPossibles') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] & reduced self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') self.FilterStoredSuccessfulStrategies(cell) if self.debug >= 2: print(self) sys.stdout.flush() if self.CheckFinished(): break def AllDifferentStrategy6_ExclusionToggles(self): ''' For different cell chains (3 or more) for which each pair of consecutive cells belong to one region where digits must be different, where consecutive cells each contain two possible digits and share one, if any two cells in the chain end up either one or the other with the same digit, then any cell seen by these two cells cannot have that digit. ''' pass def KnightTourStrategy7_ScanForSingles(self): if not self.status.finished: for n, c in enumerate(self.constraints_knight_tour): modulo = list(self.board[c['Set'][0]])[0] delta = list(self.board[c['Set'][1]])[0] basecell = c['Set'][2] if len(self.board[basecell]) == 1: basevalue = list(self.board[basecell])[0] previousvalue = (basevalue - delta - 1) % modulo + 1 nextvalue = (basevalue + delta - 1) % modulo + 1 # Find if there is a unique cell that contains the previous value setcontainsvalue = [previousvalue if previousvalue in self.board[cell] else 0 for cell in c['Set'][3:]] if setcontainsvalue.count(previousvalue) == 1: # Reduce cell to that value cell = c['Set'][setcontainsvalue.index(previousvalue) + 3] if len(self.board[cell]) > 1: if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} KnightTourStrategy7_ScanForSingles previous hidden single') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = set([previousvalue]) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') # Find if there is a unique cell that contains the next value setcontainsvalue = [nextvalue if nextvalue in self.board[cell] else 0 for cell in c['Set'][3:]] if setcontainsvalue.count(nextvalue) == 1: # Reduce cell to that value cell = c['Set'][setcontainsvalue.index(nextvalue) + 3] if len(self.board[cell]) > 1: if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} KnightTourStrategy7_ScanForSingles next hidden single') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = set([nextvalue]) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') # Find if there is a unique cell with a single value equal to the previous in sequence setdetermined = [list(self.board[cell])[0] if len(self.board[cell]) == 1 else 0 for cell in c['Set'][3:]] if setdetermined.count(previousvalue) == 1: # Reduce other cells that contain the previous digit as one of many possibles for cell in c['Set'][3:]: if len(self.board[cell]) > 1: if self.board[cell] & set([previousvalue]): if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} KnightTourStrategy7_ScanForSingles previous single') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] - set([previousvalue]) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') # Find if there is a unique cell with a single value equal to the next in sequence if setdetermined.count(nextvalue) == 1: # Reduce other cells that contain the next digit as one of many possibles for cell in c['Set'][3:]: if len(self.board[cell]) > 1: if self.board[cell] & set([nextvalue]): if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} KnightTourStrategy7_ScanForSingles next single') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] - set([nextvalue]) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') #if self.status.progress_step: # self.FilterStoredSuccessfulStrategies(cell) self.CheckFinished() return self.status def ThermoStrategy8_ReducePossibles(self): self.status.progress_step = False midrc = ((self.size + 1) // 2) if self.size % 2 else 0 nn=0 global nnn for n, c in enumerate(self.constraints_not_all_different): if c['Constraint'] in (NumbersIncrease, IndexedThermo): if c['Constraint'] == IndexedThermo: cells = c['Set'] cell1 = cell2 = 0 isarow = (cells[0][0] - cells[1][0]) == 0 if isarow: rownum = cells[0][0] else: colnum = cells[0][1] if len(self.board[cells[0]]) == 1: cell1 = list(self.board[cells[0]])[0] else: continue if len(self.board[cells[-1]]) == 1: cell2 = list(self.board[cells[-1]])[0] else: continue if cell1 < cell2: thermocells = cells[cell1-1:cell2] else: thermocells = cells[::-1][cell2-1:cell1] else: thermocells = c['Set'] mindigit = 0 for cell in thermocells: digits = copy.deepcopy(self.board[cell]) for digit in digits: if digit <= mindigit: self.board[cell] -= {digit,} self.status.removal_steps += 1 self.status.progress_step = True if len(self.board[cell]) == 0: break mindigit = min(self.board[cell]) if isarow: if rownum <= 2: cell3 = (1, cell[1]) if {1, 9} & self.board[cell3]: self.board[cell3] -= {1, 9} self.status.removal_steps += 1 self.status.progress_step = True elif rownum == midrc: cell3 = (1, cell[1]) if {midrc,} & self.board[cell3]: self.board[cell3] -= {midrc,} self.status.removal_steps += 1 self.status.progress_step = True cell4 = (self.size, cell[1]) if {midrc,} & self.board[cell4]: self.board[cell4] -= {midrc,} self.status.removal_steps += 1 self.status.progress_step = True elif rownum >= self.size-1: cell4 = (self.size, cell[1]) if {1, 9} & self.board[cell4]: self.board[cell4] -= {1, 9} self.status.removal_steps += 1 self.status.progress_step = True else: if colnum <= 2: cell3 = (cell[0], 1) if {1, 9} & self.board[cell3]: self.board[cell3] -= {1, 9} self.status.removal_steps += 1 self.status.progress_step = True elif colnum == midrc: cell3 = (cell[0], 1) if {midrc,} & self.board[cell3]: self.board[cell3] -= {midrc,} self.status.removal_steps += 1 self.status.progress_step = True cell4 = (cell[0], self.size) if {midrc,} & self.board[cell4]: self.board[cell4] -= {midrc,} self.status.removal_steps += 1 self.status.progress_step = True elif colnum >= self.size-1: cell4 = (cell[0], self.size) if {1, 9} & self.board[cell4]: self.board[cell4] -= {1, 9} self.status.removal_steps += 1 self.status.progress_step = True maxdigit = self.size + 1 for cell in thermocells[::-1]: digits = copy.deepcopy(self.board[cell]) for digit in digits: if digit >= maxdigit: self.board[cell] -= {digit,} self.status.removal_steps += 1 self.status.progress_step = True if len(self.board[cell]) == 0: break maxdigit = max(self.board[cell]) if self.CheckFinished(): break if self.status.progress_step: self.status.global_progress = True return self.status def GenericTrialAndErrorPerConstraintStrategy98_Systematic(self): self.status.progress_step = False for n, c in enumerate(self.constraints_not_all_different): # Trial and error on one constraint at a time # Compute for possible cell value combinations for each constraint variable_extent = set(cell for cell in c['Set'] if len(self.board[cell]) > 1) if 'SuccessfulSets' in c: successful_sets = c['SuccessfulSets'] else: successful_sets = self.GenericTrialAndErrorPerConstraintStrategy98_SystematicRecursive(c) c['SuccessfulSets'] = successful_sets successful_ranges = tuple({s[i] for s in successful_sets} for i in range(len(c['Set']))) if self.debug >= 2: print(f'Successful sets: {successful_sets}') print(f'Successful ranges: {successful_ranges}') alteredcells = [] for cell, possibles in zip(c['Set'], successful_ranges): if self.board[cell] & (self.digits - possibles): if self.debug >= 2: print(f'PROGRESS {self.status.recursion_level} GenericTrialAndErrorPerConstraintStrategy98_Systematic') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] & possibles alteredcells.append(cell) self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 2: print(f'{self.board[cell]}') for cell in alteredcells: self.FilterStoredSuccessfulStrategies(cell) if self.debug >= 2: print(self) sys.stdout.flush() # As this strategy can be computationally intensive, as soon as progress is made, # check out the more efficient strategies before coming back. if self.CheckFinished() or self.status.progress_step: break def GenericTrialAndErrorPerConstraintStrategy98_SystematicRecursive(self, constraint, recursion_level = 1): ''' Loop through each cell in the set that has more than one possible Loop through all possible values Recurse into the puzzle with that single constraint in mind + sifting Verify whether the constraint is satisfied Record the remaining possibles in the set (eliminate all failed solves) ''' cells = constraint['Set'] if self.debug >= 3: print(f'recursion_level: {recursion_level}') self.print_cell_set_square(cells) cellsoptions = [] for cell in cells: if len(self.board[cell]) > 1: cellsoptions.append(cell) successful_sets = set() timecheck = False if cellsoptions: if len(cellsoptions) == 1: cell = cellsoptions[0] constraint_check = constraint['Constraint'] successful_sets = {s for s in self.SetPossibles(cells) if constraint_check(*s)} if successful_sets: successful_ranges = tuple({s[i] for s in successful_sets} for i in range(len(cells))) if self.debug >= 4: print(f'Successful sets: {successful_sets}') print(f'Successful ranges: {successful_ranges}') print(f'PROGRESS {self.status.recursion_level} GenericTrialAndErrorPerConstraintStrategy98_SystematicRecursive') print(f' exclude {cell}: {self.board[cell]} => ', end='') self.board[cell] = self.board[cell] & successful_ranges[cells.index(cell)] self.status.removal_steps += 1 self.status.global_progress = True self.status.progress_step = True if self.debug >= 4: print(f'{self.board[cell]}') sys.stdout.flush() else: return successful_sets for cell in cellsoptions: for d in self.board[cell]: playpuzzle = copy.deepcopy(self) playpuzzle.status.recursion_level = recursion_level playpuzzle.singles = {cell: d,} playpuzzle.strategies = [ playpuzzle.AllDifferentStrategy2_SiftGroups, playpuzzle.FirstCellIsSumOfRestStrategy3_KnownSum_SubsetsDifference, playpuzzle.StoredSuccessfulStrategiesStrategy4_FilterOverlappingSets_with_AlwaysInDigits, playpuzzle.FirstCellIsSumOfRestStrategy5_ReductionOfPossibles, playpuzzle.ThermoStrategy8_ReducePossibles, ] # Above: limit playpuzzle strategies to the basic sifting of singles # and tuples then run the current strategy on the current constraint playpuzzle.Solve(self.debug + self.debug_step) self.status.exploratory_steps = playpuzzle.status.removal_steps + playpuzzle.status.exploratory_steps if playpuzzle.status.timedout: self.status.timedout = True return successful_sets if self.debug >= 4: playpuzzle.print_cell_set_square(cells) if playpuzzle.status.failed: if self.debug >= 4: print(f'Failed sets: {self.SetPossibles(cells)}') else: successful_sets = ( successful_sets | playpuzzle.GenericTrialAndErrorPerConstraintStrategy98_SystematicRecursive(playpuzzle.all_constraints[constraint['n']], recursion_level + 1) ) now = time.time() if (now - self.status.timechecked) > self.timetocheck: timecheck = True if timecheck or self.debug >= 4: timecheck = False self.status.timechecked = now print(playpuzzle) sys.stdout.flush() if playpuzzle.status.timedout: self.status.timedout = True return successful_sets else: constraint_check = constraint['Constraint'] successful_sets = successful_sets | {s for s in self.SetPossibles(cells) if constraint_check(*s)} return successful_sets def Solve(self, debug = None, timetocheck = 60, timeout = 0): if debug is not None: self.debug = debug self.status.global_progress = True self.status.finished = False self.status.solved = False self.status.removal_steps = 0 now = time.time() self.status.timechecked = now self.timetocheck = timetocheck if timeout or not hasattr(self, 'timeout'): self.starttime = now self.timeout = timeout timecheck = False if self.status.recursion_level == 0: print(f'{time.strftime("%F %X", time.localtime(self.status.timechecked))}, Solving:') print(f'{self.title}') sys.stdout.flush() if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - about to start global loop') while self.status.global_progress and not self.status.finished: self.__ComputeSolvabilityAndEffectiveSets() if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - global loop start, sift singles') self.status.global_progress = False self.AllDifferentStrategy1_SiftSingles() if not self.status.finished: if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - global loop, scan singles') self.AllDifferentStrategy1_ScanForSingles() self.strategy = 0 if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - pre strategy loop checks') print(f'self.strategy={self.strategy} < len(self.strategies)={len(self.strategies)}: {self.strategy < len(self.strategies)}') print(f'self.status.finished={self.status.finished}') print(f'len(self.singles) = {len(self.singles)} == 0: {len(self.singles) == 0}') while self.strategy < len(self.strategies) and not self.status.finished and len(self.singles) == 0: # Proceed with more elaborate strategies self.__ComputeSolvabilityAndEffectiveSets() if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - strategy loop, running strategy {self.strategy + 1} of {len(self.strategies)}: {self.strategies[self.strategy]}') sys.stdout.flush() self.strategies[self.strategy]() if not self.status.progress_step: self.strategy += 1 else: self.strategy = 0 if timecheck or self.debug >= (1 + self.status.recursion_level): timecheck = False self.status.timechecked = now print(f'Solve {self.status.recursion_level} - strategy loop, puzzle state') print(self) sys.stdout.flush() if self.debug >= (1 + self.status.recursion_level): print(f'Solve {self.status.recursion_level} - strategy loop, scan singles') sys.stdout.flush() self.AllDifferentStrategy1_ScanForSingles() now = time.time() if (now - self.status.timechecked) > self.timetocheck: timecheck = True if self.timeout: if (now - self.starttime) > self.timeout: break if self.timeout: if (now - self.starttime) > self.timeout: self.status.timedout = True break # if self.status.recursion_level == 0 and not self.status.solved: # print(self) # # for c in self.all_constraints: # sp = self.Possibles(c['Set']) # maxlen = max(len(p) for p in sp) # if maxlen > 1: # self.PrintSuccessfulSets(c) # ============================================================================= def BuildKnightTour(self, debug = None, timetocheck = 600, partial = 0): if debug is not None: self.debug = debug self.status.global_progress = True self.status.finished = False self.status.solved = False self.status.removal_steps = 0 starttime = time.time() timechecked = starttime print('Start time: ' + time.strftime("%F %X", time.localtime(starttime))) basecell = (1, 1) firstcell = basecell basevalue = 0 nextvalue = 0 historystack = [] solutionstack = [] explorationcells = [(2, 3),] explorationvalues = [] boardstack = [] nsolution = 0 nloops = 0 nchains = 0 nsteps = 0 nback = 0 global maxhist global maxchain global maxloop maxhist = 0 maxchain = 0 maxloop = 0 explorationfinished = False boardstack.append(copy.deepcopy(self)) ratios = [0, 0, 100, 0, 1] #historystack.append({'basecell': basecell, 'nextcell': explorationcells[0], 'nextvalue': nextvalue, 'explorationcells': explorationcells, 'ratios': ratios}) knighttourconstraints = {} for n, c in enumerate(self.all_constraints): if c['Constraint'] == PreviousAndNextOfThirdPlusMinusSecondModFirstAppearsOnceOrTwiceInRestOfSet: knighttourconstraints[c['Set'][2]] = c self.__ComputeSolvabilityAndEffectiveSets() while not explorationfinished: self.status.global_progress = True while self.status.global_progress and not self.status.finished: self.status.global_progress = False self.AllDifferentStrategy2_SiftGroups() self.KnightTourStrategy7_ScanForSingles() self.AllDifferentStrategy1_ScanForSingles() self.AllDifferentStrategy1_SiftSingles() backtrack = False # If the puzzle is not finished (all cells have at least one possible value, # and at least one cell has more than one possible value), then: # 1/ Drill down: if not self.status.finished: c = knighttourconstraints[basecell] modulo = list(self.board[c['Set'][0]])[0] delta = list(self.board[c['Set'][1]])[0] basevalue = list(self.board[basecell])[0] # Find the list of knightmove cells which contain the next number in the sequence nextvalue = (basevalue + delta - 1) % modulo + 1 explorationcells = [cell for cell in c['Set'][3:] if nextvalue in self.board[cell] if not any(h['basecell'] == cell for h in historystack)] if len(explorationcells) >= 1: nextcell = explorationcells.pop() (rc, rb, rt, nb, nt) = ratios ratios = [rc, rc, rb+(rt-rb)*(nb+1)/nt, 0, len(explorationcells)+1] (rc, rb, rt, nb, nt) = ratios while (rc + (rt - rb) / nt) < partial: nextcell = explorationcells.pop() ratios = [rb+(nb+1)*(rt-rb)/nt, rb, rt, nb+1, nt] (rc, rb, rt, nb, nt) = ratios boardstack.append(copy.deepcopy(self)) self.board[nextcell] = {nextvalue,} historystack.append({'basecell': basecell, 'nextcell': nextcell, 'nextvalue': nextvalue, 'explorationcells': explorationcells, 'ratios': ratios}) nsteps += 1 if len(historystack) > maxhist: maxhist = len(historystack) if nextcell == firstcell: backtrack = True else: backtrack = True if self.status.finished or backtrack: if ratios[0] > 0: now = time.time() ETE = time.strftime("%F %X", time.localtime(starttime + (now - starttime) / ((ratios[0] - partial)/(100 - partial)))) if (now - timechecked) > timetocheck: timechecked = now print('\n' + time.strftime("%F %X", time.localtime(now))) sys.stdout.flush() else: ETE = '?' self.check_knight_tour(f'{ratios[0]:1.4f}% ⇒{ETE}? >{nsteps} <{nback} ∞:{nloops}/{maxloop} ∝:{nchains}/{maxchain} ▷:{nsolution}', historystack, end='\033[K\r') # If some cell has no remaining possible value, the puzzle is broken, backtrack if self.status.failed: pass # If every cell has exactly one possible value, it is solved, we have one possible solution, # check whether it is a full chain and backtrack to continue exploring. if self.status.solved: print('') self.check_knight_tour(time.strftime("%F %X", time.localtime(time.time())) + f' Solved puzzle', historystack) chainlength = 1 schain = '11' basecell, nextcell, nextvalue, explorationcells, _ = list(historystack[0].values()) chain = [basecell,] explorationcells = [nextcell,] while len(explorationcells) == 1 and explorationcells[0] not in chain: chainlength += 1 basecell = explorationcells[0] (r,c) = basecell chain.append(basecell) schain += f' {r}{c}' c = knighttourconstraints[basecell] modulo = list(self.board[c['Set'][0]])[0] delta = list(self.board[c['Set'][1]])[0] basevalue = list(self.board[basecell])[0] # Find the list of knightmove cells which contain the next number in the sequence nextvalue = (basevalue + delta - 1) % modulo + 1 explorationcells = [cell for cell in c['Set'][3:] if nextvalue in self.board[cell]] basecell, _, _, _, _ = list(historystack[0].values()) c = knighttourconstraints[basecell] modulo = list(self.board[c['Set'][0]])[0] delta = list(self.board[c['Set'][1]])[0] basevalue = list(self.board[basecell])[0] previousvalue = (basevalue - delta - 1) % modulo + 1 explorationcells = [cell for cell in c['Set'][3:] if previousvalue in self.board[cell]] while len(explorationcells) == 1 and explorationcells[0] not in chain: chainlength += 1 basecell = explorationcells[0] (r,c) = basecell chain.insert(0, basecell) schain = f'{r}{c} ' + schain c = knighttourconstraints[basecell] modulo = list(self.board[c['Set'][0]])[0] delta = list(self.board[c['Set'][1]])[0] basevalue = list(self.board[basecell])[0] previousvalue = (basevalue - delta - 1) % modulo + 1 explorationcells = [cell for cell in c['Set'][3:] if previousvalue in self.board[cell]] if chainlength == self.size ** 2: nsolution += 1 self.check_knight_tour(f'Solution #{nsolution}', historystack) solutionstack.append({'board': copy.deepcopy(self), 'schain': schain, 'chain': chain}) else: nchains += 1 self.check_knight_tour(time.strftime("%F %X", time.localtime(time.time())) + f' Chain #{nchains} L={chainlength}', historystack) print(f'Chain #{nchains} L={chainlength}: {schain}') sys.stdout.flush() if chainlength > maxchain: maxchain = chainlength print(self) sys.stdout.flush() if nextcell == firstcell: nloops += 1 if len(historystack) > maxloop: maxloop = len(historystack) # Backtrack: self = boardstack.pop() basecell, nextcell, nextvalue, explorationcells, ratios = list(historystack.pop().values()) self.board[nextcell] = self.board[nextcell] - {nextvalue,} nback += 1 if len(explorationcells) > 0: nextcell = explorationcells.pop() boardstack.append(copy.deepcopy(self)) self.board[nextcell] = {nextvalue,} (rc, rb, rt, nb, nt) = ratios ratios = [rb+(nb+1)*(rt-rb)/nt, rb, rt, nb+1, nt] historystack.append({'basecell': basecell, 'nextcell': nextcell, 'nextvalue': nextvalue, 'explorationcells': explorationcells, 'ratios': ratios}) nsteps += 1 if len(historystack) > maxhist: maxhist = len(historystack) else: while len(explorationcells) == 0: if len(historystack) == 0: print(time.strftime("%F %X", time.localtime(time.time())) + f' Solutions: {nsolution}') print(solutionstack) sys.stdout.flush() explorationfinished = True break self = boardstack.pop() basecell, nextcell, nextvalue, explorationcells, ratios = list(historystack.pop().values()) nback += 1 if explorationfinished: break self.board[nextcell] = self.board[nextcell] - {nextvalue,} nextcell = explorationcells.pop() boardstack.append(copy.deepcopy(self)) self.board[nextcell] = {nextvalue,} (rc, rb, rt, nb, nt) = ratios ratios = [rb+(nb+1)*(rt-rb)/nt, rb, rt, nb+1, nt] historystack.append({'basecell': basecell, 'nextcell': nextcell, 'nextvalue': nextvalue, 'explorationcells': explorationcells, 'ratios': ratios}) nsteps += 1 if len(historystack) > maxhist: maxhist = len(historystack) basecell = nextcell def check_knight_tour(self, tag, historystack, end='\033[K\n'): global maxhist if len(historystack) > 0: cb, cn, vn, ec, r = list(historystack[-1].values()) if len(ec)>0: ce = ec[0] xb,yb = cb xe,ye = ce d = abs(xb-xe)+abs(yb-ye) else: d = 3 else: d = 3 if self.debug >= 2: print(f'{tag} ({len(historystack)}/{maxhist}) [History stack]: {historystack} {"Good" if d == 3 else "ERROR"}') sys.stdout.flush() shortstack = '' for h in historystack: (r,c) = h['basecell'] shortstack += f' {r}{c}' print(f'{tag} ({len(historystack)}/{maxhist}):{shortstack} {"Good" if d == 3 else "ERROR"}', end=end) sys.stdout.flush() # ============================================================================= def BuildIndexedThermos(self, mind, maxd, suffix, debug = None, timetocheck = 600, maxqueue = 20, maxprocesses = 10): # Split the sudoku solving load in sub-processes to speed up solution finding SolveServer = JobServer(maxqueue, maxprocesses) # Initialise search for solutions maxndiff = maxd minndiff = mind self.__ComputeSolvabilityAndEffectiveSets() self.solutions_filename = f'indexed_thermos_solutions{suffix}_ndiff{minndiff}-{maxndiff}.txt' if debug is not None: self.debug = debug self.status.global_progress = True self.status.finished = False self.status.solved = False self.status.removal_steps = 0 rstats = [0 for i in range(0,self.size)] cstats = [0 for i in range(1,self.size-1)] RCframe = '' SolveServer.Shared.RCframe = '' starttime = time.time() timechecked = starttime print('\033[2J\033[1;1HStart time: ' + time.strftime("%F %X", time.localtime(starttime))) with open(self.solutions_filename, 'at', encoding="utf-8") as solutions_file: print('Start time: ' + time.strftime("%F %X", time.localtime(starttime)), file=solutions_file) def async_check_indexed_thermos(self): playpuzzle = copy.deepcopy(self) c1 = ''.join(f'{list(self.board[(r0, 1)])[0]}' if len(self.board[(r0,1)]) == 1 else '.' for r0 in self.rows) cL = ''.join(f'{list(self.board[(r0, self.size)])[0]}' if len(self.board[(r0,self.size)]) == 1 else '.' for r0 in self.rows) r1 = ''.join(f'{list(self.board[(1, c1)])[0]}' if len(self.board[(1,c1)]) == 1 else '.' for c1 in self.columns) rL = ''.join(f'{list(self.board[(self.size, c1)])[0]}' if len(self.board[(self.size,c1)]) == 1 else '.' for c1 in self.columns) RCframe = f'{c1}/{cL} {r1}/{rL}' SolveServer.ClientToServer.put((RCframe, SquareSudokuPuzzle.check_indexed_thermos, playpuzzle, (SolveServer.Shared,))) def explorerow(self, r = 1, st = 0): nonlocal RCframe cellleft = (r, 1) cellright = (r, self.size) for dl in self.board[cellleft]: boardstack.append(copy.deepcopy(self)) self.board[cellleft] = {dl,} rstats[r-1] += 1 c1 = ''.join(f'{list(self.board[(r0, 1)])[0]}' if len(self.board[(r0,1)]) == 1 else '.' for r0 in self.rows) cL = ''.join(f'{list(self.board[(r0, self.size)])[0]}' if len(self.board[(r0,self.size)]) == 1 else '.' for r0 in self.rows) RCframe = f'{c1}/{cL}' print(f'\033[{2+st};1H{c1}/{cL}\033[K') self.status.global_progress = True while self.status.global_progress and not self.status.finished: self.status.global_progress = False self.AllDifferentStrategy2_SiftGroups() self.AllDifferentStrategy1_ScanForSingles() self.AllDifferentStrategy1_SiftSingles() self.ThermoStrategy8_ReducePossibles() if self.status.finished: if not self.status.failed: ndiff = sum(ndiffcalc(self.board[(r0, self.size)], self.board[(r0, 1)]) for r0 in self.rows) if ndiff >= minndiff: async_check_indexed_thermos(self) else: for dr in self.board[cellright]: ndiff = sum(ndiffcalc(self.board[(r0, self.size)], self.board[(r0, 1)]) if r0 != r else (abs(dr-dl) - 1) for r0 in self.rows) print(f'\033[{2+st};1H{c1}/{cL} Row ndiff = {ndiff} >? {maxndiff}: {ndiff > maxndiff}\033[K') print('\033[11;1H\033[40P') print(self) sys.stdout.flush() if ndiff <= maxndiff: ndiff = sum(ndiffcalc(self.board[(self.size, c1)], self.board[(1, c1)]) for c1 in self.columns) print(f'\033[{2+st};50HColumn ndiff = {ndiff} >? {maxndiff}: {ndiff > maxndiff}\033[K') if ndiff <= maxndiff: boardstack.append(copy.deepcopy(self)) self.board[cellright] = {dr,} cL = ''.join(f'{list(self.board[(r0, self.size)])[0]}' if len(self.board[(r0,self.size)]) == 1 else '.' for r0 in self.rows) RCframe = f'{c1}/{cL}' print(f'\033[{2+st};1H{c1}/{cL}') print('\033[57;1H') self.print_indexed_thermos() print('\033[71;1H') print(f'Row statistics: ' + ' '.join(f'{d}' for d in rstats)) print(f'\n# of solutions: {len(SolveServer.Shared.solutionstack)} / {SolveServer.Shared.Status}\033[K') print(f'\033[0J{SolveServer.Shared.JobsList}') if ((r == 1) or ((self.IndexedThermosColumnsValidation(1, [list(self.board[cell])[0] if len(self.board[cell]) == 1 else 0 for cell in self.indexedthermos_c['Set']])) and (self.IndexedThermosColumnsValidation(self.size, [list(self.board[cell])[0] if len(self.board[cell]) == 1 else 0 for cell in self.indexedthermos_c['Set']]))) ): self.status.global_progress = True while self.status.global_progress and not self.status.finished: self.status.global_progress = False self.AllDifferentStrategy2_SiftGroups() self.AllDifferentStrategy1_ScanForSingles() self.AllDifferentStrategy1_SiftSingles() self.ThermoStrategy8_ReducePossibles() ndiff = sum(ndiffcalc(self.board[(r0, self.size)], self.board[(r0, 1)]) for r0 in self.rows) if self.status.finished: if not self.status.failed: if ndiff >= minndiff: async_check_indexed_thermos(self) else: print(f'\033[{2+st};1H{c1}/{cL} Row {r} failed\033[K') else: if r == 1: explorerow(self, self.size, st + 1) else: ncombinations = 99 r2 = 0 for rr1 in range(2, self.size): cl = (rr1, 1) cr = (rr1, self.size) nc = len(self.board[cl]) * len(self.board[cr]) if nc == 0: break if nc == 1: continue if self.board[cl] & {1, 9}: nc -= 1 if self.board[cr] & {1, 9}: nc -= 1 if nc < ncombinations: ncombinations = nc r2 = rr1 if r2 > 0: explorerow(self, r2, st + 1) else: if self.CheckConstraints(): if ndiff >= minndiff: explorecolumn(self) else: print(f'\033[{2+st};1H{c1}/{cL} Row {r} failed constraint check\033[K') self = boardstack.pop() self.board[cellright] = self.board[cellright] - {dr,} self = boardstack.pop() self.board[cellleft] = self.board[cellleft] - {dl,} def explorecolumn(self, c = 2, st = 0): nonlocal RCframe c1 = ''.join(f'{d}' for r in self.rows for d in self.board[(r,1)]) cL = ''.join(f'{d}' for r in self.rows for d in self.board[(r,self.size)]) celltop = (1, c) cellbottom = (self.size, c) for dt in self.board[celltop]: boardstack.append(copy.deepcopy(self)) self.board[celltop] = {dt,} cstats[c-2] += 1 r1 = ''.join(f'{list(self.board[(1, c1)])[0]}' if len(self.board[(1,c1)]) == 1 else '.' for c1 in self.columns) rL = ''.join(f'{list(self.board[(self.size, c1)])[0]}' if len(self.board[(self.size,c1)]) == 1 else '.' for c1 in self.columns) RCframe = f'{c1}/{cL} {r1}/{rL}' print(f'\033[{50+st};1H{c1}/{cL} {r1}/{rL}', end='\033[K\r') self.status.global_progress = True while self.status.global_progress and not self.status.finished: self.status.global_progress = False self.AllDifferentStrategy2_SiftGroups() self.AllDifferentStrategy1_ScanForSingles() self.AllDifferentStrategy1_SiftSingles() self.ThermoStrategy8_ReducePossibles() if self.status.finished: if not self.status.failed: ndiff = sum(ndiffcalc(self.board[(self.size, c1)], self.board[(1, c1)]) for c1 in self.columns) if ndiff >= minndiff: async_check_indexed_thermos(self) else: for db in self.board[cellbottom]: ndiff = sum(ndiffcalc(self.board[(self.size, c1)], self.board[(1, c1)]) if c1 != c else (abs(db-dt) - 1) for c1 in self.columns) print('\033[11;1H\033[40P') print(self) if ndiff <= maxndiff: boardstack.append(copy.deepcopy(self)) self.board[cellbottom] = {db,} rL = ''.join(f'{list(self.board[(self.size, c1)])[0]}' if len(self.board[(self.size,c1)]) == 1 else '.' for c1 in self.columns) RCframe = f'{c1}/{cL} {r1}/{rL}' print(f'\033[{50+st};1H{c1}/{cL} {r1}/{rL} Column ndiff = {ndiff} >? {maxndiff}: {ndiff > maxndiff}\033[K') print('\033[57;1H') self.print_indexed_thermos() print('\033[71;1H') print(f'Row statistics: ' + ' '.join(f'{d}' for d in rstats)) print(f'Column statistics: ' + ' '.join(f'{d}' for d in cstats)) print(f'# of solutions: {len(SolveServer.Shared.solutionstack)} / {SolveServer.Shared.Status}\033[K') print(f'{SolveServer.Shared.JobsList}\033[0J') if self.IndexedThermosColumnsValidation(c, [list(self.board[cell])[0] for cell in self.indexedthermos_c['Set']]): self.status.global_progress = True while self.status.global_progress and not self.status.finished: self.status.global_progress = False self.AllDifferentStrategy2_SiftGroups() self.AllDifferentStrategy1_ScanForSingles() self.AllDifferentStrategy1_SiftSingles() self.ThermoStrategy8_ReducePossibles() ndiff = sum(ndiffcalc(self.board[(self.size, c1)], self.board[(1, c1)]) if c1 != c else (abs(db-dt) - 1) for c1 in self.columns) if self.status.finished: if not self.status.failed: if ndiff >= minndiff: async_check_indexed_thermos(self) else: print(f'\033[{50+st};43HColumn {c} failed\033[K') else: ncombinations = 99 c2 = 0 for cc1 in range(2, self.size): ct = (1, cc1) cb = (self.size, cc1) nc = len(self.board[ct]) * len(self.board[cb]) if nc == 0: break if nc == 1: continue if self.board[ct] & {1, 9}: nc -= 1 if self.board[cb] & {1, 9}: nc -= 1 if nc < ncombinations: ncombinations = nc c2 = cc1 if c2 > 0: explorecolumn(self, c2, st + 1) else: if ndiff >= minndiff: async_check_indexed_thermos(self) self = boardstack.pop() else: print(f'\033[{50+st};43HColumn {c} failed with ndiff = {ndiff}\033[K') self.board[cellbottom] = self.board[cellbottom] - {db,} self = boardstack.pop() self.board[celltop] = self.board[celltop] - {dt,} indexedthermos_cn = self.crossref['IndexedThermosNonOverlapping'][1] self.indexedthermos_c = self.all_constraints[indexedthermos_cn] boardstack = [] SolveServer.Shared.solutionstack = SolveServer.Manager.list() print('\033[s') explorerow(self) SolveServer.CloseServer() for solution in SolveServer.Shared.solutionstack: print() print(solution['board']) print(solution['thermos']) def check_indexed_thermos(self, WorkerToServer, Wn, SharedData): with silence_stdout(): #self.print_indexed_thermos() #print('\033[71;1H') #print(f'Row statistics: ' + ' '.join(f'{d}' for d in rstats)) #print(f'Column statistics: ' + ' '.join(f'{d}' for d in cstats)) #print(f'# of solutions: {len(solutionstack)}') self.CheckConstraints() if not self.status.failed: if not self.status.finished: self.Solve(timeout = 1200) if not self.CheckFinished(): self.CheckConstraints() if not self.status.failed: sols = SharedData.solutionstack sols.append({'board': copy.deepcopy(self), 'thermos': self.__str_indexed_thermos__()}) SharedData.solutionstack = sols c1 = ''.join(f'{list(self.board[(r0, 1)])[0]}' if len(self.board[(r0,1)]) == 1 else '.' for r0 in self.rows) cL = ''.join(f'{list(self.board[(r0, self.size)])[0]}' if len(self.board[(r0,self.size)]) == 1 else '.' for r0 in self.rows) r1 = ''.join(f'{list(self.board[(1, c1)])[0]}' if len(self.board[(1,c1)]) == 1 else '.' for c1 in self.columns) rL = ''.join(f'{list(self.board[(self.size, c1)])[0]}' if len(self.board[(self.size,c1)]) == 1 else '.' for c1 in self.columns) SharedData.RCframe = f'{c1}/{cL} {r1}/{rL}' S = [] if self.status.timedout: S.append(f'Solution {len(SharedData.solutionstack)} [probable / proof timed out]') else: S.append(f'Solution {len(SharedData.solutionstack)}') ndiffr = sum(ndiffcalc(self.board[(r0, self.size)], self.board[(r0, 1)]) for r0 in self.rows) ndiffc = sum(ndiffcalc(self.board[(self.size, c1)], self.board[(1, c1)]) for c1 in self.columns) S.append(self.__str__()) S.append(SharedData.RCframe) S.append(f'ndiff r/c: {ndiffr}/{ndiffc}') S.append(self.__str_indexed_thermos__()) S.append('\n') WorkerToServer.put((Wn, 'write to file', self.solutions_filename, '\n'.join(S))) #print('\033[2J\033[1;1HStart time: ' + time.strftime("%F %X", time.localtime(starttime))) #sys.stdout.flush() # ============================================================================= def FindRCIndexes(self): self.__ComputeSolvabilityAndEffectiveSets() self.CheckFinished() rcf = {} rcb = {} rcix = {} IX = {} ci = 0 S = [] sums = [] sumrc = [] patterns1 = { 'C': [ ''' 11 2. 2. 33 ''', ], 'O': [ ''' 11 23 23 44 ''', ], 'P': [ ''' 11 .2 32 3. ''', ], '26': [ ''' 12 12 .. 33 ''', ''' 11 22 .. 33 ''', ], } patterns2 = { 'C': [ ''' .11 2.. 2.. .33 ''', ], 'O': [ ''' .11 2.3 2.3 44. ''', ''' 11. 2.3 2.3 .44 ''', ''' .11. 2..3 2..3 .44. ''', ], 'P': [ ''' 11. ..2 3.2 3.. ''', ''' 112 ..2 433 4.. ''', ], '26': [ ''' 12 12 .. 33 ''', ''' 11 22 .. 33 ''', ''' 11.3 22.3 ''', ''' 12.3 12.3 ''', ''' 113 223 ''', ''' 123 123 ''', ], } patterns3 = { 'C': [ ''' 11 .. 22 ''', ], 'O': [ ''' 11 23 23 ''', ''' 12 12 33 ''', ], 'P': [ ''' .1 21 2. ''', ''' 11 2. 2. ''', ], '26': [ ''' 12 12 33 ''', ''' 11 22 33 ''', ], } def PreparePattern(patterns): patternsindex = list(patterns.items()) patterns['_index'] = patternsindex patterns['_cells'] = {} patterns['_mM'] = {} for l, pa in patternsindex: patterns['_cells'][l] = [] patterns['_mM'][l] = [] for pn, p in enumerate(pa): patterns['_cells'][l].append({}) prlist = [] pclist = [] for r, pr in enumerate(re.sub('^\n*|\n*$', '', re.sub('[^0-9a-zA-Z.\n]', '', p)).splitlines()): for c, prc in enumerate(pr): if prc != '.': if prc not in patterns['_cells'][l][pn]: patterns['_cells'][l][pn][prc] = [] patterns['_cells'][l][pn][prc].append((r, c)) prlist.append(r) pclist.append(c) patterns['_mM'][l].append({'min': (min(prlist), min(pclist)), 'max': (max(prlist), max(pclist))}) #print(f'{l}/{pn}: {patterns['_cells'][l][pn]}') PreparePattern(patterns1) PreparePattern(patterns2) PreparePattern(patterns3) fg = lambda c: f'\033[4;38;5;{c}m' bg = lambda c: f'\033[4;48;5;{c}m' nn = '\033[0m' def colourix(ix, T): nonlocal rcf, rcb, ci, S, sums, sumrc, IX IX[T] = ix rcf = {} rcb = {} s = [] for tn, t in enumerate(ix): c = 20 + (ci*15 % 234) ci += 1 rcf[t[0]] = c rcf[t[1]] = c rcb[t[2]] = c s.append(fg(c) + f'{t[0][0]}{t[0][1]},{t[1][0]}{t[1][1]}:{t[2][0]}{t[2][1]}' + nn) sums[t[2][0]+t[2][1]] += 1 sumrc[t[2][0]+t[2][1]].append(t[2]) if t[0] not in rcix: rcix[t[0]] = {} if t[1] not in rcix: rcix[t[1]] = {} rcix[t[0]][(T, tn, c)] = 0 rcix[t[1]][(T, tn, c)] = 1 for r in self.rows: s1 = '' s2 = '' for c in self.columns: if (r, c) in rcf: s1 += fg(rcf[(r, c)]) if (r, c) in rcb: s2 += fg(rcb[(r, c)]) s1 += f'{list(self.board[(r, c)])[0]}' + nn s2 += f'{list(self.board[(r, c)])[0]}' + nn S[r] += ' ' + T + ': ' + s1 + ' ' + s2 return ' '.join(s) def SearchPatterns(T, patterns): # Search patterns Matches = [] lMatch = {} for l, pa in patterns['_index']: for pn, p in enumerate(pa): rm, cm = patterns['_mM'][l][pn]['min'] rM, cM = patterns['_mM'][l][pn]['max'] for r0 in range(1, self.size + 1 + rm - rM): for c0 in range(1, self.size + 1 + cm - cM): # Check whether pattern matches Match = True ShapeMatch = [] for prc, shape in patterns['_cells'][l][pn].items(): ixlist = [] for rc in shape: rcsearch = (r0+rm+rc[0], c0+cm+rc[1]) if rcsearch in rcix: ixlist.append(set(rcix[rcsearch].keys())) if len(ixlist) == len(shape): ShapeMatch.append(set.intersection(*ixlist)) if not ShapeMatch[-1]: Match = False break else: Match = False break if Match: print(f'Matched shape [{l}/{pn}]: ({r0}, {c0}) => {ShapeMatch}') Matches.append((l, pn, (r0, c0), ShapeMatch)) lMatch[l] = True print(f'Matching patterns [{T}]: {"".join(lMatch.keys())}') if len(lMatch) == len(patterns): print(f'All patterns match [{T}]: {"".join(lMatch.keys())}') S = ['' for r in range(self.size+1)] MatchIndex = {} for l, pn, rc0, sm in Matches: if not l in MatchIndex: MatchIndex[l] = [] MatchIndex[l].append(set()) s = f'{l}/{pn}:' S[0] += f'{s:12s}' cells = {} for s in sm: _T, tn, col = list(s)[0] cells[IX[_T][tn][0]] = col cells[IX[_T][tn][1]] = col MatchIndex[l][-1].add((IX[_T][tn][0], col)) MatchIndex[l][-1].add((IX[_T][tn][1], col)) for r in self.rows: s = '' for c in self.columns: if (r, c) in cells: s += fg(cells[(r, c)]) + f'{list(self.board[(r, c)])[0]}' + nn else: s += f'{list(self.board[(r, c)])[0]}' S[r] += f' {s} ' for s in S: if s: print(s) print() # Search disjoint sets (non overlapping patterns) for full patterns DisjointSets = [] if len(MatchIndex) == len(patterns['_index']): for MatchingSet in itertools.product(*MatchIndex.values()): Disjoint = True for SetCombination in itertools.combinations(MatchingSet, 2): if set.intersection(*[set(e[0] for e in pat) for pat in SetCombination]): Disjoint = False break if Disjoint: DisjointSets.append(MatchingSet) if DisjointSets: print(f'DisjointSets [{T}]: {"".join(MatchIndex.keys())}:') S = ['' for r in range(self.size+1)] for Set in DisjointSets: cells = {e[0]: e[1] for pat in Set for e in list(pat)} try: i26 = list(MatchIndex.keys()).index('26') S[0] += f'Σ26 = {sum(list(self.board[e[0]])[0] for e in list(Set[i26])):2d} ' except: S[0] += ' ' for r in self.rows: s = '' for c in self.columns: if (r, c) in cells: s += fg(cells[(r, c)]) + f'{list(self.board[(r, c)])[0]}' + nn else: s += f'{list(self.board[(r, c)])[0]}' S[r] += f' {s} ' for s in S: if s: print(s) print() if self.status.solved: print(self) rix = [] rixr = [] rixd = [] cix = [] cixr = [] cixd = [] IX = {} for r in self.rows: for c in list(self.columns)[:-1]: dd = r rr = list(self.board[(r, c)])[0] cc = list(self.board[(r, c+1)])[0] if self.board[(rr, cc)] == {dd, }: rix.append(((r, c), (r, c+1), (rr, cc))) for r in self.rows: for c in list(self.columns)[:-1]: dd = r rr = list(self.board[(r, c+1)])[0] cc = list(self.board[(r, c)])[0] if self.board[(rr, cc)] == {dd, }: rixr.append(((r, c+1), (r, c), (rr, cc))) if ((r, c), (r, c+1), (cc, rr)) in rix: rixd.append(((r, c), (r, c+1), (cc, rr))) for c in self.columns: for r in list(self.rows)[:-1]: dd = c rr = list(self.board[(r, c)])[0] cc = list(self.board[(r+1, c)])[0] if self.board[(rr, cc)] == {dd, }: cix.append(((r, c), (r+1, c), (rr, cc))) for c in self.columns: for r in list(self.rows)[:-1]: dd = c rr = list(self.board[(r+1, c)])[0] cc = list(self.board[(r, c)])[0] if self.board[(rr, cc)] == {dd, }: cixr.append(((r+1, c), (r, c), (rr, cc))) if ((r, c), (r+1, c), (cc, rr)) in cix: cixd.append(((r, c), (r+1, c), (cc, rr))) S = ['' for r in range(self.size+1)] sumrc = [[] for ds in range(self.size*2+1)] sums = [0 for ds in range(self.size*2+1)] print(f'Number of indexes: {len(rix)+len(rixr)+len(cix)+len(cixr)} = {len(rix)}+{len(rixr)}+{len(cix)}+{len(cixr)}') print(f'Number of bi-directional indexes: {len(rixd)+len(cixd)} = {len(rixd)}+{len(cixd)}') print('Row indexes: ' + colourix(rix, 'R')) print('Row reverse indexes: ' + colourix(rixr, 'rR')) print('Column indexes: ' + colourix(cix, 'C')) print('Column reverse indexes: ' + colourix(cixr, 'rC')) print(' '.join(f's{ids}:{len(set(sumrc[ids]))}.{sd}' for ids, sd in enumerate(sums) if sd)) for s in S: if s: print(s) print() SearchPatterns("1", patterns1) SearchPatterns("2", patterns2) SearchPatterns("3", patterns3) @contextmanager def silence_stdout(): old_target = sys.stdout try: with open(os.devnull, "w") as new_target: sys.stdout = new_target yield new_target finally: sys.stdout = old_target def ndiffcalc(c1, c2): if len(c1) == 0 or len(c2) == 0: return 9 c1m = min(c1) c1M = max(c1) c2m = min(c2) c2M = max(c2) if c1M < c2m: return c2m - c1M - 1 if c2M < c1m: return c1m - c2M - 1 return 0 class JobServer: def __init__(self, maxqueue = 20, maxprocesses = 10): self.maxqueue = maxqueue self.maxprocesses = maxprocesses self.Manager = mp.Manager() self.ClientToServer = self.Manager.Queue(maxqueue) self.WorkerToServer = self.Manager.Queue(maxqueue) self.Worker = {} self.Start = {} self.Label = {} self.Shared = self.Manager.Namespace() self.Shared.Status = '' self.Shared.JobsList= '' self.Shared.RCframe = '' self.Shared.solutionstack = [] self.JobServer = mp.Process(target=self.RunJobServer, args=()) self.JobServer.start() def RunJobServer(self): Wn = 0 serving = True while serving: self.Shared.Status = f'w={list(self.Worker.keys())} cq={self.ClientToServer.qsize()} wq={self.WorkerToServer.qsize()}' # process messages from client if len(self.Worker) < self.maxprocesses: try: ClientMessage = self.ClientToServer.get(True, 5) if ClientMessage == 'Stop Server when Ready': print('Stopping server\033[K') serving = False else: # Start new job self.Worker[Wn] = mp.Process(target=self.JobWorker, args=(Wn, ClientMessage)) self.Worker[Wn].start() self.Start[Wn] = datetime.datetime.now() self.Label[Wn] = ClientMessage[0] self.Shared.JobsList = '\n'.join( f'{self.Start[i].strftime("%F %X.%f")[:-3]} Solve {i} in progress: {self.Label[i]}' for i in self.Label.keys() ) Wn += 1 except queue.Empty: pass # process messages from workers while ((len(self.Worker) == self.maxprocesses) or not self.WorkerToServer.empty() or (not serving and len(self.Worker) > 0) ): if not serving: print(f'{datetime.datetime.now().strftime("%F %X.%f")[:-3]} Waiting on {len(self.Worker)} Worker(s) to complete. Last: {self.Start[Wn-1].strftime("%F %X.%f")[:-3]}\033[K', end='\r') try: WorkerMessage = self.WorkerToServer.get((len(self.Worker) == self.maxprocesses) or not serving, 5) if WorkerMessage[1] == 'write to console': print(WorkerMessage[2]) elif WorkerMessage[1] == 'write to file': with open(WorkerMessage[2], 'at', encoding="utf-8") as outputfile: print(WorkerMessage[3], file=outputfile) elif WorkerMessage[1] == 'close task': n=WorkerMessage[0] self.Worker[n].join() self.Worker[n].terminate() del self.Label[n] del self.Start[n] del self.Worker[n] self.Shared.JobsList = '\n'.join( f'{self.Start[i].strftime("%F %X.%f")[:-3]} Solve {i} in progress: {self.Label[i]}' for i in self.Label.keys() ) except queue.Empty: pass def JobWorker(self, Wn, ClientMessage): self.WorkerToServer.put((Wn, 'write to console', f'{datetime.datetime.now().strftime("%F %X.%f")[:-3]} start {Wn}\033[K')) (Label, Function, Object, Params) = ClientMessage Function(Object, self.WorkerToServer, Wn, *Params) self.WorkerToServer.put((Wn, 'write to console', f'{datetime.datetime.now().strftime("%F %X.%f")[:-3]} end {Wn}\033[K')) self.WorkerToServer.put((Wn, 'close task')) def CloseServer(self): self.ClientToServer.put('Stop Server when Ready') self.JobServer.join() self.JobServer.terminate() # ============================================================================= # ============================================================================= debug=0 debug_step=0 Standard2x2SudokuGrid = SquareSudokuPuzzle(2, "Standard 2x2 sudoku grid") Standard3x3SudokuGrid = SquareSudokuPuzzle(3, "Standard 3x3 sudoku grid")