from gurobipy import * from itertools import * def maxAscendingSubwords(word): if len(word) == 0: return [[]] if len(word) == 1: return [word] subwords = [] # Choose the first element. first_letter = word[0] for i in range(len(word)): if word[i] <= first_letter: # Remove any letters before or less than word[i]. modified_word = [letter for letter in word[(i + 1):] if letter >= word[i]] modified_subwords = maxAscendingSubwords(modified_word) if len(modified_subwords) != 0: subwords += [[word[i]] + j for j in modified_subwords] else: subwords += [[word[i]]] first_letter = word[i] return subwords def maxAscendingKSubwords(word, k): if k == 1: return maxAscendingSubwords(word) words = [] for subword in maxAscendingSubwords(word): # For each of these, we remove its letters from word and go down recursively. filtered_word = [i for i in word if i not in subword] for smaller_ascending_subword in maxAscendingKSubwords(filtered_word, k - 1): # Now we reconstruct a bigger word. words.append([i for i in word if i in subword or i in smaller_ascending_subword]) # Now we need to make sure no words are subwords of any other. words.sort(key=len) removals = [] for i in range(len(words)): for j in range(i + 1, len(words)): try: indices = [words[j].index(k) for k in words[i]] except: continue if all([indices[k] <= indices[k + 1] for k in range(len(indices) - 1)]): removals.append(i) break for i in range(len(removals) - 1, -1, -1): words.pop(removals[i]) return words # Tries to find a counterexample to the diagonal RSK algorithm given by order and labels. # order and labels are 2D arrays of the same Young diagram shape. def evalModel(order, labels, getWordsOnly = False): if len(order) != len(labels): raise ValueError("order and labels must be the same shape") for i in range(len(order)): if len(order[i]) != len(labels[i]): raise ValueError("order and labels must be the same shape") # Create a new Gurobi model m = Model() m.setParam("OutputFlag", 0) # Create variables for the two different inputs. We'll insist their outputs are equal but at least # one input is different, so that we'll find a failure to be injective if possible. inputVars0 = {} inputVars1 = {} for row in labels: for label in row: inputVars0[label] = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I{label}") inputVars1[label] = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J{label}") words = [] # Now we need to construct each output variable, which is done one diagonal at a time. for diagonal in range(-len(order) + 1, len(order[0])): # The bottom-right-most box in this diagonal. initialBox = [max(0, -diagonal), max(0, diagonal)] terminalBox = [initialBox[0], initialBox[1]] while terminalBox[0] < len(order) and terminalBox[1] < len(order[terminalBox[0]]): terminalBox[0] += 1 terminalBox[1] += 1 # We now need to find the word associated with this diagonal. terminalBox has been incremented until # it's actually out of bounds, so the following slice syntax doesn't need to be incremented. orderRect = [row[:terminalBox[1]] for row in order[:terminalBox[0]]] labelsRect = [row[:terminalBox[1]] for row in labels[:terminalBox[0]]] orderFlat = [entry for row in orderRect for entry in row] labelsFlat = [label for row in labelsRect for label in row] orderFlatSorted = sorted(orderFlat) word = [labelsFlat[orderFlat.index(i)] for i in orderFlatSorted] if getWordsOnly: words.append(word) continue # The actual algorithm works by running RSK on this word and placing the shape of the SSYT generated # into the output RPP. We therefore just care the the shapes of both inputs are the same, then, # and the sum of the first k rows is given by the length of the maximum k-ascending subword. for k in range(min(terminalBox[0], terminalBox[1])): # Each max k-ascending subword gets its own Gurobi variable. subwordVars0 = [] subwordVars1 = [] for subword in maxAscendingKSubwords(word, k + 1): subwordVars0.append( m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I_len_{'_'.join(map(str, subword))}") ) subwordVars1.append( m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J_len_{'_'.join(map(str, subword))}") ) # These variables are the lengths of this particular subword. m.addConstr( subwordVars0[-1] == quicksum([inputVars0[label] for label in subword]) ) m.addConstr( subwordVars1[-1] == quicksum([inputVars1[label] for label in subword]) ) max0 = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I_max_{diagonal}_{k + 1}") max1 = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J_max_{diagonal}_{k + 1}") m.addGenConstrMax(max0, subwordVars0) m.addGenConstrMax(max1, subwordVars1) # Enforce that the two corresponding output entries are equal. m.addConstr(max0 == max1) if getWordsOnly: return words # Now we need to require that the inputs are *not* all identical. absDiffVars = [] for label in inputVars0: diffVar = m.addVar(vtype = GRB.INTEGER, lb = -GRB.INFINITY, name = f"diff_{label}") m.addConstr(diffVar == inputVars0[label] - inputVars1[label]) absDiffVars.append(m.addVar(vtype = GRB.INTEGER, lb = 0, name = f"abs_diff_{label}")) m.addConstr(absDiffVars[-1] == abs_(diffVar)) m.addConstr(quicksum(absDiffVars) >= 1) # Finally, we need to have something to maximize or minimize. We'll make that the total entry sum # so that we find the minimum counterexample if it exists. sum0Var = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I_sum") m.addConstr(sum0Var == quicksum([inputVars0[label] for label in inputVars0])) sum1Var = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J_sum") m.addConstr(sum1Var == quicksum([inputVars1[label] for label in inputVars1])) m.setObjective(sum0Var + sum1Var, GRB.MINIMIZE) m.update() # print("=====") # for constr in m.getConstrs(): # print(f"{m.getRow(constr)} = {constr.RHS}") # print("=====") m.optimize() if m.SolCount: return ( [int(inputVars0[label].X) for label in inputVars0], [int(inputVars1[label].X) for label in inputVars1] ) return () # Tries to find a pair of inputs for which the two given algorithms disagree. def findDifferenceBetweenAlgorithms(order0, labels0, order1, labels1): if len(order0) != len(labels0) or len(labels0) != len(order1) or len(order1) != len(labels1): raise ValueError("order and labels must be the same shape") for i in range(len(order0)): if len(order0[i]) != len(labels0[i]) or len(labels0[i]) != len(order1[i]) or len(order1[i]) != len(labels1[i]): raise ValueError("order and labels must be the same shape") # Create a new Gurobi model m = Model() m.setParam("OutputFlag", 0) # Create variables for the inputs. There's only one set this time because we want # the outputs to be distinct, but we organize the *same* variables in two different # dictionaries for easy access. inputVars = [] inputVars0 = {} inputVars1 = {} for i in range(len(order0)): inputVars.append([]) for j in range(len(order0[i])): var = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I{i}_{j}") inputVars[i].append(var) inputVars0[labels0[i][j]] = var inputVars1[labels1[i][j]] = var outputVars0 = [] outputVars1 = [] for i in range(len(order0)): outputVars0.append([0] * len(order0[i])) outputVars1.append([0] * len(order0[i])) # Now we need to construct two different output variables, which is done one diagonal at a time. for diagonal in range(-len(order0) + 1, len(order0[0])): initialBox = [max(0, -diagonal), max(0, diagonal)] # The bottom-right-most box in this diagonal. terminalBox = [initialBox[0], initialBox[1]] while terminalBox[0] < len(order0) and terminalBox[1] < len(order0[terminalBox[0]]): terminalBox[0] += 1 terminalBox[1] += 1 # We now need to find the two words associated with this diagonal. terminalBox has been incremented until # it's actually out of bounds, so the following slice syntax doesn't need to be incremented. order0Rect = [row[:terminalBox[1]] for row in order0[:terminalBox[0]]] labels0Rect = [row[:terminalBox[1]] for row in labels0[:terminalBox[0]]] order1Rect = [row[:terminalBox[1]] for row in order1[:terminalBox[0]]] labels1Rect = [row[:terminalBox[1]] for row in labels1[:terminalBox[0]]] order0Flat = [entry for row in order0Rect for entry in row] labels0Flat = [label for row in labels0Rect for label in row] order1Flat = [entry for row in order1Rect for entry in row] labels1Flat = [label for row in labels1Rect for label in row] order0FlatSorted = sorted(order0Flat) order1FlatSorted = sorted(order1Flat) word0 = [labels0Flat[order0Flat.index(i)] for i in order0FlatSorted] word1 = [labels1Flat[order1Flat.index(i)] for i in order1FlatSorted] # The actual algorithm works by running RSK on this word and placing the shape of the SSYT generated # into the output RPP. We therefore just care the the shapes of both inputs are the same, then, # and the sum of the first k rows is given by the length of the maximum k-ascending subword. for k in range(min(terminalBox[0], terminalBox[1])): # Each max k-ascending subword gets its own Gurobi variable. There's only subwordVars0 = [] subwordVars1 = [] for subword in maxAscendingKSubwords(word0, k + 1): subwordVars0.append( m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I_len_{''.join(map(str, subword))}") ) # This variable is the length of this particular subword. m.addConstr( subwordVars0[-1] == quicksum([inputVars0[label] for label in subword]) ) for subword in maxAscendingKSubwords(word1, k + 1): subwordVars1.append( m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J_len_{''.join(map(str, subword))}") ) m.addConstr( subwordVars1[-1] == quicksum([inputVars1[label] for label in subword]) ) max0 = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"I_max_{diagonal}_{k + 1}") max1 = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"J_max_{diagonal}_{k + 1}") m.addGenConstrMax(max0, subwordVars0) m.addGenConstrMax(max1, subwordVars1) # These aren't really "output vars" in the sense that they aren't really outputs, # but they're still equivalent to it. row = initialBox[0] + k col = initialBox[1] + k outputVars0[row][col] = max0 outputVars1[row][col] = max1 # Unlike evalModel, here we *don't* # enforce that the two corresponding output entries are equal. # Now we need to require that the outputs are *not* all identical. absDiffVars = [] for i in range(len(order0)): for j in range(len(order0[i])): diffVar = m.addVar(vtype = GRB.INTEGER, lb = -GRB.INFINITY, name = f"diff_{i}_{j}") m.addConstr(diffVar == outputVars0[i][j] - outputVars1[i][j]) absDiffVars.append(m.addVar(vtype = GRB.INTEGER, lb = 0, name = f"abs_diff_{i}_{j}")) m.addConstr(absDiffVars[-1] == abs_(diffVar)) m.addConstr(quicksum(absDiffVars) >= 1) # Finally, we need to have something to maximize or minimize. We'll make that the total entry sum # so that we find the minimum counterexample if it exists. sumVar = m.addVar(lb = 0, vtype = GRB.INTEGER, name = f"sum") m.addConstr(sumVar == quicksum([inputVars0[label] for label in inputVars0])) m.setObjective(sumVar, GRB.MINIMIZE) m.update() # print("=====") # for constr in m.getConstrs(): # print(f"{m.getRow(constr)} = {constr.RHS}") # print("=====") m.optimize() if m.SolCount: return ( [int(var.X) for row in inputVars for var in row], # [int(outputVars0[label].X) for label in outputVars0], # [int(outputVars1[label].X) for label in outputVars1], ) return () possiblePairs2x2 = [ [[[1, 2], [3, 4]], [[1, 3], [2, 4]]], [[[1, 3], [2, 4]], [[1, 2], [3, 4]]], [[[1, 3], [4, 2]], [[1, 4], [3, 2]]], [[[1, 3], [4, 2]], [[2, 3], [4, 1]]], [[[1, 4], [3, 2]], [[1, 3], [4, 2]]], [[[1, 4], [3, 2]], [[2, 4], [3, 1]]], [[[2, 1], [4, 3]], [[3, 1], [4, 2]]], [[[2, 3], [4, 1]], [[1, 3], [4, 2]]], [[[2, 3], [4, 1]], [[2, 4], [3, 1]]], [[[2, 4], [1, 3]], [[3, 4], [1, 2]]], [[[2, 4], [3, 1]], [[1, 4], [3, 2]]], [[[2, 4], [3, 1]], [[2, 3], [4, 1]]], [[[3, 1], [2, 4]], [[3, 2], [1, 4]]], [[[3, 1], [2, 4]], [[4, 1], [2, 3]]], [[[3, 1], [4, 2]], [[2, 1], [4, 3]]], [[[3, 2], [1, 4]], [[3, 1], [2, 4]]], [[[3, 2], [1, 4]], [[4, 2], [1, 3]]], [[[3, 4], [1, 2]], [[2, 4], [1, 3]]], [[[4, 1], [2, 3]], [[3, 1], [2, 4]]], [[[4, 1], [2, 3]], [[4, 2], [1, 3]]], [[[4, 2], [1, 3]], [[3, 2], [1, 4]]], [[[4, 2], [1, 3]], [[4, 1], [2, 3]]], [[[4, 2], [3, 1]], [[4, 3], [2, 1]]], [[[4, 3], [2, 1]], [[4, 2], [3, 1]]] ] possiblePairs3x2 = [ [[[1, 2], [3, 4], [5, 6]], [[1, 4], [2, 5], [3, 6]]], [[[1, 3], [4, 5], [6, 2]], [[1, 5], [3, 6], [4, 2]]], [[[1, 3], [5, 2], [4, 6]], [[1, 5], [4, 3], [2, 6]]], [[[1, 4], [2, 5], [3, 6]], [[1, 2], [3, 4], [5, 6]]], [[[1, 4], [2, 5], [6, 3]], [[2, 3], [4, 5], [6, 1]]], [[[1, 4], [2, 6], [5, 3]], [[2, 3], [4, 6], [5, 1]]], [[[1, 4], [5, 3], [2, 6]], [[2, 3], [5, 1], [4, 6]]], [[[1, 4], [6, 3], [2, 5]], [[2, 3], [6, 1], [4, 5]]], [[[1, 4], [6, 3], [5, 2]], [[1, 6], [5, 4], [3, 2]]], [[[1, 5], [3, 2], [6, 4]], [[3, 5], [4, 1], [6, 2]]], [[[1, 5], [3, 6], [4, 2]], [[1, 3], [4, 5], [6, 2]]], [[[1, 5], [4, 3], [2, 6]], [[1, 3], [5, 2], [4, 6]]], [[[1, 6], [3, 2], [5, 4]], [[3, 6], [4, 1], [5, 2]]], [[[1, 6], [5, 4], [3, 2]], [[1, 4], [6, 3], [5, 2]]], [[[2, 1], [4, 3], [6, 5]], [[4, 1], [5, 2], [6, 3]]], [[[2, 3], [4, 5], [6, 1]], [[1, 4], [2, 5], [6, 3]]], [[[2, 3], [4, 5], [6, 1]], [[2, 5], [3, 6], [4, 1]]], [[[2, 3], [4, 6], [5, 1]], [[1, 4], [2, 6], [5, 3]]], [[[2, 3], [5, 1], [4, 6]], [[1, 4], [5, 3], [2, 6]]], [[[2, 3], [6, 1], [4, 5]], [[1, 4], [6, 3], [2, 5]]], [[[2, 4], [6, 3], [5, 1]], [[2, 6], [5, 4], [3, 1]]], [[[2, 5], [1, 4], [3, 6]], [[3, 4], [1, 2], [5, 6]]], [[[2, 5], [1, 4], [6, 3]], [[4, 5], [2, 3], [6, 1]]], [[[2, 5], [3, 1], [6, 4]], [[3, 4], [5, 1], [6, 2]]], [[[2, 5], [3, 6], [1, 4]], [[3, 4], [5, 6], [1, 2]]], [[[2, 5], [3, 6], [4, 1]], [[2, 3], [4, 5], [6, 1]]], [[[2, 5], [6, 4], [3, 1]], [[3, 4], [6, 2], [5, 1]]], [[[2, 6], [1, 4], [5, 3]], [[4, 6], [2, 3], [5, 1]]], [[[2, 6], [4, 3], [1, 5]], [[4, 6], [5, 2], [1, 3]]], [[[2, 6], [5, 4], [3, 1]], [[2, 4], [6, 3], [5, 1]]], [[[3, 1], [2, 5], [6, 4]], [[5, 1], [3, 4], [6, 2]]], [[[3, 1], [5, 4], [2, 6]], [[5, 1], [6, 3], [2, 4]]], [[[3, 2], [1, 5], [6, 4]], [[4, 1], [3, 5], [6, 2]]], [[[3, 2], [1, 6], [5, 4]], [[4, 1], [3, 6], [5, 2]]], [[[3, 2], [5, 4], [1, 6]], [[4, 1], [5, 2], [3, 6]]], [[[3, 2], [5, 4], [1, 6]], [[5, 2], [6, 3], [1, 4]]], [[[3, 2], [6, 4], [1, 5]], [[4, 1], [6, 2], [3, 5]]], [[[3, 4], [1, 2], [5, 6]], [[2, 5], [1, 4], [3, 6]]], [[[3, 4], [5, 1], [6, 2]], [[2, 5], [3, 1], [6, 4]]], [[[3, 4], [5, 6], [1, 2]], [[2, 5], [3, 6], [1, 4]]], [[[3, 4], [6, 2], [5, 1]], [[2, 5], [6, 4], [3, 1]]], [[[3, 5], [4, 1], [6, 2]], [[1, 5], [3, 2], [6, 4]]], [[[3, 6], [1, 5], [4, 2]], [[4, 5], [1, 3], [6, 2]]], [[[3, 6], [2, 5], [1, 4]], [[5, 6], [3, 4], [1, 2]]], [[[3, 6], [2, 5], [4, 1]], [[4, 5], [2, 3], [6, 1]]], [[[3, 6], [4, 1], [2, 5]], [[4, 5], [6, 1], [2, 3]]], [[[3, 6], [4, 1], [5, 2]], [[1, 6], [3, 2], [5, 4]]], [[[3, 6], [4, 2], [1, 5]], [[4, 5], [6, 2], [1, 3]]], [[[4, 1], [3, 5], [6, 2]], [[3, 2], [1, 5], [6, 4]]], [[[4, 1], [3, 6], [2, 5]], [[6, 1], [4, 5], [2, 3]]], [[[4, 1], [3, 6], [5, 2]], [[3, 2], [1, 6], [5, 4]]], [[[4, 1], [5, 2], [3, 6]], [[3, 2], [5, 4], [1, 6]]], [[[4, 1], [5, 2], [6, 3]], [[2, 1], [4, 3], [6, 5]]], [[[4, 1], [6, 2], [3, 5]], [[3, 2], [6, 4], [1, 5]]], [[[4, 2], [3, 6], [1, 5]], [[6, 2], [4, 5], [1, 3]]], [[[4, 3], [1, 5], [2, 6]], [[5, 2], [1, 3], [4, 6]]], [[[4, 3], [2, 1], [6, 5]], [[5, 2], [4, 1], [6, 3]]], [[[4, 3], [2, 6], [1, 5]], [[5, 2], [4, 6], [1, 3]]], [[[4, 3], [6, 5], [2, 1]], [[5, 2], [6, 3], [4, 1]]], [[[4, 5], [1, 3], [6, 2]], [[3, 6], [1, 5], [4, 2]]], [[[4, 5], [2, 3], [6, 1]], [[2, 5], [1, 4], [6, 3]]], [[[4, 5], [2, 3], [6, 1]], [[3, 6], [2, 5], [4, 1]]], [[[4, 5], [6, 1], [2, 3]], [[3, 6], [4, 1], [2, 5]]], [[[4, 5], [6, 2], [1, 3]], [[3, 6], [4, 2], [1, 5]]], [[[4, 6], [2, 3], [5, 1]], [[2, 6], [1, 4], [5, 3]]], [[[4, 6], [5, 2], [1, 3]], [[2, 6], [4, 3], [1, 5]]], [[[5, 1], [2, 3], [4, 6]], [[5, 3], [1, 4], [2, 6]]], [[[5, 1], [3, 4], [6, 2]], [[3, 1], [2, 5], [6, 4]]], [[[5, 1], [6, 3], [2, 4]], [[3, 1], [5, 4], [2, 6]]], [[[5, 2], [1, 3], [4, 6]], [[4, 3], [1, 5], [2, 6]]], [[[5, 2], [4, 1], [3, 6]], [[5, 4], [3, 2], [1, 6]]], [[[5, 2], [4, 1], [6, 3]], [[4, 3], [2, 1], [6, 5]]], [[[5, 2], [4, 6], [1, 3]], [[4, 3], [2, 6], [1, 5]]], [[[5, 2], [6, 3], [1, 4]], [[3, 2], [5, 4], [1, 6]]], [[[5, 2], [6, 3], [4, 1]], [[4, 3], [6, 5], [2, 1]]], [[[5, 3], [1, 4], [2, 6]], [[5, 1], [2, 3], [4, 6]]], [[[5, 4], [1, 6], [3, 2]], [[6, 3], [1, 4], [5, 2]]], [[[5, 4], [2, 6], [3, 1]], [[6, 3], [2, 4], [5, 1]]], [[[5, 4], [3, 1], [2, 6]], [[6, 3], [5, 1], [2, 4]]], [[[5, 4], [3, 2], [1, 6]], [[5, 2], [4, 1], [3, 6]]], [[[5, 4], [3, 2], [1, 6]], [[6, 3], [5, 2], [1, 4]]], [[[5, 6], [3, 4], [1, 2]], [[3, 6], [2, 5], [1, 4]]], [[[6, 1], [2, 3], [4, 5]], [[6, 3], [1, 4], [2, 5]]], [[[6, 1], [4, 5], [2, 3]], [[4, 1], [3, 6], [2, 5]]], [[[6, 2], [3, 4], [5, 1]], [[6, 4], [2, 5], [3, 1]]], [[[6, 2], [4, 1], [3, 5]], [[6, 4], [3, 2], [1, 5]]], [[[6, 2], [4, 5], [1, 3]], [[4, 2], [3, 6], [1, 5]]], [[[6, 3], [1, 4], [2, 5]], [[6, 1], [2, 3], [4, 5]]], [[[6, 3], [1, 4], [5, 2]], [[5, 4], [1, 6], [3, 2]]], [[[6, 3], [2, 4], [5, 1]], [[5, 4], [2, 6], [3, 1]]], [[[6, 3], [5, 1], [2, 4]], [[5, 4], [3, 1], [2, 6]]], [[[6, 3], [5, 2], [1, 4]], [[5, 4], [3, 2], [1, 6]]], [[[6, 3], [5, 2], [4, 1]], [[6, 5], [4, 3], [2, 1]]], [[[6, 4], [2, 5], [3, 1]], [[6, 2], [3, 4], [5, 1]]], [[[6, 4], [3, 2], [1, 5]], [[6, 2], [4, 1], [3, 5]]], [[[6, 5], [4, 3], [2, 1]], [[6, 3], [5, 2], [4, 1]]], ] possiblePairs3x3 = [ [[[1, 2, 3], [4, 5, 6], [7, 8, 9]], [[1, 4, 7], [2, 5, 8], [3, 6, 9]]], [[[1, 2, 8], [4, 5, 3], [7, 9, 6]], [[3, 6, 8], [4, 7, 1], [5, 9, 2]]], [[[1, 2, 9], [4, 5, 3], [7, 8, 6]], [[3, 6, 9], [4, 7, 1], [5, 8, 2]]], [[[1, 3, 4], [5, 6, 7], [8, 9, 2]], [[1, 5, 8], [3, 6, 9], [4, 7, 2]]], [[[1, 4, 7], [2, 5, 8], [3, 6, 9]], [[1, 2, 3], [4, 5, 6], [7, 8, 9]]], [[[1, 4, 7], [2, 5, 8], [9, 3, 6]], [[3, 4, 5], [6, 7, 8], [9, 1, 2]]], [[[1, 4, 7], [2, 5, 9], [8, 3, 6]], [[3, 4, 5], [6, 7, 9], [8, 1, 2]]], [[[1, 4, 7], [8, 3, 6], [2, 5, 9]], [[3, 4, 5], [8, 1, 2], [6, 7, 9]]], [[[1, 4, 7], [9, 3, 6], [2, 5, 8]], [[3, 4, 5], [9, 1, 2], [6, 7, 8]]], [[[1, 5, 8], [3, 6, 9], [4, 7, 2]], [[1, 3, 4], [5, 6, 7], [8, 9, 2]]], [[[1, 6, 3], [8, 5, 2], [7, 4, 9]], [[1, 8, 7], [6, 5, 4], [3, 2, 9]]], [[[1, 7, 4], [9, 6, 3], [8, 5, 2]], [[1, 9, 8], [7, 6, 5], [4, 3, 2]]], [[[1, 8, 2], [4, 3, 5], [7, 6, 9]], [[3, 8, 6], [4, 1, 7], [5, 2, 9]]], [[[1, 8, 7], [6, 5, 4], [3, 2, 9]], [[1, 6, 3], [8, 5, 2], [7, 4, 9]]], [[[1, 9, 2], [4, 3, 5], [7, 6, 8]], [[3, 9, 6], [4, 1, 7], [5, 2, 8]]], [[[1, 9, 8], [7, 6, 5], [4, 3, 2]], [[1, 7, 4], [9, 6, 3], [8, 5, 2]]], [[[2, 1, 3], [5, 4, 6], [8, 7, 9]], [[4, 1, 7], [5, 2, 8], [6, 3, 9]]], [[[2, 1, 8], [5, 4, 3], [9, 7, 6]], [[6, 3, 8], [7, 4, 1], [9, 5, 2]]], [[[2, 1, 9], [5, 4, 3], [8, 7, 6]], [[6, 3, 9], [7, 4, 1], [8, 5, 2]]], [[[2, 3, 1], [5, 6, 4], [8, 9, 7]], [[4, 7, 1], [5, 8, 2], [6, 9, 3]]], [[[2, 3, 4], [5, 6, 7], [8, 9, 1]], [[2, 5, 8], [3, 6, 9], [4, 7, 1]]], [[[2, 3, 9], [5, 6, 4], [8, 1, 7]], [[4, 7, 9], [5, 8, 2], [6, 1, 3]]], [[[2, 5, 8], [1, 4, 7], [3, 6, 9]], [[4, 5, 6], [1, 2, 3], [7, 8, 9]]], [[[2, 5, 8], [1, 4, 7], [9, 3, 6]], [[6, 7, 8], [3, 4, 5], [9, 1, 2]]], [[[2, 5, 8], [3, 6, 1], [9, 4, 7]], [[4, 5, 6], [7, 8, 1], [9, 2, 3]]], [[[2, 5, 8], [3, 6, 9], [1, 4, 7]], [[4, 5, 6], [7, 8, 9], [1, 2, 3]]], [[[2, 5, 8], [3, 6, 9], [4, 7, 1]], [[2, 3, 4], [5, 6, 7], [8, 9, 1]]], [[[2, 5, 8], [9, 4, 7], [3, 6, 1]], [[4, 5, 6], [9, 2, 3], [7, 8, 1]]], [[[2, 5, 9], [1, 4, 7], [8, 3, 6]], [[6, 7, 9], [3, 4, 5], [8, 1, 2]]], [[[2, 7, 4], [9, 6, 3], [8, 5, 1]], [[2, 9, 8], [7, 6, 5], [4, 3, 1]]], [[[2, 9, 3], [5, 4, 6], [8, 7, 1]], [[4, 9, 7], [5, 2, 8], [6, 3, 1]]], [[[2, 9, 8], [7, 6, 5], [4, 3, 1]], [[2, 7, 4], [9, 6, 3], [8, 5, 1]]], [[[3, 1, 4], [6, 5, 7], [9, 8, 2]], [[5, 1, 8], [6, 3, 9], [7, 4, 2]]], [[[3, 2, 1], [6, 5, 4], [9, 8, 7]], [[7, 4, 1], [8, 5, 2], [9, 6, 3]]], [[[3, 2, 4], [6, 5, 7], [9, 8, 1]], [[5, 2, 8], [6, 3, 9], [7, 4, 1]]], [[[3, 2, 9], [6, 5, 4], [1, 8, 7]], [[7, 4, 9], [8, 5, 2], [1, 6, 3]]], [[[3, 4, 1], [6, 7, 5], [9, 2, 8]], [[5, 8, 1], [6, 9, 3], [7, 2, 4]]], [[[3, 4, 2], [6, 7, 5], [9, 1, 8]], [[5, 8, 2], [6, 9, 3], [7, 1, 4]]], [[[3, 4, 5], [6, 7, 8], [9, 1, 2]], [[1, 4, 7], [2, 5, 8], [9, 3, 6]]], [[[3, 4, 5], [6, 7, 9], [8, 1, 2]], [[1, 4, 7], [2, 5, 9], [8, 3, 6]]], [[[3, 4, 5], [8, 1, 2], [6, 7, 9]], [[1, 4, 7], [8, 3, 6], [2, 5, 9]]], [[[3, 4, 5], [9, 1, 2], [6, 7, 8]], [[1, 4, 7], [9, 3, 6], [2, 5, 8]]], [[[3, 6, 1], [2, 5, 8], [9, 4, 7]], [[7, 8, 1], [4, 5, 6], [9, 2, 3]]], [[[3, 6, 8], [4, 7, 1], [5, 9, 2]], [[1, 2, 8], [4, 5, 3], [7, 9, 6]]], [[[3, 6, 9], [1, 5, 8], [4, 7, 2]], [[5, 6, 7], [1, 3, 4], [8, 9, 2]]], [[[3, 6, 9], [2, 5, 8], [1, 4, 7]], [[7, 8, 9], [4, 5, 6], [1, 2, 3]]], [[[3, 6, 9], [2, 5, 8], [4, 7, 1]], [[5, 6, 7], [2, 3, 4], [8, 9, 1]]], [[[3, 6, 9], [4, 7, 1], [2, 5, 8]], [[5, 6, 7], [8, 9, 1], [2, 3, 4]]], [[[3, 6, 9], [4, 7, 1], [5, 8, 2]], [[1, 2, 9], [4, 5, 3], [7, 8, 6]]], [[[3, 6, 9], [4, 7, 2], [1, 5, 8]], [[5, 6, 7], [8, 9, 2], [1, 3, 4]]], [[[3, 8, 6], [4, 1, 7], [5, 2, 9]], [[1, 8, 2], [4, 3, 5], [7, 6, 9]]], [[[3, 9, 6], [4, 1, 7], [5, 2, 8]], [[1, 9, 2], [4, 3, 5], [7, 6, 8]]], [[[4, 1, 7], [3, 8, 6], [5, 2, 9]], [[4, 3, 5], [1, 8, 2], [7, 6, 9]]], [[[4, 1, 7], [3, 9, 6], [5, 2, 8]], [[4, 3, 5], [1, 9, 2], [7, 6, 8]]], [[[4, 1, 7], [5, 2, 8], [3, 9, 6]], [[4, 3, 5], [7, 6, 8], [1, 9, 2]]], [[[4, 1, 7], [5, 2, 8], [6, 3, 9]], [[2, 1, 3], [5, 4, 6], [8, 7, 9]]], [[[4, 1, 7], [5, 2, 9], [3, 8, 6]], [[4, 3, 5], [7, 6, 9], [1, 8, 2]]], [[[4, 3, 1], [7, 6, 5], [2, 9, 8]], [[8, 5, 1], [9, 6, 3], [2, 7, 4]]], [[[4, 3, 2], [7, 6, 5], [1, 9, 8]], [[8, 5, 2], [9, 6, 3], [1, 7, 4]]], [[[4, 3, 5], [1, 8, 2], [7, 6, 9]], [[4, 1, 7], [3, 8, 6], [5, 2, 9]]], [[[4, 3, 5], [1, 9, 2], [7, 6, 8]], [[4, 1, 7], [3, 9, 6], [5, 2, 8]]], [[[4, 3, 5], [7, 6, 8], [1, 9, 2]], [[4, 1, 7], [5, 2, 8], [3, 9, 6]]], [[[4, 3, 5], [7, 6, 9], [1, 8, 2]], [[4, 1, 7], [5, 2, 9], [3, 8, 6]]], [[[4, 5, 3], [1, 2, 8], [7, 9, 6]], [[4, 7, 1], [3, 6, 8], [5, 9, 2]]], [[[4, 5, 3], [1, 2, 9], [7, 8, 6]], [[4, 7, 1], [3, 6, 9], [5, 8, 2]]], [[[4, 5, 3], [7, 8, 6], [1, 2, 9]], [[4, 7, 1], [5, 8, 2], [3, 6, 9]]], [[[4, 5, 3], [7, 9, 6], [1, 2, 8]], [[4, 7, 1], [5, 9, 2], [3, 6, 8]]], [[[4, 5, 6], [1, 2, 3], [7, 8, 9]], [[2, 5, 8], [1, 4, 7], [3, 6, 9]]], [[[4, 5, 6], [7, 8, 1], [9, 2, 3]], [[2, 5, 8], [3, 6, 1], [9, 4, 7]]], [[[4, 5, 6], [7, 8, 9], [1, 2, 3]], [[2, 5, 8], [3, 6, 9], [1, 4, 7]]], [[[4, 5, 6], [9, 2, 3], [7, 8, 1]], [[2, 5, 8], [9, 4, 7], [3, 6, 1]]], [[[4, 7, 1], [3, 6, 8], [5, 9, 2]], [[4, 5, 3], [1, 2, 8], [7, 9, 6]]], [[[4, 7, 1], [3, 6, 9], [2, 5, 8]], [[8, 9, 1], [5, 6, 7], [2, 3, 4]]], [[[4, 7, 1], [3, 6, 9], [5, 8, 2]], [[4, 5, 3], [1, 2, 9], [7, 8, 6]]], [[[4, 7, 1], [5, 8, 2], [3, 6, 9]], [[4, 5, 3], [7, 8, 6], [1, 2, 9]]], [[[4, 7, 1], [5, 8, 2], [6, 9, 3]], [[2, 3, 1], [5, 6, 4], [8, 9, 7]]], [[[4, 7, 1], [5, 9, 2], [3, 6, 8]], [[4, 5, 3], [7, 9, 6], [1, 2, 8]]], [[[4, 7, 2], [3, 6, 9], [1, 5, 8]], [[8, 9, 2], [5, 6, 7], [1, 3, 4]]], [[[4, 7, 9], [5, 8, 2], [6, 1, 3]], [[2, 3, 9], [5, 6, 4], [8, 1, 7]]], [[[4, 9, 7], [5, 2, 8], [6, 3, 1]], [[2, 9, 3], [5, 4, 6], [8, 7, 1]]], [[[5, 1, 8], [6, 3, 9], [7, 4, 2]], [[3, 1, 4], [6, 5, 7], [9, 8, 2]]], [[[5, 2, 8], [4, 1, 7], [3, 9, 6]], [[7, 6, 8], [4, 3, 5], [1, 9, 2]]], [[[5, 2, 8], [4, 1, 7], [6, 3, 9]], [[5, 4, 6], [2, 1, 3], [8, 7, 9]]], [[[5, 2, 8], [4, 9, 7], [6, 3, 1]], [[5, 4, 6], [2, 9, 3], [8, 7, 1]]], [[[5, 2, 8], [6, 3, 1], [4, 9, 7]], [[5, 4, 6], [8, 7, 1], [2, 9, 3]]], [[[5, 2, 8], [6, 3, 9], [4, 1, 7]], [[5, 4, 6], [8, 7, 9], [2, 1, 3]]], [[[5, 2, 8], [6, 3, 9], [7, 4, 1]], [[3, 2, 4], [6, 5, 7], [9, 8, 1]]], [[[5, 2, 9], [4, 1, 7], [3, 8, 6]], [[7, 6, 9], [4, 3, 5], [1, 8, 2]]], [[[5, 4, 3], [2, 1, 8], [9, 7, 6]], [[7, 4, 1], [6, 3, 8], [9, 5, 2]]], [[[5, 4, 3], [2, 1, 9], [8, 7, 6]], [[7, 4, 1], [6, 3, 9], [8, 5, 2]]], [[[5, 4, 3], [8, 7, 6], [2, 1, 9]], [[7, 4, 1], [8, 5, 2], [6, 3, 9]]], [[[5, 4, 3], [9, 7, 6], [2, 1, 8]], [[7, 4, 1], [9, 5, 2], [6, 3, 8]]], [[[5, 4, 6], [2, 1, 3], [8, 7, 9]], [[5, 2, 8], [4, 1, 7], [6, 3, 9]]], [[[5, 4, 6], [2, 9, 3], [8, 7, 1]], [[5, 2, 8], [4, 9, 7], [6, 3, 1]]], [[[5, 4, 6], [8, 7, 1], [2, 9, 3]], [[5, 2, 8], [6, 3, 1], [4, 9, 7]]], [[[5, 4, 6], [8, 7, 9], [2, 1, 3]], [[5, 2, 8], [6, 3, 9], [4, 1, 7]]], [[[5, 6, 4], [2, 3, 1], [8, 9, 7]], [[5, 8, 2], [4, 7, 1], [6, 9, 3]]], [[[5, 6, 4], [2, 3, 9], [8, 1, 7]], [[5, 8, 2], [4, 7, 9], [6, 1, 3]]], [[[5, 6, 4], [8, 1, 7], [2, 3, 9]], [[5, 8, 2], [6, 1, 3], [4, 7, 9]]], [[[5, 6, 4], [8, 9, 7], [2, 3, 1]], [[5, 8, 2], [6, 9, 3], [4, 7, 1]]], [[[5, 6, 7], [1, 3, 4], [8, 9, 2]], [[3, 6, 9], [1, 5, 8], [4, 7, 2]]], [[[5, 6, 7], [2, 3, 4], [8, 9, 1]], [[3, 6, 9], [2, 5, 8], [4, 7, 1]]], [[[5, 6, 7], [8, 9, 1], [2, 3, 4]], [[3, 6, 9], [4, 7, 1], [2, 5, 8]]], [[[5, 6, 7], [8, 9, 2], [1, 3, 4]], [[3, 6, 9], [4, 7, 2], [1, 5, 8]]], [[[5, 8, 1], [6, 9, 3], [7, 2, 4]], [[3, 4, 1], [6, 7, 5], [9, 2, 8]]], [[[5, 8, 2], [4, 7, 1], [3, 6, 9]], [[7, 8, 6], [4, 5, 3], [1, 2, 9]]], [[[5, 8, 2], [4, 7, 1], [6, 9, 3]], [[5, 6, 4], [2, 3, 1], [8, 9, 7]]], [[[5, 8, 2], [4, 7, 9], [6, 1, 3]], [[5, 6, 4], [2, 3, 9], [8, 1, 7]]], [[[5, 8, 2], [6, 1, 3], [4, 7, 9]], [[5, 6, 4], [8, 1, 7], [2, 3, 9]]], [[[5, 8, 2], [6, 9, 3], [4, 7, 1]], [[5, 6, 4], [8, 9, 7], [2, 3, 1]]], [[[5, 8, 2], [6, 9, 3], [7, 1, 4]], [[3, 4, 2], [6, 7, 5], [9, 1, 8]]], [[[5, 9, 2], [4, 7, 1], [3, 6, 8]], [[7, 9, 6], [4, 5, 3], [1, 2, 8]]], [[[6, 1, 3], [5, 8, 2], [4, 7, 9]], [[8, 1, 7], [5, 6, 4], [2, 3, 9]]], [[[6, 3, 1], [5, 2, 8], [4, 9, 7]], [[8, 7, 1], [5, 4, 6], [2, 9, 3]]], [[[6, 3, 8], [7, 4, 1], [9, 5, 2]], [[2, 1, 8], [5, 4, 3], [9, 7, 6]]], [[[6, 3, 9], [5, 1, 8], [7, 4, 2]], [[6, 5, 7], [3, 1, 4], [9, 8, 2]]], [[[6, 3, 9], [5, 2, 8], [4, 1, 7]], [[8, 7, 9], [5, 4, 6], [2, 1, 3]]], [[[6, 3, 9], [5, 2, 8], [7, 4, 1]], [[6, 5, 7], [3, 2, 4], [9, 8, 1]]], [[[6, 3, 9], [7, 4, 1], [5, 2, 8]], [[6, 5, 7], [9, 8, 1], [3, 2, 4]]], [[[6, 3, 9], [7, 4, 1], [8, 5, 2]], [[2, 1, 9], [5, 4, 3], [8, 7, 6]]], [[[6, 3, 9], [7, 4, 2], [5, 1, 8]], [[6, 5, 7], [9, 8, 2], [3, 1, 4]]], [[[6, 5, 4], [1, 8, 7], [3, 2, 9]], [[8, 5, 2], [1, 6, 3], [7, 4, 9]]], [[[6, 5, 4], [3, 2, 1], [9, 8, 7]], [[8, 5, 2], [7, 4, 1], [9, 6, 3]]], [[[6, 5, 4], [3, 2, 9], [1, 8, 7]], [[8, 5, 2], [7, 4, 9], [1, 6, 3]]], [[[6, 5, 4], [9, 8, 7], [3, 2, 1]], [[8, 5, 2], [9, 6, 3], [7, 4, 1]]], [[[6, 5, 7], [3, 1, 4], [9, 8, 2]], [[6, 3, 9], [5, 1, 8], [7, 4, 2]]], [[[6, 5, 7], [3, 2, 4], [9, 8, 1]], [[6, 3, 9], [5, 2, 8], [7, 4, 1]]], [[[6, 5, 7], [9, 8, 1], [3, 2, 4]], [[6, 3, 9], [7, 4, 1], [5, 2, 8]]], [[[6, 5, 7], [9, 8, 2], [3, 1, 4]], [[6, 3, 9], [7, 4, 2], [5, 1, 8]]], [[[6, 7, 5], [3, 4, 1], [9, 2, 8]], [[6, 9, 3], [5, 8, 1], [7, 2, 4]]], [[[6, 7, 5], [3, 4, 2], [9, 1, 8]], [[6, 9, 3], [5, 8, 2], [7, 1, 4]]], [[[6, 7, 5], [9, 1, 8], [3, 4, 2]], [[6, 9, 3], [7, 1, 4], [5, 8, 2]]], [[[6, 7, 5], [9, 2, 8], [3, 4, 1]], [[6, 9, 3], [7, 2, 4], [5, 8, 1]]], [[[6, 7, 8], [3, 4, 5], [9, 1, 2]], [[2, 5, 8], [1, 4, 7], [9, 3, 6]]], [[[6, 7, 9], [3, 4, 5], [8, 1, 2]], [[2, 5, 9], [1, 4, 7], [8, 3, 6]]], [[[6, 9, 3], [5, 8, 1], [7, 2, 4]], [[6, 7, 5], [3, 4, 1], [9, 2, 8]]], [[[6, 9, 3], [5, 8, 2], [4, 7, 1]], [[8, 9, 7], [5, 6, 4], [2, 3, 1]]], [[[6, 9, 3], [5, 8, 2], [7, 1, 4]], [[6, 7, 5], [3, 4, 2], [9, 1, 8]]], [[[6, 9, 3], [7, 1, 4], [5, 8, 2]], [[6, 7, 5], [9, 1, 8], [3, 4, 2]]], [[[6, 9, 3], [7, 2, 4], [5, 8, 1]], [[6, 7, 5], [9, 2, 8], [3, 4, 1]]], [[[7, 1, 4], [6, 9, 3], [5, 8, 2]], [[9, 1, 8], [6, 7, 5], [3, 4, 2]]], [[[7, 2, 4], [6, 9, 3], [5, 8, 1]], [[9, 2, 8], [6, 7, 5], [3, 4, 1]]], [[[7, 4, 1], [6, 3, 8], [9, 5, 2]], [[5, 4, 3], [2, 1, 8], [9, 7, 6]]], [[[7, 4, 1], [6, 3, 9], [5, 2, 8]], [[9, 8, 1], [6, 5, 7], [3, 2, 4]]], [[[7, 4, 1], [6, 3, 9], [8, 5, 2]], [[5, 4, 3], [2, 1, 9], [8, 7, 6]]], [[[7, 4, 1], [8, 5, 2], [6, 3, 9]], [[5, 4, 3], [8, 7, 6], [2, 1, 9]]], [[[7, 4, 1], [8, 5, 2], [9, 6, 3]], [[3, 2, 1], [6, 5, 4], [9, 8, 7]]], [[[7, 4, 1], [9, 5, 2], [6, 3, 8]], [[5, 4, 3], [9, 7, 6], [2, 1, 8]]], [[[7, 4, 2], [6, 3, 9], [5, 1, 8]], [[9, 8, 2], [6, 5, 7], [3, 1, 4]]], [[[7, 4, 9], [8, 5, 2], [1, 6, 3]], [[3, 2, 9], [6, 5, 4], [1, 8, 7]]], [[[7, 6, 5], [1, 9, 8], [4, 3, 2]], [[9, 6, 3], [1, 7, 4], [8, 5, 2]]], [[[7, 6, 5], [2, 9, 8], [4, 3, 1]], [[9, 6, 3], [2, 7, 4], [8, 5, 1]]], [[[7, 6, 5], [4, 3, 1], [2, 9, 8]], [[9, 6, 3], [8, 5, 1], [2, 7, 4]]], [[[7, 6, 5], [4, 3, 2], [1, 9, 8]], [[9, 6, 3], [8, 5, 2], [1, 7, 4]]], [[[7, 6, 8], [4, 3, 5], [1, 9, 2]], [[5, 2, 8], [4, 1, 7], [3, 9, 6]]], [[[7, 6, 9], [4, 3, 5], [1, 8, 2]], [[5, 2, 9], [4, 1, 7], [3, 8, 6]]], [[[7, 8, 1], [4, 5, 6], [9, 2, 3]], [[3, 6, 1], [2, 5, 8], [9, 4, 7]]], [[[7, 8, 6], [4, 5, 3], [1, 2, 9]], [[5, 8, 2], [4, 7, 1], [3, 6, 9]]], [[[7, 8, 9], [4, 5, 6], [1, 2, 3]], [[3, 6, 9], [2, 5, 8], [1, 4, 7]]], [[[7, 9, 6], [4, 5, 3], [1, 2, 8]], [[5, 9, 2], [4, 7, 1], [3, 6, 8]]], [[[8, 1, 2], [3, 4, 5], [6, 7, 9]], [[8, 3, 6], [1, 4, 7], [2, 5, 9]]], [[[8, 1, 7], [5, 6, 4], [2, 3, 9]], [[6, 1, 3], [5, 8, 2], [4, 7, 9]]], [[[8, 3, 6], [1, 4, 7], [2, 5, 9]], [[8, 1, 2], [3, 4, 5], [6, 7, 9]]], [[[8, 5, 1], [9, 6, 3], [2, 7, 4]], [[4, 3, 1], [7, 6, 5], [2, 9, 8]]], [[[8, 5, 2], [1, 6, 3], [7, 4, 9]], [[6, 5, 4], [1, 8, 7], [3, 2, 9]]], [[[8, 5, 2], [7, 4, 1], [6, 3, 9]], [[8, 7, 6], [5, 4, 3], [2, 1, 9]]], [[[8, 5, 2], [7, 4, 1], [9, 6, 3]], [[6, 5, 4], [3, 2, 1], [9, 8, 7]]], [[[8, 5, 2], [7, 4, 9], [1, 6, 3]], [[6, 5, 4], [3, 2, 9], [1, 8, 7]]], [[[8, 5, 2], [9, 6, 3], [1, 7, 4]], [[4, 3, 2], [7, 6, 5], [1, 9, 8]]], [[[8, 5, 2], [9, 6, 3], [7, 4, 1]], [[6, 5, 4], [9, 8, 7], [3, 2, 1]]], [[[8, 7, 1], [5, 4, 6], [2, 9, 3]], [[6, 3, 1], [5, 2, 8], [4, 9, 7]]], [[[8, 7, 6], [5, 4, 3], [2, 1, 9]], [[8, 5, 2], [7, 4, 1], [6, 3, 9]]], [[[8, 7, 9], [5, 4, 6], [2, 1, 3]], [[6, 3, 9], [5, 2, 8], [4, 1, 7]]], [[[8, 9, 1], [5, 6, 7], [2, 3, 4]], [[4, 7, 1], [3, 6, 9], [2, 5, 8]]], [[[8, 9, 2], [5, 6, 7], [1, 3, 4]], [[4, 7, 2], [3, 6, 9], [1, 5, 8]]], [[[8, 9, 7], [5, 6, 4], [2, 3, 1]], [[6, 9, 3], [5, 8, 2], [4, 7, 1]]], [[[9, 1, 2], [3, 4, 5], [6, 7, 8]], [[9, 3, 6], [1, 4, 7], [2, 5, 8]]], [[[9, 1, 8], [6, 7, 5], [3, 4, 2]], [[7, 1, 4], [6, 9, 3], [5, 8, 2]]], [[[9, 2, 3], [4, 5, 6], [7, 8, 1]], [[9, 4, 7], [2, 5, 8], [3, 6, 1]]], [[[9, 2, 8], [6, 7, 5], [3, 4, 1]], [[7, 2, 4], [6, 9, 3], [5, 8, 1]]], [[[9, 3, 6], [1, 4, 7], [2, 5, 8]], [[9, 1, 2], [3, 4, 5], [6, 7, 8]]], [[[9, 4, 7], [2, 5, 8], [3, 6, 1]], [[9, 2, 3], [4, 5, 6], [7, 8, 1]]], [[[9, 5, 2], [7, 4, 1], [6, 3, 8]], [[9, 7, 6], [5, 4, 3], [2, 1, 8]]], [[[9, 6, 3], [1, 7, 4], [8, 5, 2]], [[7, 6, 5], [1, 9, 8], [4, 3, 2]]], [[[9, 6, 3], [2, 7, 4], [8, 5, 1]], [[7, 6, 5], [2, 9, 8], [4, 3, 1]]], [[[9, 6, 3], [8, 5, 1], [2, 7, 4]], [[7, 6, 5], [4, 3, 1], [2, 9, 8]]], [[[9, 6, 3], [8, 5, 2], [1, 7, 4]], [[7, 6, 5], [4, 3, 2], [1, 9, 8]]], [[[9, 6, 3], [8, 5, 2], [7, 4, 1]], [[9, 8, 7], [6, 5, 4], [3, 2, 1]]], [[[9, 7, 6], [5, 4, 3], [2, 1, 8]], [[9, 5, 2], [7, 4, 1], [6, 3, 8]]], [[[9, 8, 1], [6, 5, 7], [3, 2, 4]], [[7, 4, 1], [6, 3, 9], [5, 2, 8]]], [[[9, 8, 2], [6, 5, 7], [3, 1, 4]], [[7, 4, 2], [6, 3, 9], [5, 1, 8]]], [[[9, 8, 7], [6, 5, 4], [3, 2, 1]], [[9, 6, 3], [8, 5, 2], [7, 4, 1]]], ] def groupAlgorithms(possiblePairs): algorithms = {} for i in range(len(possiblePairs)): print(i) order0 = possiblePairs[i][0] labels0 = possiblePairs[i][1] order0Flat = [o for row in order0 for o in row] labels0Flat = [l for row in labels0 for l in row] key0 = tuple([tuple(order0Flat), tuple(labels0Flat)]) # Find which distinct algorithm this one matches, if any. j = 0 order1Flat = [] labels1Flat = [] keys = list(algorithms.keys()) while j < len(keys): order1 = algorithms[keys[j]][0][0] labels1 = algorithms[keys[j]][0][1] order1Flat = [o for row in order1 for o in row] labels1Flat = [l for row in labels1 for l in row] if findDifferenceBetweenAlgorithms(order0, labels0, order1, labels1) == (): break j += 1 if j < len(keys): algorithms[keys[j]].append([order0, labels0]) else: algorithms[key0] = [[order0, labels0]] print(algorithms) # Get all length-9 words def validWords(): for word in permutations(range(1, 10)): if len(maxAscendingKSubwords(word, 4)) != 0: continue for subword1 in combinations(word, 6): if len(maxAscendingKSubwords(subword1, 3)) != 0: continue for subword2 in combinations(word, 6): if len(maxAscendingKSubwords(subword2, 3)) != 0: continue for subword3 in combinations(subword1, 3): if len(maxAscendingKSubwords(subword3, 2)) != 0: continue for subword4 in combinations(subword2, 3): if len(maxAscendingKSubwords(subword3, 2)) != 0: continue print(subword3, subword1, word, subword2, subword4) # Brute-force evaluates all possible numRows x numCols algorithms and prints the ones that work. def evalAllAlgorithms(numRows, numCols): wordSize = numRows * numCols tableaux = [[list(orderWord[i * numCols:(i + 1) * numCols]) for i in range(numRows)] for orderWord in permutations(range(1, wordSize + 1))] for order in tableaux: for labels in tableaux: if evalModel(order, labels) == (): print(order, labels) # Verify that all algorithms are valid. # for pair in possiblePairs3x3: # order = pair[0] # labels = pair[1] # if evalModel(order, labels) == (): # print(pair) # Arrange the algorithms into groups # groupAlgorithms(possiblePairs3x3) # PS # order = [[1, 5, 8, 10], [2, 6, 9], [3, 7], [4]] # labels = [[1, 2, 3, 4], [5, 6, 7], [8, 9], [10]] # PS_r2 # order = [[2, 6, 9, 10], [1, 5, 8], [3, 7], [4]] # labels = [[4, 5, 6, 7], [1, 2, 3], [8, 9], [10]] # PS_c3 # order = [[6, 3, 1, 10], [7, 4, 2], [8, 5], [9]] # labels = [[3, 2, 1, 4], [7, 6, 5], [9, 8], [10]] # HG # order = [[7, 4, 2, 1], [8, 5, 3], [9, 6], [10]] # labels = [[4, 3, 2, 1], [7, 6, 5], [9, 8], [10]] # HG_r2 # order = [[8, 5, 3, 1], [7, 4, 2], [9, 6], [10]] # labels = [[7, 6, 5, 4], [3, 2, 1], [9, 8], [10]] # HG_c3 # order = [[2, 6, 9, 1], [3, 7, 10], [4, 8], [5]] # labels = [[2, 3, 4, 1], [5, 6, 7], [8, 9], [10]] # HG_r3_c2 # order = [[6, 10, 3, 1], [5, 9, 2], [4, 8], [7]] # labels = [[8, 9, 7, 6], [4, 5, 3], [1, 2], [10]] # print(evalModel(order, labels))