UVa 167：The Sultan's Successors， 八皇后问题

题目链接：

http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=108&page=show_problem&problem=103

题目类型： 回溯

原题：

The Sultan of Nubia has no children, so she has decided that the country will be split into up to k separate parts on her death and each part will be inherited by whoever performs best at some test. It is possible for any individual to inherit more than one or indeed all of the portions. To ensure that only highly intelligent people eventually become her successors, the Sultan has devised an ingenious test. In a large hall filled with the splash of fountains and the delicate scent of incense have been placed k chessboards. Each chessboard has numbers in the range 1 to 99 written on each square and is supplied with 8 jewelled chess queens. The task facing each potential successor is to place the 8 queens on the chess board in such a way that no queen threatens another one, and so that the numbers on the squares thus selected sum to a number at least as high as one already chosen by the Sultan. (For those unfamiliar with the rules of chess, this implies that each row and column of the board contains exactly one queen, and each diagonal contains no more than one.)

Write a program that will read in the number and details of the chessboards and determine the highest scores possible for each board under these conditions. (You know that the Sultan is both a good chess player and a good mathematician and you suspect that her score is the best attainable.)

题目大意：

Sultan没有孩子，所以她决定做一个测试，选择一个继承人。 这个测试内容是， 有一个8*8的棋盘， 棋盘上的每个格子上都有

一个1～99的数字。然后，要放8个皇后上去，使它们不能同行，同列，同斜线，  并且求出8个放置位置上的数字之和最大

的值。

分析与总结：

赤裸裸的八皇后问题了，只是增加了个求和的步骤。

首先， 可以得出这8个皇后一定是在不同行上的， 然后，还可以进一步判断每一行上的列坐标都是不同的，即恰好每行每列

放置一个皇后。这样，就只需要再判断是否斜线上有冲突即可。

接下来就好办了，我们可以开一个数组loc[9] = {0,1,2,3,4,5,6,7},   数组下标对应行，数组元素的值对应该行的列。 我们只需要

枚举loc的全排列， 然后写一个judge函数来判断这个排列方案是否符合八皇后规则即可，如果符合的话，就计算棋盘上对应的

值的和，更新维护一个全局的最大值即可。

0～7的排列一共有8！=40320个， 而枚举两不会超过这个。

1. 暴力枚举法

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
#define MOD
using namespace std;
int map[8][8];
int loc[8];  

bool judge(){
    for(int i=1; i<8; ++i){
        for(int j=0; j<i; ++j){
            if(i-j==loc[i]-loc[j] || i-j==loc[j]-loc[i])
                return false;
        }
    }
    return true;
}  

int main(){
#ifdef LOCAL
    freopen("input.txt","r",stdin);
#endif
    int T;
    scanf("%d",&T);
    while(T--){
        for(int i=0; i<8; ++i)
            for(int j=0; j<8; ++j)
                scanf("%d", &map[i][j]);  

        for(int i=0; i<8; ++i)
            loc[i] = i;
        int maxVal = -1;  

        do{
            if(judge()){
                int sum=0;
                for(int i=0; i<8; ++i)
                    sum += map[i][loc[i]];
                if(sum > maxVal) maxVal = sum;
            }
        }while(next_permutation(loc, loc+8));  

        printf("%5d\n", maxVal);
    }
    return 0;
}

以上是小编为您精心准备的的内容，在的博客、问答、公众号、人物、课程等栏目也有的相关内容，欢迎继续使用右上角搜索按钮进行搜索数组
， 八皇后
， and
， 一个
， The
， 8皇后
， 棋盘
that
八皇后问题、八皇后问题 c语言、八皇后问题c、八皇后问题答案、八皇后问题java，以便于您获取更多的相关知识。