注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

HT·生活

123

 
 
 

日志

 
 

ex51 N-Queens  

2015-05-25 22:08:48|  分类: leetcode |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

The n-queens puzzle is the problem of placing n queens on an n×n chessboard such that no two queens attack each other.

ex51 N-Queens - HT - HT·生活

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.."]
]
N皇后问题,规则比较简单,最重要的就是把规则用表达式提炼出来。我表示最开始的时候判定规则写的不对,死活都得不到正确的结果,而且用的是递归回朔的,坑死我了。先看一下递归的思路,比较容易懂。(这里用一维数组存了,nums[i]表示的是第i和皇后,它放的列的位置)
第一个皇后放在0位置,接着放第二个皇后,依次。一旦后面皇后放不了了,前一皇后位置后移,直到第一个皇后把所有的位置都遍历了一遍。

class Solution {
public:
vector<vector<string>> result;
vector<vector<string> > solveNQueens(int n) {
if (n <= 0)
return result;
vector<int>queen(n, -1);//棋盘中所有的元素都存-1
result.clear();
int index = 0;
traverse(queen,index);
return result;
}
void traverse(vector<int>&queen,int index)
{
//queen[i]表示第i行 皇后的位置
int len = queen.size();
int i = 0;
//index表示现在该存第几个皇后到了
if ((index + 1) == len)
{
//退出条件是最后一个皇后是否能够放置
bool mark = false;
for (i = 0; i < len; i++)
{
if (!conflict(queen, index, i))
{
//找到答案了
queen[index] = i;
mark = true;
break;
}
}
//构造最终结果
if (mark)
{
string str(len, '.');
vector<string>res;
for (i = 0; i < len; i++)
{
res.push_back(str);
res[i][queen[i]] = 'Q';
}
result.push_back(res);
}
}
else
{
bool mark = false;
for (i = 0; i < len; i++)
{
mark = conflict(queen, index, i);
if (!mark)
{
queen[index] = i; //第index行的Q放在 i列上
traverse(queen, index + 1); //遍历下一个皇后的位置
}
}
}
}
bool conflict(vector<int>queen,int index,int col)
{
//index表示的行
//col 表示的是列
//判定如果第index行放在第col列是否冲突
int i = 0;
int dis1, dis2,dis3,dis4;
for (i = 0; i <index;i++)
{
//擦,开始的时候判定规则写错了,恶心死我了
//注释里面的一个一个正确的规则
//dis1 = i - queen[i];
//dis2 = index - col;
//dis3 = i + queen[i];
//dis4 = index + col;
//if (dis2 == dis1||col==queen[i]||dis3==dis4)
// return true;
dis1 = abs(i - index);
dis2 = abs(queen[i] - col);

if (dis2 == dis1||col==queen[i])
return true;
}
return false;
}
};

下面说一下判定是否当前皇后位置有效,如index是当前皇后的标号,col是他放的列的位置
要做一个循环0-(index-1)所有的已经放好的皇后都应该和当前的比较一下,看有没有冲突。最简单的表达公式是
abs(index-i)==abs(queen[i]-col),如果相等话,说明他们在一条斜线上,还有一个条件就是col不能等于queen[i],因为这一列已经被人给占了。
下面给一下非递归的代码,主要判定条件就是第一个皇后的所有位置是否都走完了。

/*
*
*写一下N皇后问题的非递归解
*/
class Solution1 {
public:
vector<vector<string>> result;
vector<vector<string> > solveNQueens(int n) {
if (n <= 0)
return result;
vector<int>queen(n,-1);
traverse(queen);
return result;
}
void traverse(vector<int>queen)
{
int i, j;
i = 0; //表示放的皇后的下标
j = 0; //表示放的列下标
int len = queen.size();
bool mark = false;

int k = 0; //第一个皇后有n种可能
for (k = 0; k < len; k++)
{
mark = conflict(queen, 0, k); //第一个皇后放在(0,k)位置
if (!mark)
{
queen[0] = k;
j = 0;
i = 1;
while (j < len&&i<len)
{
mark = conflict(queen, i, j);
if (!mark)
{
//不冲突
queen[i] = j;
i++;
j = 0;
if (i == len)
{
//找到了
string str(len, '.');
vector<string>res;
for (int ii = 0; ii < len; ii++)
{
res.push_back(str);
res[ii][queen[ii]] = 'Q';
}
result.push_back(res);
}
//break;
}
else
{
j++;
}
}
}
//第一个皇后的位置继续往后挪
}


}
bool conflict(vector<int>queen, int index, int col)
{
//index表示的行
//col 表示的是列
//判定如果第index行放在第col列是否冲突
int i = 0;
int dis1, dis2;
for (i = 0; i <index; i++)
{
dis1 = abs(i - index);
dis2 = abs(queen[i] - col);

if (dis2 == dis1 || col == queen[i])
return true;
}
return false;
}
};



参考
http://blog.sina.com.cn/s/blog_696187fd0100p5ri.html
http://blog.csdn.net/pinkrobin/article/details/5378702
  评论这张
 
阅读(7)| 评论(0)
推荐 转载

历史上的今天

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017