O（N）空间中的N皇后-yiteyi-C++库

给定n，在一个nxn棋盘上，找到皇后在棋盘上的正确位置。 以前的做法： N皇后

null

算法：

Place(k, i)// Returns true if a queen can be placed// in kth row and ith column. Otherwise it// returns false. X[] is a global array// whose first (k-1) values have been set.// Abs( ) returns absolute value of r{   for j := 1 to k-1 do        // Two in the same column        // or in the same diagonal        if ((x[j] == i)  or            (abs(x[j] – i) = Abs(j – k)))           then return false;   return true;}

算法nQueens（k，n）：

// Using backtracking, this procedure prints all // possible placements of n queens on an n×n // chessboard so that they are nonattacking.{      for i:= 1 to n do      {         if Place(k, i) then         {             x[k] = i;             if (k == n)                write (x[1:n]);             else                NQueens(k+1, n);         }      }}

C++

                         // CPP code to for n Queen placement                       
                         #include <bits/stdc++.h>                       
           
                         #define breakLine cout << "---------------------------------";                       
                         #define MAX 10                       
           
                         using                                     namespace                                     std;                       
           
                         int                                     arr[MAX], no;                       
           
                         void                                     nQueens(                                     int                                     k,                                     int                                     n);                       
                         bool                                     canPlace(                                     int                                     k,                                     int                                     i);                       
                         void                                     display(                                     int                                     n);                       
           
                         // Function to check queens placement                       
                         void                                     nQueens(                                     int                                     k,                                     int                                     n){                       
           
                                                 for                                     (                                     int                                     i = 1;i <= n;i++){                       
                                                 if                                     (canPlace(k, i)){                       
                                                 arr[k] = i;                       
                                                 if                                     (k == n)                       
                                                 display(n);                       
                                                 else                       
                                                 nQueens(k + 1, n);                       
                                                 }                       
                                                 }                       
                         }                       
           
                         // Helper Function to check if queen can be placed                       
                         bool                                     canPlace(                                     int                                     k,                                     int                                     i){                       
                                                 for                                     (                                     int                                     j = 1;j <= k - 1;j++){                       
                                                 if                                     (arr[j] == i ||                       
                                                 (                                     abs                                     (arr[j] - i) ==                                     abs                                     (j - k)))                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 return                                     true                                     ;                       
                         }                       
           
                         // Function to display placed queen                       
                         void                                     display(                                     int                                     n){                       
                                                 breakLine                       
                                                 cout <<                                     "Arrangement No. "                                     << ++no;                       
                                                 breakLine                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++){                       
                                                 for                                     (                                     int                                     j = 1; j <= n; j++){                       
                                                 if                                     (arr[i] != j)                       
                                                 cout <<                                     "	_"                                     ;                       
                                                 else                       
                                                 cout <<                                     "	Q"                                     ;                       
                                                 }                       
                                                 cout << endl;                       
                                                 }                       
           
                                                 breakLine                       
                         }                       
           
                         // Driver Code                       
                         int                                     main(){                       
                                                 int                                     n = 4;                       
                                                 nQueens(1, n);                       
                                                 return                                     0;                       
                         }                       

