Hello Youssef, Mahmoud et ALL
The Bit Mask solution is quicker than the Back Tracker
Would you believe 5860 X faster than the Ring-Original
Attached
Queens-N.ring -- no change
nqueens_solver.c -- Bit Mask version
CFFI Bit Mask: 7 msec 5860 X 160 X
CFFI Back Tracker: 97 msec 423 X 14 X
Ring-Bit Mask: 1123 msec 36 X 1 X
Ring-Original : 41022 msec 1 X
==============================
C:\MyStuff\AA-Queens-CFFI>ring.exe Queens-N.ring
Enter value of n : 12
Counting N-Queens solutions for n = 12 ...
Total solutions : 14200
End millisec : 3025
Start millisec : 3018
Total millisec : 7 <<<===
Total seconds : 0.01
Exiting of the program...
==============================
Different Approach
___________________Old (backtracking)___________________New (bitmask)
Conflict check
Loop over all previous queens
Zero — bitmasks do it instantly
Memory
malloc array of columns
None — 3 integers on the stack
Operations per step
O(k) comparisons
2 bitwise ops (&, ~)
Expected speedup
baseline
~3–5× faster
============================
============================
// Queens-N.ring (ring-cffi accelerated version)
// nqueens_solver.c - Bitmask backtracking N-Queens solver
#ifdef _MSC_VER
#define EXPORT __declspec(dllexport)
#else
#define EXPORT
#endif
static long solution_count;
/*
* backtrack(colMask, diag1, diag2, all)
* Direct C translation of the Ring bitmask backtrack() function.
*/
static void backtrack(unsigned int colMask,
unsigned int diag1,
unsigned int diag2,
unsigned int all)
{
unsigned int free_bits, bit;
/* colMask == all means every column has a queen -> solution */
if (colMask == all) {
solution_count++;
return;
}
/* available positions: free columns with no diagonal conflict */
free_bits = all & ~(colMask | diag1 | diag2);
while (free_bits) {
/* pick the lowest set bit */
bit = free_bits & (-(int)free_bits);
/* remove this bit from free_bits */
free_bits -= bit;
/* recurse with updated column and diagonal masks */
backtrack(
colMask | bit,
(diag1 | bit) << 1,
(diag2 | bit) >> 1,
all
);
}
}
/*
* nqueens_count(n)
* Returns the total number of solutions for an n x n board.
* Called from Ring via ring-cffi.
*/
EXPORT long nqueens_count(int n)
{
unsigned int all;
if (n <= 0 || n > 31) return 0;
all = (1u << n) - 1u; /* n bits set, same as Ring: (1 << n) - 1 */
solution_count = 0;
backtrack(0, 0, 0, all);
return solution_count;
}
=============================
Regards
Bert Mariani