home *** CD-ROM | disk | FTP | other *** search
/ Club Amiga de Montreal - CAM / CAM_CD_1.iso / files / 417.lha / Rubik / source / solve.c < prev    next >
Encoding:
C/C++ Source or Header  |  1990-09-02  |  10.0 KB  |  696 lines
  1. /*    I couldn't get an elegant tree searcher to work.  Hence this kludge. */
  2.  
  3. #include "sequences.c"
  4.  
  5. short failed;
  6. short waiting_output;
  7. unsigned char output_buffer[20];
  8.  
  9. extern char tr [120];
  10. extern struct one_square square[56];
  11.  
  12. extern void showtwist (short, short);
  13. extern struct IntuiMessage *msg, *getmsg();
  14. extern struct Window *wnd1,*wnd2;
  15.  
  16. struct IntuiMessage *flush()
  17.     {
  18.     unsigned char move;
  19.     short layer,direc;
  20.     short i;
  21.     
  22.     msg = NULL;
  23.     
  24.     while (waiting_output && ((msg = getmsg()) == NULL))
  25.         {
  26.         move = output_buffer[0];
  27.     
  28.         layer = --move/3;
  29.         if ((direc = (move % 3)) == 0)
  30.             direc = -1;
  31.  
  32.         showtwist (layer,direc);
  33.         
  34.         for (i=0; i < waiting_output; i++)
  35.             output_buffer[i] = output_buffer[i+1];
  36.         
  37.         --waiting_output;
  38.         }
  39.     
  40.     return (msg);
  41.     }
  42.  
  43. void output (unsigned char move)
  44.     {
  45.     output_buffer [waiting_output++] = move;
  46.     }
  47.  
  48. void cornerseq (short seq)
  49.     {
  50.     unsigned short i;
  51.     
  52.     for (i=0; i<6; i++)
  53.         output(corner5[seq][i]);
  54.     }
  55.  
  56. short checkcorner
  57.     (
  58.     short offset,
  59.     short a, short b, short c,
  60.     short x, short y, short z
  61.     )
  62.     {
  63.     short corner = 0;
  64.     
  65.     if (square[x].colour == a)
  66.         {
  67.         if
  68.             (
  69.             ((square[y].colour == b) && (square[z].colour == c)) ||
  70.             ((square[y].colour == c) && (square[z].colour == b))
  71.             )
  72.             corner = 1 + offset;
  73.         }
  74.     else if (square[y].colour == a)
  75.         {
  76.         if
  77.             (
  78.             ((square[x].colour == b) && (square[z].colour == c)) ||
  79.             ((square[x].colour == c) && (square[z].colour == b))
  80.             )
  81.             corner = 2 + offset;
  82.         }
  83.     else if (square[z].colour == a)
  84.         {
  85.         if
  86.             (
  87.             ((square[x].colour == b) && (square[y].colour == c)) ||
  88.             ((square[x].colour == c) && (square[y].colour == b))
  89.             )
  90.             corner = 3 + offset;
  91.         }
  92.     
  93.     return (corner);
  94.     }
  95.  
  96. short findcorner (short a, short b, short c)
  97.     {
  98.     short corner;
  99.  
  100.     a = square[a].colour;
  101.     b = square[b].colour;
  102.     c = square[c].colour;
  103.     
  104.     if
  105.         (
  106.         ((corner = checkcorner(0,a,b,c,0,18,36)) == 0) &&
  107.         ((corner = checkcorner(3,a,b,c,2,45,20)) == 0) &&
  108.         ((corner = checkcorner(6,a,b,c,6,42,27)) == 0) &&
  109.         ((corner = checkcorner(9,a,b,c,8,29,51)) == 0) &&
  110.         ((corner = checkcorner(12,a,b,c,9,38,24)) == 0) &&
  111.         ((corner = checkcorner(15,a,b,c,11,26,47)) == 0) &&
  112.         ((corner = checkcorner(18,a,b,c,15,33,44)) == 0)
  113.         )
  114.         corner = checkcorner(21,a,b,c,17,53,35);
  115.     
  116.     return (corner);
  117.     }
  118.  
  119. void edgeseq (short seq)
  120.     {
  121.     unsigned short i;
  122.     
  123.     for (i=0; i<6; i++)
  124.         output(edge4[seq][i]);
  125.  
  126.     }
  127.  
  128. void edgeseq2 (short seq)
  129.     {
  130.     unsigned short i;
  131.  
  132.     for (i=0; i<5; i++)
  133.         output(edge5[seq][i]);
  134.     }
  135.  
  136. short checkedge
  137.     (
  138.     short offset,
  139.     short a, short b,
  140.     short x, short y
  141.     )
  142.     {
  143.     short edge = 0;
  144.     
  145.     if ((square[x].colour == a) && (square[y].colour == b))
  146.         edge = 1 + offset;
  147.     else if ((square[x].colour == b) && (square[y].colour == a))
  148.         edge = 2 + offset;
  149.  
  150.     return (edge);
  151.     }
  152.  
  153. short findedge (short a, short b)
  154.     {
  155.     short edge;
  156.  
  157.     a = square[a].colour;
  158.     b = square[b].colour;
  159.  
  160.     if    (
  161.         ((edge = checkedge(0,a,b,1,19)) == 0) &&
  162.         ((edge = checkedge(2,a,b,3,39)) == 0) &&
  163.         ((edge = checkedge(4,a,b,5,48)) == 0) &&
  164.         ((edge = checkedge(6,a,b,7,28)) == 0) &&
  165.         ((edge = checkedge(8,a,b,10,25)) == 0) &&
  166.         ((edge = checkedge(10,a,b,12,41)) == 0) &&
  167.         ((edge = checkedge(12,a,b,14,50)) == 0) &&
  168.         ((edge = checkedge(14,a,b,16,34)) == 0) &&
  169.         ((edge = checkedge(16,a,b,21,37)) == 0) &&
  170.         ((edge = checkedge(18,a,b,23,46)) == 0) &&
  171.         ((edge = checkedge(20,a,b,30,43)) == 0)
  172.         )
  173.         edge = checkedge(22,a,b,32,52);
  174.  
  175.     return (edge);
  176.     }
  177.  
  178. void edgesequence (int seq)
  179.     {
  180.     short i,j;
  181.     unsigned char u;
  182.     
  183.     if (seq < 24)
  184.         for (i = 1; i <= edge1[seq][0]; i++)
  185.             output (edge1[seq][i]);
  186.     else
  187.         for (i = 1; i <= edge2[seq-24][0]; i++)
  188.             {
  189.             if ((u = edge2[seq-24][i]) < 19)
  190.                 output (u);
  191.             else
  192.                 for (j = 1; j <= edge3[u-19][0]; j++)
  193.                     output (edge3[u-19][j]);
  194.             }
  195.     }
  196.  
  197. struct IntuiMessage *edgefix(short up, short right, short down)
  198.     {
  199.     short i;
  200.  
  201.     if ((findedge(right,up) == 1) && (findedge(right,down) == 7))
  202.         return (NULL);
  203.     
  204.     if ((i = findedge(down,right)) == 0)
  205.         {
  206.         failed = 1;
  207.         return (NULL);
  208.         }
  209.     
  210.     if (i > 1)
  211.         edgesequence(i-2);
  212.     
  213.     if (msg = flush())
  214.         return (msg);
  215.  
  216.     if ((i = findedge(right,up)) < 3)
  217.         {
  218.         failed = 1;
  219.         return (0);
  220.         }
  221.     
  222.     edgesequence(i + 21);
  223.     
  224.     return (flush());
  225.     }
  226.  
  227. struct IntuiMessage *solve()
  228.     {
  229.     short i,j;
  230.     
  231.     if (msg = flush())
  232.         return (msg);
  233.  
  234. /*    get right corners correct    */
  235.  
  236.     if ((i = findcorner(4,22,40)-2) < -1)
  237.         return (NULL);
  238.     
  239.     if (i >= 0)
  240.         for (j=1; j<=corner1[i][0]; j++)
  241.             output (corner1[i][j]);
  242.  
  243.     if (msg = flush())
  244.         return (msg);
  245.         
  246.     if ((i = findcorner(4,49,22)-5) < -1)
  247.         return (NULL);
  248.     
  249.     if (i >= 0)
  250.         for (j=1; j<=corner2[i][0]; j++)
  251.             output (corner2[i][j]);
  252.  
  253.     if (msg = flush())
  254.         return(msg);
  255.  
  256.     if ((i = findcorner(4,40,31)-8) < -1)
  257.         return (NULL);
  258.     
  259.     if (i >= 0)
  260.         for (j=1; j<=corner3[i][0]; j++)
  261.             output (corner3[i][j]);
  262.  
  263.     if (msg = flush())
  264.         return(msg);
  265.  
  266.     if ((i = findcorner(4,31,49)-11) < -1)
  267.         return (NULL);
  268.     
  269.     if (i >= 0)
  270.         for (j=1; j<=corner4[i][0]; j++)
  271.             output (corner4[i][j]);
  272.  
  273.     if (msg = flush())
  274.         return(msg);
  275.  
  276. /*    get left corners in position    */
  277.  
  278.     if ((i = findcorner(13,40,22)-13) < 0)
  279.         return (NULL);
  280.     
  281.     switch (i/3)
  282.         {
  283.         case 0:
  284.             break;
  285.         case 1:
  286.             output (5);
  287.             break;
  288.         case 2:
  289.             output (4);
  290.             break;
  291.         case 3:
  292.             output (6);
  293.             break;
  294.         default:
  295.             return (NULL);
  296.         }
  297.     
  298.     if (msg = flush())
  299.         return(msg);
  300.  
  301.     if ((i = findcorner(13,22,49)-16) < 0)
  302.         return (NULL);
  303.     
  304.     switch (i/3)
  305.         {
  306.         case 0:
  307.             break;
  308.         case 1:
  309.             output (5);
  310.             output (8);
  311.             output (4);
  312.             output (11);
  313.             output (5);
  314.             output (7);
  315.             output (4);
  316.             output (10);
  317.             break;
  318.         case 2:
  319.             output (11);
  320.             output (5);
  321.             output (8);
  322.             output (4);
  323.             output (10);
  324.             output (5);
  325.             output (7);
  326.             output (4);
  327.             break;
  328.         default:
  329.             return (NULL);
  330.         }
  331.  
  332.     if (msg = flush())
  333.         return(msg);
  334.  
  335.     if ((i = findcorner(13,31,40)-19) < 0)
  336.         return (NULL);
  337.     
  338.     switch (i/3)
  339.         {
  340.         case 0:
  341.             break;
  342.         case 1:
  343.             output (4);
  344.             output (17);
  345.             output (5);
  346.             output (14);
  347.             output (4);
  348.             output (16);
  349.             output (5);
  350.             output (13);
  351.             output (4);
  352.             break;
  353.         default:
  354.             return (NULL);
  355.         }
  356.  
  357.     if (msg = flush())
  358.         return(msg);
  359.  
  360. /*    get left corners oriented    */
  361.  
  362.     if ((i = findcorner(13,40,22)-13) < 0)
  363.         return (NULL);
  364.     
  365.     switch (i)
  366.         {
  367.         case 0:
  368.             break;
  369.         case 1:
  370.             cornerseq (1);
  371.             
  372.             if (msg = flush())
  373.                 return (msg);
  374.             
  375.             if (findcorner(13,22,49)==18)
  376.                 {
  377.                 output (5);
  378.                 cornerseq (0);
  379.                 output (4);
  380.                 }
  381.             else if (findcorner(13,31,40)==21)
  382.                 {
  383.                 output (4);
  384.                 cornerseq (0);
  385.                 output (5);
  386.                 }
  387.             else
  388.                 {
  389.                 output (6);
  390.                 cornerseq (0);
  391.                 output (6);
  392.                 }
  393.             
  394.             break;
  395.         case 2:
  396.             cornerseq (0);
  397.             
  398.             if (msg = flush())
  399.                 return (msg);
  400.  
  401.             if (findcorner(13,22,49)==17)
  402.                 {
  403.                 output (5);
  404.                 cornerseq (1);
  405.                 output (4);
  406.                 }
  407.             else if (findcorner(13,31,40)==20)
  408.                 {
  409.                 output (4);
  410.                 cornerseq (1);
  411.                 output (5);
  412.                 }
  413.             else
  414.                 {
  415.                 output (6);
  416.                 cornerseq (1);
  417.                 output (6);
  418.                 }
  419.             
  420.             break;
  421.         default:
  422.             return (NULL);
  423.         }
  424.  
  425.     if (msg = flush())
  426.         return(msg);
  427.  
  428.     if ((i = findcorner(13,22,49)-16) < 0)
  429.         return (NULL);
  430.     
  431.     switch (i)
  432.         {
  433.         case 0:
  434.             break;
  435.         case 1:
  436.             cornerseq (3);
  437.             
  438.             if (msg = flush())
  439.                 return (msg);
  440.  
  441.             if (findcorner(13,31,40)==21)
  442.                 {
  443.                 output (6);
  444.                 cornerseq (2);
  445.                 output (6);
  446.                 }
  447.             else
  448.                 {
  449.                 output (5);
  450.                 cornerseq (2);
  451.                 output (4);
  452.                 }
  453.             
  454.             break;
  455.         case 2:
  456.             cornerseq (2);
  457.             
  458.             if (msg = flush())
  459.                 return (msg);
  460.  
  461.             if (findcorner(13,31,40)==20)
  462.                 {
  463.                 output (6);
  464.                 cornerseq (3);
  465.                 output (6);
  466.                 }
  467.             else
  468.                 {
  469.                 output (5);
  470.                 cornerseq (3);
  471.                 output (4);
  472.                 }
  473.             
  474.             break;
  475.         default:
  476.             return (NULL);
  477.         }
  478.  
  479.     if (msg = flush())
  480.         return(msg);
  481.  
  482.     if ((i = findcorner(13,31,40)-19) < 0)
  483.         return (NULL);
  484.     
  485.     switch (i)
  486.         {
  487.         case 0:
  488.             break;
  489.         case 1:
  490.             cornerseq (5);
  491.             output (4);
  492.             cornerseq (4);
  493.             output (5);
  494.             break;
  495.         case 2:
  496.             cornerseq (4);
  497.             output (4);
  498.             cornerseq (5);
  499.             output (5);
  500.             break;
  501.         default:
  502.             return (NULL);
  503.         }
  504.  
  505.     if (msg = flush())
  506.         return (msg);
  507.  
  508.     if ((i = findcorner(13,49,31)) != 22)
  509.         return (NULL);
  510.  
  511. /*    make top and bottom edges correct    */
  512.     
  513.     failed = 0;
  514.     
  515.     if (msg = edgefix(22,4,31))
  516.         return (msg);
  517.     
  518.     if (failed)
  519.         return (NULL);
  520.     
  521.     output (7);
  522.     output (10);
  523.     
  524.     if (msg = flush())
  525.         return(msg);
  526.  
  527.     if (msg = edgefix(22,40,31))
  528.         return (msg);
  529.     
  530.     if (failed)
  531.         return (NULL);
  532.  
  533.     output (7);
  534.     output (10);
  535.     
  536.     if (msg = flush())
  537.         return (msg);
  538.  
  539.     if (msg = edgefix(22,13,31))
  540.         return (msg);
  541.     
  542.     if (failed)
  543.         return (NULL);
  544.  
  545.     output (7);
  546.     output (10);
  547.     
  548.     if (msg = flush())
  549.         return(msg);
  550.  
  551.     if (msg = edgefix(22,49,31))
  552.         return (msg);
  553.     
  554.     if (failed)
  555.         return (NULL);
  556.  
  557.     output (7);
  558.     output (10);
  559.     
  560.     if (msg = flush())
  561.         return(msg);
  562.  
  563. /*    get middle slice edges into position    */
  564.  
  565.     switch (findedge(4,40))
  566.         {
  567.         case 3:
  568.         case 4:
  569.             break;
  570.         case 5:
  571.         case 6:
  572.             edgeseq (0);
  573.             break;
  574.         case 11:
  575.         case 12:
  576.             edgeseq (1);
  577.             break;
  578.         case 13:
  579.         case 14:
  580.             edgeseq (2);
  581.             break;
  582.         default:
  583.             return (NULL);
  584.         }
  585.  
  586.     if (msg = flush())
  587.         return(msg);
  588.  
  589.     switch (findedge(13,49))
  590.         {
  591.         case 5:
  592.         case 6:
  593.             edgeseq (3);
  594.             break;
  595.         case 11:
  596.         case 12:
  597.             edgeseq (4);
  598.             break;
  599.         case 13:
  600.         case 14:
  601.             break;
  602.         default:
  603.             return (NULL);
  604.         }
  605.     
  606.     if (msg = flush())
  607.         return(msg);
  608.  
  609. /*    get middle edges oriented    */
  610.  
  611.     if (findedge(4,40) == 4)
  612.         {
  613.         edgeseq2 (0);
  614.         
  615.         if (msg = flush())
  616.             return(msg);
  617.  
  618.         if (findedge(4,49) == 6)
  619.             {
  620.             output (7);
  621.             output (10);
  622.             edgeseq2 (3);
  623.             output (8);
  624.             output (11);
  625.             }
  626.         else if (findedge(13,40) == 12)
  627.             {
  628.             output (8);
  629.             output (11);
  630.             edgeseq2 (4);
  631.             output (7);
  632.             output (10);
  633.             }
  634.         else
  635.             {
  636.             output (9);
  637.             output (12);
  638.             edgeseq2 (5);
  639.             output (9);
  640.             output (12);
  641.             }
  642.         }
  643.  
  644.     if (msg = flush())
  645.         return(msg);
  646.  
  647.     if (findedge(4,49) == 6)
  648.         {
  649.         edgeseq2 (1);
  650.         
  651.         if (msg = flush())
  652.             return(msg);
  653.  
  654.         if (findedge(13,40) == 12)
  655.             {
  656.             output (9);
  657.             output (12);
  658.             edgeseq2 (4);
  659.             output (9);
  660.             output (12);
  661.             }
  662.         else
  663.             {
  664.             output (7);
  665.             output (10);
  666.             edgeseq2 (5);
  667.             output (8);
  668.             output (11);
  669.             }
  670.         }
  671.  
  672.     if (msg = flush())
  673.         return(msg);
  674.  
  675.     if (findedge(13,40) == 12)
  676.         {
  677.         edgeseq2 (2);
  678.         output (8);
  679.         output (11);
  680.         edgeseq2 (5);
  681.         output (7);
  682.         output (10);
  683.         }
  684.  
  685.     if (msg = flush())
  686.         return(msg);
  687.  
  688. /*    if (findedge(13,49) != 13)
  689.         return (NULL);
  690. */
  691.     return (NULL);
  692.     }
  693.  
  694.  
  695.  
  696.