js八皇後問題(修改)

八皇後問題國際西洋棋棋手馬克斯·貝瑟爾於1848年提出:在8×8格的國際象棋上擺放八個皇後,使其不能互相攻擊,即任意兩個皇後都不能處於同一行、同一列或同一斜線上,問有多少種擺法。

這裡寫圖片描述


思路:試錯,類似迷宮

試錯過程:

1.第1行找到第一個合適的位置後直接進入第2行

2.第2行找到的位置跟已經放上去的元素做計算,判斷是否復合要求(不能攻擊),遍歷直到找到第一個滿足的元 素,直接 進入第三行

3.第3行如果所有的元素都不合適,則返回第二行,順著原來的位置向後找,如果找到合適的元素,再次進入第三 行,如果 第2行沒有合適的,則跳回第一行,第一行從上一個合適的元素向後尋找。。。。。。

互相攻擊的兩種可能性:

1.兩個棋子處於同一列

2.兩個棋子交叉處於一條45度斜線上;

事實上根據這些描述和接下來的代碼,要看明白解題過程,依然會有一些困難,即便看明白瞭,理解不夠深,過一段時間依然會忘記,最好的方式就是親眼看到程序實現的過程,然後逆推程序的流程,真正搞明白解題思路,想要做到這一點,需要借助debugger工具, 代碼後面會介紹如何借助debugger觀察程序執行過程以及皇後位置的變動,特別是回退,前進的跳轉;

代碼如下:

//借助debugger能夠非常清晰地看到跳轉的過程!

var n = 8;
var arr = [];
var str = "";
function queen( index ) {
    if( index === n ) {
        str += arr;//每次完成一種情況,輸出數組;
        str += "  "//空格隔離
     }else{
        for( var i = 0; i < n; ++i ) {
           arr[ index ] = i;//為第一行的皇後尋找位置,從0開始,直到7
           var flag = true;//這裡主要是為判定可攻擊性提供一個開關,如果在攻擊范圍內
                    // 則不進入下一列,繼續向下尋找,如果找到瞭合適的位置,則進入下一行
           for( var j = 0; j < index; ++j ) {
                        //這裡是為瞭判定攻擊范圍,把所有已經放置的皇後與當前放置的皇後做位置計算,如果在攻擊范圍內,flag為false,不在所有已經放置的皇後的攻擊范圍內,則不改變flag的屬性:true
              if( arr[ index ] === arr[ j ] 
              || arr[ index ] - arr[ j ] === j - index ) {

                 flag = false;
                  break;
              };
           };
          if( flag ) {//這裡是根據flag的屬性判定是否進入下一行的循環;
            queen( index + 1 );
          }
      }
    }
 };
queen( 0 );//從第0行進行試探
console.log( str )//輸出拼接字符串所有情況
        //queen(0)===》思路:是從第一行開始放棋子, 每放一個就檢查是否處於被攻擊的范圍,處於被攻擊范圍則向後移動一個,如果所在位置並不會被攻擊到則進入到下一行,

//代碼中已經標註瞭debugger的位置;

這裡寫圖片描述

發佈留言