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

用DFS递归得到所有结果，需要注意的是剪枝的时候有两种方式：

一种是遍历先前的皇后出现位置，判断当前行的可行位置，这种是节省空间，但时间复杂度较高（解法1）；

另一种是用空间换时间，从列、主对角线、反对角线三个方向上纪录已经被占用的位置，从而直接判断出当前行的可用位置（解法2）。

解法1

import java.util.ArrayList;

public class NQueens {
	private ArrayList<String[]> results;
	private int n;

	public ArrayList<String[]> solveNQueens(int n) {
		this.n = n;
		results = new ArrayList<String[]>();

		// index: row, value: column
		int[] queue = new int[n];
		dfs(0, queue);
		return results;
	}

	private void dfs(int row, int[] queue) {
		if (row == n) {
			results.add(constructResult(queue));
			return;
		}
		for (int j = 0; j < n; ++j) {
			boolean valid = true;
			for (int i = 0; i < row; ++i) {
				if (queue[i] == j || Math.abs(j - queue[i]) == row - i) {
					valid = false;
					break;
				}
			}
			if (valid) {
				queue[row] = j;
				dfs(row + 1, queue);
			}
		}
	}

	private String[] constructResult(int[] queue) {
		String[] array = new String[n];
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; ++i) {
			sb.append(‘.‘);
		}
		for (int i = 0; i < n; ++i) {
			sb.setCharAt(queue[i], ‘Q‘);
			array[i] = sb.toString();
			sb.setCharAt(queue[i], ‘.‘);
		}
		return array;
	}
}

解法2

import java.util.ArrayList;

public class NQueens {
	private ArrayList<String[]> results;
	private int n;
	private int[] column;
	private int[] mainDiag;
	private int[] antiDiag;
	private int[] queen;

	public ArrayList<String[]> solveNQueens(int n) {
		this.n = n;
		results = new ArrayList<String[]>();
		column = new int[n];
		mainDiag = new int[2 * n];
		antiDiag = new int[2 * n];
		queen = new int[n];
		dfs(0);
		return results;
	}

	private void dfs(int row) {
		if (row == n) {
			results.add(constructResult(queen));
			return;
		}
		for (int j = 0; j < n; ++j) {
			if (column[j] == 0 && mainDiag[row + j] == 0
					&& antiDiag[row + n - j] == 0) {
				column[j] = mainDiag[row + j] = antiDiag[row + n - j] = 1;
				queen[row] = j;
				dfs(row + 1);
				column[j] = mainDiag[row + j] = antiDiag[row + n - j] = 0;
			}
		}
	}

	private String[] constructResult(int[] queen) {
		String[] array = new String[n];
		StringBuilder sb = new StringBuilder();
		for (int i = 0; i < n; ++i) {
			sb.append(‘.‘);
		}
		for (int i = 0; i < n; ++i) {
			sb.setCharAt(queen[i], ‘Q‘);
			array[i] = sb.toString();
			sb.setCharAt(queen[i], ‘.‘);
		}
		return array;
	}
}

LeetCode | N-Queens,布布扣,bubuko.com

LeetCode | N-Queens

原文：http://blog.csdn.net/perfect8886/article/details/22203555