home *** CD-ROM | disk | FTP | other *** search
/ NetNews Usenet Archive 1992 #26 / NN_1992_26.iso / spool / comp / lang / pascal / 6483 < prev    next >
Encoding:
Text File  |  1992-11-11  |  3.4 KB  |  87 lines
  1. Organization: Freshman, CIT general, Carnegie Mellon, Pittsburgh, PA
  2. Path: sparky!uunet!zaphod.mps.ohio-state.edu!cis.ohio-state.edu!news.sei.cmu.edu!fs7.ece.cmu.edu!crabapple.srv.cs.cmu.edu!andrew.cmu.edu!sz24+
  3. Newsgroups: comp.lang.pascal
  4. Message-ID: <8f0FTSW00iUxA1MGAe@andrew.cmu.edu>
  5. Date: Wed, 11 Nov 1992 09:25:34 -0500 
  6. From: "Stephan A. Zdancewic" <sz24+@andrew.cmu.edu>
  7. Subject: Re: Chess Puzzle
  8. In-Reply-To: <1dp5hbINNbu4@west.West.Sun.COM>
  9. References: <1dp5hbINNbu4@west.West.Sun.COM>
  10. Lines: 75
  11.  
  12. >This is my first posting to this group, so I hope it even gets there,
  13. here >goes!
  14. >I'm trying to work out a solution to the "Eight Queens" chess problem
  15. whereby y
  16. >ou
  17. >try to place 8 queens on a chessboard in such a way that no one queen can get 
  18. >another queen. I've seen a solution to this problem using the "Icon"
  19. language b
  20. >ut
  21. >I,m interrested in a Pascal solution. I figure 2 arrays [1..8] can
  22. represent >the
  23. >chessboard and I've worked out a procedure on how to make a
  24. horizontal,vertical
  25. > and
  26. >both diagonals un-usable upon placement of a queen. The problem is in a
  27. recursi
  28. >ve
  29. >procedure to keep trying the next placement and so on. Anybody have any
  30. clues >or
  31. >has anyone seen this before. Steer me in the right direction!!!
  32.  
  33. We just wrote a program in my computer science class to check a chess
  34. board as you describe to see if it is 'safe.'  Based on the techniques
  35. we used I have several suggestions that I hope are of some help.
  36. First, it is probably easier to use a two dimensional array [1..8,1..8]
  37. of boolean. That way you don't have to worry about arrays of arrays -
  38. that could get messy.
  39. One way to write this program (although it would be very slow) without
  40. recursion would be to start at the upper corner of the board. Here's
  41. some pseudo-code:
  42.  
  43. start at corner;
  44. if (row is safe) and (column is safe) and (diagonals are safe) then put
  45. a queen;
  46. move to next square;
  47.  
  48. To check it a given line of squares is safe use code something like this:
  49.  
  50. function SafeLine(board : boardType; row, col, rowInc, colInc) : boolean;
  51.  
  52. var  Attacking : boolean;
  53.  
  54. begin
  55.  Attacking := false;
  56.  row := row + rowInc; {These two lines make sure you don't check the 'current' 
  57.  col := col + colInc;   square}
  58.  while (row > 0) and (row <= 8) and (col > 0) and (col <= 8) and
  59. not(Attacking)         
  60.    do begin
  61.      if board[row, col] then Attacking := true;
  62.      row := row + rowInc;
  63.      col := col + colInc;
  64.    end;
  65.  SafeLine := not(Attacking);
  66. end;
  67.  
  68. This function assumes you have a type boardType which is an array of
  69. booleans.  A true represents a queen.  This function would be used like
  70. this
  71.   If SafeLine(board, row, col, 0, 1) then writeln ('The row to the right
  72. of this square is safe');
  73. To check diagonals make rowInc and colInc equal to 1 or -1, depending on
  74. what direction you'd like to check.  The northeast diagonal would be -1,
  75. 1.
  76.  
  77. This program would generate the same board each time, and it would be
  78. slow but it would work.  I'm sure that there are much faster ways of
  79. accomplishing this, but I hope this starts you in the right direction.
  80.  
  81. ............. . . . . .  .  .  .  .   .   .   .   .   .   .    .    .   
  82.  .     .     .      .       .       .       .        .            .     
  83.  Steve Zdancewic                :  [INSERT APROPRIATE QUOTE HERE]
  84. sz24@andrew.cmu.edu    :
  85. ............. . . . . .  .  .  .  .   .   .   .   .   .   .    .    .   
  86.  .     .     .      .       .       .       .        .            .
  87.