What is the applicability of the eight queens problem?

Asked

Viewed 250 times

7

In college the professor of linear programming presented the Problem of the 8 Queens.

Basically, from what I understand, this problem consists of filling the board (could be simulated with a matrix) with the 8 queens in a way that the number of attacks of each queen is equal 0 zero. Queens can attack horizontally, vertically and diagonally, otherwise I’m wrong.

Being so, I even understood a little the problem of the 8 queens, however, this problem generated me more doubts about itself and computing.

Doubts

  1. What kind of situation the Problem of the Eight Queens tries to address in the world real? Or what would be the applicability of it?
  2. What is the relationship of the 8 Queens problem with linear programming?
  3. Are there computational limitations in solving this problem? If so, which?
computer-science
  • 1

    Read on there http://conteudo.icmc.usp.br/persons/sandra/G6_t2/rainha.htm

  • Possibly an adaptation of the graph coloring problem.

  • related https://answall.com/questions/285412/70

  • 2

    This reminds me that I can get rich: https://olhadigital.com.br/fique_seguro/noticia/desafio-paga-us-1-milhao-criador-software-que-resolve-problema-xadrez/70798

  • @Everson goes deep! Get rich and spend all your time posting content on Sopt xD

1 answer

6

The n-queen problem can be reduced to the SAT(satisfiability) problem, which is an NP-complete problem. And the most famous problem of SAT is to find a configuration of 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 of them is to make an application that allocates classes so that no class has classes in the same classroom at the same time. Or a travel plan, in which n aeroplanes cannot be flying over the same area at the same time.

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

Linear programming can be briefly summarized in: Given a set of constraints, find the best possible solution within this context. Which is exactly what we’re trying to do in the n-queen problem.

This link here has a nice explanation and implementation: https://sites.google.com/site/haioushen/search-algorithm/solvean-queensproblemusingsatsolver

Browser other questions tagged computer-science

You are not signed in. Login or sign up in order to post.