[ 前のページ ] [ 次のページ ] [ 目次 ] [ 索引 ] [ DOC Home ]

D EIGHTQUEENS.C

この付録では,第8章第9章, および第10章の各章にある多くの図で使用されるプログラムのソース・ コード,EIGHTQUEENS.Cおよび8QUEENS.C を示します。ここで示すプログラムは,上記の各章で説明されているプロシージャを理解するためだけのものです。

D.1 EIGHTQUEENS.C

例 D-1に,EIGHTQUEENS.Cを示します。 これは,eightqueens の問題を解決するための,シングル・モジュール構成のプログラムです。

例 D-1 シングル・モジュール構成のプログラムEIGHTQUEENS.C

extern void setqueen();
extern void removequeen();
extern void trycol();
extern void print();
    int a[8];     /* a : array[1..8]  of boolean */
    int b[16];    /* b : array[2..16] of boolean */
    int c[15];    /* c : array[-7..7] of boolean */
    int x[8];

/* Solve eight-queens problem */
main()
{
    int i;
    for (i=0; i <=7; i++)
 a[i] = 1;
    for (i=0; i <=15; i++)
 b[i] = 1;
    for (i=0; i <=14; i++)
 c[i] = 1;
    trycol( 0 );
} /* End main */

void trycol( j )
    int j;
{
    int m;
    int safe;
    m = -1;
    while (m++ < 7)
       {
       safe = (a[m] ==1) && (b[m + j] == 1) && (c[m - j + 7] ==1);
       if (safe)
            {
     setqueen(m, j);
     x[j] = m + 1;
     if (j < 7)
  trycol(j + 1);
     else
  print();
     removequeen(m, j);
     }
       }
} /* End trycol */

void setqueen(m, j)
    int m;
    int j;
{
    a[m] = 0;
    b[m + j] = 0;
    c[m - j + 7] = 0;
} /* End setqueen */

void removequeen(m, j)
    int m;
    int j;
{
    a[m] = 1;
    b[m + j] = 1;
    c[m - j + 7] = 1;
} /* End removequeen */

void print()
{
    int k;
    for (k=0; k<=7; k++)
 {
 printf(" %d", x[k]);
 }
    printf("\n");
} /* End print */

D.2 8QUEENS.C

8QUEENS.Cは,eightqueensの問題を解決するためのマルチ・モジュール構成のプログラムです。 このプログラムは,8QUEENS.C (例 D-2)および8QUEENS_SUB.C ( 例 D-3)の2つのモジュールから構成されます。

例 D-2 8QUEENS.Cのメイン・モジュール

extern void trycol();
    int a[8];     /* a : array[1..8]  of boolean */
    int b[16];    /* b : array[2..16] of boolean */
    int c[15];    /* c : array[-7..7] of boolean */
    int x[8];

main()    /* Solve eight-queens problem */
{
    int i;
    for (i=0; i <=7; i++)
 a[i] = 1;
    for (i=0; i <=15; i++)
 b[i] = 1;
    for (i=0; i <=14; i++)
 c[i] = 1;
    trycol(0);
    printf(" Solved eight-queens problem!\n");
} /* End main */

例 D-3 8QUEENS_SUB.Cのサブ・モジュール

extern int a[8];
extern int b[16];
extern int c[15];
extern void setqueen();
extern void removequeen();
extern void print();

    int x[8];

void trycol( j )
    int j;
{
    int m;
    int safe;
    m = -1;
    while (m++ < 7)
       {
       safe = (a[m] ==1) && (b[m + j] == 1) && (c[m - j + 7] ==1);
       if (safe)
            {
            setqueen(m, j);
            x[j] = m + 1;
            if (j < 7)
                trycol(j + 1);
            else
                print();
            removequeen(m, j);
            }
       }
}       /* End trycol */

void setqueen(m, j)
    int m;
    int j;
{
    a[m] = 0;
    b[m + j] = 0;
    c[m - j + 7] = 0;
}       /* End setqueen */

void removequeen(m, j)
    int m;
    int j;
{
    a[m] = 1;
    b[m + j] = 1;
    c[m - j + 7] = 1;
}       /* End removequeen */

void print()
{
    int k;
    for (k=0; k<=7; k++)
        {
        printf(" %d", x[k]);
        }
    printf("\n");
}       /* End print */


[ 前のページ ] [ 次のページ ] [ 目次 ] [ 索引 ] [ DOC Home ]