рефераты конспекты курсовые дипломные лекции шпоры

Реферат Курсовая Конспект

The Problem

The Problem - раздел Философия, Recursive factorials A Classic Problem That We Can Solve Using Backtracking Is The Eight Queens Pr...

A classic problem that we can solve using backtracking is the Eight Queens problem. This difficult problem deals with placing eight queens on a chessboard such that no two queens are attacking each other.

The game of chess is played on a board containing 64 squares of alternating color. Two players take turns moving a set of pieces on these squares. The object of the game is to capture the opponent's most important piece, the "king." While the king is the most important piece, the "queen" is the most powerful piece. In the game of chess, queens can "attack" or "capture" other pieces in two different ways. First, a queen can attack pieces on those squares that are in the same row or the same column as the queen. Second, a queen can attack pieces occupying the squares that run diagonally through the square that the queen occupies. Figure 2 shows the two different ways that queens attack. Note that the squares highlighted in red indicate the squares that the queen in the figure can attack.


Figure 2 Queens attack in two different ways

Combining these two methods together, we see (again in red) all the squares on a chessboard that a queen can attack in Figure 3. We consider the queen in Figure 3 to be "attacking" any piece that occupies a red square.


Figure 3 All the squares a queen can attack

A queen is considered the most powerful chess piece since it attacks the largest number of squares out of any other piece. Are queens so powerful that eight of them cannot be placed on a board without any two of them attacking each other? Spend some time and see if you can create a solution. If you do not have access to a chessboard, printing a copy of this page will give you, from the following figure, an empty board and eight queens.


Figure 4 An empty board and eight queens

Remember, when considering a solution to this problem you must make sure not to place two queens in the same row or in the same column. To complicate matters, you also cannot place two queens on the same diagonal. An example of a non-solution appears in Figure 5. This is a non-solution since the queen in the upper left corner attacks the queen in the lower right corner, and vice-versa.


Figure 5 A non-solution

– Конец работы –

Эта тема принадлежит разделу:

Recursive factorials

Example contains the output of the factorial program after the addition of the output statements to function factorial factorial begin... The output in Example shows that the program first calls function factorial... Problem Solving with Recursion Divide and...

Если Вам нужно дополнительный материал на эту тему, или Вы не нашли то, что искали, рекомендуем воспользоваться поиском по нашей базе работ: The Problem

Что будем делать с полученным материалом:

Если этот материал оказался полезным ля Вас, Вы можете сохранить его на свою страничку в социальных сетях:

Все темы данного раздела:

The Call Stack
The call stack is an area of a program's memory used to manage the currently executing function and all pending function calls. Figure 3 lends some insight into what is meant by a "pend

Removing Recursion
Recursion comes with a price: the run time system has to maintain a complicated call stack, on top of having to perform the usual evaluations contained in the function. Often, we can eliminate recu

Divide and Conquer
Divide and conquer is a problem solving technique that utilizes recursion to solve a problem by "dividing" the problem into smaller and smaller sub-problems. The base case of the r

Backtracking. The Concept
Backtracking is a problem solving technique that involves examining all possibilities in the search for a solution. An example of backtracking can be seen in the process of finding the solution to

The Solution
To solve the Eight Queens problem, we use a backtracking algorithm. The algorithm involves placing queens, column by column, onto the chessboard. The algorithm terminates when it places all eight q

The Call Stack
Call Stack это область памяти программы, используемая, чтобы управлять выполняющейся функцией и всеми последующими вызовами находящиеся в ожидании. Рисунок 3 отражает то понимание, которое принято

Замена рекурсии
Рекурсия имеет собственное решение: т.е. система времени выполнения должна поддержать сложный стек вызовов, сверх необходимости выполнять обычные оценки в функции. Часто бывает выгодно заменить рек

Отслеживание в обратном порядке. Понятие
Отслеживание в обратном порядке является проблемой, решая метод, который включает исследование всех возможностей в поиске решения. Пример отслеживания в обратном порядке может быть замечен в процес

Проблема
Классической проблемой, решения задачи методом «отслеживание в обратном порядке», является проблема Восьми Королев. Эта трудная проблема соглашения с размещением восьми королев на шахматной доске т

Решение
Чтобы решить проблему Восьми Королев, мы используем алгоритм отслеживания в обратном порядке. Алгоритм включает размещения королев, столбец за столбцом, на шахматную доску. Алгоритм завершается, ко

Хотите получать на электронную почту самые свежие новости?
Education Insider Sample
Подпишитесь на Нашу рассылку
Наша политика приватности обеспечивает 100% безопасность и анонимность Ваших E-Mail
Реклама
Соответствующий теме материал
  • Похожее
  • Популярное
  • Облако тегов
  • Здесь
  • Временно
  • Пусто
Теги