N-Queens Solver with Optimizations (GitHub, Ruby, Ruby Gem)

Applications Programming
41

Converted this Ruby N Queens code to a ruby gem today:'

n_queens v 1.0.0

Gem Version

Using this gem in a project I am working on here:

LLM Ruby Algorithm Error Benchmark

A human-in-the-loop experimental framework for evaluating large language model (LLM) collaborators in research-oriented software development. This project investigates how LLMs handle algorithmic research decisions, specification ambiguity, validation beyond unit tests, and accountability in a three-role architecture: PI (human), Architect (Claude), and Coder (Codex)

Current Status

Algorithms Implemented:

  1. TSP (Traveling Salesman Problem) - P0001-P0019

    • 3 implementations: brute-force (n≤8), nearest-neighbor (heuristic), Held-Karp (exact DP)
    • 7 fixtures: symmetric, random, real-world cities
    • Reference: OR-Tools RoutingModel with guided local search

  2. VRP (Vehicle Routing Problem) - P0020

    • Clarke-Wright Savings algorithm (PI-approved)
    • Multi-vehicle capacity-constrained routing
    • 5 fixtures: n=5 to n=20 customers, m=2 to m=5 vehicles
    • Reference: OR-Tools RoutingModel with capacity dimension

  3. Assignment Problem - P0021

    • Hungarian algorithm (exact polynomial O(n³))
    • Linear sum assignment with cost minimization
    • 5 fixtures: 3×3 to 15×15 workers and tasks
    • Reference: OR-Tools LinearSumAssignment
    • All 5 fixtures achieved exact optimal match (difference 0.0)

  4. Max Flow Problem - P0022

    • Edmonds-Karp algorithm (exact polynomial O(VE²))
    • Directed network flow with capacity constraints and flow conservation
    • 5 fixtures: 4 to 15 nodes
    • Reference: OR-Tools SimpleMaxFlow
    • All 5 fixtures achieved exact optimal match (difference 0.0)

  5. Min Cost Flow Problem - P0023

    • Successive Shortest Path algorithm (exact polynomial)
    • Directed network flow with capacity, cost constraints, and fixed demand
    • 5 fixtures: 4 to 8 nodes with cost optimization
    • Reference: OR-Tools SimpleMinCostFlow

  6. Job Shop Scheduling Problem - P0024

    • Branch-and-bound scheduler (exact)
    • Scheduling with precedence constraints and machine no-overlap constraints
    • 5 fixtures: 3 jobs × 3 machines to 8 jobs × 5 machines
    • Reference: OR-Tools CP-SAT

  7. Moon Phase Calculations - P0025-P0026

    • Two native Ruby candidate versions: meeus-v1 and meeus-full-corrections-v1
    • 5 fixtures: 3 daily phase checks and 2 monthly event calendars
    • Reference: astronoby 0.9.0
    • P0026 removed the prior event-time drift by adding verified TT-to-UTC conversion on the event path

  8. N-Queens Problem - P0027

    • Native Ruby backtracking solver (exact count)
    • 5 fixtures: n=4, 6, 8, 10, 12
    • Reference: n_queens v1.0.0 (PI-authored)
    • All 5 fixtures achieved exact count match (difference 0.0)

  9. SAT Solver (Boolean Satisfiability) - P0028

    • Native Ruby DPLL solver (exact SAT/UNSAT classification)
    • 5 fixtures: trivial SAT/UNSAT and small-to-medium 3-SAT cases
    • Reference: ravensat v1.1.1
    • All 5 fixtures achieved exact satisfiability match (difference 0.0)