首页 > 代码库 > N-Queens

N-Queens

2024-07-10 02:43:56   221人阅读

题目

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.."]
]

方法

回溯法的思想。逐行选择所在的列，并判断是否满足条件，满足条件进入下一行。不满足，则返回。
    public List<String[]> solveNQueens(int n) {
        List <String[]> list = new ArrayList<String[]>();
        int[] queenAtCol = new int[n];
        getNQueens(0, n, queenAtCol, list);
        return list;
    }
	private void getNQueens(int row, int n, int[] queenAtCol, List<String[]> list) {
		if (row == n) {
			String[] str = new String[n];
			for (int i = 0; i < n; i++) {
				StringBuilder builder = new StringBuilder();
				for (int j = 0; j < n; j++) {
					
					if (queenAtCol[i] == j) {
						builder.append('Q');
					} else {
						builder.append('.');
					}
				}
				str[i] = builder.toString();
			}
			list.add(str);
		} else {
			for (int col = 0; col < n; col++) {
				if (isValid(row,col,queenAtCol)) {
					queenAtCol[row] = col;
					getNQueens(row + 1, n, queenAtCol, list);
				}
				
			}
		}
	}
	
	private boolean isValid(int row, int col,int[] queenAtCol) {
		//row is valid.
		//column 
		for (int i = 0; i < row; i++) {
			if (queenAtCol[i] == col) {
				return false;
			}
		}
		
		for (int i = 0; i < row; i++) {
			if (i + queenAtCol[i] == row + col) {
				return false;
			}
		}
		
		for (int i = 0; i < row; i++) {
			if (col - row == queenAtCol[i] - i) {
				return false;
			}
		}
		return true;
	}


联系
我们