s**********r
发帖数: 8153 | |
l***b
发帖数: 125 | 2 这种网上搜搜很多吧。曾经有次面试，被要求把递归和非递归的都写出来。。。
【在 s**********r 的大作中提到】
: 糊涂了，不会了。。。。
: 求解！
|
s**********r
发帖数: 8153 | 3 N Queens?
【在 l***b 的大作中提到】
: 这种网上搜搜很多吧。曾经有次面试，被要求把递归和非递归的都写出来。。。
|
r**h
发帖数: 1288 | 4 iteration有什么好解法吗？
N重循环还是next permutation？ |
l***b
发帖数: 125 | 5 嗯，N queue
【在 s**********r 的大作中提到】
: N Queens?
|
s**********r
发帖数: 8153 | 6 求解法，刚搜到一个，正在验证，不知道好用不。。。
【在 l***b 的大作中提到】
: 嗯，N queue
|
s**********r
发帖数: 8153 | 7 阿？你说的这2个，怎么做。。。
【在 r**h 的大作中提到】
: iteration有什么好解法吗？
: N重循环还是next permutation？
|
l***b
发帖数: 125 | 8 随手写的，输出解的个数和wiki上一样，估计是对的吧，没仔细测
int g_nTotalSolutionNum = 0;
void PrintSolution(int *pPos, int nQueue)
{
if (pPos == NULL)
{
return;
}
for ( int i = 0; i < nQueue; ++i )
{
cout << pPos[i] << ", ";
}
cout << endl;
++g_nTotalSolutionNum;
}
void NQueue(int nQueue)
{
if ( nQueue == 0 )
{
return;
}
int *pPos = new int[nQueue];
int nCurrCol = 0;
pPos[0] = 0;
for(;;)
{
if ( pPos[nCurrCol] == nQueue )
{
if ( nCurrCol == 0 )
{
break;
}
--nCurrCol;
++pPos[nCurrCol];
continue;
}
bool bValidPos = true;
if ( nCurrCol > 0 )
{
for ( int i = 0; i < nCurrCol; ++i )
{
if (pPos[nCurrCol] == pPos[i] ||
((nCurrCol - i) == abs(pPos[nCurrCol] - pPos[i])))
{
bValidPos = false;
break;
}
}
}
if ( bValidPos )
{
if ( nCurrCol == nQueue - 1 )
{
PrintSolution(pPos, nQueue);
++pPos[nCurrCol];
continue;
}
else
{
++nCurrCol;
pPos[nCurrCol] = 0;
continue;
}
}
else
{
if ( pPos[nCurrCol] == nQueue - 1 )
{
--nCurrCol;
++pPos[nCurrCol];
continue;
}
else
{
++pPos[nCurrCol];
continue;
}
}
}
delete[] pPos;
} |
s**********r
发帖数: 8153 | 9 谢谢，我读读！
【在 l***b 的大作中提到】
: 随手写的，输出解的个数和wiki上一样，估计是对的吧，没仔细测
: int g_nTotalSolutionNum = 0;
: void PrintSolution(int *pPos, int nQueue)
: {
: if (pPos == NULL)
: {
: return;
: }
: for ( int i = 0; i < nQueue; ++i )
: {
|
d****n
发帖数: 233 | 10 Mark.
The following part at the end seems not needed:
if ( pPos[nCurrCol] == nQueue - 1 )
{
--nCurrCol;
++pPos[nCurrCol];
continue;
}
else
【在 l***b 的大作中提到】
: 随手写的，输出解的个数和wiki上一样，估计是对的吧，没仔细测
: int g_nTotalSolutionNum = 0;
: void PrintSolution(int *pPos, int nQueue)
: {
: if (pPos == NULL)
: {
: return;
: }
: for ( int i = 0; i < nQueue; ++i )
: {
|
