首页 > 代码库 > N-Queens

N-Queens

2024-07-21 16:09:46   212人阅读

The n-queens puzzle is the problem of placing n queens on ann×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.."]
]

答案

public class Solution {
    int queenPosition[];
    int N;
    List<String[]>resultList;
    StringBuilder line;
    Set<Integer> getRemainingPosition(int index){
        Set<Integer> result=new HashSet<Integer>();
        int i,j;
        for(i=0;i<N;i++){
            result.add(i);
        }
        for(i=0;i<N;i++){
            for(j=0;j<index;j++){
                if((i==queenPosition[j])||(Math.abs(i-queenPosition[j])==Math.abs(index-j))){
                    result.remove(i);
                    break;
                }
            }
        }
        return result;
    }
    public void calNQueens(int index)
    {
        Set<Integer> remainingPosition=getRemainingPosition(index);
        if(index+1==N){
            for(Integer position:remainingPosition)
            {
                queenPosition[index]=position;
                String []result=new String[N];
                for(int i=0;i<N;i++)
                {
                    line.setCharAt(queenPosition[i],'Q');
                    result[i]=line.toString();
                    line.setCharAt(queenPosition[i],'.');
                }
                resultList.add(result);
            }
        }
        else
        {
            for(Integer position:remainingPosition)
            {
                queenPosition[index]=position;
                calNQueens(index+1);
            }
        }
    }
    public List<String[]> solveNQueens(int n) 
    {
        N=n;
        resultList=new LinkedList<String[]>();
        queenPosition=new int[N];
        line=new StringBuilder(N);
        for(int i=0;i<N;i++)
        {
            line.append(".");
        }
        calNQueens(0);
        return resultList;
    }
}


N-Queens


联系
我们