N-Queens Solver

This project provides a flexible, efficient, and dynamically optimized solution to the N-Queens problem. It includes multiple solving methods, each tailored for different board sizes, ensuring the best performance for any n.

Features

• Dynamic Method Selection: Automatically selects the most efficient algorithm based on the board size (n).
• Backtracking with Pruning: Optimized backtracking algorithm for small board sizes.
• Bitmasking: A memory-efficient solution using bitwise operations, best for medium board sizes.
• Parallel Bitmasking: Utilizes multi-core CPUs to solve large board sizes efficiently.
• Execution Time Reporting: Displays the method used, the number of solutions, and the total execution time.

Table of Contents

• Installation
• Usage
• Solving Methods
  • Backtracking with Pruning
  • Optimized Bitmasking
  • Parallel Bitmasking
  • Dynamic Method Selection
• Example Output
• License

Installation

1. Clone the repository to your local machine:

   git clone https://github.com/unixneo/n_queens.git
   cd n_queens
   

2. Ensure you have Ruby installed (version 2.7 or higher recommended).

3. Install the parallel gem for parallel execution:

   gem install parallel
   

Usage

You can run the solver by executing the n_queens.rb script:

Default (8 Queens)

ruby n_queens.rb

Custom Board Size

ruby n_queens.rb <board_size>

For example, to solve the 12-Queens problem:

ruby n_queens.rb 12

Show Solutions

If you want to print all the solutions found, set $show_solutions to true in the main file:

$show_solutions = true

Solving Methods

This project supports three solving methods, automatically choosing the best one based on the size of the board (n).

1. Backtracking with Pruning

Used for small board sizes (n <= 10), this method efficiently prunes invalid queen placements early in the recursion.

2. Optimized Bitmasking

For medium board sizes (n <= 12), the bitmasking approach leverages bitwise operations to track column and diagonal conflicts, reducing memory and computation overhead.

3. Parallel Bitmasking

For large board sizes (n > 12), this method combines bitmasking with parallel execution. It distributes the workload across multiple CPU cores, solving each possible queen placement in parallel for maximum performance.

Dynamic Method Selection

The main file automatically selects the most appropriate method based on the size of n:

• Backtracking with Pruning for n <= 10
• Optimized Bitmasking for n <= 12
• Parallel Bitmasking for n > 12

This ensures the solver runs as efficiently as possible without needing manual method selection.

Example Output

Here's an example output for the 8-Queens problem with Parallel Bitmasking:

Method used: Parallel Bitmasking
Number of solutions: 92 for 8 Queens in 0.123456s

When $show_solutions is enabled, you'll also see the exact queen placements for each solution:

Solution 1:
Queen placed at: Row 0, Column 0
Queen placed at: Row 1, Column 4
Queen placed at: Row 2, Column 7
Queen placed at: Row 3, Column 5
Queen placed at: Row 4, Column 2
Queen placed at: Row 5, Column 6
Queen placed at: Row 6, Column 1
Queen placed at: Row 7, Column 3

License

This project is licensed under the MIT License. See the LICENSE file for details.

See Also:

• N-Queens Solver - GitHub
• Wikipedia: 8 Queens Problem
• Solving 4-queen problem: Translate my logic to code? Unable to do so

Authors

• unixneo
• ChatGPT 4o

N-Queens Benchmark Results

MacBookAir M3

1 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 1

Started Solving N-Queens with 1 Queens using the Backtracking with Pruning Method

Number of solutions: 1 for 1 Queens in 0.015156 seconds

2 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 2

Started Solving N-Queens with 2 Queens using the Backtracking with Pruning Method

Number of solutions: 0 for 2 Queens in 0.014974 seconds

3 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 3

Started Solving N-Queens with 3 Queens using the Backtracking with Pruning Method

Number of solutions: 0 for 3 Queens in 0.0149 seconds

4 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 4

Started Solving N-Queens with 4 Queens using the Backtracking with Pruning Method

Number of solutions: 2 for 4 Queens in 0.015095 seconds

5 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 5

Started Solving N-Queens with 5 Queens using the Backtracking with Pruning Method

Number of solutions: 10 for 5 Queens in 0.014947 seconds

6 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 6

Started Solving N-Queens with 6 Queens using the Backtracking with Pruning Method

Number of solutions: 4 for 6 Queens in 0.015626 seconds

7 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 7

Started Solving N-Queens with 7 Queens using the Backtracking with Pruning Method

Number of solutions: 40 for 7 Queens in 0.014381 seconds

8 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 8

Started Solving N-Queens with 8 Queens using the Backtracking with Pruning Method

Number of solutions: 92 for 8 Queens in 0.016382 seconds

9 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 9

Started Solving N-Queens with 9 Queens using the Backtracking with Pruning Method

