Skyscraper puzzle algorithm

Question

I'm writing an algorithm to solve skyscrapers puzzles:

Skyscraper puzzles combine the row and column constraints of Sudoku with external clue values that re-imagine each row or column of numbers as a road full of skyscrapers of varying height. Higher numbers represent higher buildings.

To solve a Skyscraper puzzle you must place 1 to 5, or 1 to whatever the size of the puzzle is, once each into every row and column, while also solving each of the given skyscraper clues.

To understand Skyscraper puzzles, you must imagine that each value you place into the grid represents a skyscraper of that number of floors. So a 1 is a 1-floor skyscraper, while a 4 is a 4-floor skyscraper. Now imagine that you go and stand outside the grid where one of the clue numbers is and look back into the grid. That clue number tells you how many skyscrapers you can see from that point, looking only along the row or column where the clue is, and from the point of view of the clue. Taller buildings always obscure lower buildings, so in other words higher numbers always conceal lower numbers.

All the basic techniques are implemented and working, but I've realized that with bigger puzzles (5x5>) I need some sort of recursive algorithm. I found a decent working python script, but I'm not really following what it actually does beyond solving basic clues.

Does anyone know the proper way of solving these puzzles or can anyone reveal the essentials in the code above?

Answer 1

Here's a working solution using constraint satisfaction strategy for n=4. It can be trivially modified for any size of the puzzle by changing the value of n.

The solution is somewhat more involved than the Sudoku solution referred to in the accepted answer, because of two reasons:

1. The Sudoku board comes prefilled with some digits, and the empty squares can be thought of having the possibilities 1..9 to begin with, but in this problem, we have to generate the board based on the clues.

2. Once a Sudoku board is filled by appropriately choosing from the possibilities for each square, it is guaranteed to be valid. In this problem, however, completed row and columns have to be further validated with the given clues.

Having generated a board, with a set of possibilities for each square, we run DFS with backtracking.

The code is generously commented, and hopefully needs no further explanation.

import copy
import itertools
import sys
from collections import defaultdict

n = 4
Digit = int
Digits = tuple[Digit, ...]
CluePair = tuple[Digit, Digit]
Clues = tuple[CluePair, ...]
Square = tuple[Digit, Digit]
Squares = list[Square]
Grid = dict[Square, set[Digit]]
Soln = tuple[Digits, ...]


def count_visible(nums: Digits) -> Digit:
    """
    :param nums: Heights of skyscrapers from left to right
    :return: The number of skyscrapers visible from the left
    """
    running_max = -sys.maxsize
    count = 0
    for i in nums:
        count += int(i > running_max)
        running_max = max(running_max, i)
    return count


def row(r: Digit) -> Squares:
    """Generates row[r] by varying the columns"""
    return [(r, c) for c in range(n)]


def col(c: Digit) -> Squares:
    """Generates col[c] by varying the rows"""
    return [(r, c) for r in range(n)]


def fill(grid: Grid, s: Square, d: Digit) -> Grid | None:
    """Eliminates all the digits except d from grid[s]"""
    if grid[s] == {d} or all(eliminate(grid, s, d2) for d2 in grid[s] - {d}):
        return grid
    return None


def eliminate(grid: Grid, s: Square, d: Digit) -> Grid | None:
    """Eliminates digit d from grid[s]; implements the two constraint propagation strategies"""
    if d not in grid[s]:  ## Already eliminated
        return grid
    if len(grid[s]) == 1:  ## Only digit left
        print(f"Cannot eliminate the only digit {d} from {s}")
        return None

    grid[s].remove(d)
    units = set(row(s[0]) + col(s[1]))
    peers = units - {s}

    # 1. If a square has only one possible digit, then eliminate
    # that digit as a possibility for each of the square's peers.
    if len(grid[s]) == 1:
        (d2,) = grid[s]
        # Failed to remove d2 from some peer. Backtrack.
        if not all(eliminate(grid, p, d2) for p in peers):
            return None

    dplaces = tuple(u for u in units if d in grid[u])
    # 2. If a unit has only one possible square that can hold a digit,
    # then fill the square with the digit.
    if not dplaces or (len(dplaces) == 1 and not fill(grid, dplaces[0], d)):
        # No place for digit d in the row and col shared by s. Backtrack.
        print(f"No place for {d} in {dplaces}")
        return None

    return grid


