Problem Description

在N*N的方格棋盘放置了N个皇后，使得它们不相互攻击（即任意2个皇后不允许处在同一排，同一列，也不允许处在与棋盘边框成45角的斜线上。

你的任务是，对于给定的N，求出有多少种合法的放置方法。

 

Input

共有若干行，每行一个正整数N≤10，表示棋盘和皇后的数量；如果N=0，表示结束。

 

Output

            共有若干行，每行一个正整数，表示对应输入行的皇后的不同放置数量。

 

Sample Input

1850

 

Sample Output

19210

 

Code

1 #include 
          
              2 #include 
           
             3 int q[11];  //q[1] means the coordinate of queue is (1, q[1]) 4 int result[11];//to save the time, so record the previous time 5 int check(int k) //check if the kth queen is conflict with previous ones 6 { 7     int i; 8     i = 1; 9     while (i < k)10     {11         //k - i == abs(q[k] - q[i]) means the current queen is not 45° with other queens12         if (q[i] == q[k] || k - i == abs(q[k] - q[i]))13             return 0;14         i++;15     }16     return 1;17 }18 //begin with the first queen, find the position for first queen19 //and use DFS to go on to find next queen's position, if u can't find it, u can go back to change the previous queen's position20 //untill there is no position for the fist queue to change 21 int Nqueens(int n)22 {23     int count, i, j, k;24     count = 0;  //record the count of rank25     //begin with first queen and the zero position26     k = 1;27     q[k] = 0;28     while (k > 0)29     {30         q[k]++;31         //when q[k] <= n, u can go on to find q[k] satisfied the condition32         while (q[k] <= n && check(k) == 0)33             q[k]++;34         //if q[k] <= n, which means u can find position for current queen35         if (q[k] <= n)36         {37             //means u find the last queen, so u can record the counr38             if (k == n)39                 count++;40             //if it's not the last queen, u should go on to find the place of next queen41             //and for next queen, u should begin with zero.42             else43             {44                 k++;45                 q[k] = 0;46             }47         }48         else49             //if u can't find the position for current queen, u should go back to modify the previous queen's position50             k--;51     }52     return count;53 }54 int main()  55 {  56     int n;57     while (scanf("%d", &n) != EOF && n)58     {59         if (result[n] == 0)60             result[n] = Nqueens(n);61         printf("%d\n", result[n]);62     }63     return 0;  64 }
           
          

 

1 #include 
          
              2 #include 
           
             3 #include 
            
              4 int q[11];  //q[1] means the coordinate of queue is (1, q[1]) 5 int result[11];//to save the time, so record the previous time 6 int n; 7 int check(int k) //check if the kth queen is conflict with previous ones 8 { 9     int i;10     i = 1;11     while (i < k)12     {13         //k - i == abs(q[k] - q[i]) means the current queen is not 45° with other queens14         if (q[i] == q[k] || k - i == abs(q[k] - q[i]))15             return 0;16         i++;17     }18     return 1;19 }20 int count;  //record the count of rank21 int flag;22 void DFS(int step)23 {24     int i, j, k;25     if (step == n + 1)26         count++;27     else28     {29         for (i = 1; i <= n; i++)30         {31             q[step] = i;32             if (check(step) == 0)33                 continue;34             DFS(step + 1);35         }36     }37 }38 int main()  39 {  40     while (scanf("%d", &n) != EOF && n)41     {42         //memset();43         count = 0;44         if (result[n] == 0)45         {46             DFS(1);47             result[n] = count;48         }49         printf("%d\n", result[n]);50     }51     return 0;  52 }
            
           
          

 

 

 

u can find that the first one use least time.

Recommend

lcy