Abstract

The N-queens problem is to place n queens on an n x n chessboard such that no two queens attack each other. This problem is commonly used as a benchmark for algorithms that solve constraint satisfaction problems (CSP).

This paper describes a novel parallel algorithm for the N-queens problem. The algorithm finds a solution by performing a probabilistic parallel search. By using n processors, its running time is O(log^2n). The algorithm demonstrates a new practical approach for solving large scale CSP on parallel computers.