LeetCode: N-Queens

题目

https://oj.leetcode.com/problems/n-queens/

分析

  1. 这道题采用的是回溯法,跟DFS非常类似,只不过是在DFS的递归前加一个判断。

  2. 关于如何表示结果。

可以采用一个N*N二维数组来存放结果,但是我们可以采用更好的办法:经过观察我们可以发现,每一行必然有一个皇后,因此我们可以用一个一维数组来表示结果,solution[0]=3 代表第0行的皇后放在第三列, solution[1]=5 代表第1行的皇后放在第5列,……以此类推。

  1. 关于如何判断一种结果是否合法。

题目要求任意两个皇后不能在同一行、同一列或者用一斜线上,在2中我们已经提过了用一维数组solution[n]来表示结果,任两个皇后肯定不在同一行,判断第i行和第j行的皇后是否同一列可以用 solution[i] == solution[j]来判断;如何判断第i行皇后和第j行皇后是否在同一斜线上呢?可以用 abs(i-j) == abs(solution[i] - solution[j]) 来判断。

代码

class Solution
{
public:
	vector<vector<string>> solveNQueens(int n)
	{
		vector<int> solution(n);
		helper(solution, 0, n);

		return res;
	}

	void helper(vector<int>& solution, int row, int n)
	{
		if (row == n)
		{
			vector<string> solution_2d(n, string(n, '.'));
			for (int i = 0; i < n; i++)
				solution_2d[i][solution[i]] = 'Q';

			res.push_back(solution_2d);
		}
		else
		{
			for (int i = 0; i < n; i++)
			{
				if (isValid(solution, row, i))
				{
					solution[row] = i;
					helper(solution, row + 1, n);
				}
			}
		}
	}

	bool isValid(vector<int>& solution, int row, int col)
	{
		for (int i = 0; i < row; i++)
			if (solution[i] == col || abs(i-row) == abs(solution[i]-col))
				return false;
		return true;
	}

private:
	vector<vector<string>> res;
};

参考

http://www.cnblogs.com/TenosDoIt/p/3801621.html

本文章迁移自http://blog.csdn.net/timberwolf_2012/article/details/40686105

/** * RECOMMENDED CONFIGURATION VARIABLES: EDIT AND UNCOMMENT THE SECTION BELOW TO INSERT DYNAMIC VALUES FROM YOUR PLATFORM OR CMS. * LEARN WHY DEFINING THESE VARIABLES IS IMPORTANT: https://disqus.com/admin/universalcode/#configuration-variables*/ /* var disqus_config = function () { this.page.url = PAGE_URL; // Replace PAGE_URL with your page's canonical URL variable this.page.identifier = PAGE_IDENTIFIER; // Replace PAGE_IDENTIFIER with your page's unique identifier variable }; */ (function() { // DON'T EDIT BELOW THIS LINE var d = document, s = d.createElement('script'); s.src = 'https://chenzz.disqus.com/embed.js'; s.setAttribute('data-timestamp', +new Date()); (d.head || d.body).appendChild(s); })();