Matching Algorithm

import random
from itertools import combinations
import time as t
import sys
sys.setrecursionlimit(15000)

def isPrime(num):
    """Checks num for primality. Returns bool."""
    if num == 2:
        return True
    elif num < 2 or not num % 2: # even numbers > 2 not prime
        return False
        # factor can be no larger than the square root of num
    for i in range(3, int(num ** .5 + 1), 2):
        if not num % i: return False
    return True

def generatePrimes(n):
    """Returns a list of prime numbers with length n"""
    primes = [2,]
    noOfPrimes = 1  # cache length of primes for speed
    testNum = 3 # number to test for primality
    while noOfPrimes < n:
        if isPrime(testNum):
            primes.append(testNum)
            noOfPrimes += 1
        testNum += 2
    return primes



class Person:
    def __init__(self, name, ID):
        self.name = name
        self.primeID = ID

    def __eq__(self, other):
        return self.primeID == other

    def __repr__(self):
        return '%d' % (self.name)

class Schedule:
    def __init__(self, numberofpeople):
        self.x = 0 #current x pos
        self.y = 0 #current y pos
        self.fill = 0 #number of slots filled
        self.board = [] #get initialized to an n-1 x n/2 grid  to hold links
        self.failed = [] #same as board but holds a list of failed links in each cell
        self.uniqueLinks = [] #list of unique links, a link is the product of two primes
        self.availableLinks = [] #links not yet placed in the grid
        self.personList = [] #list of Person. A person is a name and a unique prime number
        self.primeList = generatePrimes(numberofpeople) #list of the first n prime numbers
        random.shuffle(self.primeList)

        #initializes the empty lists
        for i in range(numberofpeople):
            self.personList.append(Person(i, self.primeList[i]))
        self.uniqueLinks = list(map(lambda x: x[0] * x[1], combinations(self.primeList, 2)))
        for i in self.uniqueLinks:
            self.availableLinks.append(i)
        tmp = len(self.uniqueLinks)
        for i in range(tmp // (numberofpeople // 2)):
            self.board.append(list())
            self.failed.append(list())
        for i in range(len(self.board)):
            for j in range(numberofpeople//2):
                self.board[i].append(None)
                self.failed[i].append(list())

    #checks if the candidate is valid in current position
    def isValid(self, candidate):
        factor1, factor2 = self.getFactor(candidate)
        for i in self.board[self.x]:
            if not i:
                return True
            if ((i % factor1) == 0) or ((i % factor2) == 0):
                return False
        return True

    #moves to the next non-None value, return True if successful
    def nextpos(self):
        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                if not self.board[i][j]:
                    self.x = i
                    self.y = j
                    return True
        return False

    #sets the last non-None value to None and adds that value to availableLinks and the failed tracker
    def prevpos(self):
        for i in range(len(self.board)-1, -1, -1):
            for j in range(len(self.board[0])-1, -1, -1):
                if self.board[i][j]:
                    self.x = i
                    self.y = j
                    tmp = self.board[self.x][self.y]
                    self.availableLinks.append(tmp)
                    self.board[i][j] = None
                    self.failed[i][j].append(tmp)
                    self.fill -= 1
                    random.shuffle(self.availableLinks)
                    return True


    #returns the prime factors of num
    def getFactor(self, num):
        for i in self.primeList:
            if num % i == 0:
                return i, num/i


    #recursive backtracking solving algorithm
    def solve(self):
        print('%d links placed, %d remaining, pos is %d, %d' % (self.fill, len(self.availableLinks), self.x, self.y))
        if not self.nextpos():
            return True
        for i in self.availableLinks:
            if self.isValid(i): and self.checkFail(i):
                self.fill += 1
                self.board[self.x][self.y] = i
                self.availableLinks.remove(i)
                if self.solve():
                    return True
                else:
                    self.prevpos()
        return False

    #replaces prime products with formatted names of people in the board
    def decompose(self):
        for i in range(len(self.board)):
            for j in range(len(self.board[0])):
                num1, num2 = self.getFactor(self.board[i][j])
                for k in self.personList:
                    if k == num1:
                        person1 = str(k)
                    if k == num2:
                        person2 = str(k)
                self.board[i][j] = person1 + '<-->' + person2


    # checks if num has already been tried at current pos, returns false if is has.
    def checkFail(self, num):
        if num in self.failed[self.x][self.y]:
            return False
        else:
            return True

    # verifies that the board has no duplicate values
    def verify(self):
        visited = []
        for i in self.board:
            for j in i:
                if j in visited:
                    print('Verification failed %s occurs twice'% j)
                    return False
                visited.append(j)
        print('Successfully verified')
        return True


s =Schedule(50)
s.solve()
s.verify()
s.decompose()
print(s.board)