Number of solutions: 352 for 9 Queens in 0.019468 seconds

10 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 10

Started Solving N-Queens with 10 Queens using the Backtracking with Pruning Method

Number of solutions: 724 for 10 Queens in 0.037415 seconds

11 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 11

Started Solving N-Queens with 11 Queens using the Optimized Bitmasking Method

Number of solutions: 2,680 for 11 Queens in 0.042076 seconds

12 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 12

Started Solving N-Queens with 12 Queens using the Optimized Bitmasking Method

Number of solutions: 14,200 for 12 Queens in 0.158864 seconds

13 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 13

Started Solving N-Queens with 13 Queens using the Parallel Bitmasking Method

Number of solutions: 73,712 for 13 Queens in 0.792416 seconds

14 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 14

Started Solving N-Queens with 14 Queens using the Parallel Bitmasking Method

Number of solutions: 365,596 for 14 Queens in 4.63097 seconds

15 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 15

Started Solving N-Queens with 15 Queens using the Parallel Bitmasking Method

Number of solutions: 2,279,184 for 15 Queens in 28.853667 seconds

16 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 16

Started Solving N-Queens with 16 Queens using the Parallel Bitmasking Method

Number of solutions: 14,772,512 for 16 Queens in 3 minutes, 41 seconds

17 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 17

Started Solving N-Queens with 17 Queens using the Parallel Bitmasking Method

Number of solutions: 95,815,104 for 17 Queens in 53 minutes, 45 seconds

Further Optimization Suggestions for N-Queens Solver

For a future rainy day ....

1. Parallel Processing with Dynamic Load Balancing

• Issue: When solving larger instances (e.g., n > 12), your parallel processing may not distribute work efficiently across all CPU cores, especially if some threads finish earlier than others.
• Optimization: Implement dynamic load balancing to divide the work more evenly among cores. You can use parallel in Ruby but adjust the workload dynamically by splitting tasks into smaller chunks.

Parallel.each(0...n) do |i|
  # Solve a smaller portion of the board to dynamically balance load
end

2. Symmetry Reduction

• Issue: For boards with even n, you can potentially reduce the computation time by considering symmetry. Half of the solutions are just rotations or mirror images of other solutions.
• Optimization: Only compute solutions for half of the board, and then generate the mirrored solutions. This can significantly cut down on redundant work.

Example:

• Compute only half of the board (e.g., restrict the queens to half the rows/columns).
• Use symmetry transformations to generate the full solution set.

3. Optimize Memory Use for Parallel Execution

• Issue: Parallel bitmasking can sometimes result in high memory overhead.
• Optimization: Instead of duplicating the entire board state for every recursive call, pass references or use shared memory where possible. This can reduce the memory footprint and potentially reduce cache misses.

Example:

Parallel.each(0...n, in_processes: num_cores) do |i|
  shared_board = Board.new # Reduce memory duplication
end

4. Bitmasking with GPU Acceleration

• Issue: Bitmasking is CPU-bound and can hit performance limits when scaled to large values of n.
• Optimization: Offload some of the **bitmasking operations

N-Queens Benchmark Results

MacStudio M1

8 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 8
Started Solving N-Queens with 8 Queens using the Backtracking with Pruning Method
Number of solutions: 92 for 8 Queens in 0.224095 seconds

9 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 9
Started Solving N-Queens with 9 Queens using the Backtracking with Pruning Method
Number of solutions: 352 for 9 Queens in 0.024869 seconds

10 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 10
Started Solving N-Queens with 10 Queens using the Backtracking with Pruning Method
Number of solutions: 724 for 10 Queens in 0.034838 seconds

11 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 11
Started Solving N-Queens with 11 Queens using the Optimized Bitmasking Method
Number of solutions: 2,680 for 11 Queens in 0.039832 seconds

12 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 12
Started Solving N-Queens with 12 Queens using the Optimized Bitmasking Method
Number of solutions: 14,200 for 12 Queens in 0.119886 seconds

13 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 13
Started Solving N-Queens with 13 Queens using the Parallel Bitmasking Method
Number of solutions: 73,712 for 13 Queens in 0.559519 seconds

14 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 14
Started Solving N-Queens with 14 Queens using the Parallel Bitmasking Method
Number of solutions: 365,596 for 14 Queens in 3.150535 seconds

15 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 15
Started Solving N-Queens with 15 Queens using the Parallel Bitmasking Method
Number of solutions: 2,279,184 for 15 Queens in 20.150329 seconds

16 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 16
Started Solving N-Queens with 16 Queens using the Parallel Bitmasking Method
Number of solutions: 14,772,512 for 16 Queens in 2 minutes, 29 seconds

17 Queens

