踩地雷的數字 - 拼圖

※ 引述《EIORU ()》之銘言：
初級版
9x9的踩地雷 共10顆
地雷隨機分佈下
當八個方向一格內有X個地雷就有數字X
(1)數字總和最大為多少? ★
(2)數字積最大為多少? ★★

作為對照:

1207959552 = 2^27 * 3^2

1934917632 = 2^15 * 3^10



叫程式找到三組排法，結果出乎意料的大，


0 0 0 0 1 1 2 1 1
0 0 0 0 1 ■ 3 ■ 2
0 0 0 0 2 2 4 ■ 2
0 0 0 0 2 ■ 4 2 2
0 0 0 0 2 ■ 3 ■ 1
0 0 0 0 2 2 4 2 2
0 0 0 0 2 ■ 4 ■ 2
0 0 0 0 2 ■ 4 ■ 2
0 0 0 0 1 1 2 1 1
乘積 = 2415919104 = 2^ 28 * 3^ 2

0 0 0 0 0 0 0 0 0
0 1 2 2 2 2 2 1 0
0 1 ■ ■ 2 ■ ■ 1 0
0 2 3 4 3 4 3 2 0
0 1 ■ 2 ■ 3 ■ 2 0
0 2 2 4 2 4 ■ 2 0
0 1 ■ 2 ■ 2 1 1 0
0 1 1 2 1 1 0 0 0
0 0 0 0 0 0 0 0 0
乘積 = 2717908992 = 2^ 25 * 3^ 4

0 0 0 0 0 0 0 0 0
0 1 2 2 2 2 2 1 0
0 1 ■ ■ 2 ■ ■ 1 0
0 2 3 4 3 4 3 2 0
0 1 ■ 2 ■ 2 ■ 1 0
0 2 2 4 2 4 2 2 0
0 1 ■ 2 ■ 2 ■ 1 0
0 1 1 2 1 2 1 1 0
0 0 0 0 0 0 0 0 0
乘積 = 3623878656 = 2^ 27 * 3^ 3


程式的大綱是

1. 隨機產生一百組地圖作為親代

2. 對每個親代作以下操作，以逐步得到改進

> 10顆地雷往八個方向(國王走法)作「擾動」最多得到80種合理的新「子代」

> 取最高(進化的)的替換原先的親代。

> 萬一無法再做任何改進，(進化死胡同) 則隨機重取一組代替親代。

3. 100組都調整過後輸出一個乘積最大的結果

4. 重覆2 & 3


雖然不保證最終會算出所有排法的最大值，但是這大概是僅次於枚舉的方法了。

而 C(81,10) = 1.8 * 10^12 就不太可能枚舉 =v=

繼續跑程式...

--