Source Code 1994 March/Source_Code_CD-ROM_Walnut_Creek_March_1994.iso/compsrcs/misc/volume37/assist7g/part02

Text File | 1993-05-16 | 16.4 KB | 499 lines

Newsgroups: comp.sources.misc
From: [e-mail] (Tom Horsley)
Subject: v37i066:  assist7g - 7th Guest Assistant programs, Part02/02
Message-ID: <[e-mail]>
X-Md4-Signature: 717c668bf4d46da6ee8b9fe715205a0c
Date: Tue, 18 May 1993 02:51:24 GMT
Approved: [e-mail]

Submitted-by: [e-mail] (Tom Horsley)
Posting-number: Volume 37, Issue 66
Archive-name: assist7g/part02
Environment: UNIX, Perl

#! /bin/sh
# This is a shell archive.  Remove anything before this line, then unpack
# it by saving it into a file and typing "sh file".  To overwrite existing
# files, type "sh file -c".  You can also feed this as standard input via
# unshar, or by typing "sh <file", e.g..  If this archive is complete, you
# will see the following message at the end:
#        "End of archive 2 (of 2)."
# Contents:  bishop.c
# Wrapped by tom@amber on Mon May 17 08:22:23 1993
PATH=/bin:/usr/bin:/usr/ucb ; export PATH
if test -f 'bishop.c' -a "${1}" != "-c" ; then
  echo shar: Will not clobber existing file \"'bishop.c'\"
