2014.2.13 19:23

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

Given an integer n, return all distinct solutions to the n-queens puzzle.

Each solution contains a distinct board configuration of the n-queens' placement, where 'Q' and '.' both indicate a queen and an empty space respectively.

For example,

There exist two distinct solutions to the 4-queens puzzle:

[ [".Q..",  // Solution 1  "...Q",  "Q...",  "..Q."], ["..Q.",  // Solution 2  "Q...",  "...Q",  ".Q.."]]

Solution:

　　The problem is a typical model for backtracking  algorithm.

　　For any pair of queens, their difference in x and y coordinates mustn't be 0 or equal, that's on the same row, column or diagonal line.

　　The code is short and self-explanatory, please see for yourself.

　　Total time complexity is O(n!). Space complexity is O(n!) as well, which comes from local parameters in recursive function calls.

Accepted code:

1 // 1CE, 1WA, 1AC, try to make the code shorter, it'll help you understand it better. 2 class Solution { 3 public: 4     vector
     
      
        > solveNQueens(int n) { 5         a = nullptr; 6         res.clear(); 7         if (n <= 0) { 8             return res; 9         }10         11         a = new int[n];12         solveNQueensRecursive(0, a, n);13         delete[] a;14         15         return res;16     }17 private:18     int *a;19     vector
       
        
          > res;20     21     void solveNQueensRecursive(int idx, int a[], const int &n) {22         if (idx == n) {23             // one solution is found24             addSingleResult(a, n);25             return;26         }27         28         int i, j;29         // check if the current layout is valid.30         for (i = 0; i < n; ++i) {31             a[idx] = i;32             for (j = 0; j < idx; ++j) {33                 if (a[j] == a[idx] || myabs(idx - j) == myabs(a[idx] - a[j])) {34                     break;35                 }36             }37             if (j == idx) {38                 // valid layout.39                 solveNQueensRecursive(idx + 1, a, n);40             }41         }42     }43     44     void addSingleResult(const int a[], int n) {45         vector
         
           single_res;46         char *str = nullptr;47         48         str = new char[n + 1];49         int i, j;50         for (i = 0; i < n; ++i) {51             for (j = 0; j < n; ++j) {52                 str[j] = '.';53             }54             str[j] = 0;55             str[a[i]] = 'Q';56             single_res.push_back(string(str));57         }58         59         res.push_back(single_res);60         single_res.clear();61         delete []str;62     }63     64     int myabs(const int x) {65         return (x >= 0 ? x : -x);66     }67 };