home *** CD-ROM | disk | FTP | other *** search
/ io Programmo 14 / IOPROG_14.ISO / soft / sdkjava / sdkjava.exe / SDKJava.cab / Samples / AFC / Puzzle15 / Src / Pz15Solver.Java < prev    next >
Encoding:
Java Source  |  1998-03-05  |  5.8 KB  |  227 lines
  1. //
  2. // (c) 1998 Microsoft Corporation.  All rights reserved.
  3. //
  4. import java.lang.Math;
  5. import com.ms.ui.*;
  6. import com.ms.fx.*;
  7.  
  8. public class Pz15Solver extends Pz15Data implements Runnable, Pz15Consts
  9. {
  10.     public int costbound;
  11.  
  12.     private Pz15Callbacks pzctrl;
  13.     private ChildNode movelist[] = new ChildNode[MAX_MOVES];
  14.     private int moveptr[] = new int[MAX_DEPTH];
  15.     private int    depth;
  16.     private long total_nodes, num_nodes;
  17.     private UIMessageBox optsoln = null;
  18.     private String solnstr = new String("");
  19.     private boolean firstdisplay;
  20.  
  21.     public Pz15Solver()
  22.     {
  23.         super();
  24.         solved = false;
  25.     }
  26.  
  27.     // In lieu of a constructor
  28.     public void registerCallback(Pz15Callbacks pzctrl, UIFrame frame)
  29.     {
  30.         this.pzctrl = pzctrl;
  31.         // Create Message Box for displaying optimal solution
  32.         optsoln = new UIMessageBox(frame, "Optimal Solution", "",
  33.                                     UIMessageBox.INFORMATION, UIButtonBar.OK);
  34.         optsoln.setFont(new FxFont("Dialog", FxFont.PLAIN, 14));
  35.     }
  36.     
  37.     public void run()
  38.     {
  39.         firstdisplay = true;
  40.         moveptr[0] = 0;
  41.         movelist[0] = new ChildNode(NO_MOVE, initial_cost);
  42.  
  43.         // Check to see if goal puzzle is passed in
  44.         if ( movelist[0].cost == 0 ) 
  45.             return;
  46.  
  47.         costbound = movelist[0].cost;
  48.  
  49.         total_nodes = 0;
  50.         num_nodes = 0;
  51.  
  52.         while ( !solved ) {
  53.             depth = 1;
  54.             genChildren(movelist[0]);
  55.             while ( depth > 0 ) {
  56.                 // if there are no children, BACKTRACK
  57.                 if ( moveptr[depth] == moveptr[depth-1] ) {
  58.                     depth--;
  59.                     if ( depth != 0 )
  60.                         privUpdate(-movelist[moveptr[depth]--].move);
  61.                 }
  62.                 else {
  63.                     ChildNode node = movelist[moveptr[depth]];
  64.                     privUpdate(node.move);
  65.                     if ( solved )
  66.                         break; // break out of depth while loop
  67.                     else  {
  68.                         depth++;
  69.                         genChildren(node);
  70.                     }
  71.                 }
  72.             }            
  73.  
  74.             if ( !solved ) 
  75.                 costbound += 2;
  76.             else
  77.                 pzctrl.setMarqueeString(MRQ_OPTIMALFND, S_RESET);
  78.  
  79.             pzctrl.setOptMoves(costbound, solved);
  80.         }
  81.         // If we get to here puzzle is solved
  82.         pzctrl.enableShowSolution(true);
  83.     }
  84.  
  85.     public void displayOptimalSolution()
  86.     {
  87.         if ( firstdisplay ) {
  88.             firstdisplay = false;
  89.             solnstr = "" + total_nodes + " total nodes expanded.\n\n";
  90.  
  91.             int navmode = pzctrl.getNavMode();
  92.             for ( int i = 0; i <= depth; i++ ) {
  93.                 switch (movelist[moveptr[i]].move) {
  94.                 case O_UP: solnstr += (navmode == M_BUTTON ? "D":"U"); break;
  95.                 case O_LEFT: solnstr += (navmode == M_BUTTON ? "R":"L"); break;
  96.                 case O_RIGHT: solnstr += (navmode == M_BUTTON ? "L":"R"); break;
  97.                 case O_DOWN: solnstr += (navmode == M_BUTTON ? "U":"D"); break;
  98.                 }
  99.                 if ( (i != 0) && (i != depth) && ((i % 4) == 0) ) solnstr += ",";
  100.                 if ( (i != 0) && (i != depth) && ((i % 20) == 0) ) solnstr += "\n";
  101.             }
  102.             solnstr += ".\n";
  103.             optsoln.setText(solnstr);
  104.         }
  105.         optsoln.doModal();
  106.     }
  107.  
  108.     private void privUpdate(int move)
  109.     {
  110.         current_cost += getCost(move);
  111.         current[hole] = current[hole+move];
  112.         hole += move;
  113.         current[hole] = 0;
  114.         if ( current_cost == 0 )
  115.             solved = true;
  116.     }
  117.  
  118.     private void genChildren(ChildNode node)
  119.     {
  120.         int i, index;
  121.         int numChildren = 0;
  122.         int possible[] = { NO_MOVE, NO_MOVE, NO_MOVE, NO_MOVE };
  123.  
  124.         moveptr[depth] = moveptr[depth-1];
  125.  
  126.         // Find out which moves are possible
  127.         for ( i = 0; i < 4; i++ )
  128.             possible[i] = validateMove(MOVES[i]);
  129.         
  130.         for ( i = 0; i < 4; i++ ) {
  131.             // don't do NO_MOVE or reverse move
  132.             if ( !((possible[i] == NO_MOVE) || (possible[i] == -node.move)) ) {
  133.                 int cost = node.cost + 1 + getCost(possible[i]);
  134.                 if ( cost <= costbound ) {
  135.                     numChildren++;
  136.                     index = ++moveptr[depth];
  137.                     addChild(numChildren, index, possible[i], cost);
  138.                 }
  139.             }
  140.         }
  141.         if ( numChildren > 0 ) {
  142.             total_nodes++;
  143.             num_nodes++;
  144.             if ( num_nodes == 50000 )
  145.             {
  146.                 num_nodes = 0;
  147.                 pzctrl.setMarqueeString(MRQ_SEARCHING + genDisplay(total_nodes) + " nodes.",
  148.                                         S_NORESET);
  149.             }
  150.         }
  151.     }
  152.  
  153.     private void addChild(int numChildren, int index, int move, int cost)
  154.     {
  155.         switch (numChildren) {
  156.         case 4:
  157.             if ( cost > movelist[index-3].cost) {
  158.                 movelist[index] = movelist[index-1];
  159.                 movelist[index-1] = movelist[index-2];
  160.                 movelist[index-2] = movelist[index-3];
  161.                 movelist[index-3] = new ChildNode(move, cost);
  162.                 break;
  163.             }
  164.             // FALL-THROUGH when if statement is FALSE
  165.         case 3:
  166.             if ( cost > movelist[index-2].cost ) {
  167.                 movelist[index] = movelist[index-1];
  168.                 movelist[index-1] = movelist[index-2];
  169.                 movelist[index-2] = new ChildNode(move, cost);
  170.                 break;
  171.             }
  172.             // FALL-THROUGH when if statement is FALSE
  173.         case 2:
  174.             if ( cost > movelist[index-1].cost ) {
  175.                 movelist[index] = movelist[index-1];
  176.                 movelist[index-1] = new ChildNode(move, cost);
  177.                 break;
  178.             }
  179.             // FALL-THROUGH when if statement is FALSE
  180.         case 1:
  181.             movelist[index] = new ChildNode(move, cost);
  182.             break;
  183.  
  184.         default:
  185.             break;
  186.         }
  187.     }
  188.  
  189.     private String genDisplay(long num)
  190.     {
  191.         if ( num >= 1000000000000L )    return "";
  192.  
  193.         String disp = "";
  194.         int i, firstnz;
  195.         long digits[] = new long[12];
  196.  
  197.         for ( i = 0; i < 12; i++ )
  198.             digits[11-i] = (num/Math.round(Math.pow(10,i))) % 10;
  199.  
  200.         for ( firstnz = 0; firstnz < 12; firstnz++ )
  201.             if ( digits[firstnz] != 0 )    break;
  202.  
  203.         switch( firstnz % 3 ) {
  204.         case 0: disp += digits[firstnz] + "" + digits[firstnz+1] + "" + digits[firstnz+2]; break;
  205.         case 1: disp += digits[firstnz] + "" + digits[firstnz+1] + "." + digits[firstnz+2]; break;
  206.         case 2: disp += digits[firstnz] + "." + digits[firstnz+1] + "" + digits[firstnz+2]; break;
  207.         }
  208.  
  209.         if ( firstnz < 3 ) disp += " billion";
  210.         else if ( firstnz < 6 ) disp += " million";
  211.         else if ( firstnz < 9 ) disp += " thousand";
  212.  
  213.         return disp;
  214.     }
  215. }
  216.  
  217. class ChildNode
  218. {
  219.     public int move;
  220.     public int cost;
  221.  
  222.     public ChildNode(int move, int cost)
  223.     {
  224.         this.move = move;
  225.         this.cost = cost;
  226.     }
  227. }