else
echo shar: Extracting \"'bishop.c'\" \(14089 characters\)
sed "s/^X//" >'bishop.c' <<'END_OF_FILE'
X/* Yet another program in the 7th guest collection. This one solves the
X * bishops problem (which some people claim is easy, but stumped me
X * totally).
X *
X * Here's the deal. There are 4 black bishops and 4 white bishops arranged
X * on a 4 x 5 chessboard like so:
X *
X * B . . . W
X * B . . . W
X * B . . . W
X * B . . . W
X *
X * The idea is to swap the white and black bishops without ever allowing a
X * black bishop to attack a white one and vice versa.
X *
X * This program tackles the problem with a breadth first search operating
X * like so:
X *
X * A hash table is kept of all board positions examined, computing legal
X * moves from one board position involves both checking for positions that
X * can be occupied without being under attack as well as checking to see if
X * we were ever at this board configuration before. Repeated configurations
X * are not allowed.
X *
X * The hash table (in addition to being keyed off the board configuration)
X * keeps a pointer to the board configuration which was the parent of this
X * one (since repeated configurations are not allowed, duplicate parents
X * will not be possible, so only one pointer is needed).
X *
X * A queue of board configurations is kept by starting with the initial
X * board as the only element in the queue.
X *
X * The algorithm proceeds through the queue, creating all possible new board
X * configurations for each element it pops off the head of the queue and
X * placing them on the tail of the queue.
X *
X * When the desired configuration is created, the algorithm terminates, and
X * back-tracks through the hash table entry pointers to trace out the
X * sequence of moves from the initial to the final configuration.
X */
X
X#include <stdio.h>
X
X#define HASH_MAX 2063
X
X/* The BoardConfiguration struct records a particular board configuration.
X * it is also the element kept in the hash table and serves as a member of
X * the processing queue.
X *
X * The board is stored as two words, each holding 20 bits. One mask
X * represents the white bishop positions, the other the black positions.
X *
X * If you imagine the board squares numbered as follows:
X *
X *   0  1  2  3  4
X *   5  6  7  8  9
X *  10 11 12 13 14
X *  15 16 17 18 19
X *
X * Then the bit masks store bishop positions by shifting 1 left by the
X * board position number, then oring it into the mask for the appropriate
X * color. For example, the initial board configuration is:
X */
X#define START_BLACK ((1 << 0) | (1 << 5) | (1 << 10) | (1 << 15))
X#define START_WHITE ((1 << 4) | (1 << 9) | (1 << 14) | (1 << 19))
X
Xtypedef struct bc {
X   struct bc *    next;        /* identical hash codes linked through this */
X   struct bc *    parent;      /* points to board config this derived from */
X   unsigned long  black_mask;  /* black bishop positions */
X   unsigned long  white_mask;  /* white bishop positions */
X} BoardConfiguration;
X
X/* The ProcessQueue struct is used to create a queue of entries to be
X * processed.
X */
Xtypedef struct pq {
X   struct pq * next;
X   BoardConfiguration * bc;
X} ProcessQueue;
X
XProcessQueue * free_space = NULL;
X
XProcessQueue * queue_head = NULL;
XProcessQueue * * queue_tail = &queue_head;
X
X/* hash_tab is the hash table of moves already seen
X */
XBoardConfiguration * hash_tab[HASH_MAX];
X
X/* attacked_from is an array with each entry corresponding to a board
X * position. Each entry is a bit mask showing the other board positions
X * which might attack this one.
X */
Xunsigned long attacked_from[20] = {
X   ((1 << 0) | (1 << 6) | (1 << 12) | (1 << 18)),
X   ((1 << 1) | (1 << 7) | (1 << 13) | (1 << 19) | (1 << 5)),
X   ((1 << 2) | (1 << 8) | (1 << 14) | (1 << 6) | (1 << 10)),
X   ((1 << 3) | (1 << 9) | (1 << 7) | (1 << 11) | (1 << 15)),
X   ((1 << 4) | (1 << 8) | (1 << 12) | (1 << 16)),
X   ((1 << 5) | (1 << 11) | (1 << 17) | (1 << 1)),
X   ((1 << 6) | (1 << 12) | (1 << 18) | (1 << 2) | (1 << 0) | (1 << 10)),
X   ((1 << 7) | (1 << 13) | (1 << 19) | (1 << 3) | (1 << 1) | (1 << 11) |
X    (1 << 15)),
X   ((1 << 8) | (1 << 14) | (1 << 4) | (1 << 2) | (1 << 12) | (1 << 16)),
X   ((1 << 9) | (1 << 3) | (1 << 13) | (1 << 17)),
X   ((1 << 10) | (1 << 16) | (1 << 6) | (1 << 2)),
X   ((1 << 11) | (1 << 17) | (1 << 7) | (1 << 3) | (1 << 5) | (1 << 15)),
X   ((1 << 12) | (1 << 18) | (1 << 8) | (1 << 4) | (1 << 6) | (1 << 0) |
X    (1 << 16)),
X   ((1 << 13) | (1 << 19) | (1 << 9) | (1 << 7) | (1 << 1) | (1 << 17)),
X   ((1 << 14) | (1 << 8) | (1 << 2) | (1 << 18)),
X   ((1 << 15) | (1 << 11) | (1 << 7) | (1 << 3)),
X   ((1 << 16) | (1 << 12) | (1 << 8) | (1 << 4) | (1 << 10)),
X   ((1 << 17) | (1 << 13) | (1 << 9) | (1 << 11) | (1 << 5)),
X   ((1 << 18) | (1 << 14) | (1 << 12) | (1 << 6) | (1 << 0)),
X   ((1 << 19) | (1 << 13) | (1 << 7) | (1 << 1))
X};
X
X/* Each row is a list of positions you can move to from a given position.
X * (each row is terminated with 20 to mark the end of the list.
X */
Xchar move_to[20][7] = {
X   {6, 12, 18, 20},
X   {7, 13, 19, 5, 20},
X   {8, 14, 6, 10, 20},
X   {9, 7, 11, 15, 20},
X   {8, 12, 16, 20},
X   {11, 17, 1, 20},
X   {12, 18, 2, 0, 10, 20},
X   {13, 19, 3, 1, 11, 15, 20},
X   {14, 4, 2, 12, 16, 20},
X   {3, 13, 17, 20},
X   {16, 6, 2, 20},
X   {17, 7, 3, 5, 15, 20},
X   {18, 8, 4, 6, 0, 16, 20},
X   {19, 9, 7, 1, 17, 20},
X   {8, 2, 18, 20},
X   {11, 7, 3, 20},
X   {12, 8, 4, 10, 20},
X   {13, 9, 11, 5, 20},
X   {14, 12, 6, 0, 20},
X   {13, 7, 1, 20}
X};
X
X/* ReflectPieces takes a board mask word and reflects the board positions
X * top for bottom to make a mirror image board position.
X *
X *   0  1  2  3  4
X *   5  6  7  8  9
X *  10 11 12 13 14
X *  15 16 17 18 19
X *
X * becomes:
X *
X *  15 16 17 18 19
X *  10 11 12 13 14
X *   5  6  7  8  9
X *   0  1  2  3  4
X */
Xunsigned long
XReflectPieces(unsigned long bm)
X{
X   unsigned long r0_4 = bm & 0x1f;
X   unsigned long r5_9 = (bm >> 5) & 0x1f;
X   unsigned long r10_14 = (bm >> 10) & 0x1f;
X   unsigned long r15_19 = (bm >> 15) & 0x1f;
X   return (r0_4 << 15) | (r5_9 << 10) | (r10_14 << 5) | r15_19;
X}
X
Xint board_count = 0;
X
X/* NewBoardConfiguration looks up a proposed new board configuration in the
X * hash table. If it is not already there, it creates the new object and
X * installs it in the table, returning a pointer to it. Otherwise it just
X * returns NULL.
X */
XBoardConfiguration *
XNewBoardConfiguration(
X   BoardConfiguration * parent,
X   unsigned long black_mask,
X   unsigned long white_mask)
X{
X   unsigned long hash = (black_mask ^ (white_mask << 11)) % HASH_MAX;
X   BoardConfiguration * ptr = hash_tab[hash];
X   while (ptr != NULL) {
X      if ((ptr->black_mask == black_mask) && (ptr->white_mask == white_mask)) {
X         return NULL;
X      }
X      ptr = ptr->next;
X   }
X   ptr = (BoardConfiguration *)malloc(sizeof(BoardConfiguration));
X   ptr->next = hash_tab[hash];
X   ptr->parent = parent;
X   ptr->black_mask = black_mask;
X   ptr->white_mask = white_mask;
X   hash_tab[hash] = ptr;
X   ++board_count;
X   {
X      /* Before we go, make an entry for the symmetric board configuration
X       * to avoid mirror image duplication of effort...
X       */
X      unsigned long mirror_white = ReflectPieces(white_mask);
X      unsigned long mirror_black = ReflectPieces(black_mask);
X      if ((mirror_white != white_mask) || (mirror_black != black_mask)) {
X         unsigned long hash = (mirror_black ^ (mirror_white << 11)) % HASH_MAX;
X         BoardConfiguration * mptr = hash_tab[hash];
X         while (mptr != NULL) {
X            if ((mptr->black_mask == mirror_black) &&
X                (mptr->white_mask == mirror_white)) {
X               return ptr;
X            }
X            mptr = mptr->next;
X         }
X         mptr = (BoardConfiguration *)malloc(sizeof(BoardConfiguration));
X         mptr->next = hash_tab[hash];
X         mptr->parent = parent;
X         mptr->black_mask = mirror_black;
X         mptr->white_mask = mirror_white;
X         hash_tab[hash] = mptr;
X      }
X   }
X   return ptr;
X}
X
Xvoid
XMakeQueueEntry(BoardConfiguration * new_board)
X{
X   ProcessQueue * qe;
X   if (new_board == NULL) {
X      return;
X   }
X   if (free_space == NULL) {
X      free_space = (ProcessQueue *)malloc(sizeof(ProcessQueue));
X      free_space->next = NULL;
X   }
X   qe = free_space;
X   free_space = qe->next;
X   qe->next = NULL;
X   qe->bc = new_board;
X   *queue_tail = qe;
X   queue_tail = &qe->next;
X}
X
XBoardConfiguration *
XGetQueueHead()
X{
X   ProcessQueue * qe;
X   BoardConfiguration * bc;
X   if (queue_head == NULL) {
X      return NULL;
X   }
X   qe = queue_head;
X   queue_head = qe->next;
X   if (queue_head == NULL) {
X      queue_tail = &queue_head;
X   }
X   bc = qe->bc;
X   qe->next = free_space;
X   free_space = qe;
X   return bc;
X}
X
X/* FindLastPosition actually runs the search algorithm, stopping
X * when it finds a solution and returning a pointer to the final
X * BoardConfiguration entry.
X */
XBoardConfiguration *
XFindLastPosition()
X{
X   BoardConfiguration * hp;
X
X   /* Install the initial board
X    */
X   MakeQueueEntry(NewBoardConfiguration(NULL, START_BLACK, START_WHITE));
X   while ((hp = GetQueueHead()) != NULL) {
X      /* Compute all the legal moves I can make from this board configuration.
X       */
X      int i;
X      unsigned long mask;
X      for (i = 0, mask = (1 << 0); i < 20; ++i, mask <<= 1) {
X         if ((hp->black_mask & mask) != 0) {
X            /* There is a black bishop at position i, check each move it
X             * can make.
X             */
X            int j, d;
X            for (j = 0; ((d = move_to[i][j]) != 20); ++j) {
X               unsigned long dmask = (1 << d);
X               /* Make sure I don't move on top of a piece of the same color
X                */
X               if ((dmask & hp->black_mask) == 0) {
X                  /* And make sure I don't move to a location under attack
X                   * by a piece of the opposite color.
X                   */
X                  if ((attacked_from[d] & hp->white_mask) == 0) {
X                     /* This entry seems legal. Make the new entry and
X                      * make sure it is not a board we have already
X                      * seen before.
X                      */
X                     BoardConfiguration * np =
X                        NewBoardConfiguration(hp,
X                           (hp->black_mask ^ mask) | dmask,
X                           hp->white_mask);
X                     if (np != NULL) {
X                        /* If this is what we have been looking for, return
X                         * it now.
X                         */
X                        if ((np->black_mask == START_WHITE) &&
X                            (np->white_mask == START_BLACK)) {
X                           return np;
X                        }
X                        MakeQueueEntry(np);
X                     }
X                  }
X               }
X            }
X         }
X         if ((hp->white_mask & mask) != 0) {
X            /* There is a white bishop at position i, check each move it
X             * can make.
X             */
X            int j, d;
X            for (j = 0; ((d = move_to[i][j]) != 20); ++j) {
X               unsigned long dmask = (1 << d);
X               /* Make sure I don't move on top of a piece of the same color
X                */
X               if ((dmask & hp->white_mask) == 0) {
X                  /* And make sure I don't move to a location under attack
X                   * by a piece of the opposite color.
X                   */
X                  if ((attacked_from[d] & hp->black_mask) == 0) {
X                     /* This entry seems legal. Make the new entry and
X                      * make sure it is not a board we have already
X                      * seen before.
X                      */
X                     BoardConfiguration * np =
X                        NewBoardConfiguration(hp,
X                           hp->black_mask,
X                           (hp->white_mask ^ mask) | dmask);
X                     if (np != NULL) {
X                        /* If this is what we have been looking for, return
X                         * it now.
X                         */
X                        if ((np->white_mask == START_WHITE) &&
X                            (np->black_mask == START_BLACK)) {
X                           return np;
X                        }
X                        MakeQueueEntry(np);
X                     }
X                  }
X               }
X            }
X         }
X      }
X   }
X}
X
Xchar * bit_names[20] = {
X   "a1", "b1", "c1", "d1", "e1",
X   "a2", "b2", "c2", "d2", "e2",
X   "a3", "b3", "c3", "d3", "e3",
X   "a4", "b4", "c4", "d4", "e4"
X};
X
Xvoid
XPrintBit(unsigned long mask)
X{
X   unsigned long t;
X   int i;
X   for (i = 0, t = (1 << 0); i < 20; ++i, t <<= 1) {
X      if (mask & t) {
X         printf(bit_names[i]);
X         return;
X      }
X   }
X   printf("??");
X   return;
X}
X
Xstatic int move_num = 0;
X
Xvoid
XPrintSolution(BoardConfiguration * bp)
X{
X   int i,j;
X   unsigned long mask;
X
X   if (bp == NULL) {
X      return;
X   }
X   PrintSolution(bp->parent);
X   printf("Board %d:\n", move_num++);
X   printf("  a b c d e ");
X   if (bp->parent == NULL) {
X      printf("starting position\n");
X   } else {
X      /* Figure out what the move was in algebraic notation and print that.
X       */
X      unsigned long old_mask = (bp->parent->black_mask |
X                                bp->parent->white_mask);
X      unsigned long new_mask = (bp->black_mask | bp->white_mask);
X      unsigned long changed_mask = old_mask ^ new_mask;
X      unsigned long old_bit = old_mask & changed_mask;
X      unsigned long new_bit = new_mask & changed_mask;
X      PrintBit(old_bit);
X      printf("-");
X      PrintBit(new_bit);
X      printf("\n");
X   }
X   mask = (1 << 0);
X   for (i = 0; i < 4; ++i) {
X      printf("%d", i + 1);
X      for (j = 0; j < 5; ++j) {
X         if (bp->black_mask & mask) {
X            printf(" B");
X         } else if (bp->white_mask & mask) {
X            printf(" W");
X         } else {
X            printf(" .");
X         }
X         mask <<= 1;
X      }
X      printf("\n");
X   }
X}
X
Xint
Xmain(int argc, char ** argv)
X{
X   BoardConfiguration * bp = FindLastPosition();
X   if (bp == NULL) {
X      printf("Failed to find solution.\n");
X      exit(2);
X   }
X   PrintSolution(bp);
X   printf("The total board count examined was %d.\n",board_count);
X}
END_OF_FILE
if test 14089 -ne `wc -c <'bishop.c'`; then
    echo shar: \"'bishop.c'\" unpacked with wrong size!
fi
# end of 'bishop.c'
fi
echo shar: End of archive 2 \(of 2\).
cp /dev/null ark2isdone
MISSING=""
for I in 1 2 ; do
    if test ! -f ark${I}isdone ; then
    MISSING="${MISSING} ${I}"
    fi
done
if test "${MISSING}" = "" ; then
    echo You have unpacked both archives.
    rm -f ark[1-9]isdone
else
    echo You still need to unpack the following archives:
    echo "        " ${MISSING}
fi
##  End of shell archive.
exit 0
--
======================================================================
domain: [e-mail]       USMail: Tom Horsley
  uucp: ...!uunet!hcx1!tahorsley               511 Kingbird Circle
                                               Delray Beach, FL  33444
+==== Censorship is the only form of Obscenity ======================+
|     (Wait, I forgot government tobacco subsidies...)               |
+====================================================================+

exit 0 # Just in case...