Ladies problem

from Wikipedia, the free encyclopedia
Eight queens problem
  a b c d e f G H  
8th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg 8th
7th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 7th
6th Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 6th
5 Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 5
4th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg 4th
3 Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 3
2 Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg 2
1 Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 1
  a b c d e f G H  
one of the solutions

Template: checkerboard / maintenance / new

The queens problem is a chess math problem. There are eight each  ladies on a chess board be set up so that no two women can beat each other in accordance with their defined in the rules of chess possible moves. The figure color is ignored and it is assumed that any figure could attack any other. Pieces arranged in this way on the chessboard are also referred to as "independent". For women this means specifically and in other words: No two women are allowed to stand on the same row, line or diagonal.

The focus of the women's problem is on the number of possible solutions. In the case of the classic chessboard, there are various options for positioning the queens accordingly. If one regards solutions as the same, which result from mirroring or rotating the board apart,  basic solutions still remain .

The problem can be generalized to square chessboards of any size: Then it is necessary to position independent queens on a board of squares (with as a parameter from the natural numbers ).

history

The women's problem was first formulated by the Bavarian chess master Max Bezzel . In 1848 in the Berliner Schachzeitung he asked about the number of possible solutions. In 1850, the dentist Franz Nauck was the first to give the correct number in the Leipziger Illustrirten Zeitung . In 1874, the English mathematician James Whitbread Lee Glaisher proved that there can be no more solutions. This completely solved the original problem. Even Carl Friedrich Gauss showed interest in the problem, so it is erroneously often attributed to him; however, he had only found the solutions.

Nauck generalized the problem and asked how many different ways queens can be placed on a chessboard.

Eight queens problem
Symmetrical, unambiguous solution
  a b c d e f G H  
8th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 8th
7th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg 7th
6th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg 6th
5 Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 5
4th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg 4th
3 Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 3
2 Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 2
1 Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qlt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 1
  a b c d e f G H  

This type provides instead of different solutions (based on unique solutions)

Template: checkerboard / maintenance / new

In 1992 Demirörs, Rafraf and Tanik found an equivalence between magic squares and ladies problems .

The ladies problem also appeared in the computer games The 7th Guest and The Whispered World . In the Nintendo DS title Professor Layton and the Mysterious Village , the player even has to solve it several times in different ways.

Number of solutions in the classic women's problem

The classic problem with eight women on one board has different solutions. If you just simply count those that are mapped onto each other by rotating or mirroring the board, unambiguous solutions are left (the different colors of the fields are ignored). Since there are four reflections (on the diagonals, horizontal and vertical through the middle of the board) and four rotations for each of these reduced solutions, one could assume a total number of solutions. However, since one of the solutions (see diagram) turns into itself when it is turned around , only four different solutions can be constructed from this and solutions result overall .

Number of solutions in the generalized ladies problem

The generalized queens problem requires the queens to be positioned on a board of squares so that they are not diagonally, vertically, and horizontally across from each other.

Number of solutions up to board size

The following table lists the number of unique solutions and the total solutions up to board size :

The previously known but not verified solution number for was independently confirmed in 1969 by Torbjörn Lindelöf and Bernd Schwarzkopf using computer analyzes. Lindelöf also calculated the sizes of and . In 1970 Lindelöf calculated the number for with the remark that computers needed 50 to 100 times the computing capacity for larger chessboards that was common at the time.

The solution number for was determined on July 11, 2009 by the Queens @ TUD project with FPGA solvers and confirmed on August 30, 2009 by the MC # project on two Russian supercomputers from the then current TOP500 list. After more than 7 years, the solution number for . This could be calculated in a follow-up project using further problem symmetries and the increased technical performance with the help of FPGA solvers. Confirmation of this number by a second independent project is still pending.

In general, it can be stated that the number of solutions increases somewhat faster than exponentially with the size of the board. Interestingly, there are fewer solutions on the board and on the board than on the smaller board.

Number of solutions for large

There is an upper bound on the number of solutions to the queens problem on a board  . This is the number of solutions for non-threatening towers. The lists of women (for ) who are not threatening each other are a real subset of this.