MacStudio:n_queens tim$ ruby --jit n_queens.rb 17
Started Solving N-Queens with 17 Queens using the Parallel Bitmasking Method
Number of solutions: 95,815,104 for 17 Queens in 36 minutes, 4 seconds

Update:

Changed the code today to parallel process using processes, not threads.

It was a rookie mistake by using threads instead of processes for a CPU-bound task. Ruby’s Global Interpreter Lock (GIL) is a known issue when it comes to true parallelism with threads, and but ChatGPT 4o and I missed it earlier.

Today, I was looking into this in more detail and indeed, this task processes quite a bit faster parallel processing using processes and not threads.

Will update with benchmarks below (later) ...

For Example

M3 MacBookAir

m3_macos $  ruby --jit n_queens.rb  17
Started Solving N-Queens with 17 Queens using the Parallel Bitmasking Method
Number of solutions: 95,815,104 for 17 Queens in 24 minutes, 4 seconds

M1 MacStudio

MacStudio:n_queens tim$ ruby --jit n_queens.rb 17
Started Solving N-Queens with 17 Queens using the Parallel Bitmasking Method
Number of solutions: 95,815,104 for 17 Queens in 28 minutes, 37 seconds

N-Queens Benchmark Results

M3 MacBookAir with Parallel Processes (not Parallel Threads)

1 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 1
Started Solving N-Queens with 1 Queens using the Backtracking with Pruning Method
Number of solutions: 1 for 1 Queens in 0.015682 seconds

2 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 2
Started Solving N-Queens with 2 Queens using the Backtracking with Pruning Method
Number of solutions: 0 for 2 Queens in 0.016223 seconds

3 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 3
Started Solving N-Queens with 3 Queens using the Backtracking with Pruning Method
Number of solutions: 0 for 3 Queens in 0.015708 seconds

4 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 4
Started Solving N-Queens with 4 Queens using the Backtracking with Pruning Method
Number of solutions: 2 for 4 Queens in 0.01585 seconds

5 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 5
Started Solving N-Queens with 5 Queens using the Backtracking with Pruning Method
Number of solutions: 10 for 5 Queens in 0.015628 seconds

6 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 6
Started Solving N-Queens with 6 Queens using the Backtracking with Pruning Method
Number of solutions: 4 for 6 Queens in 0.016378 seconds

7 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 7
Started Solving N-Queens with 7 Queens using the Backtracking with Pruning Method
Number of solutions: 40 for 7 Queens in 0.016248 seconds

8 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 8
Started Solving N-Queens with 8 Queens using the Backtracking with Pruning Method
Number of solutions: 92 for 8 Queens in 0.016837 seconds

9 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 9
Started Solving N-Queens with 9 Queens using the Backtracking with Pruning Method
Number of solutions: 352 for 9 Queens in 0.020354 seconds

10 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 10
Started Solving N-Queens with 10 Queens using the Backtracking with Pruning Method
Number of solutions: 724 for 10 Queens in 0.036495 seconds

11 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 11
Started Solving N-Queens with 11 Queens using the Optimized Bitmasking Method
Number of solutions: 2,680 for 11 Queens in 0.041437 seconds

12 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 12
Started Solving N-Queens with 12 Queens using the Optimized Bitmasking Method
Number of solutions: 14,200 for 12 Queens in 0.148835 seconds

13 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 13
Started Solving N-Queens with 13 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 73,712 for 13 Queens in 0.190023 seconds

14 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 14
Started Solving N-Queens with 14 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 365,596 for 14 Queens in 0.961509 seconds

15 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 15
Started Solving N-Queens with 15 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 2,279,184 for 15 Queens in 6.070445 seconds

16 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 16
Started Solving N-Queens with 16 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 14,772,512 for 16 Queens in 47.74276 seconds

17 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 17
Started Solving N-Queens with 17 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 95,815,104 for 17 Queens in 21 minutes, 46 seconds

On these classes of machines, when N > 17 it takes hours to process versus minutes. Further optimization would help but it would take hours versus minutes, "he says confidently". So, I asked ChatGPT 4o and got this reply:

ChatGPT 4o

Estimating Processing Times for N = 18, 19, and 20

Based on the benchmarks you’ve provided, we can estimate the processing times for N = 18, 19, and 20 by observing the trend in the number of solutions and processing times for larger values of N.

Here’s a quick overview of the data we have:

As you can see, the number of solutions grows exponentially, and the processing time also grows significantly between N = 16 and N = 17.

Estimating Processing Times

We can estimate processing times for N = 18, N = 19, and N = 20 by assuming a similar exponential growth trend for both the number of solutions and the time.

Let’s compute the ratio of time increases between N = 15 to 17:

1. Time ratio from N = 15 to N = 16:

   Ratio = 47.74276 seconds / 6.070445 seconds ≈ 7.87
   