JAVA

                         // Java code to for n Queen placement                       
                         class                                     GfG                       
                         {                       
           
                                                 static                                     void                                     breakLine()                       
                                                 {                       
                                                 System.out.print(                                     "---------------------------------"                                     );                       
                                                 }                       
                                                 static                                     int                                     MAX =                                     10                                     ;                       
           
                                                 static                                     int                                     arr[] =                                     new                                     int                                     [MAX], no;                       
           
                                                 // Function to check queens placement                       
                                                 static                                     void                                     nQueens(                                     int                                     k,                                     int                                     n)                       
                                                 {                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 if                                     (canPlace(k, i))                       
                                                 {                       
                                                 arr[k] = i;                       
                                                 if                                     (k == n)                       
                                                 {                       
                                                 display(n);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 nQueens(k +                                     1                                     , n);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Helper Function to check if queen can be placed                       
                                                 static                                     boolean                                     canPlace(                                     int                                     k,                                     int                                     i)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     1                                     ; j <= k -                                     1                                     ; j++)                       
                                                 {                       
                                                 if                                     (arr[j] == i ||                       
                                                 (Math.abs(arr[j] - i) == Math.abs(j - k)))                       
                                                 {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Function to display placed queen                       
                                                 static                                     void                                     display(                                     int                                     n)                       
                                                 {                       
                                                 breakLine();                       
                                                 System.out.print(                                     "Arrangement No. "                                     + ++no);                       
                                                 breakLine();                       
           
                                                 for                                     (                                     int                                     i =                                     1                                     ; i <= n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j =                                     1                                     ; j <= n; j++)                       
                                                 {                       
                                                 if                                     (arr[i] != j)                       
                                                 {                       
                                                 System.out.print(                                     "	_"                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 System.out.print(                                     "	Q"                                     );                       
                                                 }                       
                                                 }                       
                                                 System.out.println(                                     ""                                     );                       
                                                 }                       
           
                                                 breakLine();                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     main(String[] args)                       
                                                 {                       
                                                 int                                     n =                                     4                                     ;                       
                                                 nQueens(                                     1                                     , n);                       
                                                 }                       
                         }                       
           
                         // This code is contributed by 29AjayKumar                       

Python3

                         # Python code to for n Queen placement                       
                         class                                     GfG:                       
                                                 def                                     __init__(                                     self                                     ):                       
                                                 self                                     .                                     MAX                                     =                                     10                       
                                                 self                                     .arr                                     =                                     [                                     0                                     ]                                     *                                     self                                     .                                     MAX                       
                                                 self                                     .no                                     =                                     0                       
           
                                                 def                                     breakLine(                                     self                                     ):                       
                                                 print                                     (                                     "------------------------------------------------"                                     )                       
           
                                                 def                                     canPlace(                                     self                                     , k, i):                       
                                   
                                                 # Helper Function to check                       
                                                 # if queen can be placed                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     , k):                       
                                                 if                                     (                                     self                                     .arr[j]                                     =                                     =                                     i                                     or                       
                                                 (                                     abs                                     (                                     self                                     .arr[j]                                     -                                     i)                                     =                                     =                                     abs                                     (j                                     -                                     k))):                       
                                                 return                                     False                       
                                                 return                                     True                       
           
                                                 def                                     display(                                     self                                     , n):                       
                                   
                                                 # Function to display placed queen                       
                                                 self                                     .breakLine()                       
                                                 self                                     .no                                     +                                     =                                     1                       
                                                 print                                     (                                     "Arrangement No."                                     ,                                     self                                     .no, end                                     =                                     " "                                     )                       
                                                 self                                     .breakLine()                       
           
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 for                                     j                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 if                                     self                                     .arr[i] !                                     =                                     j:                       
                                                 print                                     (                                     "	_"                                     , end                                     =                                     " "                                     )                       
                                                 else                                     :                       
                                                 print                                     (                                     "	Q"                                     , end                                     =                                     " "                                     )                       
                                                 print                                     ()                       
           
                                                 self                                     .breakLine()                       
           
                                                 def                                     nQueens(                                     self                                     , k, n):                       
                                   
                                                 # Function to check queens placement                       
                                                 for                                     i                                     in                                     range                                     (                                     1                                     , n                                     +                                     1                                     ):                       
                                                 if                                     self                                     .canPlace(k, i):                       
                                                 self                                     .arr[k]                                     =                                     i                       
                                                 if                                     k                                     =                                     =                                     n:                       
                                                 self                                     .display(n)                       
                                                 else                                     :                       
                                                 self                                     .nQueens(k                                     +                                     1                                     , n)                       
           
                         # Driver Code                       
                         if                                     __name__                                     =                                     =                                     '__main__'                                     :                       
                                                 n                                     =                                     4                       
                                                 obj                                     =                                     GfG()                       
                                                 obj.nQueens(                                     1                                     , n)                       
           
                         # This code is contributed by vibhu4agarwal                       

C#

                         // C# code to for n Queen placement                       
                         using                                     System;                       
           
                         class                                     GfG                       
                         {                       
           
                                                 static                                     void                                     breakLine()                       
                                                 {                       
                                                 Console.Write(                                     "---------------------------------"                                     );                       
                                                 }                       
                                                 static                                     int                                     MAX = 10;                       
           
                                                 static                                     int                                     []arr =                                     new                                     int                                     [MAX];                       
                                                 static                                     int                                     no;                       
           
                                                 // Function to check queens placement                       
                                                 static                                     void                                     nQueens(                                     int                                     k,                                     int                                     n)                       
                                                 {                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 if                                     (canPlace(k, i))                       
                                                 {                       
                                                 arr[k] = i;                       
                                                 if                                     (k == n)                       
                                                 {                       
                                                 display(n);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 nQueens(k + 1, n);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
           
                                                 // Helper Function to check if queen can be placed                       
                                                 static                                     bool                                     canPlace(                                     int                                     k,                                     int                                     i)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j <= k - 1; j++)                       
                                                 {                       
                                                 if                                     (arr[j] == i ||                       
                                                 (Math.Abs(arr[j] - i) == Math.Abs(j - k)))                       
                                                 {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     true                                     ;                       
                                                 }                       
           
                                                 // Function to display placed queen                       
                                                 static                                     void                                     display(                                     int                                     n)                       
                                                 {                       
                                                 breakLine();                       
                                                 Console.Write(                                     "Arrangement No. "                                     + ++no);                       
                                                 breakLine();                       
           
                                                 for                                     (                                     int                                     i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (                                     int                                     j = 1; j <= n; j++)                       
                                                 {                       
                                                 if                                     (arr[i] != j)                       
                                                 {                       
                                                 Console.Write(                                     "	_"                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 Console.Write(                                     "	Q"                                     );                       
                                                 }                       
                                                 }                       
                                                 Console.WriteLine(                                     ""                                     );                       
                                                 }                       
           
                                                 breakLine();                       
                                                 }                       
           
                                                 // Driver Code                       
                                                 public                                     static                                     void                                     Main(String[] args)                       
                                                 {                       
                                                 int                                     n = 4;                       
                                                 nQueens(1, n);                       
                                                 }                       
                         }                       
           
                         // This code contributed by Rajput-Ji                       

Javascript

                         <script>                       
           
                         // JavaScript program to for n Queen placement                       
           
                                                 function                                     breakLine()                       
                                                 {                       
                                                 document.write(                                     "<br />"                                     );                       
                                                 document.write(                                     "---------------------------------"                                     );                       
                                                 document.write(                                     "<br />"                                     );                       
                                                 }                       
                                                 let MAX = 10;                       
                                   
                                                 let arr = [];                       
                                                 let no = 0;                       
                                   
                                                 // Function to check queens placement                       
                                                 function                                     nQueens(k, n)                       
                                                 {                       
                                   
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 if                                     (canPlace(k, i))                       
                                                 {                       
                                                 arr[k] = i;                       
                                                 if                                     (k == n)                       
                                                 {                       
                                                 display(n);                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 nQueens(k + 1, n);                       
                                                 }                       
                                                 }                       
                                                 }                       
                                                 }                       
                                   
                                                 // Helper Function to check if queen can be placed                       
                                                 function                                     canPlace(k, i)                       
                                                 {                       
                                                 for                                     (let j = 1; j <= k - 1; j++)                       
                                                 {                       
                                                 if                                     (arr[j] == i ||                       
                                                 (Math.abs(arr[j] - i) == Math.abs(j - k)))                       
                                                 {                       
                                                 return                                     false                                     ;                       
                                                 }                       
                                                 }                       
                                                 return                                     true                                     ;                       
                                                 }                       
                                   
                                                 // Function to display placed queen                       
                                                 function                                     display(n)                       
                                                 {                       
                                                 breakLine();                       
                                                 document.write(                                     "Arrangement No. "                                     + ++no);                       
                                                 breakLine();                       
                                   
                                                 for                                     (let i = 1; i <= n; i++)                       
                                                 {                       
                                                 for                                     (let j = 1; j <= n; j++)                       
                                                 {                       
                                                 if                                     (arr[i] != j)                       
                                                 {                       
                                                 document.write(                                     "	_"                                     );                       
                                                 }                       
                                                 else                       
                                                 {                       
                                                 document.write(                                     "	Q"                                     );                       
                                                 }                       
                                                 }                       
                                                 document.write(                                     "<br/>"                                     );                       
                                                 }                       
                                   
                                                 breakLine();                       
                                                 }                       
                                   
                         // Driver code                       
           
                                                 let n = 4;                       
                                                 nQueens(1, n);                       
           
                         </script>                       

输出：

---------------------------------Arrangement No. 1---------------------------------    _    Q    _    _    _    _    _    Q    Q    _    _    _    _    _    Q    _------------------------------------------------------------------Arrangement No. 2---------------------------------    _    _    Q    _    Q    _    _    _    _    _    _    Q    _    Q    _    _---------------------------------

文章版权归作者所有，未经允许请勿转载。

THE END

技术文章