陷入 n*n 棋盘上 q 个主教的算法
Getting Stuck On the Algorithm for q bishops on an n*n chessboard
我正在使用 C++,但我的问题更多是关于算法而不是实现。
问题如下:
Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard.
我的基本想法是将每个主教表示为具有 X 值和 Y 值的结构。然后我把主教放在棋盘上以获得配置。
我编写了一个名为 moveToNextPlace 的方法,它允许我将主教移动到下一个可用位置。我 return 一个字符串来帮助调试。
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, n, num-1);
b[num].setValuesLike ( b[num-1] );
findAspot (b, n, num);
}
然后我想继续回溯直到我有一个解决方案的总数,但是我卡在了如何找到下一个解决方案上。
我想我可以写一个 findNextSolution,它在 findSolutions 函数结束时不断被调用,直到它到达一个循环。但是不知道用什么算法找到下一个解
您的将主教位置存储在数组中的想法有了一个良好的开端。这是棋盘状态的紧凑表示。
您必须更正检查一个主教是否与另一个主教冲突的方法。请记住,两个冲突的象可能被垂直距离 dy
和水平距离 dx
隔开,因此 dx == -dy
。因此,您需要比较绝对值:如果 abs(dx) == abs(dy)
.
,则主教发生冲突
现在开始计算棋盘状态数量的一般问题,其中 k
象没有冲突。您需要定义一个 returns 整数值的函数。假设这个函数看起来像
count(currentBishops, numRemaining)
其中 currentBishops
是象的可行放置,numRemaining
是您尚未放置的象的数量。
那么问题的解决方法就是
count([], k)
其中 []
表示尚未放置主教。
count
功能可以按照下面的伪代码实现
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, 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)
memo[(currentBishops, numRemaining)] = sum
return sum
currentBishops
的映射应该是一个不关心你放置象的顺序的映射。您可以通过在计算 memo
.
的键时对主教位置进行排序或制作棋盘的位图来实现此目的
我正在使用 C++,但我的问题更多是关于算法而不是实现。
问题如下:
Write a program that inputs two integers n and k, where n>=k. Your program should calculate the number of different ways that k bishops could be placed on an nXn chessboard.
我的基本想法是将每个主教表示为具有 X 值和 Y 值的结构。然后我把主教放在棋盘上以获得配置。
我编写了一个名为 moveToNextPlace 的方法,它允许我将主教移动到下一个可用位置。我 return 一个字符串来帮助调试。
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, n, num-1);
b[num].setValuesLike ( b[num-1] );
findAspot (b, n, num);
}
然后我想继续回溯直到我有一个解决方案的总数,但是我卡在了如何找到下一个解决方案上。
我想我可以写一个 findNextSolution,它在 findSolutions 函数结束时不断被调用,直到它到达一个循环。但是不知道用什么算法找到下一个解
您的将主教位置存储在数组中的想法有了一个良好的开端。这是棋盘状态的紧凑表示。
您必须更正检查一个主教是否与另一个主教冲突的方法。请记住,两个冲突的象可能被垂直距离 dy
和水平距离 dx
隔开,因此 dx == -dy
。因此,您需要比较绝对值:如果 abs(dx) == abs(dy)
.
现在开始计算棋盘状态数量的一般问题,其中 k
象没有冲突。您需要定义一个 returns 整数值的函数。假设这个函数看起来像
count(currentBishops, numRemaining)
其中 currentBishops
是象的可行放置,numRemaining
是您尚未放置的象的数量。
那么问题的解决方法就是
count([], k)
其中 []
表示尚未放置主教。
count
功能可以按照下面的伪代码实现
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, 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)
memo[(currentBishops, numRemaining)] = sum
return sum
currentBishops
的映射应该是一个不关心你放置象的顺序的映射。您可以通过在计算 memo
.