我正在开发一个程序来解决n皇后问题(将n棋皇后放在n x n棋盘上的问题,这样它们中的任何一个都无法使用标准棋皇后的移动来捕获任何其他棋子)。我正在使用启发式算法,它首先在每一行中放置一个皇后,然后从尚未被占用的列中随机挑选一列。我觉得这一步是一个优化的机会。这是代码(在 C++ 中):
vector<int> colsleft;
//fills the vector sequentially with integer values
for (int c=0; c < size; c++)
colsleft.push_back(c);
for (int i=0; i < size; i++)
{
vector<int>::iterator randplace = colsleft.begin() + rand()%colsleft.size();
/* chboard is an integer array, with each entry representing a row
and holding the column position of the queen in that row */
chboard[i] = *randplace;
colsleft.erase(randplace);
}
如果从代码中不清楚:我首先为每列构建一个包含整数的向量。然后,对于每一行,我在向量中选择一个随机条目,将其值分配给该行在chboard[]
. 然后我从向量中删除该条目,因此它不适用于任何其他皇后。
我很好奇可以使用数组和指针而不是向量的方法。还是<list>
?for
除了循环之外,有没有更好的方法来顺序填充向量?我很想听听一些建议!