Solving Martin Gardner's chess problem using simulated annealing

I've found this in the Martin Gardner's "The Colossal Book of Short Puzzles and Problems" book:

(It also appears in his earlier "The Unexpected Hanging and Other Mathematical Diversions" book.)

The problem to find such a placement of chess pieces, so that maximum of squares are under attack. Another variant is: minimum squares under attack. Also: one variant is when bishops can share the same color. Another variant is when you have opposite colored bishops.

This is my simulated annealing solver, with the code been shamelessly stolen from the GNU Scientific Library library.

My solutions coincide with Gardner's.

Maximum: all 64 squares attacked:
|.|.|.|.|.|.|.|R|  |.|.|.|.|.|.|.|R|  |.|.|.|.|.|.|.|.|  |R|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|N|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|K|.|.|.|N|.|  |.|K|N|.|.|.|.|.|  |.|N|.|.|.|.|.|.|
|.|.|.|B|Q|B|.|.|  |.|.|.|B|.|.|.|.|  |.|.|.|B|Q|B|.|.|  |.|.|.|.|.|.|N|K|
|.|K|N|.|.|.|.|.|  |.|.|.|.|B|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|B|Q|B|.|.|
|.|.|.|.|.|.|.|N|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|N|.|.|.|R|.|  |R|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|R|.|.|.|.|.|.|.|  |Q|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|R|  |.|R|.|.|.|.|.|.|

(You can clearly see that some solutions are symmetric to each other.)

Maximum: 63 squares attacked, opposite-colored bishops are used:

|.|.|.|.|.|.|.|R|  |.|.|.|.|.|.|R|.|  |.|.|.|.|K|.|.|.|  |.|.|Q|.|.|.|.|B|
|.|.|.|.|.|Q|.|.|  |.|.|.|.|.|.|.|Q|  |.|.|.|.|N|.|.|.|  |.|.|.|.|.|.|.|R|
|.|.|.|.|.|.|R|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|K|.|.|B|.|.|.|  |.|.|.|.|.|B|.|.|  |.|.|.|.|.|B|.|.|
|.|.|.|.|.|.|.|.|  |.|.|B|.|.|.|.|.|  |.|.|.|.|.|B|.|.|  |.|.|N|.|.|.|.|.|
|N|B|.|N|K|.|.|.|  |.|.|.|.|.|N|.|.|  |.|.|.|N|.|.|.|R|  |.|.|N|.|.|.|K|.|
|.|B|.|.|.|.|.|.|  |.|.|N|.|.|.|.|.|  |.|Q|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|R|.|.|  |R|.|.|.|.|.|.|.|  |.|R|.|.|.|.|.|.|

Attacked squares:  Attacked squares:  Attacked squares:  Attacked squares:
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|.|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|.|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|.|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|.|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|

Minimum: 16 squares attacked:

|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|N|
|.|.|.|.|.|.|K|R|
|.|.|.|.|.|N|R|Q|
|.|.|.|.|.|.|B|B|

Attacked squares:
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|*|.|
|.|.|.|.|.|*|.|.|
|.|.|.|.|*|*|*|*|
|.|.|.|*|.|*|*|*|
|.|.|.|.|.|*|*|*|
|.|.|.|*|.|.|*|*|

What about bruteforce? You would need to enumerate $\approx 64^8 = 281474976710656$ positions.

I always wanted to know, how many bishops you have to use to cover all 64 squares? It's 10.

Maximum:           Minimum:
|.|.|.|.|.|.|.|.|  |.|.|.|.|B|.|B|.|
|.|.|.|B|.|.|.|.|  |.|.|.|.|.|B|.|B|
|.|.|.|.|.|B|.|.|  |.|.|.|.|.|.|B|.|
|.|.|B|B|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|B|B|B|B|.|  |B|.|.|.|.|.|.|.|
|.|.|.|B|.|.|.|.|  |.|B|.|.|.|.|.|.|
|.|.|.|B|.|.|.|.|  |B|.|B|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|B|.|.|.|.|.|.|

Attacked squares:  Attacked squares:
|*|*|*|*|*|*|*|*|  |.|.|.|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |.|.|.|*|.|*|.|*|
|*|*|*|*|*|*|*|*|  |.|.|*|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|*|.|*|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|.|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|.|.|.|
|*|*|*|*|*|*|*|*|  |*|.|*|.|.|.|.|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|.|.|.|
attacked_total=64  attacked_total=21

Bruteforce? $\approx 64^{10} = 1152921504606846976$ positions.

How many knights you need to cover 64 squares? It's 14:

Maximum:           Minimum:
|.|.|.|.|.|.|.|.|  |N|.|N|.|N|.|.|.|
|.|.|N|.|.|N|.|.|  |.|.|.|.|.|.|.|.|
|.|.|N|N|N|N|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|N|.|N|.|.|.|N|
|.|.|N|N|N|N|.|.|  |N|.|.|.|N|.|.|.|
|.|N|N|.|.|N|N|.|  |.|.|.|.|.|.|.|N|
|.|.|.|.|.|.|.|.|  |N|.|.|.|N|.|.|.|
|.|.|.|.|.|.|.|.|  |.|N|.|N|.|.|.|N|

