home *** CD-ROM | disk | FTP | other *** search
/ Big Blue Disk 22 / bbd22.zip / QUEENS.TXT < prev    next >
Text File  |  1988-05-23  |  4KB  |  81 lines
  1. |D╔═══════════╗═══════════════════════════════════════════════════════════════════
  2. |D║ |5Brainware |D║═══════════════════════════════════════════════════════════════════
  3. |D╚═══════════╝═══════════════════════════════════════════════════════════════════
  4.  
  5. ^C^1The Eight Queens Problem
  6. ^Cby
  7. ^CJohn Sigle
  8.  
  9.    Can you place eight queens on a chess board so that no two are attacking each
  10. other, that is, so that no two are on the same row, column, or diagonal?  Yes,
  11. it can be done!  This program is an animated demonstration of an algorithm to
  12. solve this problem.  It is adapted from a program in the book ^1Algorithms + Data
  13. ^1Structures = Programs^0 by Niklaus Wirth, Prentice-Hall, 1976.
  14.  
  15.    This program makes good use of recursion to search for a solution.  It places
  16. queens on the board column by column.  In order to place eight queens safely on
  17. the board, it places a queen safely in the first column and then tries to place
  18. the seven remaining queens safely on the board.  The latter problem (placing
  19. seven queens safely) is the same problem as the original (placing eight queens)
  20. only smaller in size.  This leads to a recursive solution.
  21.  
  22.    The program also illustrates backtracking, a method commonly used in
  23. applications requiring searching, such as many areas of artificial intelligence.
  24. When a "dead end" is reached (it is impossible to place any more of the
  25. remaining queens safely) the most recently placed queen is removed from its
  26. placement and advanced to a new position, if possible.  If it cannot be advanced
  27. then it is removed entirely and the next most recently placed queen is advanced,
  28. and so on.
  29.  
  30.    The choice of data structures in this program is also interesting.  It does
  31. not use a 2-dimensional array to represent the board as you might expect.  The
  32. most frequent task to be done by the program is testing to see if a position is
  33. safe, that is, whether or not any queens lie on the same row or diagonal as that
  34. position. The order of attempted queen placement (column by column) insures that
  35. no queen lies on the same column.  The data structures are chosen in order to
  36. make the testing task convenient and efficient.  "InRow" is a boolean array
  37. whose i-th element indicates whether a queen has been placed in row i.
  38. Similarly, "InDiag1" is a boolean array whose i-th element indicates whether a
  39. queen has been placed in the i-th / diagonal (a / diagonal slants upward to the
  40. right.)  For the numbering scheme shown below, all the positions on a given /
  41. diagonal have the same sum for their column and row numbers.  This sum can be
  42. used as an index to uniquely identify a / diagonal.  These indices range from 2
  43. thru 16.  "InDiag2" records occupancy for the \ diagonals.  The column number
  44. minus the row number is constant for all positions on a \ diagonal, and is used
  45. as an index, which ranges from -7 thru +7.
  46.  
  47. ^C^I 1 * * * * * * * * ^N
  48. ^C^I 2 * * * * * * * * ^N
  49. ^C^I 3 * * * * * * * * ^N
  50. ^C^I 4 * * * * * * * * ^N
  51. ^C^I 5 * * * * * * * * ^N
  52. ^C^I 6 * * * * * * * * ^N
  53. ^C^I 7 * * * * * * * * ^N
  54. ^C^I 8 * * * * * * * * ^N
  55. ^C^I   1 2 3 4 5 6 7 8 ^N
  56.  
  57.    This demo shows the PASCAL program as it executes as well as the data values
  58. being manipulated.  In addition it illustrates the program's actions on a chess
  59. board. The demo can be run at varying speeds.  It vividly shows the nature of
  60. this searching method and relates it directly to the PASCAL program performing
  61. the task.
  62.  
  63.    You can control the speed by pressing a digit 0-9 (not the numeric keypad) at
  64. any time.  Nine is the highest speed while 1 is the lowest.  A speed of 0 lets
  65. you single-step through the program by pressing the spacebar twice to execute
  66. each line of the program.  Also, by pressing the + key you can switch between
  67. two display modes: Full and Overview.  In Full mode every line executed is
  68. displayed.  In Overview mode only selected lines, actually comment lines, are
  69. displayed. In Overview mode the demo proceeds more quickly, yet shows the
  70. highlights of the process. You can scroll the program display forward or
  71. backward at any time by means of the up or down arrows.  At the conclusion of
  72. the demo the total number of positions tested and queen placements performed is
  73. reported.
  74.  
  75.    Type ^1PASRUN QUEENS-D^0 to run this program from outside the BIG BLUE DISK menu.
  76.  
  77. DISK FILES THIS PROGRAM USES:
  78. ^FQUEENS-D.CHN
  79. ^FPASRUN.COM
  80. ^FRETURN.CHN
  81.