7x7 Skyscrapers Solver

Below is an example of a reasonably optimized JavaScript backtracking solver for the 7×7 Skyscrapers puzzle. The core ideas behind making it run in time are:

1. Precompute all permutations of the numbers 1..7.
2. For each permutation, precompute how many skyscrapers are visible from the left and from the right.
3. For each row and column, filter out only those permutations that match the given clues on that row/column (if a clue is given, i.e. nonzero).
4. During backtracking:
   • Assign a valid permutation to row r only among those that satisfy that row’s left/right clues.
   • Make sure you do not repeat a number in a column (the usual Sudoku-like constraint).
   • Heavily prune by checking partial column prefixes against the permutations allowed for that column. If at any point a partial column cannot match any valid column permutation, prune immediately rather than waiting to fill all rows.

This approach is a lot faster than naive backtracking, because it cuts out enormous portions of the search space up front.

---

Explanation of the Steps

1. Generate all permutations of [1..7]

There are $7! = 5040$ permutations of the numbers 1 through 7. We can generate them once and reuse them.

2. Visibility counts

For each permutation, we calculate:

• visibleFromLeft(perm): how many skyscrapers can be "seen" from the left edge.
• visibleFromRight(perm): how many skyscrapers can be "seen" from the right edge.

A skyscraper is "visible" when it is taller than all skyscrapers in front of it (from that viewpoint). For example, in a row [2, 1, 4, 3, 5, 7, 6]:

• From the left:
  • 2 is seen first,
  • 1 is smaller than 2, so it’s hidden,
  • 4 is taller than 2, so it's seen,
  • 3 is smaller than 4, hidden,
  • 5 is taller than 4, so it's seen,
  • 7 is taller than 5, seen,
  • 6 is smaller than 7, hidden.
    So we see 2,4,5,7, which is 4 skyscrapers.
• From the right we do the same but reversed order.

3. Matching row and column permutations

• For each of the 7 rows, if the clue from the left is nonzero, we keep only permutations whose visibleFromLeft matches that clue. Same for the right clue.
• For each of the 7 columns, if the top clue is nonzero, we keep only permutations whose visibleFromLeft (when read top-down) matches that clue. Same for the bottom clue.

This gives us:

• rowPerms[r]: a list of all permutations valid for row $r$ given its left/right clues.
• colPerms[c]: a list of all permutations valid for column $c$ given its top/bottom clues.

4. Backtracking with prefix-pruning

We place rows one by one:

• Pick a permutation p from rowPerms[r].
• Check that for each column $c$, the value p[c] is not already used in previous rows (no duplication in the column).
• Additionally, check if the partial column $[grid[0][c], grid[1][c], ..., p[c]]$ can still match a prefix of at least one permutation in colPerms[c]. If it cannot, prune immediately.

