비 귀속 구 해 N 황후 문제 (역 추적 법)

/*
 * 【    】   8×8          8   ，
 *            “  ”，        “ 
 *  ”        ，              
 *                    ，     
 *  、  、         。
 *
 *     （   ）  8       
 *
 *           MAXQUEEN  ，    N    。
 *
 */

#include <stdio.h>
#include <conio.h>

#define TRUE 1
#define FALSE 0
#define MAXQUEEN 4
#define ABS(x) ((x>0)?(x):-(x))  /* x    */

/*  8       ，           */
int queen[MAXQUEEN];
int total_solution = 0;  /*       */

/*      */
void backtrack();
int attack(int,int);
void output_solution();


int main(void)
{
    backtrack();

    return 0;
}

/*            */
void backtrack()
{
    int row = 0;
    queen[row] = -1;
    while(row >= 0)
    {
        queen[row]++;
        while(queen[row] < MAXQUEEN && attack(row, queen[row]))
            queen[row]++;
        if(queen[row] < MAXQUEEN)
            if(row == (MAXQUEEN-1))
                output_solution(); /*       */
            else
                queen[++row] = -1;
        else
            row--;
    }
}

/*    （row,col）                    1，    0 */
int attack(int row, int col)
{
    int i, atk=FALSE;
    int offset_row, offset_col;
    i=0;
    while(!atk && i<row)
    {
        offset_row=ABS(i-row);
        offset_col=ABS(queen[i]-col);
        /*            ，         */
        /*             ，     ，atk==TRUE */
        atk = (queen[i] == col) || (offset_row == offset_col);
        i++;
    }
    return atk;
}

/*   8      */
void output_solution()
{
    int x,y;
    total_solution += 1;
    printf("Solution#%3d
\t",total_solution);
    for(x=0;x<MAXQUEEN;x++)
    {
        for(y=0;y<MAXQUEEN;y++)
        if(y==queen[x])
            printf("Q"); /*    Q     */
        else
            printf("-"); /*  -     */
        printf("
\t");
    }
    printf("
");

    getchar();
}