首页 > 代码库 > 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:
分析: 著名的N皇后问题,可以采用一位数组来代替二维数组,利用回溯,注意皇后行走的条件
class Solution { public: bool isOk(int start,int value, const vector<int>& array){ for(int i =start-1; i>=0; i--) if((array[i]==value) || (abs(array[i]-value)==abs(start-i))) return false; if(abs(array[start-1]-value)==1) return false; return true; } void Queen(int start, vector<int>& array, vector<vector<int>> & res ){ //cout << start <<endl; if(start == array.size()){ res.push_back(array); return; } for(int i =0; i< array.size(); i++){ if(isOk(start, i, array)){ // cout <<"hello"<<endl; array[start] =i; Queen(start+1, array, res); } } return; } void convert(const vector<vector<int>> res, vector<vector<string>>& str){ for(vector<int> t: res){ int n = t.size(); vector<string> strlist; for(int i=0; i<n; i++){ string s(n,‘.‘); s[t[i]] = ‘Q‘; strlist.push_back(s); } str.push_back(strlist); } } vector<vector<string>> solveNQueens(int n) { vector<vector<int>> res; vector<vector<string>> str; if(n==0) return str; vector<int> array(n,0); for(int i =0; i< n; i++){ array[0] =i; Queen(1,array,res); } convert(res,str); return str; } };
N-Queens
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。