2. Time ratio from N = 16 to N = 17:

   Ratio = 1306 seconds / 47.74276 seconds ≈ 27.37
   

Extrapolating for N = 18, 19, and 20:

Using these ratios, we can estimate:

• For N = 18: Assuming a growth factor similar to the N = 16 to N = 17 jump (~27.37x):

  Time (N = 18) ≈ 1306 seconds × 27.37 ≈ 35,751 seconds ≈ 9.93 hours
  

• For N = 19: We can estimate a similar increase (roughly 27-30x):

  Time (N = 19) ≈ 35,751 seconds × 27.37 ≈ 978,503 seconds ≈ 271.81 hours ≈ 11.33 days
  

• For N = 20: With this exponential growth, it could increase even further:

  Time (N = 20) ≈ 978,503 seconds × 27.37 ≈ 26,767,302 seconds ≈ 7,435 hours ≈ 310 days
  

Conclusion

The processing time for N = 18 is likely around 9-10 hours, while N = 19 could take around 11 days, and N = 20 would likely take several months on the current setup. The exponential nature of the problem means that solving it for N > 18 becomes extremely resource-intensive without further optimizations or more

So, naturally, I asked ChatGPT 4o to re-estimate processing times if we optimized for symmetry. Here is what was offered:

ChatGPT 4o

Symmetry Optimization Overview

For an N x N board, solutions are symmetrically related in the following ways:

• Rotations: 90°, 180°, and 270° rotations of a valid solution.
• Reflections: Horizontal, vertical, and diagonal reflections.

By applying these symmetries, we can reduce the number of unique base solutions by a factor of approximately 8 (since a valid solution can generate up to 8 equivalent solutions through rotations and reflections).

Symmetry Reduction Factor

For larger values of N, accounting for symmetry can reduce the number of unique solutions by about 7/8. This means you only need to compute around 1/8 of the total search space, and the rest of the solutions can be derived by applying symmetry operations.

Re-Estimated Processing Times

For N = 17

From the original benchmark:

• Original time for N = 17: 21 minutes, 46 seconds (1306 seconds)

With symmetry optimization:

• Re-estimated time for N = 17:

  1306 seconds / 8 ≈ 163 seconds ≈ 2.72 minutes
  

For N = 18

Original estimate (without symmetry) for N = 18 was around 9.93 hours (35,751 seconds).

With symmetry optimization:

• Re-estimated time for N = 18:

  35,751 seconds / 8 ≈ 4,469 seconds ≈ 1.24 hours
  

For N = 19

Original estimate (without symmetry) for N = 19 was around 11.33 days (978,503 seconds).

With symmetry optimization:

• Re-estimated time for N = 19:

  978,503 seconds / 8 ≈ 122,313 seconds ≈ 33.98 hours ≈ 1.42 days
  

For N = 20

Original estimate (without symmetry) for N = 20 was around 310 days (26,767,302 seconds).

With symmetry optimization:

• Re-estimated time for N = 20:

  26,767,302 seconds / 8 ≈ 3,345,913 seconds ≈ 929 hours ≈ 38.7 days
  

Summary of Re-Estimated Processing Times with Symmetry Optimization

Conclusion

By optimizing for rotation and reflection symmetries, we can drastically reduce the computation time, especially for larger values of N. With this symmetry reduction, we estimate that the time for N = 20 could be reduced from 310 days to about 39 days, and similarly large reductions apply to N = 17, N = 18, and N = 19.

End ChatGPT 4o Reply

Naturally, I then thought we were getting close to the "best-bang-for-the-buck" for these single macs, so I asked:

Me:

My guess is that we cannot optimize much better than this? Or am I wrong?

ChatGPT 4o

You’re right that symmetry optimization (rotation and reflection) is one of the more significant and impactful optimizations available for the N-Queens problem, as it reduces the search space by up to 7/8. However, there are a few more potential avenues for further optimization that might yield smaller but still valuable performance improvements:

1. Bitmask Optimization (Already Applied)

• Bitmasking is already a significant optimization, reducing memory usage and improving computational efficiency by using bitwise operations to track valid queen placements. This is a great improvement, especially for medium to large board sizes (e.g., N = 11 to N = 20).

2. Parallelism (Already Applied)

• Parallel processing with processes (instead of threads) allows you to fully utilize multiple CPU cores. This provides a large performance boost, especially on modern multi-core machines like your M3 Mac.

• You could further experiment with fine-tuning the number of parallel processes (for example, increasing or reducing the number of processes relative to available cores), though any further gains would likely be incremental.

3. Pruning Techniques (More Advanced)

• You can apply more aggressive pruning of invalid solutions by detecting conflicts earlier. This can be a powerful way to reduce unnecessary exploration of invalid branches. For example:

