home *** CD-ROM | disk | FTP | other *** search
/ AmigActive 3 / AACD03.BIN / AACD / Programming / sofa / archive / SmallEiffel.lha / SmallEiffel / lib_show / knight.e < prev    next >
Text File  |  1999-06-05  |  6KB  |  205 lines
  1. --          This file is part of SmallEiffel The GNU Eiffel Compiler.
  2. --          Copyright (C) 1994-98 LORIA - UHP - CRIN - INRIA - FRANCE
  3. --            Dominique COLNET and Suzanne COLLIN - colnet@loria.fr
  4. --                       http://SmallEiffel.loria.fr
  5. -- SmallEiffel is  free  software;  you can  redistribute it and/or modify it
  6. -- under the terms of the GNU General Public License as published by the Free
  7. -- Software  Foundation;  either  version  2, or (at your option)  any  later
  8. -- version. SmallEiffel is distributed in the hope that it will be useful,but
  9. -- WITHOUT ANY WARRANTY; without even the implied warranty of MERCHANTABILITY
  10. -- or  FITNESS FOR A PARTICULAR PURPOSE.   See the GNU General Public License
  11. -- for  more  details.  You  should  have  received a copy of the GNU General
  12. -- Public  License  along  with  SmallEiffel;  see the file COPYING.  If not,
  13. -- write to the  Free Software Foundation, Inc., 59 Temple Place - Suite 330,
  14. -- Boston, MA 02111-1307, USA.
  15. --
  16. class KNIGHT
  17. --|
  18. --| In this program a knight try to go over the n*n squares of a
  19. --| chessboard without pass by the same square again.
  20. --| The position of the knigth is given by a number.
  21. --|
  22. --|  Auteur: Christophe ALEXANDRE
  23. --|  date :  Thu Mar 21 1996
  24. --
  25. -- Here is an example of solution on a 7 X 7 chesboard,
  26. -- knigth starting at position <1,1> :
  27. --                 ----------------------
  28. --                 | 1|28|37|24| 3|26|17|
  29. --                 ----------------------
  30. --                 |36|39| 2|27|18|11| 4|
  31. --                 ----------------------
  32. --                 |29|42|23|38|25|16| 9|
  33. --                 ----------------------
  34. --                 |40|35|30|19|10| 5|12|
  35. --                 ----------------------
  36. --                 |43|22|41|32|15| 8|47|
  37. --                 ----------------------
  38. --                 |34|31|20|45|48|13| 6|
  39. --                 ----------------------
  40. --                 |21|44|33|14| 7|46|49|
  41. --                 ----------------------
  42. --
  43.  
  44. inherit ANY redefine print_on end;
  45.  
  46. creation make
  47.  
  48. feature
  49.  
  50.    make is
  51.       local
  52.          size, line, column: INTEGER;
  53.       do
  54.          if argument_count >= 1 and then argument(1).is_integer then
  55.             size := argument(1).to_integer;
  56.          end;
  57.          if not size.in_range(chess_min,chess_max) then
  58.             size := ask("Chess-board size: ",chess_min,chess_max);
  59.          end;
  60.          if argument_count >= 2 and then argument(2).is_integer then
  61.             line := argument(2).to_integer;
  62.          end;
  63.          if not line.in_range(1,size) then
  64.             line := ask("Start line: ",1,size);
  65.          end
  66.          if argument_count >= 3 and then argument(3).is_integer then
  67.             column := argument(3).to_integer;
  68.          end;
  69.          if not column.in_range(1,size) then
  70.             column := ask("Start column: ",1,size);
  71.          end;
  72.          knight(size,line,column)
  73.       end;
  74.  
  75. feature {NONE}
  76.  
  77.    chess_min: INTEGER is 3;
  78.  
  79.    chess_max: INTEGER is 24;
  80.  
  81.    chessboard: ARRAY2[INTEGER];
  82.  
  83.    nb_tries: INTEGER;
  84.  
  85.    tl: ARRAY[INTEGER] is
  86.       once
  87.          Result := <<-2,-1,1,2,2,1,-1,-2>>;
  88.       end;
  89.  
  90.    tc: ARRAY[INTEGER] is
  91.       once
  92.          Result := <<1,2,2,1,-1,-2,-2,-1>>;
  93.       end;
  94.  
  95.    knight(size, line, column: INTEGER) is
  96.       require
  97.          size >= 3;
  98.          1 <= line;
  99.          line <= size;
  100.          1 <= column;
  101.          column <= size;
  102.       do
  103.          !!chessboard.make(1,size,1,size);
  104.          chessboard.put(1,line,column);
  105.          if solution(line,column) then
  106.             print_on(std_output);
  107.          else
  108.             io.put_string("Sorry, there is no solution.%N");
  109.          end;
  110.          io.put_string("%NNumber of tries : ");
  111.          io.put_integer(nb_tries);
  112.          io.put_new_line;
  113.       end; -- knight
  114.  
  115.    solution(line,column:INTEGER):BOOLEAN is
  116.       local
  117.          value,i : INTEGER;
  118.       do
  119.          if chessboard.count = chessboard.item(line,column) then
  120.             Result := true;
  121.          else
  122.             from
  123.                i := 1;
  124.                value := chessboard.item(line,column);
  125.             until
  126.                Result or else i > 8
  127.             loop
  128.                Result := try(line+tl.item(i),column+tc.item(i),value);
  129.                i := i + 1;
  130.             end;
  131.          end;
  132.       end; -- solution
  133.  
  134.    try(line, column, value: INTEGER): BOOLEAN is
  135.          -- Try to place the knight by used cross back-tracking method.
  136.       do
  137.          nb_tries := nb_tries + 1;
  138.          if chessboard.valid_index(line,column) then
  139.             if chessboard.item(line,column) = 0 then
  140.                chessboard.put(value+1,line,column);
  141.                Result := solution(line,column);
  142.                if not Result then
  143.                   chessboard.put(0,line,column)
  144.                end;
  145.             end;
  146.          end
  147.       end; -- try
  148.  
  149.    ask(s:STRING; min, max: INTEGER):INTEGER is
  150.          -- Ask for question `s' until the answer is in range `min' `max'.
  151.       local
  152.          stop: BOOLEAN;
  153.       do
  154.          from until stop
  155.          loop
  156.             io.put_string(s);
  157.             io.flush;
  158.             io.read_integer;
  159.             Result := io.last_integer;
  160.             if Result < min then
  161.                io.put_string("Value too small.%N");
  162.             elseif max < Result then
  163.                io.put_string("Value too big.%N");
  164.             else
  165.                stop := true;
  166.             end;
  167.          end;
  168.       end;
  169.  
  170.    print_on(file: OUTPUT_STREAM) is
  171.          -- Display the cheesboard.
  172.       local
  173.          line,column : INTEGER;
  174.          separator : STRING;
  175.       do
  176.          from
  177.             !!separator.blank(3 * chessboard.upper1 + 1);
  178.             separator.fill_with('-');
  179.             separator.extend('%N')
  180.             file.put_string(separator);
  181.             line := chessboard.lower1
  182.          until
  183.             line > chessboard.upper1
  184.          loop
  185.             from
  186.                column := chessboard.lower2
  187.             until
  188.                column > chessboard.upper2
  189.             loop
  190.                if chessboard.item(line,column) < 10 then
  191.                   file.put_string("| ");
  192.                else
  193.                   file.put_character('|');
  194.                end;
  195.                file.put_integer(chessboard.item(line,column));
  196.                column := column + 1;
  197.             end;
  198.             file.put_string("|%N");
  199.             file.put_string(separator);
  200.             line := line + 1;
  201.          end;
  202.       end;
  203.  
  204. end -- KNIGHT
  205.