Приложение     A

Исходный код программ для задачи "Восемь ферзей"

Разделы

Содержание

В этом приложении приведены готовые программы для задачи о восьми ферзях, описанной в главе═5.

А.1. "Задача о восьми ферзях" на языке Apple Object Pascal

Разделы 

(*
 Задача "Восемь ферзей", язык Object Pascal
 Автор: Тимоти Бадд, университет штата Орегон,═1996
*)
Program EightQueen;

type

 Queen = object
			(* поля данных *)
    row : integer;
    column : integer;
    neighbor : Queen;

			(* инициализация *)
    procedure initialize (col : integer; ngh : Queen);

			(* операции *)
    function canAttack (testRow, testColumn : integer) : boolean;
    function findSolution : boolean;
    function advance : boolean;
    procedure print;
  end;

var
  neighbor, lastQueen : Queen;
  i : integer;

procedure Queen.initialize (col : integer; ngh : Queen);
begin
  (* инициализация нашего столбца и соседних значений *)
  column := col;
  neighbor :=ngh;

  (* начать со строки═1 *)
  row :=═1;
end;

function Queen.canAttack(testRow, testColumn : integer) 
                        : boolean;
var
  can : boolean;
  columnDifference : integer;

begin
  (* проверить, одинаковые ли строки *)
  can := (row = testRow);

  (* теперь проверить диагонали *)
  if not can then
  begin
    columnDifference := testColumn═≈ column;
    if( (row + columnDifference = testrow) or
        (row═≈ columnDifference = testRow) ) 
    then can := true;
  end;

  (* наконец проверить соседей *)
  if ((not can) and (neighbor <> nil)) then
    can := neighbor.canAttack(testRow, testColumn);

  canAttack := can;
end;

function Queen.findSolution : boolean;
var
  done : boolean;

begin
  done := false;
  findSolution := true;

  (* найти подходящую позицию *)
  if neighbor <> nil then
    while (not done and neighbor.canAttack(row, column)) do
      if not self.advance then 
      begin
        findSolution := false;
        done := true;
      end;
end;

function Queen.advance : boolean;
begin
  advance := false;

  (* попробовать следующий ряд *)
  if row <═8 then 
  begin
    row := row +═1;
    advance := self.findSolution;
  end
  else begin
	(* дальше нельзя *)
    (* передвинуть соседа, чтобы получить следующее решение *)
    if neighbor <> nil then
      if not neighbor.advance then
        advance := false
      else begin
        (* начать снова с горизонтали═1 *)
        row :=═1;
        advance := self.findSolution;
      end;
  end;
end;

procedure Queen.print;
begin
  if neighbor <> nil then neighbor.print;
  writeln('row ', row, ' column ', column);
end;

begin
  neighbor := nil;

  for i :=═1 to═8 do begin
    (* создать и инициализировать нового ферзя *)
    new (lastqueen);
    lastQueen.initialize (i, neighbor);
    if not lastQueen.findSolution then
      writeln(▒no solution▓);

    (* самый новый ферзь является следующим соседом *)
    neighbor := lastQueen;
  end;

  lastQueen.print;

  for i :=═1 to═8 do begin
    neighbor := lastQueen.neighbor;
    dispose (lastQueen);
    lastQueen := neighbor;
  end;
end.

A.2. "Задача о восьми ферзях" на языке С++

Разделы 

//  Задача "Восемь ферзей", язык С++
//  Автор: Тимоти Бадд, университет штата Орегон,═1996
//

#include <iostream.h>
#define bool int
#define true═1
#define false═0

class queen
{
public:
    // конструктор
    queen (int, queen *);

    // найти и напечатать решения
    bool findSolution();
    bool advance();
    void print();

private:
    // поля данных
    int row;
    const int column;
    queen * neighbor;

    // внутренний метод
    bool canAttack (int, int);
};

queen::queen(int col, queen * ngh) :
             column(col), neighbor(ngh)
{
  row =═1;
}

bool queen::canAttack (int testRow, int testColumn)
{
    // проверка горизонталей
    if (row == testRow) return true;

    // проверка диагоналей
    int columnDifference = testColumn═≈ column;
    if (
          (row + columnDifference == testRow) 
        ||(row═≈ columnDifference == testRow)
       )
      return true;

    // попробовать соседа
    return neighbor && neighbor->canAttack(testRow, testColumn);
}

bool queen::findSolution()
{
    // проверить позицию, не атакуют ли соседи
    while (neighbor && neighbor->canAttack (row, column))
     if (! advance ()) return false;

    // решение найдено!
    return true;
}

