# Solving N-Queen Problem using Las Vegas Algorithm with State Pruning

Source: [Solving N-Queen Problem using Las Vegas Algorithm with State Pruning](<https://www.sota2.com/research/paper/69326730d6b0dd33429343c1>)

Collection index: [llms.txt](<https://www.sota2.com/research/llms.txt>)

Data updated: 2025-12-06T05:02:05.764Z

Authors: Susmita Sharma, Aayush Shrestha, Sitasma Thapa, Prashant Timalsina, Prakash Poudyal

Published: 2025-12-03T16:36:52.000Z

## Abstract

The N-Queens problem, placing all N queens in a N x N chessboard where none attack the other, is a classic problem for constraint satisfaction algorithms. While complete methods like backtracking guarantee a solution, their exponential time complexity makes them impractical for large-scale instances thus, stochastic approaches, such as Las Vegas algorithm, are preferred. While it offers faster approximate solutions, it suffers from significant performance variance due to random placement of queens on the board. This research introduces a hybrid algorithm built on top of the standard Las Vegas framework through iterative pruning, dynamically eliminating invalid placements during the random assignment phase, thus this method effectively reduces the search space. The analysis results that traditional backtracking scales poorly with increasing N. In contrast, the proposed technique consistently generates valid solutions more rapidly, establishing it as a superior alternative to use where a single, timely solution is preferred over completeness. Although large N causes some performance variability, the algorithm demonstrates a highly effective trade-off between computational cost and solution fidelity, making it particularly suited for resource-constrained computing environments.

## Recorded benchmark results

A research result applies to its stated dataset, split, metric and evaluation configuration. Compare like-for-like settings, preserve the metric's unit and direction, and distinguish paper-reported results from independent reproduction. The best result recorded here is not a claim of exhaustive, current global coverage.

- [N-Queens problem on N-Queens](<https://www.sota2.com/research/sota/n-queens-problem-on-n-queens.md>): N-Queens Problem; N-Queens; Mean: 9.792.

## Original sources and implementation

[Original paper](<https://arxiv.org/abs/2512.04139>)

[PDF](<https://arxiv.org/pdf/2512.04139.pdf>)