1#include <stdio.h>
2
3int has_solution(int n) {
4    return (n % 4 == 0) || (n % 4 == 3);
5}
6
7int main(void) {
8    for (int n = 1; n <= 12; n++) {
9        printf("n=%d -> %s\n", n, has_solution(n) ? "possible" : "impossible");
10    }
11    return 0;
12}

1#include <stdio.h>
2#include <string.h>
3
4static int n;
5static int slots[64];
6
7int solve(int k) {
8    if (k == 0) return 1;
9
10    for (int i = 0; i + k + 1 < 2 * n; i++) {
11        int j = i + k + 1;
12        if (slots[i] == 0 && slots[j] == 0) {
13            slots[i] = k;
14            slots[j] = k;
15
16            if (solve(k - 1)) return 1;
17
18            slots[i] = 0;
19            slots[j] = 0;
20        }
21    }
22    return 0;
23}
24
25int main(void) {
26    n = 7;
27    if ((n % 4 != 0) && (n % 4 != 3)) {
28        printf("No solution for n=%d\n", n);
29        return 0;
30    }
31
32    memset(slots, 0, sizeof(slots));
33
34    if (solve(n)) {
35        for (int i = 0; i < 2 * n; i++) {
36            printf("%d ", slots[i]);
37        }
38        printf("\n");
39    }
40    return 0;
41}

langford :: Int -> [[Int]]
langford n
| n `mod` 4 /= 0 && n `mod` 4 /= 3 = [] | otherwise = place n (replicate (2 * n) 0) where place 0 xs = [xs] place k xs = [ result | i <- [0 .. (2 * n - k - 2)] , let j = i + k + 1 , xs !! i == 0 , xs !! j == 0 , let xs1 = setAt i k (setAt j k xs) , result <- place (k - 1) xs1 ] setAt :: Int -> a -> [a] -> [a] setAt i v xs = take i xs ++ [v] ++ drop (i + 1) xs main :: IO () main = print (take 1 (langford 7)) ``` This is compact and readable, though list updates can be slower than mutable arrays for larger searches. ### Counting All Solutions and Symmetry Pruning If you need counts instead of one arrangement, remove early returns and increment a counter on complete placements. For larger `n`, symmetry pruning reduces duplicate mirrored results. A common trick is to constrain the first placement of the largest number to half the available range. In C, a counter based version can look like this: ```c long long total = 0; void count_all(int k) { if (k == 0) { total++; return; } for (int i = 0; i + k + 1 < 2 * n; i++) { int j = i + k + 1; if (slots[i] == 0 && slots[j] == 0) { slots[i] = slots[j] = k; count_all(k - 1); slots[i] = slots[j] = 0; } } } ``` Counting can grow expensive quickly, so pruning strategy matters more than micro optimizations at first. ## Common Pitfalls * Forgetting the feasibility rule and recursing on impossible `n`. * Placing the second copy at `i + k` instead of `i + k + 1`. * Failing to backtrack both slots after recursive calls. * Starting from small values, which increases branching early. * Confusing one solution mode with all solutions counting mode. ## Summary * Langford sequences exist only when `n mod 4` equals `0` or `3`. * Backtracking with distance `k + 1` is the core constraint. * C implementations are fast and memory efficient for deeper search. * Haskell implementations are concise and good for experimentation. * Counting variants need pruning and clear search goals to scale.