converted to PDF by BoJIoc
{
//проверка горизонталей 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
*/
converted to PDF by BoJIoc
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);
converted to PDF by BoJIoc
//затем нарисуем себя
//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
<html>
<title>Eight-Queen Puzzle</title> <body>
<h1> Головоломка «8 Ферзей» на языке Java</h1> <h2>Из главы 5 книги</h2>
<h2>«Объектно-ориентированное программирование в действии»</h2> <h2>Автор: Тимоти Бадд<</h2>
<hr>