bool queen::advance()
{
  if (row <═8)
   {
    row++;
    return findSolution();
   }

  if(neighbor && ! neighbor->advance())
    return false;

  row =═1;
  return findSolution ();
}

void queen::print()
{
  if(neighbor) neighbor->print();
  cout << " column " << column << " row " 
       << row << '\n';
}

void main()
{
  queen * lastQueen =═0;
  for (int i =═1; i <=═8; i++)
   {
    lastQueen = new queen(i, lastQueen);
    if (! lastQueen->findSolution())
      cout << "no solution\n";
   }
  lastQueen->print();
}

A.3. "Задача о восьми ферзях" на языке Java

Разделы 

/*
 	Задача "Восемь ферзей", язык Java
  	Автор: Тимоти Бадд, университет штата Орегон, январь═1996
*/

import java.awt.*;
import java.applet.*;

class Queen
{
    // поля данных
    private int row;
    private int column;
    private Queen neighbor;

    // конструктор
    Queen (int c, Queen n)
     {
      // инициализировать поля данных
      row =═1;
      column = c;
      neighbor = n;
     }

    public boolean findSolution ()
     {
      while ( 
               (neighbor != null) 
             && neighbor.canAttack(row, column)
            )
       if (! advance()) return false;

      return true;
     }

    public boolean advance()
     {
      if (row <═8)
       {
        row++;
        return findSolution();
       }

      if (neighbor != null)
       {
        if (! neighbor.advance ()) return false;
       }
      else return false;

      row =═1;
      return findSolution();
     }

    private boolean canAttack(int testRow, int testColumn)
     {
      int columnDifference = testColumn═≈ column;

      if(
           (row == testRow)
         ||(row + columnDifference == testRow) 
         ||(row═≈ columnDifference == testRow)
        )
        return true;

      if(neighbor != null)
        return neighbor.canAttack(testRow, testColumn);

      return false;
     }

    public void paint (Graphics g)
     {
      // сперва нарисуем соседа
      if (neighbor != null) neighbor.paint(g);

      // затем нарисуем себя
      // x, y═≈ это верхний левый угол
      int x = (row═≈═1) *═50;
      int y = (column═≈═1) *═50;

      g.drawLine(x+5,  y+45, x+45, y+45);
      g.drawLine(x+5,  y+45, x+5,  y+5);
      g.drawLine(x+45, y+45, x+45, y+5);
      g.drawLine(x+5, y+35, x+45, y+35);
      g.drawLine(x+5, y+5, x+15, y+20);
      g.drawLine(x+15, y+20, x+25, y+5);
      g.drawLine(x+25, y+5, x+35, y+20);
      g.drawLine(x+35, y+20, x+45, y+5);
      g.drawOval(x+20, y+20,═10,═10);
     }
}

public class QueenSolver extends Applet
{
  private Queen lastQueen;

  public void init()
   {
    int i;
    lastQueen = null;
    for (i =═1; i <=═8; i++)
     {
      lastQueen = new Queen(i, lastQueen);
      lastQueen.findSolution();
     }
   }

  public void paint(Graphics g)
   {
    // нарисовать доску
    for (int i =═0; i <=═8; i++)
     {
      g.drawLine(50 * i,═0,═50*i,═400);
      g.drawLine(0,═50 * i,═400,═50*i);
     }

    // нарисовать ферзей
    lastQueen.paint(g);
   }

  public boolean mouseDown(java.awt.Event evt, int x, int y)
   {
    lastQueen.advance();
    repaint();
    return true;
   }
}

A.3.1. HTML-файл для апплета Java

"Задача о восьми ферзях" на языке Java 

<html>
<title>Eight-Queen Puzzle</title>
<body>
<h1> Головоломка "8 Ферзей" на языке Java</h1>
<h2>Из главы═5 книги</h2>
<h2>"Объектно-ориентированное программирование в действии"</h2>
<h2>Автор: Тимоти Бадд<</h2>
<hr>
<applet code="QueenSolver.class" width=500 height=500>

Если Вы увидите этот текст, ваш броузер не обеспечивает 
выполнение апплетов Java.

</applet>
<hr>
<p>

Броузер первоначально изображает только одно решение.
После каждого щелчка мышью будет появляться новое решение.

<p>
<a href="QueenSolver.java">Исходный текст программы.</a>
</body>
</html>

A.4. "Задача о восьми ферзях" на языке Objective-C

Разделы

В данном примере классы Queen и SentinelQueen начинают прямо с раздела implementation без предшествующей части interface. Это вызовет предупреждающее сообщение со стороны компилятора, но не сообщение об ошибке. 