The asymptotic form of is unknown. Rivin et al. a. suggest that

is.

From the known terms of the sequence, the following approximation formula can be estimated for large :

 with  .

Algorithms for finding solutions

The ladies problem is a good example of an easy-to-formulate problem with non-trivial solutions. A number of programming techniques are suitable for generating all of the solutions. Recursive backtracking is classic ; this is particularly easy to implement with logical programming . Genetic algorithms are another possibility .

Such approaches are much more efficient than a naive brute force algorithm, which (in the case) tries out all ( ) possible positions of the eight women and thereby filters out all positions in which two women could hit each other. This algorithm generates the same solutions several times if permutations of the queens occupy the same fields.

A more efficient brute force algorithm places only one queen in each row, reducing the complexity to possible positions.

Recursive backtracking

Animation of the recursive backtracking algorithm

The queens problem can be efficiently solved by a recursive algorithm in that the problem with queens is interpreted in such a way that it is necessary to add another queen to each solution with queens. Ultimately, every queens problem can be traced back to a problem with queens, which is nothing more than an empty chessboard.

The following Python program finds all solutions to the ladies problem using a recursive algorithm. A board is recursively reduced to smaller boards with a smaller number of rows . The program directly takes advantage of the fact that no two women are in the same row. It also used a solution with queens on a ironing board definitely a solution with queens on a must include ironing board. In other words, if you remove the bottom (or top) row of the partial solution on a board, queens are left on a board, who in turn represent a partial solution on the board.

The algorithm thus constructs all solutions from the solutions on a smaller board. Since it is ensured that the partial solutions are conflict-free on the small boards, this algorithm saves the checking of many positions. Overall, only positions are checked for the board .

# Erzeuge eine Liste von Lösungen auf einem Brett mit Reihen und Spalten.
# Eine Lösung wird durch eine Liste der Spaltenpositionen,
# indiziert durch die Reihennummer, angegeben.
# Die Indizes beginnen mit Null.
def damenproblem(reihen, spalten):
    if reihen <= 0:
        return [[]] # keine Dame zu setzen; leeres Brett ist Lösung
    else:
        return eine_dame_dazu(reihen - 1, spalten, damenproblem(reihen - 1, spalten))

# Probiere alle Spalten, in denen für eine gegebene Teillösung
# eine Dame in "neue_reihe" gestellt werden kann.
# Wenn kein Konflikt mit der Teillösung auftritt,
# ist eine neue Lösung des um eine Reihe erweiterten
# Bretts gefunden.
def eine_dame_dazu(neue_reihe, spalten, vorherige_loesungen):
    neue_loesungen = []
    for loesung in vorherige_loesungen:
        # Versuche, eine Dame in jeder Spalte von neue_reihe einzufügen.
        for neue_spalte in range(spalten):
            # print('Versuch: %s in Reihe %s' % (neue_spalte, neue_reihe))
            if kein_konflikt(neue_reihe, neue_spalte, loesung):
                # Kein Konflikte, also ist dieser Versuch eine Lösung.
                neue_loesungen.append(loesung + [neue_spalte])
    return neue_loesungen

# Kann eine Dame an die Position "neue_spalte"/"neue_reihe" gestellt werden,
# ohne dass sie eine der schon stehenden Damen schlagen kann?
def kein_konflikt(neue_reihe, neue_spalte, loesung):
    # Stelle sicher, dass die neue Dame mit keiner der existierenden
    # Damen auf einer Spalte oder Diagonalen steht.
    for reihe in range(neue_reihe):
        if (loesung[reihe]         == neue_spalte              or  # gleiche Spalte
            loesung[reihe] + reihe == neue_spalte + neue_reihe or  # gleiche Diagonale
            loesung[reihe] - reihe == neue_spalte - neue_reihe):   # gleiche Diagonale
                return False
    return True

for loesung in damenproblem(8, 8):
    print(loesung)

Using a coroutine can simplify the algorithm somewhat. The following program is a translation of Niklaus Wirth's solution into the Python programming language, but dispenses with the index arithmetic used in the original and uses simple lists instead. The procedure is replaced by a generator: a restricted form of a coroutine that generates an iterator .