If all checks pass, accept p for row $r$ and move on to row $r+1$. If we fill all 7 rows successfully, we have a candidate grid. Finally, we can do a final consistency check on columns (though if we've pruned thoroughly, it should already match).

---

JavaScript Example

js
function solvePuzzle(clues) {
  // Clue order on Codewars (same as the smaller 4x4, 6x6 puzzles):
  //
  //  clues[0..6]     => top clues for columns 0..6 (looking downward)
  //  clues[7..13]    => right clues for rows 0..6 (looking leftward)
  //  clues[14..20]   => bottom clues for columns 0..6 (looking upward)
  //  clues[21..27]   => left clues for rows 0..6 (looking rightward)
  //
  // Each clue is 0 if not specified.

  const N = 7;
  
  // Extract the clues for each row/column for easier reference
  const topClues    = clues.slice(0, N);       // columns top->down
  const rightClues  = clues.slice(N, 2*N);     // rows right->left
  const bottomClues = clues.slice(2*N, 3*N);   // columns bottom->up
  const leftClues   = clues.slice(3*N, 4*N);   // rows left->right
  
  // 1) Generate all permutations of [1..7].
  const allPerms = generatePermutations(N);
  
  // 2) Precompute visibility from left and right for each permutation
  //    We'll store them in an object for quick access.
  const permInfo = allPerms.map(perm => ({
    perm,
    left:   countVisibleFromLeft(perm),
    right: countVisibleFromLeft(perm.slice().reverse())
  }));
  
  // 3) Build possible row permutations (rowPerms[r]) 
  //    that match row's left clue and right clue (if nonzero).
  const rowPerms = [];
  for (let r = 0; r < N; r++) {
    const leftReq  = leftClues[r];
    const rightReq = rightClues[r];
    rowPerms[r] = permInfo
      .filter(info => {
        if (leftReq !== 0 && info.left !== leftReq)   return false;
        if (rightReq !== 0 && info.right !== rightReq) return false;
        return true;
      })
      .map(info => info.perm);
  }

  // 4) Build possible column permutations (colPerms[c])
  //    that match top clue and bottom clue (if nonzero).
  //    We'll also store prefix sets to quickly check feasibility.
  const colPerms = [];
  for (let c = 0; c < N; c++) {
    const topReq    = topClues[c];
    const bottomReq = bottomClues[c];
    
    colPerms[c] = permInfo
      .filter(info => {
        // For columns, reading top -> down is the "left" viewpoint
        // and reading bottom -> up is the "right" viewpoint.
        if (topReq !== 0 && info.left !== topReq)      return false;
        if (bottomReq !== 0 && info.right !== bottomReq) return false;
        return true;
      })
      .map(info => info.perm);
  }

  // 4b) Build a quick "prefix set" for each column c.
  //     prefixSet[c][rowCount] is a Map from a string of rowCount values -> boolean,
  //     telling us if that prefix can appear in at least one of the colPerms[c].
  const prefixSet = colPerms.map(colList => buildColumnPrefixSets(colList));

  // Prepare the result grid
  const solution = Array.from({length: N}, () => Array(N).fill(0));

  // Backtracking function
  function backtrack(row) {
    // If we've assigned all rows, we're done
    if (row === N) {
      return true;
    }
    
    // Try each candidate permutation for this row
    for (const perm of rowPerms[row]) {
      // Check column conflicts & prefix feasibility
      let valid = true;
      for (let c = 0; c < N; c++) {
        const val = perm[c];
        
        // Check if val is already used in column c (by previous rows)
        for (let r2 = 0; r2 < row; r2++) {
          if (solution[r2][c] === val) {
            valid = false;
            break;
          }
        }
        if (!valid) break;
        
        // Check prefix feasibility:
        // the partial column is [solution[0][c], ..., solution[row-1][c], val]
        const prefixArray = [];
        for (let r2 = 0; r2 < row; r2++) {
          prefixArray.push(solution[r2][c]);
        }
        prefixArray.push(val);
        
        const prefixKey = prefixArray.join(',');
        // If no column permutation can have this prefix, prune
        if (!prefixSet[c][row+1].has(prefixKey)) {
          valid = false;
          break;
        }
      }
      
      if (!valid) {
        continue;
      }

      // If we get here, perm is valid for row "row"
      solution[row] = perm;
      
      // Recurse
      if (backtrack(row + 1)) {
        return true;
      }
      // Otherwise backtrack
    }
    
    return false;
  }

  // Run the backtracking
  backtrack(0);

  return solution;
}


/**
 * Generate all permutations of [1..n].
 */
function generatePermutations(n) {
  const result = [];
  const nums = Array.from({length: n}, (_, i) => i+1);
  
  function permute(arr, start) {
    if (start === arr.length) {
      result.push(arr.slice());
      return;
    }
    for (let i = start; i < arr.length; i++) {
      [arr[start], arr[i]] = [arr[i], arr[start]];
      permute(arr, start+1);
      [arr[start], arr[i]] = [arr[i], arr[start]];
    }
  }
  
  permute(nums, 0);
  return result;
}

/**
 * Returns how many buildings are visible from the left side of a permutation.
 */
function countVisibleFromLeft(perm) {
  let visible = 0;
  let maxSoFar = 0;
  for (let i = 0; i < perm.length; i++) {
    if (perm[i] > maxSoFar) {
      visible++;
      maxSoFar = perm[i];
    }
  }
  return visible;
}

/**
 * Build a set of valid prefixes for a column, up to length N,
 * given the list of valid permutations for that column.
 *
 * prefixSet[c][k] = a Set of strings that represent the first k elements
 * of some permutation in colPerms[c].
 *
 * E.g., if k=3 and a valid column permutation is [2, 5, 7, 1, 6, 4, 3],
 * then the prefix [2,5,7] => "2,5,7" will be in the set.
 */
function buildColumnPrefixSets(colList) {
  const n = colList[0].length; // 7
  // prefixSets[k] = Set of prefix of length k as a string
  const prefixSets = Array.from({ length: n+1 }, () => new Set());
  // The empty prefix of length 0 is always valid
  prefixSets[0].add('');

  for (const colPerm of colList) {
    // Build cumulative prefix strings
    let prefix = [];
    for (let k = 1; k <= n; k++) {
      prefix.push(colPerm[k-1]);
      prefixSets[k].add(prefix.join(','));
    }
  }

  return prefixSets;
}

How It Works

1. Permutation Generation
   generatePermutations(7) produces all 7! permutations of [1,2,3,4,5,6,7].

2. Visibility Precomputation
   For each permutation, we store its left and right visibility counts to compare against clues quickly.

3. Row/Column Clues Filtering

   • rowPerms[r] keeps only the permutations that satisfy the row $r$'s leftClue and rightClue (if given).
   • colPerms[c] keeps only the permutations that satisfy the column $c$'s topClue and bottomClue.

4. Prefix Feasibility Sets
   For each column $c$, we build prefixSet[c], a structure that lets us quickly check whether a partial column $[x_0, x_1, ..., x_k]$ can be the beginning of some valid column permutation in colPerms[c]. This is stored as a set of comma-joined strings representing each possible prefix.

5. Backtracking
   We assign row 0, row 1, ... row 6 in turn. For each candidate permutation of row $r$:

   • We check for no duplication within each column so far.
   • We convert the partial columns to a string (e.g., "2,5" for the first two rows in a column) and see if it's in prefixSet[c][r+1]. If not, we prune immediately.
   • If all columns are okay, recurse to the next row.
     This drastically cuts down the branching factor, because invalid partial columns are immediately discarded rather than waiting until the very end.

6. Solution Returned
   Once all 7 rows are assigned consistently, we have our solution grid, which is then returned.

---

Usage

Given an input array clues of length 28, call:

js
const solvedGrid = solvePuzzle(clues);
console.log(solvedGrid);

solvedGrid will be a 7×7 array of numbers 1..7 satisfying all Skyscraper conditions.

This approach, with prefix pruning and precomputation of valid permutations per row and per column, is usually fast enough to solve typical 7×7 puzzles within a few seconds (or less) in JavaScript.