table {
        width: 236px;
    }

    table, tr, td {
        border: 0px;
    }

In a grid of 4 by 4 squares you want to place a skyscraper in each square with only some clues:

The height of the skyscrapers is between 1 and 4
No two skyscrapers in a row or column may have the same number of floors
A clue is the number of skyscrapers that you can see in a row or column from the outside
Higher skyscrapers block the view of lower skyscrapers located behind them


Can you write a program that can solve this puzzle?


Example:


To understand how the puzzle works, this is an example of a row with 2 clues. Seen from the left side there are 4 buildings visible while seen from the right side only 1:




 4
    
    
    
    
 1



There is only one way in which the skyscrapers can be placed. From left-to-right all four buildings must be visible and no building may hide behind another building:




 4
 1
 2
 3
 4
 1



Example of a 4 by 4 puzzle with the solution:




  
    
    
 1
 2
  


  
  
  
  
  
  


  
  
  
  
  
 2


 1
  
  
  
  
  


  
  
  
  
  
  


  
  
  
 3
  
  





  
  
  
 1
 2
  


  
 2
 1
 4
 3
  


  
 3
 4
 1
 2
 2


 1
 4
 2
 3
 1
  


  
 1
 3
 2
 4
  


  
  
  
 3
  
  



Task:



Finish:

Source: codewars | Difficulty: MEDIUM_HARD
Tags: Ad-hoc

Starter code: def solve_puzzle (clues):
	

Solutions:
from itertools import permutations, chain

def solve_puzzle(clues):
	size = 4
	for poss in permutations(permutations(list(range(1, size + 1)), size), size):
		for i in range(size):
			if len(set((row[i] for row in poss))) < size:
				break
		else:
			cols_top = [[row[i] for row in poss] for i in range(size)]
			rows_right = [list(reversed(row)) for row in poss]
			cols_btm = [[row[i] for row in reversed(poss)] for i in reversed(list(range(size)))]
			rows_left = list(reversed(poss))
			for (i, row) in enumerate(chain(cols_top, rows_right, cols_btm, rows_left)):
				if not clues[i]:
					continue
				visible = 0
				for (j, v) in enumerate(row):
					visible += v >= max(row[:j + 1])
				if visible != clues[i]:
					break
			else:
				return poss


from itertools import chain, product

def unique_products(sets, excluding=frozenset()):
	if not sets:
		yield ()
		return
	for x in sets[0] - excluding:
		for rest in unique_products(sets[1:], excluding | {x}):
			yield ((x,) + rest)

def solve_column(column, clue):
	combos = [set(x) for x in list(zip(*[x for x in unique_products(column) if see(x) == clue]))]
	for i in range(len(column)):
		column[i] -= column[i] - combos[i]

def see(column):
	visible = tallest = 0
	for building in column:
		visible += building > tallest
		tallest = max(building, tallest)
	return visible

def simplify(column, clue, n):
	if clue is 1:
		column[0] -= set(range(1, n))
	elif clue > 0:
		for i in range(clue - 1):
			column[i] -= set(range(n, n + i + 1 - clue, -1))
		solve_column(column, clue)

def solve_cross(city, x, y):
	if len(city[x][y]) is not 1:
		solve_uniqueness(city, x, y)
		return
	for i in chain(range(x), range(x + 1, len(city))):
		city[i][y] -= city[x][y]
	for j in chain(range(y), range(y + 1, len(city))):
		city[x][j] -= city[x][y]

def solve_uniqueness(city, x, y):
	for n in city[x][y]:
		if not any([n in city[i][y] for i in chain(range(x), range(x + 1, len(city)))]) or not any([n in city[x][j] for j in chain(range(y), range(y + 1, len(city)))]):
			city[x][y].clear()
			city[x][y].add(n)
			solve_cross(city, x, y)
			break

def solve(n, clues):
	city = list((list((set(range(1, n + 1)) for i in range(n))) for j in range(n)))
	while not all([len(cell) is 1 for row in city for cell in row]):
		for i in range(n):
			for j in range(n):
				simplify([city[k][j] for k in range(n)], clues[i * n + j], n)
			for s in range(n):
				for t in range(n):
					solve_cross(city, s, t)
			city = [list(row) for row in reversed(list(zip(*city)))]
	return tuple((tuple((cell.pop() for cell in row)) for row in city))
