Optimizing recursive backtrack search algorithm in skyscraper puzzle

Question

I'm trying to solve a skyscraper puzzle for 6x6 boards using constraint programming and then backtracking. My solution works but is too slow for certain cases. It takes up to 2 seconds, and I was wondering how I could reduce this.

Here is the structure of my algorithm:

1. Create board of N size with each element having integers from 1 to 6 denoting all the possibilities ie: [[[1,2,3,4,5,6] , [1,2,3,4,5,6,] , [1,2,3,4,5,6]]], etc.

2. Using the clues given, fill out values which I am certain of. ie: If clue is 1, then closest element is 6 , if clue is 6 then the row is [1,2,3,4,5,6]

3. Cross out possibilities if the value is already in column or row

4. If inside one row (or column) a list of possibilities has a value that none of the other have, then it becomes that number: ie: [[1,2,3,4,5,6] , [1,2,3,4,5] , [1,2,3,4,5]] becomes [ 6 , [1,2,3,4,5] , [1,2,3,4,5]]

Finally, I have my backtracking algorithm, which according to Pycharm, takes 98% of the time of execution:

def search(zero, clues, searchBoard):
 #zeros is a deepcopy of searchboard but with possibilities replaces with 0s ; search board is the board after being processed by first 4 steps
 find = empty(zero) # Checks for zeroes in a duplicate list
 findLeast = full(searchBoard) # Checks for elements that have more than one possibility
 if not find:
 return True
 else:
 row, col = findLeast # Fetches the index of the element with least amount of possibilities
 val = searchBoard[row][col]
 for i in val: # loops through those possibilties
 if is_valid_solution(zero, clues, 6, i, (row, col)):
 zero[row][col] = i # If the possibilitie works, insert it
 searchBoard[row][col] = i
 if search(zero, clues,
 searchBoard): # recursively do this (backtrack) until no more empty elements in the zeroes duplicate list
 return True
 zero[row][col] = 0 # else: reset, try again for different values
 searchBoard[row][col] = val
 return False
def is_valid_solution(board, clues, n, num, pos):
 row = [num if i == pos[1] else board[pos[0]][i] for i in range(6)]
 col = [num if i == pos[0] else board[i][pos[1]] for i in range(6)]
 if row.count(num) > 1:
 return False
 if col.count(num) > 1:
 return False
 clue = clues[pos[1]]
 if clue != 0 and clue not in flatten(col):
 return False
 clue = clues[pos[0] + 6]
 if clue != 0 and clue not in flatten(row[::-1]):
 return False
 clue = clues[::-1][pos[1] + 6]
 if clue != 0 and clue not in flatten(col[::-1]):
 return False
 clue = clues[::-1][pos[0]]
 if clue != 0 and clue not in flatten(row):
 return False
 return True
def verifyDistance(cell):
 visible = 0
 max = 0
 for i in range(len(cell)):
 if cell[i] > max:
 visible += 1
 max = cell[i]
 return visible
def flatten(incompleted_row):
 possible_rows = []
 d = list({1, 2, 3, 4, 5, 6} - set([x for x in incompleted_row if x != 0]))
 for perm in permutations(d):
 row = incompleted_row.copy()
 for e in perm:
 row[row.index(0)] = e
 possible_rows.append(row)
 possible_clues = set()
 for r in possible_rows:
 possible_clues.add(verifyDistance(r))
 return list(possible_clues)
def empty(puzzle):
 if 0 in chain.from_iterable(puzzle):
 return True
 return None
def full(puzzle):
 pos = []
 for i in range(len(puzzle)): # loop through the rows of the puzzle
 try:
 pos.append([(i, puzzle[i].index(min((x for x in puzzle[i] if isinstance(x, list)), key=len))), puzzle[i]])
 # append the tuple (i , j) where i is the row number and j the column number, and the smallest list of possibilities in each row
 except ValueError:
 i += 1
 try:
 champion, champion_len = pos[0][0], len(pos[0][1]) # unpack the pos list into the tuple, and the possibilties
 except IndexError:
 return None
 for t, sl in pos:
 if len(sl) < champion_len:
 champion, champion_len = t, len(sl) # look for the smallest number of possibilities and return their index
 return champion

Answer 1

Documentation

The PEP 8 style guide recommends adding docstrings for functions. For example, you can convert this comment:

def search(zero, clues, searchBoard):
 #zeros is a deepcopy of searchboard but with possibilities replaces with 0s ; search board is the board after being processed by first 4 steps

into a docstring:

def search(zero, clues, searchBoard):
 """
 zeros is a deepcopy of searchboard but with possibilities replaces with 0s
 search board is the board after being processed by first 4 steps
 """

The docstrings should also state the function return type as well as summarize the purpose of the function.

Naming

PEP 8 recommends snake_case for function and variable names.

For example, verifyDistance would be verify_distance

searchBoard would be search_board, etc.

In the verifyDistance function don't use max as a variable name because it is the name of a built-in function. This can be confusing. To eliminate the confusion, rename the variable. The first clue is that "max" has special coloring (syntax highlighting) in the question, as it does when I copy the code into my editor.

Simpler

In the search function, these lines can be simplified:

if not find:
 return True
else:
 row, col = findLeast

There is no need for the else line, and code is more conventionally written as:

if not find:
 return True
row, col = findLeast

In fact, the code can be more efficient with an earlier return from the function:

def search(zero, clues, searchBoard):
 if not empty(zero):
 return True

I removed the comments to emphasize the point. This also eliminates the intermediate variable (find).

The return type of the empty function is a little inconsistent because it can return True or None. It can be more consistent as:

 return True
return False