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
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:]))
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))))
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'
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']
if givens:
if isinstance(givens, dict):
self.givens = givens
else:
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,}
self.singles = copy.deepcopy(self.givens)
if clues:
self.board.update(clues)
self.givens.update(clues)
TODO
if constraints:
self.puzzle['AllSets'].update(constraints)
self.__BuildConstraintsInventory()
TODO
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,
'NumberOfLinkedConstraints': 0,
'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 = {}
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)
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)
)))
)
allboxes = {}
nallboxes = {}
alladjacentboxes = {}
self.boxaliases = {}
for n, rc in enumerate(self.puzzle['AllSets']['Boxes']['Sets'][1]):
allboxes[n] = rc
nallboxes[rc] = n
alladjacentboxes[n] = self.OrthogonallyAdjacentBoxes(rc)
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:
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],
})
for n, c in enumerate(self.all_constraints):
TODO
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
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,})
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 '<Empty cell set>\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}')
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:
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 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()
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:
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):
'''
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.
'''
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 = 0
for r, c in self.board:
if r == 0:
if c > nextclue:
nextclue = c
nextclue += 1
self.status.progress_step = False
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 = [(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 = []
parent_givens = set(cell for cell in parent if len(self.board[cell]) == 1)
sum_givens = self.SumGivens(parent)
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:
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):
sumsubsetscombinations = [[(-1, combisum, combiregion),],]
if sum(len(sr[2]) for sr in sumsubsets) != len(combiregion):
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))
if self.debug >= 2:
print(f'Sum subset combinations count = {C(len(sumsubsets2), ngroups)}')
for nc, combi in enumerate(sumsubsetscombinations):
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):
complement = parent - combiregion2 - parent_givens
if complement not in allsumsets:
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:
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
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}')
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:
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:
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):
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
setcontainsvalue = [previousvalue if previousvalue in self.board[cell] else 0 for cell in c['Set'][3:]]
if setcontainsvalue.count(previousvalue) == 1:
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]}')
setcontainsvalue = [nextvalue if nextvalue in self.board[cell] else 0 for cell in c['Set'][3:]]
if setcontainsvalue.count(nextvalue) == 1:
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]}')
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:
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]}')
if setdetermined.count(nextvalue) == 1:
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]}')
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):
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()
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,
]
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:
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
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]
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 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]
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 self.status.failed:
pass
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]
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)
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):
SolveServer = JobServer(maxqueue, maxprocesses)
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.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)))
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))})
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):
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):
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()
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()}'
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:
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
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")