51. & 52. N Queens
51. N-Queens & 52. N-Queens
這個題目也是透過棋類遊戲的規則所設計出的一個回溯法的問題,如同前言所示,棋類遊戲需要快速的找出幾個可行解,接著在心中的棋盤放下那個旗子,並繼續往下推演,如果推演下去發現並不好或是無法滿足遊戲規則,就換下一個可行解來找。
皇后問題的困難點在於,題目有兩個大方向去思考,第一個是回溯法的邏輯要怎麼處理,第二個是要怎麼處理該棋盤位置皇后是否可以放上去,而這兩個處理的方法又有部份交疊,所以讓這個題目的細節不怎麼好處理。
首先先看一眼皇后在棋盤上的的規則
1. 同一行不能有皇后,在程式裡面很好透過行的遍歷來處理
2. 同一列不能有皇后,在程式裡面很好透過列的遍歷來處理
3. 主對角線上不能有皇后,這沒有這個好處理,晚點再來討論
4. 反對角線上不能有皇后,這沒有這個好處理,晚點再來討論
了解以上的規則後,就可以開始想我們會怎麼樣的放置皇后,這裡請先忽略第三第四個條件,假設我們在一個位置上放置了皇后,只考慮該行和該列就再也不能放置,我們就可以用以下的方式來走訪。
下面的走訪方式是一列一列的方式往下找下一個可以放的位置,走到該