###### tags: `資料結構 & 演算法`
{%hackmd @kk6333/theme-sty1 %}
# DS4 - 遞迴文法 & Backtracking

## 1. 遞迴文法

利用遞迴文法，可以方便設定遞迴的中止條件
而文法的定義，要依照執行的任務作出篩選

### - 文法符號

 <x> |<y>     : 條件 <x> or <y>
<x><y> or <x>*<y>  : <x> 接在 <y> 的前面

### - 文法寫法 :

:::warning
**- 定義 -**
利用遞迴文法的 Symbol 定義遞迴任務條件
每當符合其中一個合法條件，會繼續遞迴到下一迴圈，又或是抵達 Base Line

<輸入> = <要符合的文法>
<輸入> = <文法一> | <文法二> | <文法3-1><文法3-2>

:::

:::info
EX :
> 目地-確認字串是否為數字
> <number> = <digit><number> | <digit>
> - <number> : 代表輸入的數字字串
> - <digit> : 代表數字型態 => 0|1|2|3...|9
> - <digit><number> : 代表讀取第一個字是數字，後面的 number 代表還沒檢查的字串
>
> 當符合第一個文法，會繼續跑遞迴檢查字串，
> 如符合第二個文法則達到 Base Line 回傳 "true"
> 如都不符合也達到 Base Line 回傳 "false"
>

寫成 Code :

bool IsNumber( string number){
    if( number is digit ) return true;
    if( number 第一個字是 digit ) return IsNumber( number 去掉第一個字 );
    else return false;
}

:::

<br>

## 2. Backtracking

### 定義

:::warning
Backtracking 是一個遞迴常用的手法，
意思是當碰到不能執行的條件後就退回

好處是，比起窮舉所有可能再檢查可行性，backtrack 可以減少計算的次數


:::

### 舉例 : 八皇后問題

:::success
有 8 個西洋棋的皇后，每個皇后的直、橫、斜的方向列不能相同
那有幾種排法 ?


<br>

**Code**

簡單列出實作城堡的方法 ( 詳細的函數就不列了~ )
這邊就使用了 Backtrack 的概念

如果想做皇后、主教的情況，只需要修改 <位置合法> 的條件即可

int Queens[8] = {-1,-1,-1,-1,-1,-1,-1,-1};    // 皇后擺放的位置
    
void PlaceQueen( int curr_line ){
    
    // 當沒有 line 時回傳
    if( curr_line >= 8 ){
        return;
    }

    // Search 此 line 合法的位置
    for( int i=0 ; i < 8 ; i++ ){
        if(  <位置合法>  ) {
            Queens[ curr_line ] = i;              // 將皇后放置在這個位置
            PlaceQueen( curr_line + 1 );          // 前往下一 line
        }
    }
}

:::