8- Queens片段
-
26-10-2019 - |
题
我目前已经学习了回溯,并陷入了8-Queen问题,我正在使用8x8矩阵,并且我认为我在传递到功能的矩阵中遇到了一些问题,任何帮助都会受到高度关注。我不介意是否介意任何人都会对代码进行任何优化,谢谢。
这是我的代码。
#include <stdio.h>
#include <stdlib.h>
#define MAX 7
//void azzera(int **mat);
void posiziona(int **mat, int r,int c);
void stampa(int **mat);
int in_scacchi(int **mat,int r ,int c);
int main(int argc, char *argv[])
{
int i=0,j=0;
int **mat=(int **)malloc(sizeof(int *)*MAX);
for(i=0;i<=MAX;i++){
mat[i]=(int *)malloc(MAX*sizeof(int));
for(j=0;j<=MAX;j++){
mat[i][j]=-1;
}
}
printf("insert pos of the first queen on the first row (1-8) :");
scanf("%d",&i);
i-=1;
mat[0][i]=1;
posiziona(mat,1,0);
stampa(mat);
system("PAUSE");
return 0;
}
/*void azzera(int **mat){
int i=0,j=0;
for(i=0;i<=MAX;i++){
for(j=0;j<=MAX;j++){
mat[i][j]=-1;
}
}
}*/
void stampa(int **mat){
int i,j;
for(i=0;i<=MAX;i++){
for(j=0;j<=MAX;j++){
printf(" %d",mat[i][j]);
}
printf("\n");
}
}
void posiziona(int **mat, int r,int c){
int i=0,riga=1,flag_col=-1,flag_riga=-1;
if(riga<=7&&flag_riga!=1){
if(flag_riga==1){
flag_riga=-1;
posiziona(mat,r+1,0);
}
else if(in_scacchi(mat,r,c)==1){
if(c==MAX)
posiziona(mat,r-1,0);
posiziona(mat,r,c+1);
}
else{
flag_riga=1;
}
}
}
int in_scacchi(int **mat,int r ,int c){
int i,j,k,m;
int flag=0;
//col
for(i=0;i<r;i++){
for(j=0;j<=c;j++){
if(((mat[i][j]==1)&&(c==j)))
return 1;
}
}
//diag \
for(i=0;i<MAX-r;i++){
for(j=0;j<=MAX-c;j++){
if(mat[MAX-r-i][MAX-c-j]==1)
return 1;
}
}
//antidiag
for(i=r+1;i<=MAX;i++){
for(j=c+1;j<=MAX;j++){
if(mat[r-i][c+j]==1) {
return 1;
}
}
}
return 0;
}
解决方案
您的矩阵必须从0到max-1迭代,
IE
int **mat= malloc(sizeof(int *)*MAX);
for(i=0;i< MAX;i++){ //see for i<MAX
mat[i]= malloc(MAX*sizeof(int));
for(j=0;j<MAX;j++){ //see for j<MAX
mat[i][j]=-1;
}
}
其他提示
1. 一个明显的问题是内存分配:
int **mat=(int **)malloc(sizeof(int *)*MAX);
for(i=0;i<=MAX;i++){
mat[i]=(int *)malloc(MAX*sizeof(int));
鉴于 MAX
是7,两个 mallocs
为矩阵分配了太少的内存(七个元素而不是八个元素)。
老实说,我会重命名 MAX
至 SIZE
或类似的东西,然后更改所有循环以使用严格的较小的循环,即
for(i = 0; i < SIZE; i++) {
我认为这更惯用,并且易于错误。
2. 我没有试图调试逻辑(我认为期望我们这样做是不公平的)。但是,我注意到除了 main
你分配给 mat
. 。对我来说,这表明代码不可能是正确的。
3. 除此之外,观察到在有效的解决方案中,棋盘的每一行都完全包含一个女王。这意味着您实际上不需要8x8矩阵来表示解决方案:列位置的8个元素阵列将做到。
编辑 为了回答您在评论中的问题,这是一个完整的python实施,该实施证明了以上第3点:
def can_place(col_positions, col):
row = len(col_positions)
for r, c in enumerate(col_positions):
if c == col or abs(c - col) == abs(r - row): return False
return True
def queens(n, col_positions = []):
if len(col_positions) >= n:
pretty_print(n, col_positions)
return True
for col in xrange(n):
if can_place(col_positions, col):
if queens(n, col_positions + [col]):
return True
return False
def pretty_print(n, col_positions):
for col in col_positions:
print '.' * col + 'X' + '.' * (n - 1 - col)
queens(8)
必须在I-和J-LOOP中使用SizeOf(...) *(最大+1)调用Malloc。
此外,当我运行您的程序时,我在IN_SCACCHI(...)的反迪亚格(Antidiag 垫[RI] [C+J 评估 垫[-1] [1 因为 r == 1 和 i == 2.
因此,您对矩阵的抗双重分子的描述似乎存在逻辑错误。
不隶属于 StackOverflow