def are_clues_satisfied(digits: Digits, clues: CluePair) -> bool:
    """Checks if the given clues are satisfied for the given line"""
    return (clues[0] == 0 or count_visible(digits) == clues[0]) and (
        clues[1] == 0 or count_visible(digits[::-1]) == clues[1]
    )


# Inspired by https://github.com/norvig/pytudes/blob/main/ipynb/Sudoku.ipynb.
def search(grid: Grid, row_clues: Clues, col_clues: Clues) -> Soln | None:
    rows = [
        tuple(next(iter(grid[c])) for c in row(r) if len(grid[c]) == 1)
        for r in range(n)
    ]
    # Check all completed rows satisfy the given clues.
    if not all(
        are_clues_satisfied(r, row_clues[i]) for i, r in enumerate(rows) if len(r) == n
    ):
        return None

    cols = [
        tuple(next(iter(grid[r])) for r in col(c) if len(grid[r]) == 1)
        for c in range(n)
    ]
    # Check all completed columns satisfy the given clues.
    if not all(
        are_clues_satisfied(c, col_clues[i]) for i, c in enumerate(cols) if len(c) == n
    ):
        return None
    # Find the square with the minimum number of possibilities.
    s = min(
        (s for s, xs in grid.items() if len(xs) > 1),
        default=None,
        key=lambda x: len(grid[x]),
    )
    # No squares with multiple possibilities; the search has succeeded.
    if s is None:
        return tuple(tuple(grid[(r, c)].pop() for c in range(n)) for r in range(n))

    for d in grid[s]:
        # Try filling square s with digit d and see if it leads to a solution.
        if (g := fill(copy.deepcopy(grid), s, d)) is not None and (
            soln := search(g, row_clues, col_clues)
        ) is not None:
            return soln
    return None


def solve_puzzle(clues: Digits) -> Soln | None:
    # Create dictionaries keyed by clues to possible arrangement of skyscrapers
    # that satisfy those clues. A clue is the number of skyscrapers visible
    # when viewed from left, right, top or bottom.
    #
    # We will use these dictionaries to constrain the heights of the skyscrapers
    # that may be placed at a grid.
    clue_to_candidates: dict[Digit, set[Digits]] = defaultdict(set)
    rev_clue_to_candidates: dict[Digit, set[Digits]] = defaultdict(set)
    all_candidates = set(itertools.permutations(range(1, n + 1)))
    for c in all_candidates:
        clue_to_candidates[count_visible(c)].add(c)
        x = c[::-1]
        rev_clue_to_candidates[count_visible(x)].add(c)
    clue_to_candidates[0] = all_candidates
    rev_clue_to_candidates[0] = all_candidates

    def candidates(clues: Clues) -> list[list[set[Digit]]]:
        """
        :param clues: Clues at both ends of the row or column
        :return: Heights of the skyscrapers that may be placed at each square
        """
        result: list[list[set[Digit]]] = []
        for clue, rev_clue in clues:
            cs = clue_to_candidates[clue] & rev_clue_to_candidates[rev_clue]
            result.append([set(c) for c in zip(*cs)])
        return result

    m = n * n
    # Clues are given in a clockwise manner around the n x n grid, pair them.
    batched_clues = [
        clues[i : i + n] if i < 2 * n else clues[i + n - 1 : i - 1 : -1]
        for i in range(0, m - n + 1, n)
    ]
    row_clues = tuple(zip(batched_clues[3], batched_clues[1]))
    col_clues = tuple(zip(batched_clues[0], batched_clues[2]))

    # Find the candidates (heights of the skyscrapers that may be placed at each square)
    # row by row.
    row_candidates = {
        (r, c): cs
        for r, cols in enumerate(candidates(row_clues))
        for c, cs in enumerate(cols)
    }

    # Create the grid by intersecting the column-wise candidates with the row-wise candidates.
    grid = {
        (r, c): cs & row_candidates[(r, c)]
        for c, rows in enumerate(candidates(col_clues))
        for r, cs in enumerate(rows)
    }

    return search(grid, row_clues, col_clues)

