8 Queens problem - All 92 FENs

Discussion of chess software programming and technical issues.

Moderator: Ras

JohnWoe
Posts: 529
Joined: Sat Mar 02, 2013 11:31 pm

8 Queens problem - All 92 FENs

Post by JohnWoe »

Still warmed up after Advent Of Code -24. Decided to solve 8 queens problem for fun:
Here are the 92 FENs where 8 queens are placed so they don't ray each other. Hopefully correct :lol:
Program: https://github.com/SamuraiDangyo/Mayhem8Queens

And the 92 FENs: This is what the program outputs. Nothing else.
Solved: in 1946 milliseconds

Code: Select all

Mayhem8Queens 1.0

Solving Queens 8 problem

...

1: 3Q4/1Q6/6Q1/2Q5/5Q2/7Q/4Q3/Q7 w - - 0 1
2: 4Q3/1Q6/3Q4/6Q1/2Q5/7Q/5Q2/Q7 w - - 0 1
3: 2Q5/4Q3/1Q6/7Q/5Q2/3Q4/6Q1/Q7 w - - 0 1
4: 2Q5/5Q2/3Q4/1Q6/7Q/4Q3/6Q1/Q7 w - - 0 1
5: 4Q3/6Q1/Q7/2Q5/7Q/5Q2/3Q4/1Q6 w - - 0 1
6: 3Q4/5Q2/7Q/2Q5/Q7/6Q1/4Q3/1Q6 w - - 0 1
7: 2Q5/5Q2/7Q/Q7/3Q4/6Q1/4Q3/1Q6 w - - 0 1
8: 4Q3/2Q5/7Q/3Q4/6Q1/Q7/5Q2/1Q6 w - - 0 1
9: 4Q3/6Q1/3Q4/Q7/2Q5/7Q/5Q2/1Q6 w - - 0 1
10: 3Q4/Q7/4Q3/7Q/5Q2/2Q5/6Q1/1Q6 w - - 0 1
11: 2Q5/5Q2/3Q4/Q7/7Q/4Q3/6Q1/1Q6 w - - 0 1
12: 3Q4/6Q1/4Q3/2Q5/Q7/5Q2/7Q/1Q6 w - - 0 1
13: 5Q2/3Q4/1Q6/7Q/4Q3/6Q1/Q7/2Q5 w - - 0 1
14: 5Q2/3Q4/6Q1/Q7/7Q/1Q6/4Q3/2Q5 w - - 0 1
15: Q7/6Q1/3Q4/5Q2/7Q/1Q6/4Q3/2Q5 w - - 0 1
16: 5Q2/7Q/1Q6/3Q4/Q7/6Q1/4Q3/2Q5 w - - 0 1
17: 5Q2/1Q6/6Q1/Q7/3Q4/7Q/4Q3/2Q5 w - - 0 1
18: 3Q4/6Q1/Q7/7Q/4Q3/1Q6/5Q2/2Q5 w - - 0 1
19: 4Q3/7Q/3Q4/Q7/6Q1/1Q6/5Q2/2Q5 w - - 0 1
20: 3Q4/7Q/Q7/4Q3/6Q1/1Q6/5Q2/2Q5 w - - 0 1
21: 1Q6/6Q1/4Q3/7Q/Q7/3Q4/5Q2/2Q5 w - - 0 1
22: Q7/6Q1/4Q3/7Q/1Q6/3Q4/5Q2/2Q5 w - - 0 1
23: 1Q6/4Q3/6Q1/3Q4/Q7/7Q/5Q2/2Q5 w - - 0 1
24: 3Q4/1Q6/6Q1/4Q3/Q7/7Q/5Q2/2Q5 w - - 0 1
25: 4Q3/6Q1/Q7/3Q4/1Q6/7Q/5Q2/2Q5 w - - 0 1
26: 5Q2/3Q4/Q7/4Q3/7Q/1Q6/6Q1/2Q5 w - - 0 1
27: 4Q3/Q7/3Q4/5Q2/7Q/1Q6/6Q1/2Q5 w - - 0 1
28: 4Q3/1Q6/5Q2/Q7/6Q1/3Q4/7Q/2Q5 w - - 0 1
29: 5Q2/2Q5/6Q1/1Q6/7Q/4Q3/Q7/3Q4 w - - 0 1
30: 1Q6/6Q1/2Q5/5Q2/7Q/4Q3/Q7/3Q4 w - - 0 1
31: 6Q1/2Q5/Q7/5Q2/7Q/4Q3/1Q6/3Q4 w - - 0 1
32: 4Q3/Q7/7Q/5Q2/2Q5/6Q1/1Q6/3Q4 w - - 0 1
33: Q7/4Q3/7Q/5Q2/2Q5/6Q1/1Q6/3Q4 w - - 0 1
34: 2Q5/5Q2/7Q/Q7/4Q3/6Q1/1Q6/3Q4 w - - 0 1
35: 5Q2/2Q5/Q7/6Q1/4Q3/7Q/1Q6/3Q4 w - - 0 1
36: 6Q1/4Q3/2Q5/Q7/5Q2/7Q/1Q6/3Q4 w - - 0 1
37: 6Q1/2Q5/7Q/1Q6/4Q3/Q7/5Q2/3Q4 w - - 0 1
38: 4Q3/2Q5/Q7/6Q1/1Q6/7Q/5Q2/3Q4 w - - 0 1
39: 1Q6/4Q3/6Q1/Q7/2Q5/7Q/5Q2/3Q4 w - - 0 1
40: 2Q5/5Q2/1Q6/4Q3/7Q/Q7/6Q1/3Q4 w - - 0 1
41: 5Q2/Q7/4Q3/1Q6/7Q/2Q5/6Q1/3Q4 w - - 0 1
42: 7Q/2Q5/Q7/5Q2/1Q6/4Q3/6Q1/3Q4 w - - 0 1
43: 1Q6/7Q/5Q2/Q7/2Q5/4Q3/6Q1/3Q4 w - - 0 1
44: 4Q3/6Q1/1Q6/5Q2/2Q5/Q7/7Q/3Q4 w - - 0 1
45: 2Q5/5Q2/1Q6/6Q1/4Q3/Q7/7Q/3Q4 w - - 0 1
46: 5Q2/1Q6/6Q1/Q7/2Q5/4Q3/7Q/3Q4 w - - 0 1
47: 2Q5/6Q1/1Q6/7Q/5Q2/3Q4/Q7/4Q3 w - - 0 1
48: 5Q2/2Q5/6Q1/1Q6/3Q4/7Q/Q7/4Q3 w - - 0 1
49: 3Q4/1Q6/6Q1/2Q5/5Q2/7Q/Q7/4Q3 w - - 0 1
50: 6Q1/Q7/2Q5/7Q/5Q2/3Q4/1Q6/4Q3 w - - 0 1
51: Q7/5Q2/7Q/2Q5/6Q1/3Q4/1Q6/4Q3 w - - 0 1
52: 2Q5/7Q/3Q4/6Q1/Q7/5Q2/1Q6/4Q3 w - - 0 1
53: 5Q2/2Q5/6Q1/3Q4/Q7/7Q/1Q6/4Q3 w - - 0 1
54: 6Q1/3Q4/1Q6/7Q/5Q2/Q7/2Q5/4Q3 w - - 0 1
55: 3Q4/5Q2/7Q/1Q6/6Q1/Q7/2Q5/4Q3 w - - 0 1
56: 1Q6/5Q2/Q7/6Q1/3Q4/7Q/2Q5/4Q3 w - - 0 1
57: 1Q6/3Q4/5Q2/7Q/2Q5/Q7/6Q1/4Q3 w - - 0 1
58: 2Q5/5Q2/7Q/1Q6/3Q4/Q7/6Q1/4Q3 w - - 0 1
59: 5Q2/2Q5/Q7/7Q/3Q4/1Q6/6Q1/4Q3 w - - 0 1
60: 7Q/3Q4/Q7/2Q5/5Q2/1Q6/6Q1/4Q3 w - - 0 1
61: 3Q4/7Q/Q7/2Q5/5Q2/1Q6/6Q1/4Q3 w - - 0 1
62: 1Q6/5Q2/7Q/2Q5/Q7/3Q4/6Q1/4Q3 w - - 0 1
63: 6Q1/1Q6/5Q2/2Q5/Q7/3Q4/7Q/4Q3 w - - 0 1
64: 2Q5/5Q2/1Q6/6Q1/Q7/3Q4/7Q/4Q3 w - - 0 1
65: 3Q4/6Q1/2Q5/7Q/1Q6/4Q3/Q7/5Q2 w - - 0 1
66: 3Q4/7Q/4Q3/2Q5/Q7/6Q1/1Q6/5Q2 w - - 0 1
67: 2Q5/4Q3/7Q/3Q4/Q7/6Q1/1Q6/5Q2 w - - 0 1
68: 3Q4/1Q6/7Q/4Q3/6Q1/Q7/2Q5/5Q2 w - - 0 1
69: 4Q3/6Q1/1Q6/3Q4/7Q/Q7/2Q5/5Q2 w - - 0 1
70: 6Q1/3Q4/1Q6/4Q3/7Q/Q7/2Q5/5Q2 w - - 0 1
71: 7Q/1Q6/3Q4/Q7/6Q1/4Q3/2Q5/5Q2 w - - 0 1
72: 6Q1/1Q6/3Q4/Q7/7Q/4Q3/2Q5/5Q2 w - - 0 1
73: 4Q3/Q7/7Q/3Q4/1Q6/6Q1/2Q5/5Q2 w - - 0 1
74: 3Q4/Q7/4Q3/7Q/1Q6/6Q1/2Q5/5Q2 w - - 0 1
75: 4Q3/1Q6/7Q/Q7/3Q4/6Q1/2Q5/5Q2 w - - 0 1
76: 2Q5/6Q1/1Q6/7Q/4Q3/Q7/3Q4/5Q2 w - - 0 1
77: 2Q5/Q7/6Q1/4Q3/7Q/1Q6/3Q4/5Q2 w - - 0 1
78: 7Q/1Q6/4Q3/2Q5/Q7/6Q1/3Q4/5Q2 w - - 0 1
79: 2Q5/4Q3/1Q6/7Q/Q7/6Q1/3Q4/5Q2 w - - 0 1
80: 2Q5/4Q3/6Q1/Q7/3Q4/1Q6/7Q/5Q2 w - - 0 1
81: 4Q3/1Q6/3Q4/5Q2/7Q/2Q5/Q7/6Q1 w - - 0 1
82: 5Q2/2Q5/4Q3/7Q/Q7/3Q4/1Q6/6Q1 w - - 0 1
83: 4Q3/7Q/3Q4/Q7/2Q5/5Q2/1Q6/6Q1 w - - 0 1
84: 3Q4/1Q6/4Q3/7Q/5Q2/Q7/2Q5/6Q1 w - - 0 1
85: 3Q4/5Q2/Q7/4Q3/1Q6/7Q/2Q5/6Q1 w - - 0 1
86: 5Q2/2Q5/Q7/7Q/4Q3/1Q6/3Q4/6Q1 w - - 0 1
87: 4Q3/2Q5/Q7/5Q2/7Q/1Q6/3Q4/6Q1 w - - 0 1
88: 3Q4/1Q6/7Q/5Q2/Q7/2Q5/4Q3/6Q1 w - - 0 1
89: 5Q2/2Q5/4Q3/6Q1/Q7/3Q4/1Q6/7Q w - - 0 1
90: 5Q2/3Q4/6Q1/Q7/2Q5/4Q3/1Q6/7Q w - - 0 1
91: 3Q4/6Q1/4Q3/1Q6/5Q2/Q7/2Q5/7Q w - - 0 1
92: 4Q3/6Q1/1Q6/5Q2/2Q5/Q7/3Q4/7Q w - - 0 1

