8 Queens problem - All 92 FENs

[mar]

nice, 2 seconds is very very slow though

if you come the the realization that you only need to quickly generate permutations
and the fact that you can use bitmask and bitscan, you can generalize to even much bigger boards,
like I just got 14'772'512 positions for 16 queens on a 16x16 board,
then you can realize you can also track diagonal masks incrementally
this can be simplifier further: you don't even need bsf/ctz if you only need the count

Code: Select all

constexpr int N = 16;

int perm[N];

ulong cnt = 0;

void dump_perm()
{
	++cnt;
/*	for (int i : N)
		"%d ", 1+perm[i];
	"\n";*/
}

void gen_perm(ulong mask, ulong diag1, ulong diag2, int n)
{
	auto tmp = mask & ~(diag1 | diag2);

	while (tmp)
	{
		auto bit = bsf(tmp);
		tmp &= tmp-1;

		perm[n] = bit;

		auto zmask = 1ul << bit;
		auto nmask = mask & ~zmask;

		auto d1 = diag1 | zmask;
		auto d2 = diag2 | zmask;

		if (nmask)
			gen_perm(nmask, d1 << 1, d2 >> 1, n+1);
		else
			dump_perm();
	}
}

void main()
{
	ulong mask = (1ul << N)-1;
	gen_perm(mask, 0, 0, 0);
	"count: %t\n", cnt;
}

[towforce]

It was fun to try to solve the problem, many years ago with a programmable calculator, in this case my cherished Casio FX 501 P

Here is a very long speed benchmark list of programmable calculators und pocket computers solving 8 queens, including the FX-502P: https://www.hpmuseum.org/cgi-sys/cgiwra ... i?read=700

Wow - that's been around 18 years and I never knew! Mine, the TI-58C, comes in at just under an hour.

I do not understand why some computer needs even one minute to solve the easy 8 queen problem.
I think even computer from 1985 should be able to solve it in less than a minute.

The programmable calculators of the mid to late 1970s were impressively slow: My TI-58C delivered fewer than 30 program steps per second. Generating a single random number (using the linear congruential method, which is considered primitive today), would take the best part of a second. A combinatorial puzzle with 4 dice (6^4=1296 permutations) would take a day to solve. However, they were the only type of computer device I had any realistic hope of owning at the time, and I used mine heavily.

[Martin Hertz]

2 seconds is very very slow though

Indeed. What strikes me are the 30709079 nodes. The algorithm on the benchmark list needs only 15720 nodes for all solutions.

[Uri Blass]

nice, 2 seconds is very very slow though

if you come the the realization that you only need to quickly generate permutations
and the fact that you can use bitmask and bitscan, you can generalize to even much bigger boards,
like I just got 14'772'512 positions for 16 queens on a 16x16 board,
then you can realize you can also track diagonal masks incrementally
this can be simplifier further: you don't even need bsf/ctz if you only need the count

Code: Select all

constexpr int N = 16;

int perm[N];

ulong cnt = 0;

void dump_perm()
{
	++cnt;
/*	for (int i : N)
		"%d ", 1+perm[i];
	"\n";*/
}

void gen_perm(ulong mask, ulong diag1, ulong diag2, int n)
{
	auto tmp = mask & ~(diag1 | diag2);

	while (tmp)
	{
		auto bit = bsf(tmp);
		tmp &= tmp-1;

		perm[n] = bit;

		auto zmask = 1ul << bit;
		auto nmask = mask & ~zmask;

		auto d1 = diag1 | zmask;
		auto d2 = diag2 | zmask;

		if (nmask)
			gen_perm(nmask, d1 << 1, d2 >> 1, n+1);
		else
			dump_perm();
	}
}

void main()
{
	ulong mask = (1ul << N)-1;
	gen_perm(mask, 0, 0, 0);
	"count: %t\n", cnt;
}

16 is too easy
If you want something new try 28

https://en.wikipedia.org/wiki/Eight_queens_puzzle

I see in the link the following table

Code: Select all

1	1	1
2	0	0
3	0	0
4	1	2
5	2	10
6	1	4
7	6	40
8	12	92
9	46	352
10	92	724
11	341	2,680
12	1,787	14,200
13	9,233	73,712
14	45,752	365,596
15	285,053	2,279,184
16	1,846,955	14,772,512
17	11,977,939	95,815,104
18	83,263,591	666,090,624
19	621,012,754	4,968,057,848
20	4,878,666,808	39,029,188,884
21	39,333,324,973	314,666,222,712
22	336,376,244,042	2,691,008,701,644
23	3,029,242,658,210	24,233,937,684,440
24	28,439,272,956,934	227,514,171,973,736
25	275,986,683,743,434	2,207,893,435,808,352
26	2,789,712,466,510,289	22,317,699,616,364,044
27	29,363,495,934,315,694	234,907,967,154,122,528

[mar]

Indeed. What strikes me are the 30709079 nodes. The algorithm on the benchmark list needs only 15720 nodes for all solutions.

yes. the algorithm I presented does 2056 inner cycles of the while loop ("nodes") for 8 queens

[Ajedrecista]

Hello Uri:

16 is too easy
If you want something new try 28

https://en.wikipedia.org/wiki/Eight_queens_puzzle

[...]

It took more than one year to compute Q(27) (source) in a distributed project, from what I understood. Other high numbers took even more (source, look into EXTENTIONS). This is too much time for a wannabe fast, recreative project!

There is neither known recurrence relation nor generating function so far, so Q(28) and surely higher values must be computed in a try to get some relation or function, which is not sure it exists at all.

There are other chess-related sequences where relations and even generating functions are known, such as nonintersecting (or self-avoiding) rook paths joining opposite corners of k×N boards (for example 3×N, 4×N, 5×N, 6×N and 7×N). Just as an example, taking the sequence R5×N(n), I was able to compute R5×N(50) = 554,463,323,757,096,922,520,674,423,477,990,122,778,083,506,296 ~ 5.54 × 10^47 for a 5×50 board in less than a minute using a 32-bit, single core programme in a CPU from 2010 without computing intermediate values. We are far from this point with the N-queen problem.

Just for fun, the factorization of R5×N(50) in less than 1 ms:

Code: Select all

554,463,323,757,096,922,520,674,423,477,990,122,778,083,506,296
=
2^3
×
11
×
19
×
3,347
×
298,801
×
331,587,989,847,932,411,031,587,715,656,517,269

Regards from Spain.

Ajedrecista.