Answer 2

If you're desperate, you can brute-force the puzzle. I usually do this as a first step to become familiar with the puzzle. Basically, you need to populate NxN squares with integers from 1 to N inclusive, following the following constraints:

• Each integer appears in every row exactly once
• Each integer appears in every column exactly once
• The row "clues" are satisfied
• The column "clues" are satisfied

The brute force solution would work like this. First, represent the board as a 2D array of integers. Then write a function is_valid_solution that returns True if the board satisfies the above constraints, and False otherwise. This part is relatively easy to do in O(N^2).

Finally, iterate over the possible board permutations, and call is_valid_solution for each permutation. When that returns True, you've found a solution. There are a total of N^(NxN) possible arrangements, so your complete solution will be O(N^(NxN)). You can do better by using the above constraints for reducing the search space.

The above method will take a relatively long while to run (O(N^(NxN)) is pretty horrible for an algorithm), but you'll (eventually) get a solution. When you've got that working, try to think of a better way to to it; if you get stuck, then come back here.

EDIT

A slightly better alternative to the above would be to perform a search (e.g. depth-first) starting with an empty board. At each iteration of the search, you'd populate one cell of the table with a number (while not violating any of the constraints). Once you happen to fill up the board, you're done.

Here's pseudo-code for a recursive brute-force depth-first search. The search will be NxN nodes deep, and the branching factor at each node is at most N. This means you will need to examine at most 1 + N + N^2 + ... + N^(N-1) or (N^N-1)/(N-1) nodes. For each of these nodes, you need to call is_valid_board which is O(N^2) in the worst case (when the board is full).

def fill_square(board, row, column):
  if row == column == N-1: # the board is full, we're done
    print board
    return
  next_row, next_col = calculate_next_position(row, col)
  for value in range(1, N+1):
    next_board = copy.deepcopy(board)
    next_board[row][col] = value
    if is_valid_board(next_board):
      fill_square(next_board, next_row, next_col)

board = initialize_board()
fill_square(board, 0, 0)

The function calculate_next_position selects the next square to fill. The easiest way to do this is just a scanline traversal of the board. A smarter way would be to fill rows and columns alternately.

Answer 3

Misha showed you the brute-force way. A much faster recursive algorithm can be made based on constraint propagation. Peter Norvig (head of Google Research) wrote an excellent article about how to use this technique to solve Sudoku with python. Read it and try to understand every detail, you will learn a lot, guaranteed. Since the skyscraper puzzle has a lot in common with Sudoku (without the 3X3 blocks, but with some extra constraints given by the numbers on the edge), you could probably steal a lot of his code.

You start, as with Sudoku, where each field has a list of all the possible numbers from 1..N. After that, you look at one horizontal/vertical line or edge clue at a time and remove illegal options. E.g. in a 5x5 case, an edge of 3 excludes 5 from the first two and 4 from the first squares. The constraint propagation should do the rest. Keep looping over edge constraints until they are fulfilled or you get stuck after cycling through all constraints. As shown by Norvig, you then start guessing and remove numbers in case of a contradiction.

In case of Sudoku, a given clue has to be processed only once, since once you assign a single number to one square (you remove all the other possibilities), all the information of the clue has been used. With the skyscrapers, however, you might have to apply a given clue several times until it is totally satisfied (e.g. when the complete line is solved).