import numpy as np #a = raw_input() inputData = ["4321, 412341, 32, 22, 12, 1222"] a = inputData[0] a = [i.strip() for i in a.split(',')] boardSize = len(a[0]) board = [[0] + [int(i) for i in a[0]] + [0]] for i in a[1:-1]: board.append([int(i[0])] + [-1] * boardSize + [int(i[-1])]) board.append([0] + [int(i) for i in a[-1]] + [0]) board = np.array(board) isValid = lambda n: [n[i] > max(n[1:i]) if i > 1 else True for i in range(1, boardSize + 1)].count(True) == n[0] answer = [] def checkBoard(n): temp = [n[1:-1], n.T[1:-1]] for i in temp: if False in [len([k for k in j[1:-1] if k != -1]) == len(set([k for k in j[1:-1] if k != -1])) for j in i]: return False for j in i: if not(isValid(j) and isValid(j[::-1])) and -1 not in j: return False return True def prune(node): global answer if node.children == []: if sum([i.count(-1) for i in node.b.tolist()]) != 0: return False else: answer = node.b return True return True in [prune(i) for i in node.children] class State: def __init__(self, newBoard): self.children = [] self.b = newBoard for i in range(boardSize): for j in range(boardSize): if self.b[i + 1][j + 1] == -1: for k in range(boardSize): temp = np.copy(self.b) temp[i + 1][j + 1] = k + 1 if checkBoard(temp): self.children.append(State(temp)) return head = State(board) prune(head) for i in inputData[1:]: print answer[int(i[0])][int(i[-1])]