Attacked squares:  Attacked squares:
|*|*|*|*|*|*|*|*|  |.|.|.|.|.|.|.|.|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|*|.|.|
|*|*|*|*|*|*|*|*|  |.|.|*|.|.|.|*|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|*|.|.|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |.|*|.|*|.|*|.|.|
|*|*|*|*|*|*|*|*|  |.|.|*|.|.|.|*|.|
attacked_total=64  attacked_total=21

Bruteforce? $\approx 64^{14} = 19342813113834066795298816$ positions.

How many queens? 5.

Maximum:           Minimum:
|.|.|.|.|.|.|.|.|  |Q|.|Q|.|Q|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|Q|.|.|Q|.|.|Q|.|  |.|.|Q|.|Q|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|Q|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|Q|.|.|.|  |.|.|.|.|.|.|.|.|

Attacked squares:  Attacked squares:
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|.|.|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|*|*|*|*|.|*|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |*|*|*|.|*|*|.|*|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|*|.|
|*|*|*|*|*|*|*|*|  |*|.|*|.|*|.|.|*|
attacked_total=64  attacked_total=47

Bruteforce? $\approx 64^5 = 1073741824$ positions, that would be easy to do.

4 queens' placement demonstrates nice patterns:

Maximum:           Minimum:
|.|.|.|.|.|.|.|.|  |Q|.|.|.|.|.|.|Q|
|.|.|.|.|.|.|Q|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|Q|.|Q|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|Q|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |Q|.|.|.|.|.|.|Q|

Attacked squares:  Attacked squares:
|*|*|.|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
|*|*|*|*|*|*|*|*|  |*|*|.|.|.|.|*|*|
|*|*|*|*|*|*|*|*|  |*|.|*|.|.|*|.|*|
|*|*|*|*|*|*|*|*|  |*|.|.|*|*|.|.|*|
|*|*|*|*|*|*|*|*|  |*|.|.|*|*|.|.|*|
|*|*|*|*|*|*|*|*|  |*|.|*|.|.|*|.|*|
|*|*|.|*|*|*|*|*|  |*|*|.|.|.|.|*|*|
|*|*|.|*|*|*|*|*|  |*|*|*|*|*|*|*|*|
attacked_total=61  attacked_total=40

And if I only use one knight, one bishop, one rook, one queen, one king:

Maximum:           Minimum:
|.|.|.|.|.|.|.|R|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|N|.|Q|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|N|
|.|.|B|.|.|K|.|.|  |.|.|.|.|.|.|B|R|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|K|Q|

Attacked squares:  Attacked squares:
|*|*|*|*|*|*|*|*|  |*|.|.|.|.|.|.|.|
|*|.|.|*|.|.|*|*|  |.|*|.|.|.|.|.|.|
|*|*|*|*|.|*|*|*|  |.|.|*|.|.|.|.|.|
|.|.|*|*|*|*|.|*|  |.|.|.|*|.|.|*|.|
|*|*|*|.|*|*|*|*|  |.|.|.|.|*|*|.|.|
|.|*|*|*|*|*|*|*|  |.|.|.|.|.|*|.|*|
|*|*|*|*|*|*|*|*|  |.|.|.|.|.|*|*|*|
|*|*|.|*|*|*|*|*|  |.|.|.|.|.|*|*|*|
attacked_total=53  attacked_total=15

Two knights and two bishops:

Maximum:           Minimum:           Minimum (opposite-colored bishops):
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|B|  |B|.|.|.|.|.|.|B|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|N|.|  |.|N|.|.|.|.|N|.|
|.|.|.|N|N|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|B|B|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |.|N|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|.|.|.|.|.|.|  |B|.|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|

Attacked squares:  Attacked squares:  Attacked squares:
|*|.|*|*|*|*|.|*|  |.|.|.|.|*|.|.|.|  |.|.|.|*|*|.|.|.|
|*|*|*|.|.|*|*|*|  |.|.|.|.|.|.|*|.|  |.|*|.|.|.|.|*|.|
|.|*|*|.|.|*|*|.|  |.|.|.|.|*|.|.|.|  |.|.|.|*|*|.|.|.|
|.|*|*|*|*|*|*|.|  |.|.|.|.|.|*|.|*|  |*|.|*|.|.|*|.|*|
|.|.|*|*|*|*|.|.|  |*|.|*|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|.|*|*|*|*|.|.|  |.|.|.|*|.|.|.|.|  |.|.|.|.|.|.|.|.|
|.|*|*|.|.|*|*|.|  |.|*|.|.|.|.|.|.|  |.|.|.|.|.|.|.|.|
|*|*|.|.|.|.|*|*|  |.|.|.|*|.|.|.|.|  |.|.|.|.|.|.|.|.|
attacked_total=38  attacked_total=10  attacked_total=10

The program

.. in pure C, get it here, with no external dependencies, compile: gcc find.c -O3 -lm

Further work

Weed out symmetrical solutions and leave only unique ones.

UPD: at Reddit: 1, 2.

List of my other blog posts.

Yes, I know about these lousy Disqus ads. Please use adblocker. I would consider to subscribe to 'pro' version of Disqus if the signal/noise ratio in comments would be good enough.