def tryout(n, i, a, b, c):
    if i < n:
        for j in range(n):
            if j not in a and i+j not in b and i-j not in c:
                for solution in tryout(n, i+1, a+[j], b+[i+j], c+[i-j]):
                    yield solution
    else:
        yield a

for solution in tryout(8, 0, [], [], []):
    print(solution)

Constraint programming

The constraint programming over finite fields can formulate a task like queens problem very compact. The following Prolog program (in GNU Prolog ) quickly finds a solution even for large chessboards.

 /* Dieses Prädikat erzeugt eine Liste, die eine einzige Lösung darstellt.
    Es ist sichergestellt, dass jeder Wert zwischen 1 und N genau einmal auftritt. */

 n_damen(N,Ls) :- length(Ls,N),
                fd_domain(Ls,1,N),
                fd_all_different(Ls),
                constraint_damen(Ls),
                fd_labeling(Ls,[variable_method(random)]).

 /* Dieses Prädikat stellt sicher,
    dass alle Stellungen die Lösungsbedingungen erfuellen */

 constraint_damen([]).
 constraint_damen([X|Xs]) :- nicht_schlagen(X,Xs,1), constraint_damen(Xs).

 /* Mit diesem Prädikat wird sichergestellt,
    dass zwei Damen nicht auf einer Diagonalen stehen */

 nicht_schlagen(_,[],_).
 nicht_schlagen(X,[Y|Xs],N) :- X#\=Y+N, X#\=Y-N, T#=N+1, nicht_schlagen(X,Xs,T).

Explicit solution

Solid white.svg a b c d e f Solid white.svg
6th a6 b6 c6 d6 e6 f6 6th
5 a5 b5 c5 d5 e5 f5 5
4th a4 b4 c4 d4 e4 f4 4th
3 a3 b3 c3 d3 e3 f3 3
2 a2 b2 c2 d2 e2 f2 2
1 a1 b1 c1 d1 e1 f1 1
a b c d e f
Design specification for straight , which when divided by not the rest results

A construction specification for a special solution with arbitrarily large n was first given by Emil Pauls in 1874 . In this way it was proven in particular that the ladies' problem has at least one solution for anything.

For even numbers that result in division with the remainder or , you start in the second column of the top row and place a queen. Place the following ladies two columns to the right and one row below the previous one until rows are filled. The rows of the lower half of the board are obtained from the reflection of the upper queens at the center of the board.

For even numbers that result when dividing with the remainder (including the normal chessboard ) this rule does not lead to a valid solution. In this case, an alternative, somewhat complicated design specification can be specified.

With both construction rules, all fields of the long diagonal (top left to bottom right) remain unoccupied. For odd , form a valid solution for according to the above rules and place the last queen in the last column of the last row.

Other methods

An iterative repair algorithm begins with any queue position on the board. It then counts the number of conflicts and tries to reduce the number of conflicts by repositioning the ladies. It is efficient, for example, to move the queen with the most conflicts vertically to the position where the fewest conflicts occur. With this method, the lady problem can be solved starting from a “reasonable” trial position. Such large boards cannot be solved with explicit construction algorithms (except for trivial solutions); however, such an iteration algorithm cannot find a solution with certainty.

Related problems

Other figures

The problem can also be formulated for other chess pieces (king, bishop, knight, rook).

Another generalization of the problem is the super ladies problem. Super ladies are allowed to move like ladies and jumpers. It's not clear who invented super ladies or the super ladies problem. In Mathematische Knobeleien (Vieweg-Verlag, 1973) Martin Gardner mentions a chess variation in which a super queen is played. Gardner calls this figure Maharajah there . Others know her as an Amazon .

The question of how many ways super queens can be placed on a chessboard without threat was also examined:

Frank Schwellinger has also had an explicit solution to the problem of super ladies since 2001 .

It should be noted that the knight problem is not the analogous task for knights , but a knight wandering across the entire chessboard.

Different board geometry

George Pólya looked at the queens problem on a toroidal board . He proved that at least one solution exists if and only if is too coprime, i.e. is neither divisible by nor by . Three-dimensional generalizations were also examined.