solve_puzzle = lambda x: solve(4, x)


import numpy as np

def duped(l):
	for e in l:
		if l.count(e) > 1:
			return True
	return False

def find_empty(city):
	for r in range(4):
		for c in range(4):
			if city[r][c] == 0:
				return (r, c)

def check_clue(clue, counter):
	if clue == 0:
		return True
	return counter == clue

def vis(arr, clues):
	l = len(arr)
	a1 = 0
	a2 = 0
	counter1 = 0
	counter2 = 0
	for k in range(l):
		if arr[k] > a1:
			a1 = arr[k]
			counter1 += 1
		if arr[l - k - 1] > a2:
			a2 = arr[l - k - 1]
			counter2 += 1
	if l < 4:
		return True
	return check_clue(clues[0], counter1) and check_clue(clues[1], counter2)

def is_valid(r, c, city, clues):
	row = [h for h in city[r] if h != 0]
	col = [r[c] for r in city if r[c] != 0]
	if duped(row) or duped(col):
		return False
	(tc, rc, bc, lc) = [clues[k][c] if k % 2 == 0 else clues[k][r] for k in range(4)]
	return vis(row, (lc, rc)) and vis(col, (tc, bc))

def solve(city, clues):
	pos = find_empty(city)
	if not pos:
		return True
	(r, c) = pos
	for n in range(1, 5):
		city[r][c] = n
		if is_valid(r, c, city, clues):
			if solve(city, clues):
				return True
		city[r][c] = 0
	return False

def solve_puzzle(clues):
	clues = [list(clues[k:k + 4]) if k < 5 else list(reversed(clues[k:k + 4])) for k in range(0, 13, 4)]
	city = [[0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0], [0, 0, 0, 0]]
	solve(city, clues)
	return tuple([tuple(a) for a in city])


from itertools import permutations, chain
from math import factorial

def num_visible(row):
	visible = 0
	max_height = 0
	for i in row:
		if i > max_height:
			visible = visible + 1
			max_height = i
	return visible

def check_solution(solution, clues):
	solution = list(solution)
	solution = list(chain.from_iterable(solution))
	front_facing_key = {0: [0, 4, 8, 12], 1: [1, 5, 9, 13], 2: [2, 6, 10, 14], 3: [3, 7, 11, 15], 4: [3, 2, 1, 0], 5: [7, 6, 5, 4], 6: [11, 10, 9, 8], 7: [15, 14, 13, 12], 8: [15, 11, 7, 3], 9: [14, 10, 6, 2], 10: [13, 9, 5, 1], 11: [12, 8, 4, 0], 12: [12, 13, 14, 15], 13: [8, 9, 10, 11], 14: [4, 5, 6, 7], 15: [0, 1, 2, 3]}
	front_facing_values = {0: [0, 0, 0, 0], 1: [0, 0, 0, 0], 2: [0, 0, 0, 0], 3: [0, 0, 0, 0], 4: [0, 0, 0, 0], 5: [0, 0, 0, 0], 6: [0, 0, 0, 0], 7: [0, 0, 0, 0], 8: [0, 0, 0, 0], 9: [0, 0, 0, 0], 10: [0, 0, 0, 0], 11: [0, 0, 0, 0], 12: [0, 0, 0, 0], 13: [0, 0, 0, 0], 14: [0, 0, 0, 0], 15: [0, 0, 0, 0]}
	f_len = len(front_facing_values)
	for i in range(f_len):
		for j in range(4):
			front_facing_values[i][j] = solution[front_facing_key[i][j]]
	for i in range(f_len):
		if num_visible(front_facing_values[i]) != clues[i] and clues[i] != 0:
			return False
	return True

def solve_puzzle(clues):
	counter = 1
	for i in list(permutations([1, 2, 3, 4])):
		for j in list(permutations([1, 2, 3, 4])):
			for k in list(permutations([1, 2, 3, 4])):
				for l in list(permutations([1, 2, 3, 4])):
					solution = (i, j, k, l)
					trip = False
					for m in range(4):
						test = [i[m], j[m], k[m], l[m]]
						if len(set(test)) != 4:
							trip = True
					if trip == False:
						if check_solution(solution, clues):
							return solution
	return 'No Solution'


