6

Solving Martin Gardner's chess problem using simulated annealing

 3 years ago
source link: https://yurichev.com/news/20200224_Martin_Gardner_and_chess/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
Solving Martin Gardner's chess problem using simulated annealing

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 coincides 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 ≈648=281474976710656≈648=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? ≈6410=1152921504606846976≈6410=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? ≈6414=19342813113834066795298816≈6414=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? ≈645=1073741824≈645=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.

dot.png?body_20200224_Martin_Gardner_and_chess

List of my other blog posts.


report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK