Задача о 8 ферзях

Размещено на http://www.allbest.ru/

УРАЛЬСКИЙ ГОСУДАРСТВЕННЫЙ ГОРНЫЙ УНИВЕРСИТЕТ

КАФЕДРА ИНФОРМАТИКИ

КУРСОВАЯ РАБОТА

по программированию

Задача о 8 ферзях

Студент: Сорокин С

гр. АСУ-09-1

Преподаватель: доц. Дружинин А.В.

алгоритмический язык: С#

среда разработки: Microsoft Visual Studio 2010

Екатеринбург 2011

Оглавление

1. Постановка задачи

2. Описание базового класса

3. Визуализация

Литература

1. Постановка задачи

комбинация ферзь шахматный пользователь

Нужно расставить восемь ферзей на пустой шахматной доске, в которой ни один из ферзей не находится под боем другого.

2. Описание базового класса

Базовым классом является класс Queens.

class Queens

{

/// <summary>

/// Размер доски.

/// </summary>

public const int BoardSize = 8;

/// <summary>

/// Позиция ферзя на доске.

/// </summary>

private class Pos {

public int row, col;

public bool placed;

public Pos(int r, int c, bool pl)

{

row = r; col = c; placed = pl;

}

};

/// <summary>

/// Состояние клетки доски (Queen - клетка занята ферзём, Empty - пустая клетка).

/// </summary>

private enum PosState { Queen, Empty };

private PosState[,] board = new PosState[BoardSize, BoardSize];

private Stack<Pos> qStack = new Stack<Pos>();

/// <summary>

/// Проверить: находится ли позиция под боем?

/// </summary>

private bool IsPosUnderAttack(Pos p)

{

int i;

for (i = 0; i < p.col; i++)

{

if (board[p.row, i] == PosState.Queen) return true;

if (p.row-i-1 >= 0)

if (board[p.row-i-1, p.col-i-1] == PosState.Queen)

return true;

if (p.row+i+1 < BoardSize)

if (board[p.row+i+1, p.col-i-1] == PosState.Queen)

return true;

//Console.WriteLine("{0}:{1} {2}", p.col-i-1, p.row-i-1, p.row+i+1);

}

return false;

}

/// <summary>

/// Получить свободную (не под боем) позицию в столбце col

/// Возвращается номер строки или -1 - при неудаче

/// Просмотр строк начинаем со строки startRow + 1

/// </summary>

private int GetFreePos(int col, int startRow)

{

for (int r = startRow + 1; r < BoardSize; r++)

if (!IsPosUnderAttack(new Pos(r, col, false)))

return r;

return -1;

}

/// <summary>

/// Получить свободную (не под боем) позицию в столбце col

/// Возвращается номер строки или -1 - при неудаче

/// Просмотр строк начинаем со строки 0.

/// </summary>

int GetFreePos(int col)

{

return GetFreePos(col, -1);

}

/// <summary>

/// Инициализация объекта перед решением задачи.

/// </summary>

public Queens()

{

for(int i=0; i<BoardSize; i++)

for(int j=0; j<BoardSize; j++)

board[i,j] = PosState.Empty;

}

/// <summary>

/// Решить задачу.

/// </summary>

public bool SolveTask()

{

Pos p = new Pos(0, 0, true);

qStack.Push(p);

board[0, 0] = PosState.Queen;

while(qStack.Count > 0) {

p = qStack.Peek();

if (p.placed) { // Предыдущий ферзь установлен - ставим следующий

if (p.col < BoardSize-1) { // Справа от этого ферзя можно попытаться поставить ещё.

int r = GetFreePos(p.col+1);

if (r > -1) { // Ставим нового ферзя справа от старого (есть позиция, которая не под боем).

qStack.Push(new Pos(r, p.col+1, true));

board[r, p.col+1] = PosState.Queen;

}

else { // Нового ферзя поставить нельзя - производим откат назад

qStack.Peek().placed = false; // Из-за этого Pos не может быть структурой

}

}

else { // В последний столбец был поставлен ферзь - задача решена.

return true;

}

}

else { // Корректируем позицию ферзя на котором произошел возврат (если возможно)

while(true) {

if (qStack.Count == 0) return false;

board[qStack.Peek().row, qStack.Peek().col] = PosState.Empty;

int r = GetFreePos(qStack.Peek().col, qStack.Peek().row);

if (r > -1) { // Корректируем позицию ферзя на котором произошел возврат

qStack.Peek().row = r;

qStack.Peek().placed = true;

board[qStack.Peek().row, qStack.Peek().col] = PosState.Queen;

break;

}

else { // Удаляем последнего ферзя (откорректировать позицию не удалось)

qStack.Pop();

}

}

}

}

return false;

}

/// <summary>

///.

/// </summary>

}

}

3.Визуализация

При запуске программы пользователь видит шахматную доску, на которую при нажатии кнопки «расставить» происходит расстановка ферзей (одна из 92 возможных комбинаций)

Выход - кнопка “Выход”

Литература

1. Рекурсия, вероятностные алгоритмы. Макконелл Дж.

2. Основы современных алгоритмов. М., Техносфера, 2004 , Корнилов Е.

3. Программирование шахмат и других логических игр. СПб., БХВ-Петербург, 2005

4. http://msdn.microsoft.com/ru-ru/vcsharp/

Размещено на Allbest.ru