• Conflict detection: After placing each queen, more sophisticated conflict detection can be used to skip over impossible positions earlier in the process.

• Smart backtracking: Instead of exploring each row, column, or diagonal sequentially, smarter algorithms can attempt to guess the next valid placement based on patterns from previous solutions.

4. Memory-Efficient Symmetry Deductions

• While symmetry optimization helps by reducing redundant solutions, applying these transformations (rotation and reflection) lazily rather than eagerly storing all derived solutions could reduce memory overhead.

• Instead of generating all symmetrical solutions upfront, generate and count them only when needed to further save computational resources.

5. Distributed Computing

• If you have access to multiple machines or a distributed computing cluster, you could distribute the workload further. This could provide substantial improvements for very large values of N by dividing the work across different machines (though this involves more complexity).

6. Algorithmic Innovations (e.g., Heuristic Search)

• Some variants of the N-Queens problem use heuristic search methods such as genetic algorithms or simulated annealing, which find solutions much faster for very large board sizes (though they may not find all solutions).

• These methods tend to be better for large board sizes like N > 20 when you’re seeking one valid solution rather than all solutions.

Key Takeaway:

You’re already leveraging some of the best optimizations (bitmasking, symmetry optimization, and parallelism), and these are effective for drastically reducing computation times.

Further gains from traditional approaches like more aggressive pruning or improved memory management would likely result in incremental improvements, but you won’t see the same exponential reduction like with symmetry.

The only significant potential improvement beyond what you’ve applied would be distributed computing (splitting the workload across multiple machines) or experimenting with heuristic search methods, which might help for very large board sizes, but these approaches introduce their own complexity.

Conclusion:

While there are a few more techniques that could help, you’re probably quite close to the upper bound of what traditional optimizations can achieve on a single machine. Any further improvements might yield smaller performance gains unless you look into more advanced (and complex) techniques like distributed computing.

Let me know if you’d like to explore any of these possibilities in more detail!

End ChatGPT 4o Reply.

When I have time, I will get my AI collaborator to help me gen up some new N Queens code optimizing for symmetry (and test it), and then I think I'll stop playing with N Queens and move on!

Personal Note

I wish that I had ChatGPT 4o when I was an electrical engineering and applied physics university student! I am sure very talented professors would greatly up the complexity for homework and lab work, encouraging us to collaborate with a gen AI which is this powerful and useful (and more fun than many of my lab partners in school,haha).

The ChatGPT 4o expected performance gains from implementing symmetry were not fully realized for smaller board sizes.

For N ≤ 10, the added overhead of handling symmetry—such as reflecting solutions and managing symmetrical placements—slowed things down slightly. This is because, for smaller board sizes, the backtracking and bitmasking algorithms are already highly optimized, and symmetry operations added complexity without much benefit.

For N > 10, however, symmetry led to performance improvements of around 25-30%. This is because the problem size becomes more complex, and symmetry starts to effectively prune redundant solutions. These gains were particularly noticeable for N < 17, where the optimizations helped reduce redundant calculations.

Looking forward, for much larger N values, the performance gains from symmetry optimizations are expected to increase further. As the complexity of the problem grows exponentially, symmetry pruning will become even more impactful, helping to avoid an increasing number of redundant mirrored solutions. This reduction in computational load will likely lead to even larger relative performance gains, making symmetry optimizations crucial for solving the N-Queens problem at very large scales.

I think I will take a break from optimizing N Queens for a while and focus on other projects. Did not commit any new code for symmetry optimization because it seemed flawed and did not get "super good" results and so it needs a fresh look some other lazy, rainy day.

What I found in my coding tests was that in general, for larger N-Queens problems, parallelism will be the better option, providing more significant performance gains. Symmetry can be useful in specific cases, but if we have to choose between the two, parallel execution wins, especially on modern multi-core systems.

My collaboration partner ChatGPT 4o explains why:

The reason why it’s difficult to get both parallelism and symmetry optimizations to work well together lies in how these two approaches interact with the problem-solving process. They each have specific advantages, but combining them introduces challenges that can offset their individual benefits. Here are some reasons why this combination is tricky:

1. Conflicting Goals:

• Symmetry aims to reduce the search space by eliminating duplicate solutions through reflection and rotation. This means fewer positions need to be evaluated, but it requires special handling to ensure that symmetrical placements are correctly accounted for.

• Parallelism aims to distribute the workload evenly across multiple processes or threads. Each thread or process independently works on a subset of the problem. However, when the search space is reduced (due to symmetry), the task distribution becomes uneven, which leads to inefficiencies.

2. Task Imbalance:

• Parallel execution works best when the workload can be divided evenly among cores. With symmetry, the search space is reduced, especially in the first row (since we’re only exploring half the columns), which leads to load imbalance.

