let 51 N-Queens

本文主要是介绍let 51 N-Queens，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

主题思想： 这是一道搜索题， 典型的回溯算法思路。 当搜索时，通常满足条件，需要改变某种状态。一种情况处理完后，应该把改变的状态再改回来，这就是回溯的核心。 典型的深度搜索。 具体到这道题， 可以对存储空间优化，因为搜索时可以一行一行搜索，即先寻找第一行合适的位置，再寻找第二行，这样可以用一个List 记录每一行的位置，list中添加的下标就是行号，存储的值是对应的列值。

具体代码：

class Solution {public List<List<String>> solveNQueens(int n) {List<List<String>> ans=new ArrayList<List<String>>();dfs(0,n,new ArrayList<Integer>(),ans);return ans;}public void  dfs(int step,int n,List<Integer> record,List<List<String>> ans){if(step==n){List<String> tmp=generateString(record,n);ans.add(tmp);return ;}for(int i=0;i<n;i++){if(!check(record,step,i)) continue;record.add(i);dfs(step+1,n,record,ans);int len=record.size();record.remove(len-1);}return ;}public boolean check(List<Integer> record,int step,int index){for(int i=0;i<record.size();i++){if((step-i)==Math.abs(index-record.get(i))||index==record.get(i)) return false;}return true;}public List<String> generateString(List<Integer> indexs,int n){List<String> ans=new ArrayList<String>();for(int i=0;i<indexs.size();i++){String tmp="";for(int j=0;j<n;j++){if(j==indexs.get(i)) tmp+="Q";else tmp+=".";}ans.add(tmp);}return ans;}
}

这篇关于let 51 N-Queens的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---