51. N-Queens

這題還蠻好玩的, 但也有點難, 算是backtrace的經典之一

要如何在一個棋盤, 擺出所有可能讓皇后不能互殺, 棋子都只能放皇后

西洋棋皇后的攻擊範圍是 行, 列, 斜邊通吃, 而且距離無線, 可以直線殺

所以我們在一列放完後, 即可前往下一列, 因為這列不可能再放皇后了, 只是要特別注意的就是行, 跟斜邊可能就會碰撞

所以我們可以寫一個isValid, 來判斷i, j 這個位置能不能放, 能放就前往下一行, 然後做backtrace

可以確定的是一定存在所有列都有皇后, 所以一旦走完了所有列即可把狀態輸出

class Solution {
public:
  Solution(){
      dirs = { {-1, 1}, {-1, -1}};
  }
  bool isValid(vector<string> &board, int i, int j, int &n) {
    for (int row = 0; row < n; row++) {
      if (board[row][j] == 'Q')
        return false;
    }
    for (auto dir : dirs) {
      for(int x = i, y = j ; x >=0 && x < n && y>=0 && y < n;x+=dir[0], y+=dir[1]){
          if (board[x][y] == 'Q')
        return false;
      }  
    }
  
    return true;
  }
  
  void backtrace(vector<string> &board, int row, vector<vector<string>> &res) {
    if (row == board.size()) {
      res.push_back(board);
      return;
    }
    int n = board.size();
    for (int col = 0; col < n; col++) {
      if (!isValid(board, row, col, n)) {
        continue;
      }
      board[row][col] = 'Q';
      backtrace(board, row + 1, res);
      board[row][col] = '.';
    }
  }
  vector<vector<string>> solveNQueens(int n) {
    // empty board
    vector<string> board(n, string(n, '.'));
    vector<vector<string>> res;
    backtrace(board, 0, res);
return res;
  }
private:
    vector<vector<int>> dirs;
};