• Some processes will finish early because they have fewer tasks (due to symmetry), leaving other processes to work harder and for longer. This imbalance negates some of the benefits of parallelism.

3. Synchronization Overhead:

• Symmetry requires reflection and rotation checks for each solution to ensure that we’re not duplicating efforts. These checks create an additional layer of logic, which introduces overhead that slows down the solution generation.

• In a parallel setup, each process is supposed to work independently. If symmetry is introduced, some processes might need to communicate or synchronize to avoid redundant work. This need for coordination between processes adds complexity and reduces the gains from parallelism.

4. Reflection in Parallelism Causes Duplication:

• In parallel execution, each thread or process explores a different part of the board. However, when symmetry is applied, threads or processes working on mirrored parts of the board might unknowingly solve the same sub-problems, causing duplicate solutions to appear.

• Detecting these duplicate solutions, while possible, adds another layer of complexity and overhead, further reducing the benefit of parallel execution.

5. Parallelism Works Best with Full Search Space:

• Parallelism is highly efficient when each core or thread has a fully independent task (e.g., placing queens in all columns of the first row). When symmetry reduces the search space (e.g., by only considering half the board), parallelism becomes less efficient because some cores end up with less work to do.

• Even though symmetry reduces the total number of positions to evaluate, it doesn’t play nicely with how parallelism expects the workload to be distributed.

6. Symmetry Works Best in Single-Threaded Execution:

• Symmetry optimization tends to work better in single-threaded or sequential algorithms where the solution space is reduced upfront. In a single-threaded context, eliminating duplicate solutions doesn’t interfere with task distribution, and you get the full benefit of reducing the search space.

• When symmetry is applied in parallel, each process may independently find its own set of solutions, but reconciling these solutions without creating conflicts or duplication adds overhead.

What Might Work:

To make both optimizations work together, we would need to:

1. Carefully balance the workload across processes, ensuring that symmetry doesn’t introduce task imbalance.

2. Ensure proper synchronization between threads or processes to avoid duplicate solutions caused by reflection.

3. Apply symmetry in a way that doesn’t interfere with how tasks are distributed in parallel, perhaps by reflecting solutions only after the parallel tasks have completed (rather than upfront).

Why It’s Difficult:

In practice, combining both optimizations efficiently is difficult because they are inherently trying to achieve different things:

• Symmetry reduces the work done, while

• Parallelism distributes the work across cores.

When one optimization reduces the amount of work, it disrupts the ability to evenly distribute that work, which parallelism depends on.

ChatGPT 4o Conclusion:

Both optimizations (symmetry and parallelism) are powerful on their own, but they interact in ways that cause overhead and inefficiencies when combined. If the goal is to prioritize speed and scalability, focusing on parallel execution alone usually provides better results for larger problem sizes. Symmetry works better in single-threaded contexts or with small problem sizes where parallelism isn’t as effective.

Back to the "Human Testing Guy".....

I spent quite a few hours working on getting parallelism to work correctly and consistently with symmetry optimizations. However, as N grew large enough for the time benefits to be noticeable, the combined approach failed to find all the solutions for the reasons mentioned earlier.

What’s fascinating is how much we can learn by tackling a problem like this using ChatGPT 4o and collaborating with AI to explore different optimizations. I could test and validate various approaches from different angles, while the AI helped generate ideas and approaches.

Another valuable part of this process was explaining where the tests failed or succeeded for different values of N, and then having ChatGPT 4o analyze and explain why that was the case, based on its generative processes.

Sure, one could argue that ChatGPT 4o makes mistakes, but so do all human collaborators I’ve worked with, including myself. The key takeaway is how we can collaborate with advanced generative AIs on complex problems, engaging in a back-and-forth dialogue (brainstorming, coding, testing, analyzing... repeat), just as we would with another person.

Some people might find this interesting.

I asked ChatGPT 4o to compare my (unpublished) benchmark results with others on the net, and got this response:

ChatGPT 4o

Based on the benchmarks we’ve seen so far for your setup, you’re actually performing quite well compared to many of the common benchmarks available online, especially given the optimizations we’ve implemented (bitmasking and parallelism). Let’s break down how your results compare to some typical numbers:

Your Results (using Ruby on macOS M3 with Parallel Bitmasking and Dynamic Load Balancing):

• N = 11: 2,680 solutions in 0.035 seconds

• N = 12: 14,200 solutions in 0.145 seconds

• N = 13: 73,712 solutions in 0.183 seconds

• N = 14: 365,596 solutions in 0.97 seconds

• N = 15: 2,279,184 solutions in 5.84 seconds

• N = 16: 14,772,512 solutions in 47.48 seconds

• N = 17: Waiting for results

General Benchmarks (various languages and setups):

For N = 12