/*
 	Задача "Восемь ферзей", язык Objective-C
  	Автор: Тимоти Бадд, университет штата Орегон,═1996
*/

# include <stdio.h>
# include <objc/Object.h>

/*
  'Сторожевой' ферзь находится левее самого левого ферзя
*/

@implementation SentinelQueen : Object
- (int) advance
{
  /* ничего не делать */
  return═1;
}

- (int) findSolution
{
  /* ничего не делать */
  return═1;
}

- (void) print
{
  /* ничего не делать */
}

- (int) canAttack: (int) testRow column: (int) testColumn;
{
  /* нельзя атаковать */
  return═0;
}

@end

@interface Queen : Object

{  /* поля данных */
  int row;
  int column;
  id neighbor;
}

   /* методы */
- (void) initialize: (int) c neighbor: ngh;
- (int) advance;
- (void) print;
- (int) canAttack: (int) testRow column: (int) testColumn;
- (int) findSolution;
@end

@implementation Queen : Object
- (void) initialize: (int) c neighbor: ngh;
{
   /* задать постоянные значения */
   column = c;
   neighbor = ngh;
   row =═1;
}

- (int) advance
{
   /* сначала попробовать следующую горизонталь */
   if (row <═8)
    {
     row = row +═1;
     return [ self findSolution ];
    }

   /* дальше двигаться нельзя, подвинем соседа */
   if ( ! [ neighbor advance ] ) return═0;

   /* начать снова с первой горизонтали */
   row =═1;
   return [ self findSolution ];
}

- (void) print
{
  if (neighbor)
    [ neighbor print ];

  print("column %d row %d\n", column, row);
}

- (int) canAttack: (int) testRow column: (int) testColumn
{
  int columnDifference;

  /* если та же горизонталь, то можно аттаковать */
  if (row == testRow) return═1;
  columnDifference = testColumn═≈ column;
  if(
       (row + columnDifference == testRow) 
     ||(row═≈ columnDifference == testRow)
    )
    return═1;
  return [ neighbor canAttack:testRow column: testColumn ];
}

- (int) findSolution
{
  /* если сосед может атаковать, то продвинуться */
  while ( [ neighbor canAttack:row column: column ] )
    if ( ! [ self advance ] ) return═0;

   /* в противном случае мы в безопасности */
   return═1;
}
@end

main()
{
  id lastQueen, neighbor;
  int i;

  // создать и инициализировать ферзей
  neighbor = [ SentinelQueen new ];
  for (i =═1; i <=═8; i++)
   {
    lastQueen = [ Queen new ];
    [ lastQueen initialize: i neighbor: neighbor ];
    [ lastQueen findSolution ];
    neighbor = lastQueen;
   }

  // теперь напечатать решение
  [ lastQueen print ];
}

A.5. "Задача о восьми ферзях" на языке Smalltalk

Разделы

Класс SentinelQueen не имеет переменных экземпляра. Класс использует следующие методы: 

advance
    ^ false

canAttack: row column: column
    ^ false

result
    ^ List new

Класс Queen имеет три переменные экземпляра: row, column, neighbor. Определены следующие методы класса: 

setColumn: aNumber neighbor: aQueen
    " инициализировать поля данных "
    column := aNumber.
    neighbor := aQueen.

    " найти первое решение "
    row :=═1.

canAttack: testRow column: testColumn ╫ columnDifference ╫
     columnDifference := testColumn═≈ column.
     (((row = testRow) or:
      [ row + columnDifference = testRow]) or:
      [ row═≈ columnDifference = testRow])
     ifTrue: [ ^ true ].

     ^ neighbor canAttack: testRow column: testColumn

advance
    " сначала испытать следующую строку "
    (row <═8)
     ifTrue: [ row := row +═1. ╜ self findSolution ].

    " нельзя двигаться дальше, подвинем соседа "
    (neighbor advance )
     ifFalse: [ ╜ false ].

    row :=═1.
    ^ self findSolution

findSolution
   [ neighbor canAttack: row column: column ]
    whileTrue: [ self advance
       ifFalse: [ ^ false ] ].
   ^ true

result
   ^ neighbor result; addLast: row

Чтобы найти решение, выполняется следующий метод:
run  | lastQueen |
   lastQueen <- SentinelQueen new.
  ═1 to:═8 do: [:i ╫ lastQueen <- (Queen new)
     setColumn: i neighbor: lastQueen.
     lastQueen findSolution ].
   'результат получен' print.
   lastQueen result do: [:x | x print. ' ' print ].
   Char newline print.

Исходный код программ для задачи "Восемь ферзей"