#include <mpi.h>
#include <stdio.h>
#define QUEENS 8
#define MAX_SOLUTIONS 92
typedef int bool;
const int true = 1;
const int false = 0;
/*枚举信号*/
enum msg_content
{
READY,
ACCOMPLISHED,
NEW_TASK,
TERMINATE
};
/*枚举信息标签*/
enum msg_tag
{
REQUEST_TAG,
SEED_TAG,
REPLY_TAG,
NUM_SOLUTIONS_TAG,
SOLUTIONS_TAG
};
int solutions[MAX_SOLUTIONS][QUEENS];
int solution_count = 0;
/*
*函数名：collides
*功能：检查两个位置是否有列、对角线或反对角线冲突
*输入：row1为位置1的行号；
* col1为位置1的列号；
* row2为位置2的行号；
* col2为位置2的列号。
*输出：返回1代表两位置有行、对角线或反对角线冲突；
* 否则返回0
*/
bool collides(int row1, int col1, int row2, int col2)
{
return (col1 == col2)
|| (col1 - col2 == row1 - row2)
|| (col1 + row1 == col2 + row2);
} /* collides */
/*
*函数名：generate_seed
*功能：生成初始化棋盘，只初始化棋盘的前两列
*输入：无
*输出：返回0代表已没有可初始化的棋盘，
* 否则返回生成的初始化的棋盘。
*/
int generate_seed()
{
static int seed = 0;
do
{
seed++;
} while (seed <= QUEENS * QUEENS - 1
&& collides(0, seed / QUEENS, 1, seed % QUEENS));
if (seed > QUEENS * QUEENS - 1)
return 0;
else
return seed;
} /* generate_seed */
/*
*函数名：print_solutions
*功能：打印结果
*输入：count为需要打印的结果的个数；
* solutions[][QUEENS]为所要打印出来的结果，即皇后所摆放的位置。
*输出：无
*/
void print_solutions(int count, int solutions[][QUEENS])
{
int i, j, k;
for (i = 0; i < count; i++)
{
/*打印第i+1个结果*/
printf("Solution %d :\n", i + 1);
for (j = 0; j < QUEENS; j++)
{
printf("%d ", solutions[i][j]);
/*打印棋盘，*表示皇后所在位置*/
for (k = 0; k < solutions[i][j]; k++) printf("- ");
printf("* ");
for (k = QUEENS - 1; k > solutions[i][j]; k--) printf("- ");
printf("\n");
}
printf("\n");
}
} /* print_solutions */
/*
*函数名：is_safe
*功能：检查当前皇后所摆放的位置是否与已摆放的皇后的位置相冲突
*输入：chessboard[]为存放皇后所摆放的位置的数组;
* row为当前位置的行；
* col为当前位置的列。
*输出：返回0代表当前位置有冲突，不可摆放皇后；
返回1代表当前位置没有冲突，可以摆放皇后。
*/
bool is_safe(int chessboard[], int row, int col)
{
int i;
for (i = 0; i < row; i++)
{
/*检查当前位置是否与第i行皇后的位置相冲突*/
if (collides(i, chessboard[i], row, col))
return false;
} /* for */
return true;
} /* is_safe */
/*
*函数名：place_queens
*功能：为当前行的皇后寻找适当的摆放位置，
* 如果皇后摆放完毕则记录所摆放的位置，
* 递归的摆放后面的皇后，
* 当所有皇后摆放完毕后，记录所得的解。
*输入：chessboard[]为存放皇后所摆放位置的数组；
row为当前皇后所要摆放的行号。
*输出：无
*/
void place_queens(int chessboard[], int row)
{
int i, col;
if (row >= QUEENS) /*所有皇后均摆放完毕*/
{
/* 结束递归并记录当前解 */
for (i = 0; i < QUEENS; i++)
{
solutions[solution_count][i] = chessboard[i];
}
solution_count++;
}
else
{
/*还有皇后没有摆好*/
for (col = 0; col < QUEENS; col++) /*在当前行寻找适当位置摆放皇后*/
{
if (is_safe(chessboard, row, col)) /*当前位置不冲突*/
{
chessboard[row] = col; /* 在当前位置放置一个皇后 */
place_queens(chessboard, row + 1);/* 递归放置下一个皇后 */
} /* if */
} /* for */
} /* else */
} /* place_queens */
/*
*函数名：sequential_eight_queens
*功能：串行地求解八皇后问题，并将解打印出来
*输入：无
*输出：无
*/
void sequential_eight_queens()
{
int chessboard[QUEENS];
solution_count = 0;
/*开始求解八皇后问题*/
place_queens(chessboard, 0);
/*打印所求结果*/
print_solutions(solution_count, solutions);
} /*sequential_eight_queens*/
/*
*函数名：eight_queens_master
*功能：生成初始化棋盘，并将其发送给空闲的子进程；
* 从子进程中接受并记录解；
* 当所有子进程都已终止且没有新的初始化棋盘时，打印所有的解。
*输入：nodes为工作组中进程数
*输出：无
*/
void eight_queens_master(int nodes)
{
MPI_Status status;
int active_slaves = nodes - 1; // except the master itself
int new_task = NEW_TASK;
int terminate = TERMINATE;
int reply;
int child;
int num_solutions;
int seed;
while (active_slaves) /*有未结束的子进程*/
{
/*从子进程中接受返回信号*/
MPI_Recv(&reply, 1, MPI_INT, MPI_ANY_SOURCE, REPLY_TAG, MPI_COMM_WORLD, &status);
child = status.MPI_SOURCE;
if (reply == ACCOMPLISHED) /*子进程已完成求解任务*/
{
/* 从子进程接收并记录解 */
MPI_Recv(&num_solutions, 1, MPI_INT, child, NUM_SOLUTIONS_TAG, MPI_COMM_WORLD, &status);
if (num_solutions > 0)
{
MPI_Recv(solutions[solution_count],
QUEENS * num_solutions, MPI_INT,
child, SOLUTIONS_TAG, MPI_COMM_WORLD, &status);
solution_count += num_solutions;
}
}
seed = generate_seed(); /*产生初始棋盘*/
if (seed) /* 还有新的初始棋盘 */
{
/* 向子进程发送一个new_task信号 */
MPI_Send(&new_task, 1, MPI_INT, child, REQUEST_TAG, MPI_COMM_WORLD);
/* 向子进程发送一个合法的新棋盘 */
MPI_Send(&seed, 1, MPI_INT, child, SEED_TAG, MPI_COMM_WORLD);
}
else /* 已求出所有解 */
{
/* 向子进程发送终止信号 */
MPI_Send(&terminate, 1, MPI_INT, child, REQUEST_TAG, MPI_COMM_WORLD);
active_slaves--;
}
} /* while */
/*打印所有解*/
print_solutions(solution_count, solutions);
} /* eight_queens_master */
/*
*函数名：eight_queens_slave
*功能：从主进程接受新的初始化的棋盘；
* 在初始化的棋盘基础上求出所有合法的解；
* 将求得的解发送给主进程。
*输入：my_rank为子进程在整个工作组中的进程标识符
*输出：无
*/
void eight_queens_slave(int my_rank)
{
MPI_Status status;
int ready = READY;
int accomplished = ACCOMPLISHED;
bool finished = false;
int request;
int seed;
int num_solutions = 0;
int chessboard[QUEENS];
/*向主进程发送ready信号*/
MPI_Send(&ready, 1, MPI_INT, 0, REPLY_TAG, MPI_COMM_WORLD);
while (! finished) /*子进程未终止*/
{
/* 从主进程接收消息 */
MPI_Recv(&request, 1, MPI_INT, 0, REQUEST_TAG, MPI_COMM_WORLD, &status);
if (request == NEW_TASK)
{
/* 从主进程接收初始棋盘 */
MPI_Recv(&seed, 1, MPI_INT, 0, SEED_TAG, MPI_COMM_WORLD, &status);
/* 在初始棋盘基础上求解 */
chessboard[0] = seed / QUEENS;
chessboard[1] = seed % QUEENS;
solution_count = 0;
place_queens(chessboard, 2);
/* 将解发送给主进程 */
/*向主进程发送accomplished信号*/
MPI_Send(&accomplished, 1, MPI_INT, 0, REPLY_TAG, MPI_COMM_WORLD);
MPI_Send(&solution_count, 1, MPI_INT, 0, NUM_SOLUTIONS_TAG, MPI_COMM_WORLD);
if (solution_count > 0)
{
MPI_Send(*solutions,
QUEENS * solution_count,
MPI_INT, 0,
