8个皇后问题的C语言的解法。
//
// main.m
// HuangHou
//
// Created by apple on 14-2-14.
// Copyright (c) 2014年 apple. All rights reserved.
//
//#include<iostream.h>
#include<math.h>
#import <Foundation/Foundation.h>
#include "stdio.h"
//#include "windows.h"
#define N 8/* 定义棋盘大小 */
int place(int k); /* 确定某一位置皇后放置与否,放置则返回1,反之返回0 */
void backtrack(int i);/* 主递归函数,搜索解空间中第i层子树 */
void chessboard(); /* 每找到一个解,打印当前棋盘状态 */
staticint sum, /* 当前已找到解的个数 */
x[N]; /* 记录皇后的位置,x[i]表示皇后i放在棋盘的第i行的第x[i]列 */
int main(int argc, const char * argv[])
{
@autoreleasepool {
backtrack(0);
system("pause");
}
return 0;
}
int place(int k)
{
/* 测试皇后k在第k行第x[k]列时是否与前面已放置好的皇后相攻击。 x[j] == */
/* x[k] 时,两皇后在同一列上;abs(k - j) == abs(x[j] - x[k]) 时,两皇 */
/* 后在同一斜线上。两种情况两皇后都可相互攻击,故返回0表示不符合条件。*/
for (int j = 0; j < k; j ++)
if (abs(k - j) == abs(x[j] - x[k]) || (x[j] == x[k])) return 0;////这里只判断了两个相减的情况,相加的都不用判断,因为for循环的时候说了。小于,没有等于。。。。
return 1;
}
void backtrack(int t)
{
/* t == N 时,算法搜索至叶结点,得到一个新的N皇后互不攻击的放置方案 */
if (t == N) chessboard();
else
for (int i = 0; i < N; i ++) {
x[t] = i;
if (place(t)) backtrack(t + 1);///当前行有几种方法,就递归几次。。。
}
}
void chessboard()
{
printf("第%d种解法:\n", ++ sum);
for (int i = 0; i < N; i ++) {
for (int j = 0; j < N; j ++)
if (j == x[i]) printf("@ ");
else printf("* ");
printf("\n");
}
printf("\n");
}