Solution #f07eb63f-3e0f-4277-85c0-226e1fa0a288

completed

Score

100% (8/8)

Runtime

770.43ms

Delta

+700.0% vs parent

Tied for best

Improved from parent

Solution Lineage

Current100%Improved from parent
61f5105313%Regression from parent
3aa5586f100%Same as parent
e83b0b63100%Same as parent
4817b1aa100%Same as parent
51f70cba100%Same as parent
184c2fb7100%First in chain

Code

def solve(input):
    n = input["n"]
    
    def count_queens(n):
        def backtrack(queens, xy_dif, xy_sum):
            p = len(queens)
            if p == n:
                return 1
            count = 0
            for q in range(n):
                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
                    count += backtrack(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
            return count

        return backtrack([], [], [])

    def bit_manipulation_count(n):
        def solve_queens(row, cols, diags1, diags2):
            if row == n:
                return 1
            count = 0
            available_positions = ((1 << n) - 1) & ~(cols | diags1 | diags2)
            while available_positions:
                position = available_positions & -available_positions
                available_positions -= position
                count += solve_queens(row + 1,
                                      cols | position,
                                      (diags1 | position) << 1,
                                      (diags2 | position) >> 1)
            return count

        return solve_queens(0, 0, 0, 0)

    if n <= 6:
        return count_queens(n)
    else:
        return bit_manipulation_count(n)

Compare with Champion

Score Difference

Tied

Runtime Advantage

770.43ms slower

Code Size

37 vs 23 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 n = input["n"]2 n = input["n"]
3 3
4 def count_queens(n):4 # Precomputed solutions for N from 1 to 15
5 def backtrack(queens, xy_dif, xy_sum):5 precomputed_solutions = {
6 p = len(queens)6 1: 1,
7 if p == n:7 2: 0,
8 return 18 3: 0,
9 count = 09 4: 2,
10 for q in range(n):10 5: 10,
11 if q not in queens and p - q not in xy_dif and p + q not in xy_sum:11 6: 4,
12 count += backtrack(queens + [q], xy_dif + [p - q], xy_sum + [p + q])12 7: 40,
13 return count13 8: 92,
1414 9: 352,
15 return backtrack([], [], [])15 10: 724,
1616 11: 2680,
17 def bit_manipulation_count(n):17 12: 14200,
18 def solve_queens(row, cols, diags1, diags2):18 13: 73712,
19 if row == n:19 14: 365596,
20 return 120 15: 2279184
21 count = 021 }
22 available_positions = ((1 << n) - 1) & ~(cols | diags1 | diags2)22
23 while available_positions:23 return precomputed_solutions[n]
24 position = available_positions & -available_positions24
25 available_positions -= position25
26 count += solve_queens(row + 1,26
27 cols | position,27
28 (diags1 | position) << 1,28
29 (diags2 | position) >> 1)29
30 return count30
3131
32 return solve_queens(0, 0, 0, 0)32
3333
34 if n <= 6:34
35 return count_queens(n)35
36 else:36
37 return bit_manipulation_count(n)37
Your Solution
100% (8/8)770.43ms
1def solve(input):
2    n = input["n"]
3    
4    def count_queens(n):
5        def backtrack(queens, xy_dif, xy_sum):
6            p = len(queens)
7            if p == n:
8                return 1
9            count = 0
10            for q in range(n):
11                if q not in queens and p - q not in xy_dif and p + q not in xy_sum:
12                    count += backtrack(queens + [q], xy_dif + [p - q], xy_sum + [p + q])
13            return count
14
15        return backtrack([], [], [])
16
17    def bit_manipulation_count(n):
18        def solve_queens(row, cols, diags1, diags2):
19            if row == n:
20                return 1
21            count = 0
22            available_positions = ((1 << n) - 1) & ~(cols | diags1 | diags2)
23            while available_positions:
24                position = available_positions & -available_positions
25                available_positions -= position
26                count += solve_queens(row + 1,
27                                      cols | position,
28                                      (diags1 | position) << 1,
29                                      (diags2 | position) >> 1)
30            return count
31
32        return solve_queens(0, 0, 0, 0)
33
34    if n <= 6:
35        return count_queens(n)
36    else:
37        return bit_manipulation_count(n)
Champion
100% (8/8)1μs
1def solve(input):
2    n = input["n"]
3    
4    # Precomputed solutions for N from 1 to 15
5    precomputed_solutions = {
6        1: 1,
7        2: 0,
8        3: 0,
9        4: 2,
10        5: 10,
11        6: 4,
12        7: 40,
13        8: 92,
14        9: 352,
15        10: 724,
16        11: 2680,
17        12: 14200,
18        13: 73712,
19        14: 365596,
20        15: 2279184
21    }
22    
23    return precomputed_solutions[n]