Return to puzzle.c CVS log

Up to [Research Unix] / researchv9 / X11 / src / X.V11R1 / clients / puzzle

Annotation of researchv9/X11/src/X.V11R1/clients/puzzle/puzzle.c, revision 1.1

1.1     ! root        1: /*
        !             2:  *     $Source: /orpheus/u1/X11/clients/puzzle/RCS/puzzle.c,v $
        !             3:  *     $Header: puzzle.c,v 1.1 87/09/08 17:27:13 swick Exp $
        !             4:  */
        !             5: 
        !             6: #ifndef lint
        !             7: static char *rcsid_puzzle_c = "$Header: puzzle.c,v 1.1 87/09/08 17:27:13 swick Exp $";
        !             8: #endif lint
        !             9: 
        !            10: /**
        !            11:  **  Puzzle
        !            12:  **
        !            13:  ** Don Bennett, HP Labs
        !            14:  ** 
        !            15:  ** this is the code that does the real work to solve the
        !            16:  ** puzzle.  (Commonly seen as a 4x4 grid of sliding pieces
        !            17:  ** numbered 1-15 with one empty space.) 
        !            18:  **
        !            19:  ** The idea for the solution algorithm - solving the puzzle
        !            20:  ** in layers working from the outside in - comes to me
        !            21:  ** indirectly from John Nagle.
        !            22:  **/
        !            23: 
        !            24: #include <setjmp.h>
        !            25: 
        !            26: #define min(x,y)       (((x)>(y))?(x):(y))
        !            27:     
        !            28: #define MAX_PLAN       1000
        !            29: 
        !            30: #define LEFT   0
        !            31: #define RIGHT  1
        !            32: #define UP     2
        !            33: #define        DOWN    3
        !            34: 
        !            35: int other_dir[4] = { RIGHT, LEFT, DOWN, UP };
        !            36: 
        !            37: /** layer info macros ->  (innermost 4 tiles are layer zero, ordinal goes up
        !            38:  **                       as you move out)
        !            39:  ** layer_depth                - returns number of (rows down),(cols across) the layer starts;
        !            40:  ** layer_width        - number of blocks wide the layer is;
        !            41:  **/
        !            42: 
        !            43: #define layer_depth(l) (layers-1-(l))
        !            44: #define layer_width(l) (PuzzleSize - 2*layer_depth(l))
        !            45: 
        !            46: /** macros for finding the corners of each layer **/
        !            47: 
        !            48: #define UL(l)  (layer_depth(l)*(PuzzleSize+1) + \
        !            49:                 ExtraRows*PuzzleWidth + ExtraColumns*(layers-(l)))
        !            50: #define UR(l)   (layer_depth(l)*(PuzzleSize+1) + layer_width(l) - 1 + \
        !            51:                 ExtraRows*PuzzleWidth + ExtraColumns*(layers-(l)))
        !            52: #define LL(l)   ((layer_depth(l)+layer_width(l)-1)*PuzzleSize+layer_depth(l)+ \
        !            53:             ExtraRows*PuzzleSize + ExtraColumns*(PuzzleHeight+1+(l)-layers))
        !            54: #define LR(l)  ((layer_depth(l)+layer_width(l)-1)*(PuzzleSize+1) + \
        !            55:             ExtraRows*PuzzleSize + ExtraColumns*(PuzzleHeight+1+(l)-layers))
        !            56: 
        !            57: /** get the x and y coordinates of a location in the matrix **/
        !            58: 
        !            59: #define get_x(loc)     ((loc) % PuzzleWidth)
        !            60: #define get_y(loc)     ((loc) / PuzzleWidth)
        !            61: #define indx(x,y)      (((y)*PuzzleWidth) + (x))
        !            62: 
        !            63: #define next_left(loc) (loc - 1)
        !            64: #define next_right(loc)        (loc + 1)
        !            65: #define next_up(loc)   (loc - PuzzleWidth)
        !            66: #define next_down(loc) (loc + PuzzleWidth)
        !            67: 
        !            68: #define sign(foo)      (((foo)>0)?1:-1)
        !            69: 
        !            70: int OutputLogging = 0;
        !            71: 
        !            72: static int SolvingFlag = 0;
        !            73: static int AbortSolvingFlag = 0;
        !            74: 
        !            75: static int ExtraRows = 0;
        !            76: static int ExtraColumns = 0;
        !            77: 
        !            78: /** PuzzleSize MUST be a multiple of 2; **/
        !            79: extern int PuzzleSize;
        !            80: extern int PuzzleWidth, PuzzleHeight;
        !            81: 
        !            82: int layers;
        !            83: 
        !            84: int *tmp_matrix;
        !            85: int *target;
        !            86: int *locked;
        !            87: int *link;
        !            88: int *position;
        !            89: 
        !            90: int space_x, space_y;          /** location of space in the position matrix **/
        !            91: 
        !            92: static jmp_buf solve_env;
        !            93: 
        !            94: /**
        !            95:  ** this piece of code needs to be fixed if you want to use it
        !            96:  ** for non-square matrices;
        !            97:  **/
        !            98: print_matrix(mat)
        !            99: int (*mat)[];
        !           100: {
        !           101:    int i,j;
        !           102: 
        !           103:    printf("\n");
        !           104:    for (i=0; i<PuzzleHeight; i++) {
        !           105:       for (j=0; j<PuzzleWidth; j++)
        !           106:          printf(" %2d ",(*mat)[indx(j,i)]);
        !           107:       printf("\n");
        !           108:    }
        !           109:    printf("\n");
        !           110: }
        !           111: 
        !           112: find_piece(piece)
        !           113: int piece;
        !           114: {
        !           115:    int i;
        !           116: 
        !           117:    for (i=0; i<PuzzleWidth*PuzzleHeight; i++)
        !           118:       if (position[i] == piece)
        !           119:          return(i);      
        !           120: 
        !           121:    printf("piece %d not found!\n",piece);
        !           122:    exit(1);
        !           123: }
        !           124: 
        !           125: move_space_to(loc)
        !           126: int loc;
        !           127: {
        !           128:    int i,current_dir,dist;
        !           129:    int plan[MAX_PLAN];
        !           130: 
        !           131:    plan_move(indx(space_x,space_y),loc,plan);
        !           132:    current_dir = plan[1];
        !           133:    dist = 0;
        !           134:    for (i=1; i<=plan[0]; i++)
        !           135:       if (plan[i] == current_dir)
        !           136:          dist++;
        !           137:       else if (plan[i] == other_dir[current_dir])
        !           138:          dist--;
        !           139:       else {
        !           140:          move_space(current_dir,dist);
        !           141:          current_dir = plan[i];
        !           142:          dist = 1;
        !           143:       }
        !           144:    move_space(current_dir,dist);
        !           145: }
        !           146: 
        !           147: move_piece(loc,target)
        !           148: int loc,target;
        !           149: {
        !           150:    int i;
        !           151:    int plan[MAX_PLAN];
        !           152: 
        !           153:    plan_move(loc,target,plan);
        !           154:    for (i=1; i<=plan[0]; i++)
        !           155:       switch(plan[i]) {
        !           156:       case LEFT:       locked[loc] = 1;
        !           157:                        move_space_to(next_left(loc));
        !           158:                        locked[loc] = 0;
        !           159:                        move_space_to(loc);
        !           160:                        loc = next_left(loc);
        !           161:                        break;
        !           162:       case RIGHT:      locked[loc] = 1;
        !           163:                        move_space_to(next_right(loc));
        !           164:                        locked[loc] = 0;
        !           165:                        move_space_to(loc);
        !           166:                        loc = next_right(loc);
        !           167:                        break;
        !           168:       case UP:         locked[loc] = 1;
        !           169:                        move_space_to(next_up(loc));
        !           170:                        locked[loc] = 0;
        !           171:                        move_space_to(loc);
        !           172:                        loc = next_up(loc);
        !           173:                        break;
        !           174:       case DOWN:       locked[loc] = 1;
        !           175:                        move_space_to(next_down(loc));
        !           176:                        locked[loc] = 0;
        !           177:                        move_space_to(loc);
        !           178:                        loc = next_down(loc);
        !           179:                        break;
        !           180:       }
        !           181: }
        !           182: 
        !           183: plan_move(start_loc,end_loc,path)
        !           184: int start_loc, end_loc;
        !           185: int (*path)[];
        !           186: {
        !           187: 
        !           188: #define QUEUE_SIZE     1000
        !           189: #define DIST(loc1,loc2)        (abs(get_x(loc1) - get_x(loc2)) + abs(get_y(loc1) - get_y(loc2)))
        !           190: 
        !           191:    int i, next_loc, next_dist, chosen, found_path, move_num;
        !           192:    int loc_x, loc_y;
        !           193:    int loc_queue[QUEUE_SIZE];
        !           194:    int loc_dist[QUEUE_SIZE];
        !           195:    int loc_queue_used[QUEUE_SIZE];
        !           196:    int queue_head, queue_tail;
        !           197:    int candidate[4];
        !           198: 
        !           199:    found_path = 0;
        !           200: 
        !           201:    for (i=0; i<PuzzleWidth*PuzzleHeight; i++) {
        !           202:       tmp_matrix[i] = -locked[i];
        !           203:       link[i] = -1;
        !           204:    }
        !           205: 
        !           206:    for (i=0; i<QUEUE_SIZE; i++)
        !           207:       loc_queue_used[i] = 0;
        !           208: 
        !           209:    queue_head = 0;
        !           210:    queue_tail = 0;
        !           211: 
        !           212:    loc_queue[0] = start_loc;
        !           213:    loc_dist[0]  = DIST(end_loc,start_loc);
        !           214:    tmp_matrix[start_loc] = 1;
        !           215:    queue_tail++;
        !           216: 
        !           217:    /** if the selected element has a distance of zero, we've found it;
        !           218:     **  (This really isn't a queue, but rather a range of elements
        !           219:     ** to be searched for an element of the desired properties;    
        !           220:     **/
        !           221: 
        !           222:    /** as we search for a path, 
        !           223:     ** LINK       array is used to indicate the direction from which 
        !           224:     **            we moved into a location;  
        !           225:     ** TMP_MATRIX array is used to keep track of the move number;
        !           226:     **/
        !           227: 
        !           228:    while(queue_head < queue_tail && !found_path) {
        !           229:       /** find the entry that
        !           230:        ** (1) has the smallest distance and
        !           231:        ** (2) has the smallest move number;
        !           232:        **/
        !           233: 
        !           234:       next_loc = loc_queue[queue_head];
        !           235:       next_dist = loc_dist[queue_head];
        !           236:       chosen = queue_head;
        !           237: 
        !           238:       for (i=queue_head+1; i<queue_tail; i++)
        !           239:          if (!loc_queue_used[i]                &&
        !           240:              (   loc_dist[i] < next_dist)         ||
        !           241:                  (      (loc_dist[i] == next_dist)    && 
        !           242:                         (tmp_matrix[loc_queue[i]] < tmp_matrix[next_loc])
        !           243:               )) {
        !           244:             next_loc = loc_queue[i];
        !           245:             next_dist = loc_dist[i];
        !           246:             chosen = i;
        !           247:          }
        !           248: 
        !           249:       if (next_dist == 0) {
        !           250:          found_path = 1;
        !           251:          break;
        !           252:       }
        !           253: 
        !           254:       loc_queue_used[chosen] = 1;
        !           255: 
        !           256:       /********************************/
        !           257:       /** permute the chosen element **/
        !           258:       /********************************/
        !           259: 
        !           260:       candidate[0] = next_left(next_loc);
        !           261:       candidate[1] = next_right(next_loc);
        !           262:       candidate[2] = next_up(next_loc);
        !           263:       candidate[3] = next_down(next_loc);
        !           264: 
        !           265:       loc_x = get_x(next_loc);
        !           266:       loc_y = get_y(next_loc);
        !           267:       
        !           268:       if (loc_x == 0)                  candidate[0] = -1;
        !           269:       if (loc_x == PuzzleWidth-1)      candidate[1] = -1;
        !           270:       if (loc_y == 0)                  candidate[2] = -1;
        !           271:       if (loc_y == PuzzleHeight-1)     candidate[3] = -1;
        !           272: 
        !           273:       move_num = tmp_matrix[next_loc] + 1;
        !           274: 
        !           275:       for (i=0; i<4; i++)
        !           276:          if (candidate[i] != -1 && tmp_matrix[candidate[i]] == 0) {
        !           277:             tmp_matrix[candidate[i]] = move_num;
        !           278:             /** the next line works because the candidate index is  
        !           279:              ** same as the direction moved to reach the candidate;
        !           280:              **/
        !           281:             link[candidate[i]] = i;
        !           282:             loc_queue[queue_tail] = candidate[i];
        !           283:             loc_dist[queue_tail] = DIST(end_loc,candidate[i]);
        !           284:             queue_tail++;
        !           285:             if (queue_tail == QUEUE_SIZE) goto broke;
        !           286:          }
        !           287: 
        !           288:       /***************************************************/
        !           289:       /** delete used items from the front of the queue **/
        !           290:       /***************************************************/
        !           291: 
        !           292:       while(loc_queue_used[queue_head] && queue_head < queue_tail)
        !           293:          queue_head++;
        !           294:    }
        !           295: 
        !           296:    if (!found_path) {
        !           297:       printf("couldn't find a way to move (%d,%d) to (%d,%d).\n",
        !           298:               get_x(start_loc),get_y(start_loc),
        !           299:               get_x(end_loc),get_y(end_loc));
        !           300: #ifdef UNDEFINED
        !           301:       print_matrix(position);
        !           302:       printf("\n");
        !           303:       print_matrix(locked);
        !           304:       printf("\n");
        !           305: #endif UNDEFINED
        !           306:       return(0);
        !           307:    }
        !           308: 
        !           309: broke:   if (queue_tail == QUEUE_SIZE) {
        !           310:             printf("it didn't work.\n");
        !           311:             return(0);
        !           312:          }
        !           313: 
        !           314:    /** copy the path we found into the path array;
        !           315:     ** element 0 will contain the number of moves in the path;
        !           316:     **/
        !           317: 
        !           318:    /** by the time we get there, next_loc is in the final location **/
        !           319: 
        !           320:    (*path)[0] = tmp_matrix[next_loc] - 1;
        !           321:    for (i=(*path)[0]; i>0; i--) {
        !           322:       (*path)[i] = link[next_loc];
        !           323:       switch(link[next_loc]) {
        !           324:       case LEFT:       next_loc = next_right(next_loc);
        !           325:                        break;
        !           326:       case RIGHT:      next_loc = next_left(next_loc);
        !           327:                        break;
        !           328:       case UP:         next_loc = next_down(next_loc);
        !           329:                        break;
        !           330:       case DOWN:       next_loc = next_up(next_loc);
        !           331:                        break;
        !           332:       }
        !           333:    }
        !           334: }
        !           335: 
        !           336: move_space(dir,dist)
        !           337: int dir,dist;
        !           338: {
        !           339:    int i, step, count;
        !           340:    int min_x,max_x,min_y,max_y;
        !           341:    int first_x,first_y;
        !           342:    int last_x,last_y, shift_dir;
        !           343: 
        !           344: 
        !           345:    if (PuzzlePending()) ProcessEvents();
        !           346:    if (SolvingFlag && AbortSolvingFlag)
        !           347:       longjmp(solve_env,1);
        !           348: 
        !           349:    if (dist == 0)
        !           350:       return;
        !           351: 
        !           352:    if (dir == LEFT) {
        !           353:       dir = RIGHT;
        !           354:       dist = -dist;
        !           355:    }
        !           356: 
        !           357:    if (dir == UP) {
        !           358:       dir = DOWN;
        !           359:       dist = -dist;
        !           360:    }
        !           361: 
        !           362:    first_x = space_x;
        !           363:    first_y = space_y;
        !           364: 
        !           365:    step = 1;
        !           366:    count = dist;
        !           367:    if (dist < 0) {
        !           368:       step  = -1;
        !           369:       count = -count;
        !           370:    }
        !           371: 
        !           372:    /** first_x,y are the location of the first piece to be shifted **/
        !           373:    if (dir == RIGHT)
        !           374:       first_x += step;
        !           375:    else
        !           376:       first_y += step;
        !           377: 
        !           378:    /** shift_dir is the direction the pieces need to be shifted **/
        !           379:    if (dist < 0)
        !           380:       shift_dir = dir;
        !           381:    else
        !           382:       switch (dir) {
        !           383:       case LEFT:  shift_dir = RIGHT; break;
        !           384:       case RIGHT: shift_dir = LEFT;  break;
        !           385:       case UP:    shift_dir = DOWN;  break;
        !           386:       case DOWN:  shift_dir = UP;    break;
        !           387:       }
        !           388: 
        !           389:    for (i=0; i<count; i++)
        !           390:       if (dir == RIGHT) {
        !           391:          position[indx(space_x,space_y)] = position[indx(space_x+step,space_y)];
        !           392:          position[indx(space_x+step,space_y)] = 0;
        !           393:          space_x += step;
        !           394:       }
        !           395:       /** dir == DOWN **/
        !           396:       else {
        !           397:          position[indx(space_x,space_y)] = position[indx(space_x,space_y+step)];
        !           398:          position[indx(space_x,space_y+step)] = 0;
        !           399:          space_y += step;
        !           400:       }
        !           401: 
        !           402:    last_x = space_x;
        !           403:    last_y = space_y;
        !           404:    
        !           405:    /** the blocks first_x,y through last_x,y need to be shifted
        !           406:     ** one block in the shift_dir direction;
        !           407:     **/
        !           408: 
        !           409:    if (OutputLogging)
        !           410:      LogMoveSpace(first_x,first_y,last_x,last_y,shift_dir);
        !           411: }
        !           412: 
        !           413: initialize()
        !           414: {
        !           415:    /** Initialize the position and
        !           416:     ** the target matrices;
        !           417:     **/
        !           418: 
        !           419:    int i;
        !           420:    int sp_x, sp_y;
        !           421: 
        !           422:    srand(42);
        !           423:    layers = PuzzleSize / 2;
        !           424: 
        !           425:    ExtraRows    = PuzzleHeight - PuzzleSize;
        !           426:    ExtraColumns = PuzzleWidth - PuzzleSize;
        !           427: 
        !           428:    tmp_matrix = (int *) malloc(PuzzleWidth*PuzzleHeight*sizeof(int));
        !           429:    target     = (int *) malloc(PuzzleWidth*PuzzleHeight*sizeof(int));
        !           430:    locked     = (int *) malloc(PuzzleWidth*PuzzleHeight*sizeof(int));
        !           431:    link       = (int *) malloc(PuzzleWidth*PuzzleHeight*sizeof(int));
        !           432:    position   = (int *) malloc(PuzzleWidth*PuzzleHeight*sizeof(int));
        !           433: 
        !           434:    for (i=0; i<PuzzleWidth*PuzzleHeight; i++)
        !           435:       locked[i] = 0;
        !           436: 
        !           437:    if (!tmp_matrix || !target || !locked || !link || !position) {
        !           438:        printf("matrix allocation failed.\n");
        !           439:        exit(1);
        !           440:    }
        !           441: 
        !           442:    for (i=0; i<PuzzleWidth*PuzzleHeight-1; i++) {
        !           443:       target[i] = i+1;
        !           444:       position[i] = i+1;
        !           445:    }
        !           446: 
        !           447:    /** assert i == PuzzleWidth * PuzzleHeight - 1; **/
        !           448:    position[i] = 0;
        !           449:    target[i] = 0;
        !           450: 
        !           451:    space_x = PuzzleWidth - 1;
        !           452:    space_y = PuzzleHeight - 1;
        !           453: 
        !           454: 
        !           455:    /** Move the space into the LR corner of the
        !           456:     ** innermost layer; 
        !           457:     ** For each of the outer layers, move the space
        !           458:     ** left one and up one;
        !           459:     **/
        !           460: 
        !           461:    sp_x = space_x;
        !           462:    sp_y = space_y;
        !           463: 
        !           464:    for (i=0; i<layers-1; i++) {
        !           465:       /** move the space left one; **/
        !           466:       target[indx(sp_x,sp_y)] = target[indx(sp_x-1,sp_y)];
        !           467:       target[indx(sp_x-1,sp_y)] = 0;
        !           468:       sp_x -= 1;
        !           469: 
        !           470:       /** move the space up one; **/
        !           471:       target[indx(sp_x,sp_y)] = target[indx(sp_x,sp_y-1)];
        !           472:       target[indx(sp_x,sp_y-1)] = 0;
        !           473:       sp_y -= 1;
        !           474:    }
        !           475: }
        !           476: 
        !           477: Scramble()
        !           478: {
        !           479:    int i;
        !           480:    int new_x, new_y;
        !           481:    int old_output_state;
        !           482: 
        !           483:    old_output_state = OutputLogging;
        !           484:    OutputLogging = 0;
        !           485: /*   srand(42); */
        !           486:    
        !           487: 
        !           488:    for (i=0; i<10*PuzzleWidth*PuzzleHeight; i++) {
        !           489:       new_x = rand() % PuzzleWidth;
        !           490:       new_y = rand() % PuzzleHeight;
        !           491: 
        !           492:       move_space(RIGHT,new_x-space_x);
        !           493:       move_space(DOWN,new_y-space_y);
        !           494:    }
        !           495: 
        !           496:    OutputLogging = old_output_state;
        !           497: }
        !           498: 
        !           499: /** To solve this puzzle, work from the outside in;
        !           500:  ** For each successive ring working your way in, 
        !           501:  ** 
        !           502:  ** (1) put the corners in place;
        !           503:  ** (2) finish off the rest of the boundaries;
        !           504:  ** (3) do the next layer in;
        !           505:  **/
        !           506: 
        !           507: solve_layer_0()
        !           508: {
        !           509:    move_piece(find_piece(target[UL(0)]),UL(0));
        !           510:    move_space_to(LR(0));   
        !           511: }
        !           512: 
        !           513: do_last_two_on_edge(ntlast,last,tmp,emergency)
        !           514: int ntlast,last,tmp,emergency;
        !           515: {
        !           516:    int last_piece, ntlast_piece;
        !           517:    last_piece = target[last];
        !           518:    ntlast_piece = target[ntlast];
        !           519: 
        !           520:    move_piece(find_piece(ntlast_piece),last);
        !           521:    locked[last] = 1;
        !           522: 
        !           523:    /** if the last piece is stuck where the next to the last
        !           524:     ** piece should go, do some magic to fix things up;
        !           525:     **/
        !           526:    if (find_piece(0) == ntlast)
        !           527:       move_space_to(tmp);
        !           528: 
        !           529:    if (find_piece(last_piece) == ntlast) {
        !           530:    /** a rescue is necessary **/
        !           531:       locked[last] = 0;
        !           532:       move_piece(find_piece(ntlast_piece),ntlast);
        !           533:       locked[ntlast] = 1;
        !           534:       move_piece(find_piece(last_piece),emergency);
        !           535:       locked[emergency] = 1;
        !           536:       locked[ntlast] = 0;
        !           537:       move_piece(find_piece(ntlast_piece),last);
        !           538:       locked[emergency] = 0;
        !           539:       locked[last] = 1;
        !           540:    }
        !           541: 
        !           542:    move_piece(find_piece(last_piece),tmp);
        !           543:    locked[tmp] = 1;
        !           544:    move_space_to(ntlast);
        !           545:    locked[tmp]  = 0;
        !           546:    locked[last] = 0;
        !           547:    move_space_to(last);
        !           548:    move_space_to(tmp);
        !           549:    locked[ntlast] = 1;
        !           550:    locked[last] = 1;
        !           551: }
        !           552: 
        !           553: solve_layer(layer)
        !           554: int layer;
        !           555: {
        !           556:    int i, tmp, last, ntlast, emergency;
        !           557:    int ul, ur, ll, lr;
        !           558: 
        !           559: 
        !           560:    if (layer == 0)
        !           561:       solve_layer_0();
        !           562:    else {
        !           563:       /** find and put each of the corners into place **/      
        !           564:       ul = UL(layer);      
        !           565:       ur = UR(layer);
        !           566:       ll = LL(layer);
        !           567:       lr = LR(layer);
        !           568: 
        !           569:       move_piece(find_piece(target[ul]),ul);
        !           570:       locked[ul] = 1;
        !           571:       move_piece(find_piece(target[ur]),ur);
        !           572:       locked[ur] = 1;
        !           573:       move_piece(find_piece(target[ll]),ll);
        !           574:       locked[ll] = 1;
        !           575:       move_piece(find_piece(target[lr]),lr);
        !           576:       locked[lr] = 1;
        !           577: 
        !           578:       /** Strategy for doing the pieces between the corners:
        !           579:        ** (1) put all but the last two edge pieces in place; 
        !           580:        ** (2) put the next to the last piece next to the corner;
        !           581:        ** (3) put the last piece one move in from its final position;
        !           582:        ** (4) move the space to the final position of the next
        !           583:        **     to the last piece;
        !           584:        ** (5) slide the next to the last piece over and the last 
        !           585:        **     piece into the edge where it goes.
        !           586:        **/
        !           587: 
        !           588:       /**************/
        !           589:       /** top edge **/
        !           590:       /**************/
        !           591:       for (i=ul+1; i<ur-2; i++) {
        !           592:          move_piece(find_piece(target[i]),i);
        !           593:          locked[i] = 1;
        !           594:       }
        !           595: 
        !           596:       ntlast = i;
        !           597:       last   = i+1;
        !           598:       tmp    = UR(layer-1);
        !           599:       emergency = next_down(tmp);
        !           600:       do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           601: 
        !           602:       /*****************/
        !           603:       /** bottom edge **/
        !           604:       /*****************/
        !           605:       for (i=ll+1; i<lr-2; i++) {
        !           606:          move_piece(find_piece(target[i]),i);
        !           607:          locked[i] = 1;
        !           608:       }
        !           609: 
        !           610:       ntlast = i;
        !           611:       last   = i+1;
        !           612:       tmp    = LR(layer-1);
        !           613:       emergency = next_up(tmp);
        !           614:       do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           615: 
        !           616:       /***************/
        !           617:       /** left side **/
        !           618:       /***************/
        !           619:       for (i=ul+PuzzleWidth; i<ll-2*PuzzleWidth; i+=PuzzleWidth) {
        !           620:          move_piece(find_piece(target[i]),i);
        !           621:          locked[i] = 1;
        !           622:       }
        !           623: 
        !           624:       ntlast = i;
        !           625:       last   = i + PuzzleWidth;
        !           626:       tmp    = LL(layer-1);
        !           627:       emergency = next_right(tmp);
        !           628:       do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           629: 
        !           630:       /****************/
        !           631:       /** right side **/
        !           632:       /****************/
        !           633:       for (i=ur+PuzzleWidth; i<lr-2*PuzzleWidth; i+=PuzzleWidth) {
        !           634:          move_piece(find_piece(target[i]),i);
        !           635:          locked[i] = 1;
        !           636:       }
        !           637: 
        !           638:       ntlast = i;
        !           639:       last   = i + PuzzleWidth;
        !           640:       tmp    = LR(layer-1);
        !           641:       emergency = next_left(tmp);
        !           642:       do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           643:    }
        !           644: }
        !           645: 
        !           646: solve_row(row)
        !           647: int row;
        !           648: {
        !           649:     int i, loc, last, ntlast, tmp, emergency;
        !           650: 
        !           651:     for (i=0; i<PuzzleWidth-2; i++) {
        !           652:        loc = indx(i,row);
        !           653:        move_piece(find_piece(target[loc]),loc);
        !           654:        locked[loc] = 1;
        !           655:     }
        !           656: 
        !           657:     ntlast = indx(PuzzleWidth-2,row);
        !           658:     last = indx(PuzzleWidth-1,row);
        !           659:     tmp = last + PuzzleWidth;
        !           660:     emergency = tmp + PuzzleWidth;
        !           661:     do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           662: }
        !           663: 
        !           664: solve_col(col)
        !           665: int col;
        !           666: {
        !           667:     int i, loc, last, ntlast, tmp, emergency;
        !           668: 
        !           669:     for (i=0; i<PuzzleHeight-2; i++) {
        !           670:        loc = indx(col,i);
        !           671:        move_piece(find_piece(target[loc]),loc);
        !           672:        locked[loc] = 1;
        !           673:     }
        !           674: 
        !           675:     ntlast = indx(col,PuzzleHeight-2);
        !           676:     last = indx(col,PuzzleHeight-1);
        !           677:     tmp = last + 1;
        !           678:     emergency = tmp + 1;
        !           679:     do_last_two_on_edge(ntlast,last,tmp,emergency);
        !           680: }
        !           681: 
        !           682: AbortSolving()
        !           683: {
        !           684:    if (SolvingFlag) 
        !           685:       AbortSolvingFlag = 1;
        !           686: }
        !           687: 
        !           688: SolvingStatus()
        !           689: {
        !           690:     return(SolvingFlag);
        !           691: }
        !           692: 
        !           693: Solve()
        !           694: {
        !           695:    /** determine the position we want to be in when
        !           696:     ** we are done; This position will have the space in 
        !           697:     ** the center;  Then, we'll move the space back to 
        !           698:     ** the outside.
        !           699:     **/
        !           700: 
        !           701:    int i;  
        !           702: 
        !           703: 
        !           704:    if (SolvingFlag)
        !           705:       return;
        !           706: 
        !           707:    if (!setjmp(solve_env)) {
        !           708:       SolvingFlag = 1;
        !           709: 
        !           710:       for (i=0; i<PuzzleWidth*PuzzleHeight; i++)
        !           711:          locked[i] = 0;
        !           712: 
        !           713:       /** solve the extra rows and cols **/
        !           714:       for (i=0; i<ExtraRows; i++)
        !           715:          solve_row(i);
        !           716: 
        !           717:       for (i=0; i<ExtraColumns; i++)
        !           718:          solve_col(i);
        !           719: 
        !           720:       /** solve each layer **/
        !           721:       for (i=layers-1; i>=0; i--)
        !           722:          solve_layer(i);
        !           723: 
        !           724:       /** move the space back out to the LR corner; **/
        !           725:       /** i is the layer the space is moving into **/
        !           726:       for (i=1; i<layers; i++) {
        !           727:          move_space(DOWN,1);
        !           728:          move_space(RIGHT,1);
        !           729:       }
        !           730:    }
        !           731:    else
        !           732:       RepaintTiles();
        !           733: 
        !           734:    for (i=0; i<PuzzleWidth*PuzzleHeight; i++)
        !           735:       locked[i] = 0;
        !           736: 
        !           737:    AbortSolvingFlag = 0;
        !           738:    SolvingFlag = 0;
        !           739: }
        !           740: 
        !           741: #ifdef UNDEFINED
        !           742: main()
        !           743: {
        !           744: #ifdef DEBUG
        !           745:    int plan[1000];
        !           746:    int i;
        !           747: #endif DEBUG
        !           748: 
        !           749:    initialize();
        !           750: 
        !           751: #ifdef DEBUG
        !           752:    print_matrix(position);
        !           753: #endif DEBUG
        !           754: 
        !           755:    scramble();
        !           756: 
        !           757: #ifdef DEBUG
        !           758:    print_matrix(position);
        !           759: 
        !           760: #ifdef UDEFINED
        !           761:    locked[indx(4,3)] = 1;
        !           762:    locked[indx(4,2)] = 1;
        !           763:    locked[indx(4,1)] = 1;
        !           764:    locked[indx(5,2)] = 1;
        !           765: 
        !           766:    plan_move(indx(space_x,space_y),indx(5,1),plan);
        !           767:    print_matrix(tmp_matrix);
        !           768:    printf("\nplan has %d moves.\n",plan[0]);
        !           769:    for (i=0; i<plan[0]; i++) {
        !           770:       switch(plan[i+1]) {
        !           771:       case UP:    printf("up\n");
        !           772:                   break;
        !           773:       case DOWN:  printf("down\n");
        !           774:                   break;
        !           775:       case LEFT:  printf("left\n");
        !           776:                   break;
        !           777:       case RIGHT: printf("right\n");
        !           778:                   break;
        !           779:       }
        !           780:    }
        !           781: #endif UDEFINED
        !           782: #endif DEBUG
        !           783: 
        !           784:    solve();
        !           785: }
        !           786: #endif UNDEFINED

This archive runs on limited infrastructure. Preserving old code on modern bandwidth. Automated agents are requested to crawl responsibly.