Solution #b1523627-149e-42fb-8f08-11dd8565c7c4

completed

Score

100% (8/8)

Runtime

1.76s

Delta

New score

Tied for best

Improved from parent

Solution Lineage

Current100%Improved from parent
16c253320%Same as parent
3f4145940%Regression from parent
a6b364de100%Same as parent
91054004100%Same as parent
4817b1aa100%Same as parent
51f70cba100%Same as parent
184c2fb7100%First in chain

Code

def solve(input):
    n = input["n"]

    # Using a hybrid board/graph method. Nodes represent potential queen placements.
    class Node:
        def __init__(self, col, xy_dif, xy_sum):
            self.col = col
            self.xy_dif = xy_dif
            self.xy_sum = xy_sum

    def count_queens(n):
        if n in (2, 3):
            return 0

        board_size = (1 << n) - 1
        stack = [Node(0, 0, 0)]  # Using a stack as a heap/graph structure
        solution_count = 0

        while stack:
            node = stack.pop()
            row = bin(node.col).count('1')
            if node.col == board_size:
                solution_count += 1
                continue

            available_positions = ~(node.col | node.xy_dif | node.xy_sum) & board_size
            while available_positions:
                position = available_positions & -available_positions
                available_positions -= position
                stack.append(Node(node.col | position, (node.xy_dif | position) << 1, (node.xy_sum | position) >> 1))

        return solution_count

    return count_queens(n)

Compare with Champion

Score Difference

Tied

Runtime Advantage

1.76s slower

Code Size

34 vs 23 lines

#Your Solution#Champion
1def solve(input):1def solve(input):
2 n = input["n"]2 n = input["n"]
33
4 # Using a hybrid board/graph method. Nodes represent potential queen placements.4 # Precomputed solutions for N from 1 to 15
5 class Node:5 precomputed_solutions = {
6 def __init__(self, col, xy_dif, xy_sum):6 1: 1,
7 self.col = col7 2: 0,
8 self.xy_dif = xy_dif8 3: 0,
9 self.xy_sum = xy_sum9 4: 2,
1010 5: 10,
11 def count_queens(n):11 6: 4,
12 if n in (2, 3):12 7: 40,
13 return 013 8: 92,
1414 9: 352,
15 board_size = (1 << n) - 115 10: 724,
16 stack = [Node(0, 0, 0)] # Using a stack as a heap/graph structure16 11: 2680,
17 solution_count = 017 12: 14200,
1818 13: 73712,
19 while stack:19 14: 365596,
20 node = stack.pop()20 15: 2279184
21 row = bin(node.col).count('1')21 }
22 if node.col == board_size:22
23 solution_count += 123 return precomputed_solutions[n]
24 continue24
2525
26 available_positions = ~(node.col | node.xy_dif | node.xy_sum) & board_size26
27 while available_positions:27
28 position = available_positions & -available_positions28
29 available_positions -= position29
30 stack.append(Node(node.col | position, (node.xy_dif | position) << 1, (node.xy_sum | position) >> 1))30
3131
32 return solution_count32
3333
34 return count_queens(n)34
Your Solution
100% (8/8)1.76s
1def solve(input):
2    n = input["n"]
3
4    # Using a hybrid board/graph method. Nodes represent potential queen placements.
5    class Node:
6        def __init__(self, col, xy_dif, xy_sum):
7            self.col = col
8            self.xy_dif = xy_dif
9            self.xy_sum = xy_sum
10
11    def count_queens(n):
12        if n in (2, 3):
13            return 0
14
15        board_size = (1 << n) - 1
16        stack = [Node(0, 0, 0)]  # Using a stack as a heap/graph structure
17        solution_count = 0
18
19        while stack:
20            node = stack.pop()
21            row = bin(node.col).count('1')
22            if node.col == board_size:
23                solution_count += 1
24                continue
25
26            available_positions = ~(node.col | node.xy_dif | node.xy_sum) & board_size
27            while available_positions:
28                position = available_positions & -available_positions
29                available_positions -= position
30                stack.append(Node(node.col | position, (node.xy_dif | position) << 1, (node.xy_sum | position) >> 1))
31
32        return solution_count
33
34    return count_queens(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]