Beautiful Arrangement and Constraint Satisfaction

def countArrangement(n):
    # Precompute valid numbers for each position
    valid = [[] for _ in range(n + 1)]
    for pos in range(1, n + 1):
        for num in range(1, n + 1):
            if num % pos == 0 or pos % num == 0:
                valid[pos].append(num)

    count = [0]
    used = [False] * (n + 1)

    def bt(pos):
        if pos > n:
            count[0] += 1
            return
        for num in valid[pos]:
            if not used[num]:
                used[num] = True
                bt(pos + 1)
                used[num] = False

    bt(1)
    return count[0]

# Bitmask DP version: O(n * 2^n)
def countArrangementDP(n):
    dp = [0] * (1 << n)
    dp[0] = 1
    for mask in range(1 << n):
        pos = bin(mask).count('1') + 1  # next position
        for num in range(1, n + 1):
            if mask >> (num-1) & 1: continue  # used
            if num % pos == 0 or pos % num == 0:
                dp[mask | (1 << (num-1))] += dp[mask]
    return dp[(1 << n) - 1]

# Zuma Game-style: remove all blocks
def zuma(board):
    from functools import lru_cache
    @lru_cache(None)
    def dp(s):
        if not s: return 0
        # Group consecutive same colors
        i, result = 0, float('inf')
        while i < len(s):
            j = i
            while j < len(s) and s[j] == s[i]: j += 1
            # s[i:j] are same color, need (3-j+i) more to remove
            # Try inserting from other parts
            rest = dp(s[:i] + s[j:])
            result = min(result, 3 - (j - i) + rest)  # oversimplified
            i = j
        return result
    return dp(tuple(board))

#include <bits/stdc++.h>
using namespace std;

int countArrangement(int n) {
    vector<int> dp(1 << n, 0);
    dp[0] = 1;
    for (int mask = 0; mask < (1 << n); mask++) {
        int pos = __builtin_popcount(mask) + 1;
        for (int num = 1; num <= n; num++) {
            if (mask >> (num-1) & 1) continue;
            if (num % pos == 0 || pos % num == 0)
                dp[mask | (1 << (num-1))] += dp[mask];
        }
    }
    return dp[(1 << n) - 1];
}

public class BeautifulArrangement {
    int count = 0;

    public int countArrangement(int n) {
        backtrack(n, 1, new boolean[n + 1]);
        return count;
    }

    void backtrack(int n, int pos, boolean[] used) {
        if (pos > n) { count++; return; }
        for (int num = 1; num <= n; num++) {
            if (!used[num] && (num % pos == 0 || pos % num == 0)) {
                used[num] = true;
                backtrack(n, pos + 1, used);
                used[num] = false;
            }
        }
    }
}