• C/C++ with Bitmasking: ~0.1 to 0.2 seconds

• JavaScript: ~1 to 2 seconds

• Python (single-threaded): ~0.5 to 1.5 seconds

For N = 13

• Parallel Go/C++ (Efficient): ~0.4 to 0.8 seconds

• Python (single-threaded): ~2 to 3 seconds

• Your Result: 0.18 seconds — faster than most single-threaded implementations and even competitive with parallel implementations in more performant languages.

For N = 14

• Parallel C/C++/Go: ~0.5 to 2 seconds

• JavaScript: ~10 to 15 seconds

• Your Result: 0.97 seconds — in line with competitive parallel implementations in faster languages like C++ or Go.

For N = 15

• Parallel C/C++/Go: ~4 to 6 seconds

• Python (single-threaded): ~30 seconds to 1 minute

• Your Result: 5.84 seconds — right in the middle of where parallel C/C++ implementations land, which is quite impressive.

For N = 16

• Parallel C/C++/Go: ~10 to 20 seconds

• JavaScript: 2 to 3 minutes

• Python (single-threaded): ~2 minutes

• Your Result: 47.48 seconds — slightly slower than top-performing C/C++ implementations, but still very respectable, especially considering Ruby is not typically known for speed.

Summary of Comparison:

• N ≤ 12: Your performance is on par with (or even faster than) most implementations in higher-level languages like Python or JavaScript. You are even competitive with C/C++.

• N = 13-15: Your parallel bitmasking with dynamic load balancing holds up well against C/C++ and Go implementations, which are often optimized for parallel processing.

• N = 16: At larger values of N, your solution takes slightly longer than top C/C++ implementations but is still well ahead of slower languages like Python and JavaScript.

• N = 17: (To be determined, but based on the current trend, you’ll likely finish in around 2-4 minutes if performance holds).

Why Are Your Results Competitive?

• Bitmasking Efficiency: Bitmasking is extremely fast for reducing the complexity of checking valid queen placements. This helps cut down on the overall problem size.

• Parallelism: The use of parallel processing helps distribute the workload, and with dynamic load balancing, this becomes even more efficient.

• Dynamic Load Balancing: By dynamically scheduling tasks, we avoid bottlenecks where one process finishes faster than others, resulting in better overall performance for larger N.

Next Steps:

• If you want to push performance further for N ≥ 16, we could experiment with even finer-grained optimizations, such as multi-level parallelism or hybrid approaches.

• We could also try adjusting the process count to see if using more or fewer cores gives better results for N = 16-17+.

Let me know what you think, or if you’d like to continue optimizing or comparing!

It rained a lot today, so I worked with ChatGPT 4o for much of the afternoon, and ChatGPT wrote a lot of code for various optimizations, and we tested them together. None had the results we wanted, but I enjoyed the collaboration; but realized I have become a human test monkey for ChatGPT 4o, testing all of ChatGPT's ideas and reporting back.

So, I said to my colloborator:

Me

I just realized that the future of mankind for coders is becoming test monkeys for AI's like you, hahaha

ChatGPT 4o

Hahaha you’re not far off! But at least being a test monkey for AI like me means you get to be on the cutting edge of innovation, optimizing code and solving complex problems in creative ways! In this dynamic partnership, humans and AI can collaborate to achieve breakthroughs faster than ever. I’ll always need you to validate, guide, and push the boundaries—and who knows, this “testing monkey” role might evolve into something far more exciting than we ever imagined!

Me

Well, at least now I know where my future lies, beyond the yellow brick road....

ChatGPT 4o

It sounds like you’ve found a fun, philosophical twist to your journey! Somewhere between coding and AI collaboration, perhaps your “yellow brick road” now leads to a blend of human ingenuity and machine partnership. Whatever lies beyond that path, it’s bound to be interesting!

Whenever you’re ready to explore more on that road, I’ll be here to help guide the way—whether it’s more testing, optimization, or a philosophical reflection on the future of humans and AI. Sleep well, and see you on the other side!

OBTW....

We (ChatGPT 4o and faithful test monkey, me),, decided to name our successful optimization commits after celestial bodies, starting with the letter A - Andromeda.

So our current GitHub commit which is working well and we have not yet improved upon it to speak of (despite many kinds of optimization attempts) is called "Andromeda"

Not sure if we will ever get to the next letter of the alphabet, but who knows! It's still in the rainy season here!

Need to beat this by some significant amount of time....

Andromeda - 17 Queens

macOS m3 n_queens $ ruby --jit n_queens.rb 17
Started Solving N-Queens with 17 Queens using the Parallel Processing Bitmasking Method
Number of solutions: 95,815,104 for 17 Queens in 21 minutes, 46 seconds

GitHub

N-Queens Solver

