首页 > 代码库 > 【leetcode】N-Queens
【leetcode】N-Queens
N-Queens
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.."]]
采用q[i]表示第i行的Queen放置的位置
不合法的条件：q[i]==q[level]||abs(q[level]-q[i])==abs(level-i)
1 class Solution { 2 public: 3 vector<vector<string> > solveNQueens(int n) { 4 5 vector<int> q(n,-1); 6 vector<vector<string> > result; 7 getQueens(0,n,result,q); 8 return result; 9 }10 11 void PrintQueens(vector<int> &q,vector<vector<string> > &result)12 {13 int n=q.size();14 vector<string> tmp;15 string str;16 for(int i=0;i<n;i++)17 {18 str="";19 for(int j=0;j<n;j++)20 {21 if(q[i]==j)str+=‘Q‘;22 else str+=‘.‘;23 }24 tmp.push_back(str);25 }26 27 result.push_back(tmp);28 }29 30 void getQueens(int level,int &n,vector<vector<string> > &result,vector<int> &q)31 {32 if(level==n)33 {34 PrintQueens(q,result);35 return;36 }37 bool flag=false;38 for(int i=0;i<n;i++)39 {40 q[level]=i;41 if(isValid(q,level))42 {43 getQueens(level+1,n,result,q);44 }45 q[level]=-1;46 }47 } 48 49 bool isValid(vector<int> &q,int &level)50 {51 52 for(int i=0;i<level;i++)53 {54 if(q[i]==q[level]||abs(q[level]-q[i])==abs(level-i)) return false;55 }56 57 return true;58 }59 };
【leetcode】N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。