N = 4

def count(lst):
	l = 0
	c = 0
	for v in lst:
		if v > l:
			l = v
			c += 1
	return c

def check_clues(clues, curr_soln):
	visible = []
	for j in range(N):
		c = count([curr_soln[i][j] for i in range(N)])
		visible.append(c)
	for i in range(N):
		c = count([curr_soln[i][j] for j in range(N - 1, -1, -1)])
		visible.append(c)
	for j in range(N - 1, -1, -1):
		c = count([curr_soln[i][j] for i in range(N - 1, -1, -1)])
		visible.append(c)
	for i in range(N - 1, -1, -1):
		c = count([curr_soln[i][j] for j in range(N)])
		visible.append(c)
	for (viz, clue) in zip(visible, clues):
		if clue != 0:
			if viz != clue:
				return False
	return True

def r_solve_puzzle(clues, curr_soln, col_avail, row_avail, i, j):
	if i == N:
		if check_clues(clues, curr_soln):
			return tuple((tuple(row) for row in curr_soln))
		else:
			return None
	ni = i + 1 if j == N - 1 else i
	nj = 0 if j == N - 1 else j + 1
	for v in range(1, N + 1):
		if v in col_avail[j] and v in row_avail[i]:
			col_avail[j].remove(v)
			row_avail[i].remove(v)
			curr_soln[i][j] = v
			res = r_solve_puzzle(clues, curr_soln, col_avail, row_avail, ni, nj)
			curr_soln[i][j] = 0
			col_avail[j].add(v)
			row_avail[i].add(v)
			if res is not None:
				return res

def solve_puzzle(clues):
	curr_soln = [[0 for j in range(N)] for i in range(N)]
	col_avail = [set(range(1, N + 1)) for i in range(N)]
	row_avail = [set(range(1, N + 1)) for i in range(N)]
	return r_solve_puzzle(clues, curr_soln, col_avail, row_avail, 0, 0)


import numpy as np

def solve_puzzle(clues):
	nonlocal grid
	grid = np.array([('1234', '1234', '1234', '1234'), ('1234', '1234', '1234', '1234'), ('1234', '1234', '1234', '1234'), ('1234', '1234', '1234', '1234')])
	nonlocal gridComplete
	gridComplete = np.array([(0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0), (0, 0, 0, 0)])
	nonlocal cluesN
	cluesN = list(map(str, clues))
	clues = list(map(str, clues))
	nonlocal hor
	nonlocal vert
	hor = [clues[0] + clues[11], clues[1] + clues[10], clues[2] + clues[9], clues[3] + clues[8]]
	vert = [clues[15] + clues[4], clues[14] + clues[5], clues[13] + clues[6], clues[12] + clues[7]]
	for z in range(len(cluesN)):
		if cluesN[z] == '4' and z <= 3:
			placeNum(1, 0, z, check=False)
			placeNum(2, 1, z, check=False)
			placeNum(3, 2, z, check=False)
			placeNum(4, 3, z, check=False)
		elif cluesN[z] == '4' and 4 <= z <= 7:
			placeNum(1, z - 4, 3, check=False)
			placeNum(2, z - 4, 2, check=False)
			placeNum(3, z - 4, 1, check=False)
			placeNum(4, z - 4, 0, check=False)
		elif cluesN[z] == '4' and 8 <= z <= 11:
			placeNum(1, 3, 11 - z, check=False)
			placeNum(2, 2, 11 - z, check=False)
			placeNum(3, 1, 11 - z, check=False)
			placeNum(4, 0, 11 - z, check=False)
		elif cluesN[z] == '4' and 12 <= z <= 15:
			placeNum(1, 15 - z, 0, check=False)
			placeNum(2, 15 - z, 1, check=False)
			placeNum(3, 15 - z, 2, check=False)
			placeNum(4, 15 - z, 3, check=False)
		if cluesN[z] == '1' and z <= 3:
			placeNum(4, 0, z, check=False)
		elif cluesN[z] == '1' and 4 <= z <= 7:
			placeNum(4, z - 4, 3, check=False)
		elif cluesN[z] == '1' and 8 <= z <= 11:
			placeNum(4, 3, 11 - z, check=False)
		elif cluesN[z] == '1' and 12 <= z <= 15:
			placeNum(4, 15 - z, 0, check=False)
	removeM1(2, 1, 3)
	removeM1(2, 0, 4)
	removeM1(3, 0, 3)
	lookforsingle()
	double2()
	lookforspace2()
	lookforspace2REV()
	grid = grid.astype(np.integer)
	return tuple(map(tuple, grid))