Other tasks

Ladies and farmer (n)
  a b c d e f G H  
8th Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 8th
7th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 7th
6th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg 6th
5 Chess qdt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 5
4th Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 4th
3 Chess --t45.svg Chess qdt45.svg Chess plt45.svg Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg Chess --t45.svg 3
2 Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess qdt45.svg 2
1 Chess --t45.svg Chess --t45.svg Chess qdt45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg Chess --t45.svg 1
  a b c d e f G H  
Nine ladies and a farmer

Template: checkerboard / maintenance / new

For a chessboard you determine the dominance number, that is the minimum number of queens that is sufficient to dominate every square on the board. Five ladies are enough on the board. There are solutions (such as , , , , ). b7d5e4f3h1

The nine queens problem requires nine queens and a pawn to be accommodated on a board in such a way that the queens cannot observe each other, i.e. have no direct horizontal, vertical or diagonal line of sight to one another. Again, this problem can be generalized to any board size and a higher number of pawns.

See also

literature

  • John J. Watkins: Across the Board: The Mathematics of Chess Problems. Princeton University Press, Princeton 2004, ISBN 0-691-11503-6 .

Web links

Wiktionary: lady problem  - explanations of meanings, word origins, synonyms, translations

Individual evidence

  1. Yevgeny Gik: Chess and Mathematics . Reinhard Becker Verlag, 1986, ISBN 3-930640-37-6 .
  2. Evgeni J. Gik: Chess and Mathematics . Verlag Deutsch Harri GmbH, ISBN 3-87144-987-3 .
  3. Klaus Menzel (Ed.): Algorithmen: From Problem to Program . Springer-Verlag, 2013, ISBN 978-3-322-91373-9 , pp. 106 (128 p., Limited preview in Google Book search).
  4. Onur Demirörs, Nader Rafraf, Murat Tanik: Obtaining- queens solutions from magic squares and constructing magic squares from -queens solutions . In: Journal of Recreational Mathematics . No. 24 , 1992, ISSN  0022-412X , pp. 272-280 .
  5. Karl Fable : The ladies' problem. In: The swallow . Issue 1, October 1969, p. 20.
  6. Karl Fable: The ladies' problem. In: The swallow. Issue 5, September 1970, p. 146.
  7. 26 women problem solved on heise.de, July 19, 2009
  8. MC # project ( Memento from March 1, 2012 in the Internet Archive )
  9. heise online: Pay, please! The 27 women problem is solved. In: heise online. Retrieved September 27, 2016 .
  10. preusser / q27. In: GitHub. Retrieved September 20, 2016 .
  11. ^ I. Rivin, I. Vardi, P. Zimmermann: The -Queens Problem. In: The American Mathematical Monthly. Volume 101, 1994, pp. 629-639.
  12. Follow A000170 in OEIS
  13. Niklaus Wirth : Algorithmen und Datenstruktur, Oberon version 2004, correction 2012, pp. 114–118. ( online ; PDF)
  14. ^ Emil Pauls : The maximum problem of the queens on the chess board I. Study from the field of mathematical chess. In: German chess newspaper . 29th year, no.  5 . Leipzig May 1874, p. 129–134 ( digitized in the Google book search).
  15. Emil Pauls : The maximum problem of the women on the chess board (II. Conclusion) . Study from the field of mathematical chess. In: German chess newspaper . 29th year, no.  9 . Leipzig September 1874, p. 257–267 ( digitized in the Google book search).
  16. a b W. Ahrens : Mathematical Entertainments and Games Volume 1 . Leipzig, 1901, pp. 114–156. Digitized
  17. Hoffman et al. a .: Construction for the Solutions of the Queens Problem . In: Mathematics Magazine , Volume XX, 1969, pp. 66-72. PDF
  18. Follow A051223 in OEIS
  19. Martin S. Pearson: Queens On A Chessboard - Beyond The 2nd Dimension ( en , php) Retrieved January 27, 2020.
  20. Alfred Diel: The game of kings. Bamberger Schachverlag 1983, ISBN 3-923113-03-X , p. 114.
This version was added to the list of articles worth reading on September 20, 2005 .