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