破解＂八皇后問題＂

"八皇后問題"，是一個古老而著名的問題，裡面的"皇后"指的是西洋棋裡面的一種棋子,可以橫著豎著斜著走(所以比中國象棋的車威力更大)。該問題是棋手馬克斯·貝瑟爾於1848年提出：在8×8格的西洋棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處於同一行、同一列或同一斜線上，問有多少種擺法?雖然是來源自西洋棋,但是卻可以抽象為一個純數學問題,所以有不少數學家都曾涉足鑽研:其中包括大名鼎鼎的數學王子高斯!據說高斯認為有76種方案,如果屬實,那麼該問題真是讓老司機都折腰了(正確答案應該是92)

如果這個問題擺在我們面前,該怎麼辦呢?

都9102年了,當然首選計算機了啊.

那麼計算機怎麼來呢?

暴力破解嗎?

每個可能的組合暴力輪一遍,

然後篩選出合格的就行了,

總條件數:

64*63*62*61*60*59*58*57約為178.46萬億

看著計算機也夠嗆啊~

然後有同學說只要組合就行了,不用排列?

ok,good idea!

那麼64*63*62*61*60*59*58*57/(8*7*6*5*4*3*2*1)

=44.26億,貌似也可以勉強暴力破解了,

不過計算機怎麼地也得跑個大半天吧,

還能不能更快點呢?

面對這個問題,很自然的還有另一種思路:

分支查找法.

先擺好第一個皇后,然後把相應的行列斜線都標記一下,

然後在剩下位置中隨機挑選一個位置放第二個皇后,

然後再把相應的行列斜線都標記一下,

然後放第三個...

....

到了第八個還有位置可以放,就得到了一個ok的組合

否則就返回上一個結點走另一條路

...

所有都走完之後,所有的解都出來了.

這個問題可以避免很多無意義的組合,

看似還是可以的.

但是,複雜啊!!!

如果只是為了求個解,有必要弄那麼複雜嗎?

還有更簡單的方案嗎?

更簡單的方案還是有的!

這樣就得深入分析這個八皇后問題了.

仔細一想不難發現,同一行肯定不能有兩個,

那麼行號的集合肯定是不多不少的{1,2,3,4,5,6,7,8}

同一列也不能有兩個皇后,

所以列號也xxx的{1,2,3,4,5,6,7,8}

既然都是1~8那麼巧,

那就可以跨出一大步:

固定行號為順序的1,2,3,4,5,6,7,8

只考慮列號的變化為j1,j2,j3,j4.j5,j6,j7,j8

(其中j1~j8是1~8的一個排列)

這樣總的變化數只是列號的排列數,

顯然是8!=4萬320

才4w多點啊,

這麼點玩意對於計算機來說算個毛線啊有木有,

再怎麼垃圾的計算機都可以秒出啊是不是呢,

所以這個問題考慮到這就變得非常簡單了:

暴力遍歷8!+過濾有效組合

就這麼簡單罷了

所以得分兩步走:第一步"暴力遍歷8!"

先想想怎麼暴力遍歷8!吧,

理論上是個找所有字典序的問題,

雖說不怎麼複雜吧,

也沒那麼簡單,

還是得繞一會的,

但是鑑於問題規模這麼小,

還繞個毛線呢,

除了暴力組合我們還可以隨機抽樣啊!

瘋狂隨機,把符合的留下來就行.

雖然隨機一次不一定碰到樣本,

那我隨機10次,100次總可以了吧,

雖然概率上隨機1億億億次都有可能不能完全抽樣,

但這種概率小的幾乎可以無視了,

這樣問題就大大化簡了,

好了,就這麼幹吧

那第二個問題,如何判斷一個組合是否是ok的?

也就是說給了8個坐標,如何判斷是否滿足要求呢?

其實行列已經保證不重合了,

只用管斜線就行了.

雖然這個問題很簡單,

大不了數一數每條斜線就知道了,

也沒幾個計算量,

但是能優化還是多少優化一下吧.

我的方案是:

(先看圖吧:粉色都屬於紅色方塊的斜線範圍,藍色方塊不屬於)

同在一個斜線的兩個方塊,坐標記為(x1,y1),(x2,y2)

不難得到|x1-x2|=|y1-y2|

一想到這個,這個問題也化簡不少了呢

整個問題解決起來就更輕鬆了

下面就直接上代碼了:

主幹流程部分:

判斷一個組合是否ok的部分:

代碼跑的很快的,即使使用不求效率的python腳本語言編寫的程序,

也要不了幾秒鐘就出結果了.

所有結果一共92種,

分別如下(列號):

15863724

16837425

17468253

17582463

24683175

25713864

25741863

26174835

26831475

27368514

27581463

28613574

31758246

35281746

35286471

35714286

35841726

36258174

36271485

36275184

36418572

36428571

36814752

36815724

36824175

37285146

37286415

38471625

41582736

41586372

42586137

42736815

42736851

42751863

42857136

42861357

46152837

46827135

46831752

47185263

47382516

47526138

47531682

48136275

48157263

48531726

51468273

51842736

51863724

52468317

52473861

52617483

52814736

53168247

53172864

53847162

57138642

57142863

57248136

57263148

57263184

57413862

58413627

58417263

61528374

62713584

62714853

63175824

63184275

63185247

63571428

63581427

63724815

63728514

63741825

64158273

64285713

64713528

64718253

68241753

71386425

72418536

72631485

73168524

73825164

74258136

74286135

75316824

82417536

82531746

83162574

84136275

當然細心點還可以發現,

這個程序對於N皇后問題也是可以的,

我試了幾個,結論還是對的.

對於更多的N,wiki上也有解的個數的結論,

而且暫時還沒有已知的通項公式,

虛位以待大神破解呢..

往期:

不想求行列式! 還能簡單判斷行列式值是否為0?

球面兩點,咋走最短?

求不出原函數還怎麼求定積分啊?分析一個特例:sinx的n次方的積分,0到2分之π

斐波那契數學通項最簡單求法,保證學過數列的人都能看懂

僅在一點可導的函數，可能存在嗎？

歡迎關注公眾號: