c – 在n * n棋盘上争夺q主教的算法
|
我正在使用C,但我的问题更多的是算法而不是实现.
问题如下：
我的基本想法是将每个主教表示为具有X值和Y值的结构.然后我将主教放在板上以获得配置. 我写了一个名为moveToNextPlace的方法,它允许我将主教移动到下一个可用的位置.我返回一个字符串来帮助调试. struct bishop {
int y=0;
int x=0;
string moveToNextPlace (int n){
if (y<n-1) {y++; return "move to next y value";}
else if (x<n-1) {x++; return "move to next x value";}
else {reset(); return "reset";};
}
void setValuesLike (bishop b){
y=b.y;
x=b.x;
}
void reset (){
y=0;
x=0;
}
bool clashesWith (bishop b){
if (b.x==x && b.y==y){
return true;
}
if ( b.y-y == b.x-x ) return true; //if their slope is 1
return false;
}
};
然后我通过使用我想要的设置调用findSolutions将电路板设置为初始配置. int findSolutions (int k,int n){ //k bishops on n*n board
bishop *b = new bishop [k];
for (int i=0; i<k; i++){
findAspot (b,n,i);
}
}
bool check (int num,bishop b[]){
for (int i=0 ; i<num; i++){
if (b[i].clashesWith (b[num])) return false;
}
return true;
}
void findAspot (bishop b[],int n,int num){ //n=boardsize
while (1){
if (check(num,b)){return;}
if (b[num].moveToNextPlace(n) == "reset") break;
}
b[num-1].moveToNextPlace(n);
findAspot (b,num-1);
b[num].setValuesLike ( b[num-1] );
findAspot (b,num);
}
然后,我想继续回溯,直到我有多个解决方案,但我不知道如何找到下一个解决方案. 我以为我可以写一个findNextSolution,它会在findSolutions函数结束时被调用,直到它到达一个循环.但我不知道用什么算法来寻找下一个解决方案. 解决方法
你想要将主教阵地存放在一个阵列中,这是一个良好的开端.这是电路板状态的紧凑表示.
你必须纠正检查一位主教是否与另一位主教发??生冲突的方法.请记住,两个冲突的主教可以被垂直距离dy和水平距离dx分开,使得dx == -dy.因此,您需要比较绝对值：如果abs(dx)== abs(dy),主教会发生冲突. 现在讨论计算k主教在没有冲突的情况下安排的董事会状态数的一般问题.您需要定义一个返回整数值的函数.让我们说这个函数看起来像 count(currentBishops,numRemaining) 其中currentBishops是主教的可行位置,numRemaining是你还没有放置的主教的数量. 然后问题的解决方案是 count([],k) 其中[]表示尚未安置主教. 计数功能可以根据以下伪代码实现. count(currentBishops,numRemaining):
if numRemaining == 0:
return 1
sum = 0
for each possible board position (x,y):
if (x,y) does not clash with any bishop in currentBishops:
let nextBishops be currentBishops augmented with (x,y)
sum += count(nextBishops,numRemaining-1)
return sum
为了避免递归调用的指数级爆炸,您需要缓存每个子问题的结果.这种技术称为memoization,您可以按如下方式实现. let memo be a map from (currentBishops,numRemaining) to an integer value
count(currentBishops,numRemaining):
if numRemaining == 0:
return 1
if memo contains (currentBishops,numRemaining):
return memo[(currentBishops,numRemaining)]
sum = 0
for each possible board position (x,numRemaining-1)
memo[(currentBishops,numRemaining)] = sum
return sum
currentBishops的映射应该是一个不关心你放置主教的顺序的映射.您可以通过在计算备忘录密钥时对主教职位进行排序或制作董事会位图来实现此目的. （编辑：李大同） 【声明】本站内容均来自网络，其相关言论仅代表作者个人观点，不代表本站立场。若无意侵犯到您的权利，请及时与联系站长删除相关内容! |