首页 > 代码库 > Leetcode-N-Queens
Leetcode-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.."]]
Have you met this question in a real interview?
Analysis:
How to determine whether the current position at jth row is valid? Suppose jth row position is place[j] and ith row position is place[i]. Then we found that place[i] leads three positions at jth row invalid. They are place[i], place[i]+j-i, place[i]-(j-i).
Solution:
1 public class Solution { 2 public List<String[]> solveNQueens(int n) { 3 List<String[]> res = new ArrayList<String[]>(); 4 int[] place = new int[n]; 5 Arrays.fill(place,-1); 6 int level = 0; 7 8 while (level!=-1){ 9 if (level>=n){10 constructRes(place,res,n);11 level--;12 continue;13 }14 15 int val = place[level];16 val++;17 while (val<n){18 boolean valid = true;19 for (int i=0;i<level;i++)20 if (val==place[i] || val==place[i]+level-i || val==place[i]-(level-i)){21 valid = false;22 break;23 }24 if (valid) break;25 else val++;26 }27 28 if (val<n){29 place[level]=val;30 level++;31 } else {32 place[level]=-1;33 level--;34 }35 }36 37 return res;38 39 }40 41 public void constructRes(int[] place, List<String[]> res, int n){42 char[] line = new char[n];43 Arrays.fill(line,‘.‘);44 String[] oneRes = new String[n];45 for (int i=0;i<n;i++){46 int val = place[i];47 line[val]=‘Q‘;48 String lineStr = new String(line);49 line[val]=‘.‘;50 oneRes[i]=lineStr;51 }52 res.add(oneRes);53 } 54 }
Leetcode-N-Queens
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。