前言

各位和我一樣的剛學(xué)完遞歸的小白們，是不是突然遇見了一個大BOSS，八皇后????問題?。“炎孕诺恼f著“老子遞歸學(xué)好了！”的你一棒子打回了出生點，就像你剛玩只狼遇到的那個大胖子，剛玩原神遇到的雪山。今天，我就和大家一起學(xué)習(xí)一下這個著名的八皇后????問題。

題目介紹

八皇后問題，是一個古老而著名的問題，是回溯算法的典型例題。該問題是十九世紀(jì)著名的數(shù)學(xué)家高斯1850年提出：在8×8格的國際象棋上擺放八個皇后，使其不能互相攻擊，即任意兩個皇后都不能處于同一行、同一列或同一斜線上，問有多少種擺法并輸出每一種擺法。

升華：我在做這個東西的時候本來想用人腦將他們擺進去，發(fā)現(xiàn)太！麻！煩！可能這就是計算機存在的意義吧！

—————————————————————————————————————————

引入：

不知道大家有沒有在前面學(xué)習(xí)遞推的時候?qū)W過馬攔過河卒的問題沒看過的可以點這，這個問題和那個問題都是一個棋類的問題，他們也有相同之處，都是需要用一個數(shù)組來表示這個地方有沒有被占領(lǐng)，象棋的那個題是馬占領(lǐng)的地方需要標(biāo)記，而這個題是皇后占領(lǐng)的每一行每一列每一個對角線都需要標(biāo)記。所以我們可以采用一些個數(shù)組來表示這個地方被皇后占領(lǐng)了。當(dāng)然這個題還用到了一個重要的算法就是遞歸算法和回溯的思想。

—————————————————————————————————————————

解決思路：

1.首先定義三個數(shù)組分別表示列被占領(lǐng)，左對角線被占領(lǐng)，和右對角線被占領(lǐng)。因為我們一行一行的放進去所以不用考慮行的問題。????

2.利用遞歸算法在沒有被占領(lǐng)的地方一行一行的放入我們的皇后。????

3.利用遞歸和回溯算法一行一行的放入皇后。????

__________________________________________________________________________

? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? ? 理論存在，實踐開始！

難點1：如何表示對角線被占領(lǐng)？

用數(shù)組來表示列被占領(lǐng)很簡單，只要讓皇后所在的那一列的數(shù)組的值都等于0，就可以解決這個問題，但如何用數(shù)組來表達對角線呢？？你知道吧！你數(shù)一數(shù)，這一共有多少個對角線？一共有15條對角線，所以我們可以定義兩個數(shù)組d1和d2來用來表示兩個方向的對角線。如果被占領(lǐng)就是1沒有被占領(lǐng)就是0

綠色的就是右對角線，col【】；

紫色的就是左對角線，umcol【】；

如何在擺放的時候來確定哪一行哪一列呢？

這樣定義十五行太好定義了但是想要表示就難了，我們來研究一下這個東西。

看下圖，如這個第五列第三行的這個女皇，這個皇后占領(lǐng)了這兩個對角線， 如何來表示上對角線（皇后????的左上和右下從右上腳開始1、2、3、4、5...）

通過這兩個公式就能得到當(dāng)前皇后所在的兩條斜線是否有其他的皇后

col[u-i+n]=?;uncol[u+i]=?

至于為什么可以這樣算出來呢，看下圖就知道了：

uncol【u+i】//行加列，算出左對角線是否皇后：

?這樣我們不就可以用行標(biāo)和列標(biāo)來表示他所在的左對角線了嘛，神器吧??！

希望各位xdm都把這個背過說實話我要是自己推我也推不出來這個玩意??！

右對角線：用行-列+n就會神奇的發(fā)現(xiàn)變成了下面這個樣子：

col【u-i+n】：

版權(quán)聲明：本文為CSDN博主「孤獨時代的c0re」的原創(chuàng)文章，遵循CC 4.0 BY-SA版權(quán)協(xié)議，轉(zhuǎn)載請附上原文出處鏈接及本聲明。

原文鏈接：https://blog.csdn.net/m0_63830846/article/details/123927967