===============

Total:    92
Nodes:    30709079
NPS:      15780616
Time(ms): 1946
User avatar
towforce
Posts: 12157
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: 8 Queens problem - All 92 FENs

Post by towforce »

I am guessing you used tree generation. I think that 8 Queens problems are best resolved by SAT solvers or integer programming - but I'm not going to challenge you on this. :)
Want to attract exceptional people? Be exceptional.
User avatar
Eelco de Groot
Posts: 4633
Joined: Sun Mar 12, 2006 2:40 am
Full name:   Eelco de Groot

Re: 8 Queens problem - All 92 FENs

Post by Eelco de Groot »

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 It has a maximum of 128 program steps, 11 registers but that was just enough. You could do a lot with that. A bit like the old 8 bit chessprograms and semi assembler programming. But then with floating point possibilty, and all mathematical functions so math was much easier that way compared with assembler. I think the calcultor still runs but the last time I had new batteries installed, the big warehouse Vroom and Dreesman was still around, it was somewhere in the eighties or nineties of the previous century. As far as I can remember I had no new batteries installed after that but maybe memory fails me; and those batteries still worked a few years back :) With non volatile memory the calculator beats me there I think it's pretty amazing CMOS efficiency.


I checked, batteries still work LCD still legible.

Image
Debugging is twice as hard as writing the code in the first
place. Therefore, if you write the code as cleverly as possible, you
are, by definition, not smart enough to debug it.
-- Brian W. Kernighan
User avatar
towforce
Posts: 12157
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: 8 Queens problem - All 92 FENs

Post by towforce »

Eelco de Groot wrote: Thu Jan 16, 2025 8:56 am 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 It has a maximum of 128 program steps, 11 registers but that was just enough. You could do a lot with that. A bit like the old 8 bit chessprograms and semi assembler programming. But then with floating point possibilty, and all mathematical functions so math was much easier that way compared with assembler. I think the calcultor still runs but the last time I had new batteries installed, the big warehouse Vroom and Dreesman was still around, it was somewhere in the eighties or nineties of the previous century. As far as I can remember I had no new batteries installed after that but maybe memory fails me; and those batteries still worked a few years back :) With non volatile memory the calculator beats me there I think it's pretty amazing CMOS efficiency.


I checked, batteries still work LCD still legible.

Image

Excellent - you've even still got the keyboard overlays!

My first computer was a programmable calculator. It was great fun at the time - but the speed of execution was slow (about 30 steps per second). I immediately put it to use testing varieties of Martingale betting systems (link), starting them before bed, and by morning it would have worked its way through 5000 or so cycles (which was enough to discover that they didn't work). Now, my maths skill and tools is good enough to resolve expected outcomes for such systems without simulation.
Want to attract exceptional people? Be exceptional.
Martin Hertz
Posts: 63
Joined: Wed Mar 14, 2012 9:43 pm

Re: 8 Queens problem - All 92 FENs

Post by Martin Hertz »

Eelco de Groot wrote: Thu Jan 16, 2025 8:56 am 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
User avatar
towforce
Posts: 12157
Joined: Thu Mar 09, 2006 12:57 am
Location: Birmingham UK
Full name: Graham Laight

Re: 8 Queens problem - All 92 FENs

Post by towforce »

Martin Hertz wrote: Wed Jan 22, 2025 4:26 am
Eelco de Groot wrote: Thu Jan 16, 2025 8:56 am 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.
Want to attract exceptional people? Be exceptional.
Uri Blass
Posts: 10696
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: 8 Queens problem - All 92 FENs

Post by Uri Blass »

towforce wrote: Wed Jan 22, 2025 9:33 am
Martin Hertz wrote: Wed Jan 22, 2025 4:26 am
Eelco de Groot wrote: Thu Jan 16, 2025 8:56 am 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.

there are only 4 options for a queen in the first line(if you ignore symmetry)
and it seems for that I can solve it even manually without a computer in less than 1000 minutes and even old computers are more than 1000 times faster than me.

Here is a short proof that a1 c2 is impossible to complete to 8 queen by checking all possibilities for line 3:
a1 c2 e3->d6 only possible queen at line 6->g8 only possible queen at line 8->no possible queen at f file
a1 c2 f3(only 2 cases for line 4)
a1 c2 f3 b4->g5 only option for line 5->e6 only option for line 6->no option for line 7
a1 c2 f3 h4->b5 (only option for line 5)->no option for line 7
a1 c2 g3->b4(for line 4)->f7 for f file->no possibility for line 5.
a1 c2 h3(only 2 cases for line 4)
a1 c2 h3 b4 is impossible because no option for line 6
a1 c2 h3 f4->b6(for line 6)->e7(for line 7)->d5 for line 5->no option for line 8
Uri Blass
Posts: 10696
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: 8 Queens problem - All 92 FENs

Post by Uri Blass »

solved manually the a1 d2 case to be impossible

a1 d2 b3->2 options for f file f5 and f8
a1 d2 b3 f5-> no option for g file
a1 d2 b3 f8->h5 only option for rank 5->no option for g file
a1 d2 f3->2 option for rank 4 c4 and h4
a1 d2 f3 c4->no option for rank 5
a1 d2 f3 h4->c7 only option for rank 7->b5 only option for b file->g8 only option for rank 8->no option for rank 6
a1 d2 g3->2 options for rank 4 c4 and e4
a1 d2 g3 c4->b6 only option for rank 6->2 options for rank 7 and both are impossible because if e7 no option for rank 8 and if h7 no option for rank 5.
a1 d2 g3 e4->b6 only option for rank 6->h5 only option for rank 5->no option for rank 7.
a1 d2 h3 c4->no option for line 5
a1 d2 h3 e4->b6 only option for line 6->no option for line 5.
Uri Blass
Posts: 10696
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: 8 Queens problem - All 92 FENs

Post by Uri Blass »

a1 e2 3 options for line 3

a1 e2 b3 has 2 cases for rank 4 f4 and h4
a1 e2 b3 f4->c5 only option for line 5->g6 only option for line 5->no option for h file.
a1 e2 b3 h4 we have 2 cases for rank 5 c5 and f5 and in both of them no option for rank 8.

a1 e2 g3->b4 only option for line 4->2 options for line 5 d5 and f5
a1 e2 g3 b4 d5->no option for f file
a1 e2 g3 b4 f5->no option for rank 7
so a1 e2 g3 is impossible

a1 e2 h3 only 2 options for rank 4 b4 and f4.
a1 e2 h3 b4->f7 only option for f file->d8 only option for rank 8->no option for the g file
a1 e2 h3 f4->b7 only option for 7 file->c5 only option for rank 5->g6 only option for rank 6->d8 only option for rank 8.
found one solution a1 e2 h3 f4 c5 g6 b7 d8(practically I can choose every corner and a1 e2 and a1 b5 are symmetric so without symmetry I already found 8 solutions manually).
Uri Blass
Posts: 10696
Joined: Thu Mar 09, 2006 12:37 am
Location: Tel-Aviv Israel

Re: 8 Queens problem - All 92 FENs

Post by Uri Blass »

I will not continue now but in less than 80 minutes I could find 8 solutions out of 92 and I believe I can find all of them in less than 1000 minutes.