📄 710-713.html
字号:
<HTML>
<HEAD>
<META name=vsisbn content="1571690433"><META name=vstitle content="Black Art of Java Game Programming"><META name=vsauthor content="Joel Fan"><META name=vsimprint content="Sams"><META name=vspublisher content="Macmillan Computer Publishing"><META name=vspubdate content="11/01/96"><META name=vscategory content="Web and Software Development: Programming, Scripting, and Markup Languages: Java"><TITLE>Black Art of Java Game Programming:The Magic Squares Puzzle</TITLE>
<!-- HEADER --><STYLE type="text/css"> <!-- A:hover { color : Red; } --></STYLE><META NAME="ROBOTS" CONTENT="NOINDEX, NOFOLLOW"><script><!--function displayWindow(url, width, height) { var Win = window.open(url,"displayWindow",'width=' + width +',height=' + height + ',resizable=1,scrollbars=yes'); if (Win) { Win.focus(); }}//--></script><SCRIPT><!--function popUp(url) { var Win = window.open(url,"displayWindow",'width=400,height=300,resizable=1,scrollbars=yes'); if (Win) { Win.focus(); }}//--></SCRIPT><script language="JavaScript1.2"><!--function checkForQuery(fm) { /* get the query value */ var i = escape(fm.query.value); if (i == "") { alert('Please enter a search word or phrase'); return false; } /* query is blank, dont run the .jsp file */ else return true; /* execute the .jsp file */}//--></script></HEAD><BODY>
<TABLE border=0 cellspacing=0 cellpadding=0>
<tr>
<td width=75 valign=top>
<img src="../1571690433.gif" width=60 height=73 alt="Black Art of Java Game Programming" border="1">
</td>
<td align="left">
<font face="arial, helvetica" size="-1" color="#336633"><b>Black Art of Java Game Programming</b></font>
<br>
<font face="arial, helvetica" size="-1"><i>by Joel Fan</i>
<br>
Sams, Macmillan Computer Publishing
<br>
<b>ISBN:</b> 1571690433<b> Pub Date:</b> 11/01/96</font>
</td>
</tr>
</table>
<P>
<!--ISBN=1571690433//-->
<!--TITLE=Black Art of Java Game Programming//-->
<!--AUTHOR=Joel Fan//-->
<!--AUTHOR=Eric Ries//-->
<!--AUTHOR=Calin Tenitchi//-->
<!--PUBLISHER=Macmillan Computer Publishing//-->
<!--IMPRINT=Sams//-->
<!--CHAPTER=17//-->
<!--PAGES=710-713//-->
<!--UNASSIGNED1//-->
<!--UNASSIGNED2//-->
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="706-710.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="713-717.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
<P><BR></P>
<P>The commented code in Listing 17-15 speaks for itself and contains all of the global variables necessary for the solver to operate. The <I>start_board</I> initially has the same state as the board to solve and is modified to test the results of different combinations of moves. The <I>solve_window</I> is a TextArea supplied by the calling method to tell the class where to place its text output. The remaining variables serve to store information about the current state of the solve at any given time.</P>
<H4 ALIGN="CENTER"><A NAME="Heading19"></A><FONT COLOR="#000077">The solver Class Constructor</FONT></H4>
<P>This class employs only one constructor (given in Listing 17-16), which takes and stores its parameters. These parameters direct the class where to put the text information and what board configuration to solve for. The modularity of the game_board class and the presence of a copying constructor makes this method very simple.
</P>
<P><B>Listing 17-16</B> The constuctor for the solver class</P>
<!-- CODE SNIP //-->
<PRE>
solver (game_board board,TextArea t){ //thread constructor
start_board = new game_board(board); //create and copy new board
solve_window = t; //get the textarea to write to
}
</PRE>
<!-- END CODE SNIP //-->
<H4 ALIGN="CENTER"><A NAME="Heading20"></A><FONT COLOR="#000077">The solver Class run() Method</FONT></H4>
<P>The run() method for this class (shown in Listing 17-17) acts mostly as a driver for the try_all_squares() method. From the run() method’s perspective, the try_all_squares() method returns <I>true</I> if a board solution can be found within <I>i</I> moves. The run method thus tests try_all_squares() with integers increasing from one to a set maximum value to make sure that the shortest solve is found. If a path is found, the loop is broken and the thread stops.</P>
<P><B>Listing 17-17</B> The run() method for the solver class</P>
<!-- CODE //-->
<PRE>
public void run(){ //The thread's run method, what to do on start
int i;
visited = 0;
solve_window.appendText("Beginning solve.\n"); //little greeting
for (i=1;i<=max_depth;i++){ //go through each depth of search
solve_window.appendText("Attempting depth search of "+i+"\n");
if (try_all_squares(i) == true){ /*try every position from here*/
break;
}
solve_window.appendText("No solution found in "+visited+" boards.\n");
}
solve_window.appendText("Done solving\n");
}
</PRE>
<!-- END CODE //-->
<H4 ALIGN="CENTER"><A NAME="Heading21"></A><FONT COLOR="#000077">The try_all_squares() Method</FONT></H4>
<P>The run() method behaves without any concern for the implementation of try_all_squares(), which is important so that another implementation could be quickly integrated if a better one were found. Before looking at the current try_all_squares() method, some discussion of how it works is in order. The try_all_squares() method is recursive and brings all of the headaches that come with trying to understand any recursive method. For people who have managed to avoid using recursion, a recursive method is a method that calls itself. This would lead to infinite cycles and the like except that a check called “the basis” is put in the method to make it terminate on some condition. Recursion is seen in things like maze searching, tree traversals, and the solve routine for simple puzzles like the Towers of Hanoi and this one. The algorithm for the solve without the recursion looks like Listing 17-18.
</P>
<P><B>Listing 17-18</B> The algorithm for the try_all_squares() method without the recursion</P>
<!-- CODE SNIP //-->
<PRE>
starting with the board you want to solve
Make the first move. (ie. click on square one)
Check if this move completed the board
if so, quit
If not, take back the move and try the next move in the sequence
</PRE>
<!-- END CODE SNIP //-->
<P>If the algorithm in Listing 17-18 were implemented, it would successfully check to determine whether there were any one move that would solve the puzzle. Unfortunately, that would not solve any general puzzle, and most one-move puzzles could be solved by hand anyway. This is where the power of recursion comes in. To complete the algorithm, one extra step is needed. Instead of just checking whether the move solved the board, the try_all_squares() method is applied to the board after the move has been made, to try all of the possible moves one board away from that. In this way, a tree structure of calls is made that systematically tries all possible moves.
</P>
<P>What keeps this calling from infinitely occurring is the parameter <I>depth.</I> In each recursive call, the current depth is compared with <I>depth</I>, and the method terminates if the calls become too deep. Thus, if try_all_squares() is called with <I>depth</I> being three, the moves demonstrated in Figure 17-4 and Listing 17-19 would be made.</P>
<P><B>Listing 17-19</B> The try_all_squares() method</P>
<!-- CODE //-->
<PRE>
public boolean try_all_squares(int depth){ //do a board search of depth
//depth
int i,j,k,l,m; //counter variables
i=j=0;
if (start_board.is_completed()){ //start off the bat checking if
completed
print_solution();
return true;
}
if (current_depth > depth) //basis, don't recurse too far
return false; //return didn't find anything
try {
this.sleep(7); //Brief sleep to appease netscape
} catch (InterruptedException e){}
for (i=0;i<start_board.side_squares;i++) //go through each possible move
for (j=0;j<start_board.side_squares;j++){
start_board.apply_move_s(i,j); //apply the current move
solved[current_depth][0]=i; //save the current move on solved stack
solved[current_depth][1]=j;
if (is_repeat()){ //if this move would be a repeated move
start_board.undo_move(i,j); //undo the last move so can resume
continue; //skip this move, should have some savings
}
visited++; //count the number of boards seen
if (start_board.is_completed()){ //if this move completed the board
print_solution(); //print out the solution
return true;
}
else { //didn't solve the board with this move
current_depth++; //go to next depth
if (try_all_squares(depth)==true) //if next depth found a solution
return true; //then done, return
else
current_depth--; //come back to this depth and try another
}
start_board.undo_move(i,j); //undo the last move so can continue
}
start_board.undo_move(i,j); //restore the board
return false;
}
</PRE>
<!-- END CODE //-->
<P><A NAME="Fig4"></A><A HREF="javascript:displayWindow('images/17-04.jpg',562,345 )"><IMG SRC="images/17-04t.jpg"></A>
<BR><A HREF="javascript:displayWindow('images/17-04.jpg',562,345)"><FONT COLOR="#000077"><B>Figure 17-4</B></FONT></A> The first few moves of a solve with depth of 3<P><BR></P>
<CENTER>
<TABLE BORDER>
<TR>
<TD><A HREF="706-710.html">Previous</A></TD>
<TD><A HREF="../ewtoc.html">Table of Contents</A></TD>
<TD><A HREF="713-717.html">Next</A></TD>
</TR>
</TABLE>
</CENTER>
</BODY>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -