Comment #0 by bearophile_hugs — 2011-04-14T18:14:14Z
This program generates a "stack overflow" with DMD2 2.052, but it compiles and runs correctly with DMD1 v1.026.
The problem appears to be here:
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong cols) {
Removing the ref avoids the problem:
uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) {
Additionally: this program (with enum result=nqueen(10);) can also be used as one benchmark for CTFE speed (if run at runtime it allocates no heap memory).
import std.c.stdio: printf;
bool test(int k, int j, ulong diag45, ulong diag135, ulong cols) {
return ((cols & (1UL << j)) +
(diag135 & (1UL << (j + k))) +
(diag45 & (1UL << (32 + j - k))) ) == 0;
}
void mark(int k, int j, ref ulong diag45, ref ulong diag135, ref ulong cols) {
cols ^= (1UL << j);
diag135 ^= (1UL << (j + k));
diag45 ^= (1UL << (32 + j - k));
}
//uint solve(int niv, int dx, ulong diag45, ulong diag135, ulong cols) { // OK
uint solve(int niv, int dx, ref ulong diag45, ref ulong diag135, ref ulong cols) { // stack overflow
uint solutions_found;
if (niv) {
for (int i = 0; i < dx; i++)
if (test(niv, i, diag45, diag135, cols)) {
mark(niv, i, diag45, diag135, cols);
solutions_found += solve(niv - 1, dx, diag45, diag135, cols);
mark(niv, i, diag45, diag135, cols);
}
} else {
for (int i = 0; i < dx; i++)
solutions_found += test(0, i, diag45, diag135, cols);
}
return solutions_found;
}
ulong nqueen(int n) {
ulong diag45 = 0; // / diagonal bitboard
ulong diag135 = 0; // \ diagonal bitboard
ulong cols = 0; // column bitboard
return solve(n - 1, n, diag45, diag135, cols);
}
const ulong result = nqueen(8);
void main() {
// NQUEENS: 1, 0, 0, 2, 10, 4, 40, 92, 352, 724,
// 2_680, 14_200, 73_712, 365_596
printf("%lld\n", result);
}
Comment #1 by clugdbug — 2011-05-17T14:04:11Z
This is not useful as a benchmark.
Reduced test case:
void test5845(ulong cols) {}
uint solve(bool niv, ref ulong cols) {
if (niv)
solve(false, cols);
else
test5845(cols);
return 65;
}
ulong nqueen(int n) {
ulong cols = 0;
return solve(true, cols);
}
static assert(nqueen(2) == 65);
Comment #2 by bearophile_hugs — 2011-05-17T16:03:23Z
(In reply to comment #1)
> This is not useful as a benchmark.
Do you want to tell me why?
Comment #3 by clugdbug — 2011-05-18T01:31:35Z
(In reply to comment #2)
> (In reply to comment #1)
> > This is not useful as a benchmark.
>
> Do you want to tell me why?
Because a simpler benchmark that tests exactly the same things is:
int foo(int n) {
for (int i=0; i< n; ++i) {}
return 0;
}
static assert(foo(10000));
Your code is longer but it tests NOTHING else.