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:
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.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]
Cross out possibilities if the value is already in column or row
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
