What is the applicability of the 8 queens problem?

6

In college the linear programming teacher introduced the Problem of the 8 Queens.

Basically, as I understand it, this problem consists of filling the board (could be simulated with an array) with the 8 queens in a way that the number of attacks of each queen is equal 0 zero. The queens can attack horizontally, vertically and diagonally, otherwise I am wrong.

So, I even understood the problem of the 8 queens a bit, however, this problem gave me more doubts about himself and the computer.

Questions

  • What kind of situation is the Problem of the 8 Queens trying to address in the world real? Or what would be its applicability?
  • What is the relationship of the 8 Queens Problem with linear programming?
  • Is there any computational limitations in solving this problem? If so, which ones?
  • asked by anonymous 22.03.2018 / 18:26

    1 answer

    4

    The problem of n-queens can be reduced to the problem of SAT (satisfaction), which is an NP-Complete problem. And the most famous SAT problem is to find a configuration of the variables to satisfy a Boolean expression.

    For example, find values of A, B, C, D, and E so that the following expression is satisfied: A and B and C or D and E .

    The applications of this problem are several in real life. One is to make an application that allocates classes so that no class has a class in the same room at the same time. Or a travel plan, in which%% of airplanes can not be flying over the same area at the same time.

    Usually to solve this type of problem are used local search algorithms, in which the path to the solution does not matter, what matters simply is the final state in which it represents a solution. For example, if I'm doing a class allocation application, I do not want to know what the intermediate states were during computing the solution, I just want to know the last state, which represents the solution. The same thing applies to the n-queens problem, I do not want to know the intermediate states, I just want to know a state in which no one attacks.

    Linear programming can be briefly summarized in: Given a set of constraints, find the best possible solution within that context. That's just what we're trying to do in the n-queens problem.

    This link here has a nice explanation and implementation: link

        
    22.03.2018 / 20:46