d324 - 00750 - 8 Queens Chess Problem
題目描述
題目要求在 8x8 的西洋棋盤上放置 8 個皇后，使得任何兩個皇后都不互相攻擊。給定一個皇后的位置，輸出所有可能的棋盤配置，並按照字典順序排列。輸出格式要求包含表頭，並以列的形式顯示每個皇后的位置。
解題思路
本題採用回溯法 (Backtracking) 解決。回溯法是一種試探性的解決問題的方法，它會逐步建立一個候選解，如果發現目前的候選解不可行，則放棄該候選解，並回溯到上一步，嘗試其他的可能性。
具體來說，程式碼從第一列開始，逐列嘗試放置皇后。對於每一列，程式碼會檢查該列的每個位置是否可以放置皇后，即該位置是否不與已放置的皇后衝突。如果可以放置皇后，則將皇后放置在該位置，並遞迴地處理下一列。如果遞迴調用成功，則說明找到了一個可行的解，將其儲存。如果遞迴調用失敗，則將該位置的皇后移除，並嘗試下一列的位置。
chat 函數用於檢查在給定的行列位置放置皇后是否會與已放置的皇后衝突。locate_queen 函數使用遞迴方式尋找所有可能的解。主函數讀取輸入，並根據輸入的皇后位置輸出所有可能的解。
複雜度分析
- 時間複雜度: O(8!)。在最壞的情況下，需要嘗試所有可能的皇后放置方式，其數量為 8!。
- 空間複雜度: O(8)。主要用於儲存棋盤狀態和遞迴調用堆疊。
ans陣列的大小為 8x8x92，但實際儲存的解的數量通常遠小於 92，因此空間複雜度主要由遞迴深度決定。