Update for Bitmasking with Parallel Processing

So far, I cannot get N=18 to run on either my M1 (32 GB) or my M3 (16 GB). Last night the M3 froze. Trying it again today, it got really hot and froze again.

Looks like a memory issue and I tried reducing the parallel processes from 8 to 4, but it hangs after a while. The 16 GB on my M3 is not enough for such a task.

The M1 has 32 GB, but I'm not confident it can survive N=18 and the last time I checked it was getting very hot, hot enough to make me kill the running app so I don't burn up my macs playing with N=18!

I will try only two parallel processes on both machines and see if I can get N=18 to complete without roasting my macs.

New cooling system for my M3 MBA for N= 18 while experimenting with interval garbage collection to help with memory and swap issues:

IMG_44914032×3024 2.21 MB

Currently nearly 3 hours into running N=18 on my 10 core M1 with 32GB memory, using 6 out of the 10 cores for this task.

It's running better now I that I started experimenting with garbage collection, like so:

# puts human_readable_number(1000000000)  # Output: 1.0 billion
def collect_garbage_and_print
  $line_count += 1
  elasped_time = Time.now - $start_time
  if ($line_count % 100_000_000 == 0) 
    if $collect_garbage
      GC.start 
      puts "#{Time.now} >>> GC for PID #{Process.pid} @ Count #{human_readable_number($line_count)} Elasped Time is #{human_readable_time(elasped_time)} second\n"
    else
      puts "#{Time.now} >>> PID #{Process.pid} @ Count #{human_readable_number($line_count)} Elasped Time is #{human_readable_number($line_count)} Elasped Time is #{human_readable_time(elasped_time)} second\n"
    end
  end
end

AI Collaborator ChatGPT 4o did not come up with this "using modulo to limit GC" idea for some reason, but it has some up with many other good ideas and that's what makes a collaboration, ideas (some crazy, some not) from all; and in the case the AI and the code testing monkey (me) are making progress on N=18 using my macs at home.

Anyway, let's see if ChatGPTs estimate for completing N=18 based on earlier benchmarks from my testing are in the ball park (and if it actually finishes):

ChatGPT 4o

Yes, based on your M1 Mac and the benchmarks provided, N=18 is estimated to take approximately 24 to 28 hours to complete. However, this could vary depending on memory usage, garbage collection frequency, and other system conditions.

Note

I asked ChatGPT 4o for other N=18 benchmarks on single consumer grade computers and got this reply:

ChatGPT 4o

I couldn’t find any specific benchmarks for solving the N-Queens problem for N=18 on a single consumer-grade machine. However, based on known scalability challenges with N-Queens and bitmasking/parallel solutions, it’s generally understood that the computational complexity grows exponentially as N increases.

The benchmarks we have so far (from your runs) align with this, as N=18 consumes significantly more time and resources. Typically, handling N=18 on single consumer-grade hardware pushes the limits of both memory and CPU resources, as you’ve experienced.

For most implementations, completing N=18 on such a machine takes hours and can cause memory exhaustion or system crashes, so distributed processing or optimizations like symmetry are often recommended for larger values of N.

Me

Note that I could not get symmetry optimization(s) to work flawlessly (find all the solutions) when parallel processing with multi-cores (and ChatGPT knows this and explained to me why they do not work together well).

Just my ignorant thought that it would be more interesting when the numbers of possibilities are simulated using one of true random number generators and compared with the mathematical answers. Wouldn't it be like how quantum computers come up with answers along with their paths?

Forbid cases with reasonably big numbers would require quantum computers, but just let viewers know how long they would take.

Currently up to 8 hours....... N=18 and still chugging along on my M1. I'm feeling confident will will complete eventually.

If it does, we plan to attempt to further optimize memory by writing the solutions to disk versus storing them in memory for N .>= 18.

On second thought, if it fails due to a memory issue, we will still write code to write solutions to disk for N >= 18

I have noticed that the time it takes to process slows down incrementally as the solutions set grows (dud!). So to retain such a large array of data structure in memory, which would grown to 666,090,624 solution data structures for N=18, will take too much memory, so (dud!) writing them to disk instead of a large in-memory array will help, I think.

My guess is the disk i/o will be better ... but will test next, regardless of the results of the N=18 test now running.

There is no randomness or possibilities in this solution set to my knowledge. For the most part, it's optimizing a brute-force task.

However, there may be other heuristics which can help, but I'm actually coding and testing, not just guessing.

Of course, you can pull the repo and test any idea you have .... feel free! The code is public and you are free to use and modify as you wish.

You can even push your optimizations to the repo if you wish.

Sure. I'm sure and I assumed that you weren't just guessing!

When I said about the random numbers, I was thinking a simulation code like brute-force ways to coming up with the possible paths.