# DS Backtracking

{%hackmd theme-dark %}

## 回朔法

:::info
設定狀態->往下遞迴->還原狀態
:::

## 八皇后

int K;
vector<int> g;
vector<bool> chkC, chkD1, chkD2;
void solve(int R) {
  if (R == K) {
    for (int i = 0; i < K; i++, cout << '\n')
      for (int j = 0; j < K; j++) cout << "*Q"[g[i] == j];
    cout << '\n';
  } else
    for (int C = 0; C < K; C++) {
      int D1 = R + C, D2 = R - C + K - 1;
      if (!chkC[C] && !chkD1[D1] && !chkD2[D2]) {

        // Set Status
        g[R] = C;
        chkC[C] = chkD1[D1] = chkD2[D2] = true;

        // Recur
        solve(R + 1);
          
        // Back
        g[R] = -1;
        chkC[C] = chkD1[D1] = chkD2[D2] = false;

      }
    }
}

int main() {
  cin >> K;
  g = vector<int>(K, -1);
  chkC.resize(K), chkD1.resize(K * 2 - 1), chkD2 = chkD1;

  solve(0);

  return 0;
}

## 走迷宮

- [DS1ex1Note](/w_NNjW25TsCQGiWrzXnE-Q)

## HPAir problem(有向圖兩點路徑)

解法類似走迷宮，注意有無環