def lookforspace2():
	first = True
	first2 = True
	for y in range(4):
		view = vert[y][0]
		view1 = hor[y][0]
		lstOption1 = np.copy(grid[y])
		lstOption2 = np.copy(grid[y])
		lstVertOption1 = np.copy(grid[:, y])
		lstVertOption2 = np.copy(grid[:, y])
		for x in range(4):
			if len(str(lstOption1[x])) == 2:
				if first == True:
					optionPair = str(lstOption1[x])
					lstOption2[x] = str(lstOption2[x]).replace(str(optionPair[0]), '')
					lstOption1[x] = str(lstOption1[x]).replace(str(optionPair[1]), '')
					first = False
				elif first == False:
					lstOption1[x] = str(lstOption1[x]).replace(optionPair[0], '')
					lstOption2[x] = str(lstOption2[x]).replace(optionPair[1], '')
					first = True
			if len(str(lstVertOption1[x])) == 2:
				if first2 == True:
					optionPair2 = str(lstVertOption1[x])
					lstVertOption2[x] = str(lstVertOption2[x]).replace(str(optionPair2[0]), '')
					lstVertOption1[x] = str(lstVertOption1[x]).replace(str(optionPair2[1]), '')
					first2 = False
				elif first2 == False:
					lstVertOption1[x] = str(lstVertOption1[x]).replace(optionPair2[0], '')
					lstVertOption2[x] = str(lstVertOption2[x]).replace(optionPair2[1], '')
					first2 = True
		calc1 = viewCalc(lstOption1.tolist())
		calc2 = viewCalc(lstOption2.tolist())
		calc3 = viewCalc(lstVertOption1.tolist())
		calc4 = viewCalc(lstVertOption2.tolist())
		if int(calc3) == int(view1) and int(calc3) != int(calc4):
			grid[:, y] = lstVertOption1
		elif int(calc4) == int(view1) and int(calc3) != int(calc4):
			grid[:, y] = lstVertOption2
		if int(calc1) == int(view) and int(calc1) != int(calc2):
			grid[y] = lstOption1
		elif int(calc2) == int(view) and int(calc1) != int(calc2):
			grid[y] = lstOption2
	lookforsingle()

def lookforspace2REV():
	first = True
	first2 = True
	for y in range(4):
		view = vert[y][1]
		view1 = hor[y][1]
		lstOption1 = np.copy(grid[y])[::-1]
		lstOption2 = np.copy(grid[y])[::-1]
		lstVertOption1 = np.copy(grid[:, y])[::-1]
		lstVertOption2 = np.copy(grid[:, y])[::-1]
		for x in range(4):
			if len(str(lstOption1[x])) == 2:
				if first == True:
					optionPair = str(lstOption1[x])
					lstOption2[x] = str(lstOption2[x]).replace(str(optionPair[0]), '')
					lstOption1[x] = str(lstOption1[x]).replace(str(optionPair[1]), '')
					first = False
				elif first == False:
					lstOption1[x] = str(lstOption1[x]).replace(optionPair[0], '')
					lstOption2[x] = str(lstOption2[x]).replace(optionPair[1], '')
					first = True
			if len(str(lstVertOption1[x])) == 2:
				if first2 == True:
					optionPair2 = str(lstVertOption1[x])
					lstVertOption2[x] = str(lstVertOption2[x]).replace(str(optionPair2[0]), '')
					lstVertOption1[x] = str(lstVertOption1[x]).replace(str(optionPair2[1]), '')
					first2 = False
				elif first2 == False:
					lstVertOption1[x] = str(lstVertOption1[x]).replace(optionPair2[0], '')
					lstVertOption2[x] = str(lstVertOption2[x]).replace(optionPair2[1], '')
					first2 = True
		calc1 = viewCalc(lstOption1.tolist())
		calc2 = viewCalc(lstOption2.tolist())
		calc3 = viewCalc(lstVertOption1.tolist())
		calc4 = viewCalc(lstVertOption2.tolist())
		if int(calc3) == int(view1) and int(calc3) != int(calc4):
			grid[:, y] = lstVertOption1[::-1]
		elif int(calc4) == int(view1) and int(calc3) != int(calc4):
			grid[:, y] = lstVertOption2[::-1]
		if int(calc1) == int(view) and int(calc1) != int(calc2):
			grid[y] = lstOption1[::-1]
		elif int(calc2) == int(view) and int(calc1) != int(calc2):
			grid[y] = lstOption2[::-1]
	lookforsingle()

