7x7 Skyscrapers Solver

Solving the puzzle

I'm working through a 7x7 Skyscrapers puzzle, ensuring each row has unique values from 1 to 7, and no column duplicates. The goal is to determine the number of skyscrapers visible from the given hints.

Crafting a strategy

I’m precomputing permutations of [1..7], storing their visibility and values. Assigning permutations to rows while ensuring column constraints will be a crucial step, using advanced backtracking with pruning.

Pulling together constraints

I'm analyzing row and column constraints, leveraging constraint propagation or advanced backtracking with strong pruning. The aim is to match permutations effectively while ensuring no duplicates in columns.

Crafting the function

I’m gathering 28 clues in a specific format to solve the 7x7 puzzle. The function will match these clues with permutations, checking for column constraints and visibility.

Laying out the options

I’m listing all 7x7 permutations and assessing their visibility from left and right. Then, I’ll form "possibleRows" with valid permutations, respecting given clues.

Piecing together clues

I'm mapping out how the clues align with specific row and column indices. This allows for the creation of dictionaries storing permutations that meet each left and right clue combination.

Filling in the details

I'm considering a backtracking method to fill the 7x7 grid, ensuring column constraints. Each cell value will be checked against computed permutations and visibility constraints.

Mapping valid permutations

I’m working on validating permutations for each row and column, ensuring they meet visibility clues. This approach involves thorough backtracking to avoid column conflicts.

Piecing together the puzzle

I’m crafting a recursive function for placing rows, ensuring no column conflicts by checking permutations and tracking grid progress. Then, I’ll review column constraints for a valid grid.

Pruning early

I'm exploring methods to streamline column constraints by identifying valid prefixes for each permutation. This approach should simplify the process considerably.

Crafting the solution

I’m finalizing a JavaScript function to solve the Skyscrapers puzzle. It involves generating permutations, calculating visibility clues, and deploying backtracking with prefix pruning.

Mapping the steps

I’m outlining a detailed JavaScript function to solve the Skyscrapers puzzle, ensuring clarity with well-commented code, and incorporating a concise implementation approach.

Refining the approach

I’m considering prefix sets and pruning for efficient backtracking, targeting an optimal solution for the Skyscrapers puzzle. This streamlined method should significantly cut down on complexity.

Thought about skyscraper puzzle solver для 25 секунд

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

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:

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.