def removeM1(viewpos, coord, removeNum):
	lstCord = []
	for z in range(len(cluesN)):
		if cluesN[z] == str(viewpos):
			if z <= 3:
				lstCord = [coord, z]
			if 4 <= z <= 7:
				lstCord = [z - 4, 3 - coord]
			if 8 <= z <= 11:
				lstCord = [3 - coord, 11 - z]
			if 12 <= z <= 15:
				lstCord = [15 - z, coord]
			grid[lstCord[0]][lstCord[1]] = str(grid[lstCord[0]][lstCord[1]]).replace(str(removeNum), '')

def double2():
	dbl = False
	for y in range(4):
		for x in range(4):
			lst = gridComplete.sum(axis=1)
			if len(grid[y][x]) == 2:
				for x2 in range(x + 1, 4):
					if grid[y][x] == grid[y][x2]:
						for g in range(4):
							try:
								if len(str(grid[y][g])) > 1 and str(grid[y][g]) != grid[y][x2]:
									grid[y][x2] = str(grid[y][x2]).replace(str(grid[y][x])[0], '')
									dbl = True
							except:
								pass
							try:
								if len(str(grid[y][g])) > 1 and str(grid[y][g]) != grid[y][x2]:
									grid[y][x2] = str(grid[y][x2]).replace(str(grid[y][x])[1], '')
									dbl = True
							except:
								pass
	if dbl == True:
		lookforsingle()
		double2()

def lookforsingle():
	count = 0
	pos = []
	placed = False
	posC = np.array([(0, 0), (0, 0), (0, 0), (0, 0)])
	countC = [0, 0, 0, 0]
	for p in range(1, 5):
		for a in range(4):
			if placed == False:
				for o in range(4):
					if str(p) in str(grid[a][o]) and len(str(grid[a][o])) > 1 and (gridComplete[a][o] == 0):
						count += 1
						countC[a] = countC[a] + 1
						posC[a] = [a, o]
						pos = [a, o]
					elif len(str(grid[a][o])) == 1 and gridComplete[a][o] == 0:
						placeNum(str(grid[a][o]), a, o, check=False)
						placed = True
						break
				if count == 1 and placed == False:
					placeNum(p, pos[0], pos[1], check=False)
					placed = True
					break
				count == 0
		for u in range(4):
			if placed == True:
				break
			if countC[u] == 1:
				placeNum(p, posC[u][0], posC[u][1], check=False)
				placed = True
		countC = [0, 0, 0, 0]
	if placed == True:
		lookforsingle()

def viewCalc(lstCalc):
	prev = 0
	count = 0
	for i in range(4):
		if int(lstCalc[i]) > prev:
			count += 1
			prev = int(lstCalc[i])
	return count

def placeNum(num, ypos, xpos, check=True):
	for y in range(4):
		try:
			if len(str(grid[ypos][y])) > 1:
				grid[ypos][y] = str(grid[ypos][y]).replace(str(num), '')
		except:
			pass
		try:
			if len(str(grid[y][xpos])) > 1:
				grid[y][xpos] = str(grid[y][xpos]).replace(str(num), '')
		except:
			pass
	grid[ypos][xpos] = num
	gridComplete[ypos][xpos] = 1
	if check == True:
		lookforsingle()