Problem of the eight ladies

The goal of the " problème" of the eight ladies (sometimes called wrongly problem of the eight queens ), is to place eight ladies of a Jeu of failures on a chess-board of 8×8 boxes without the ladies not being able to threaten themselves mutually, in accordance with the rules of the game of failures (the color of the parts being ignored.) Consequently, two ladies should never share the same line, column, or diagonal.

Simple but noncommonplace, this problem is often used as example with techniques of Programmation.

the term of problem is put here between quotation marks, because it is indeed of a problem to the general direction of the term, but not a problem of failures within the meaning of the Composition échiquéenne. Indeed, this problem was not composed and does not have an author. Moreover, it does not have a single solution, but on this last point, it would be enough to change its statement into asking to find the number of solutions and it could then be arranged in the category of the mathematical problems of failures.

History

During years, much of Mathematician S, including Gauss worked on this problem, which is a particular case of the problem generalized of N - ladies, posed in 1850 by Franz Nauck, and who is to place “free” N ladies on a chess-board of N × N boxes. In 1874, S. Gunther proposed a method to find solutions by employing determining, and J.W.L. Glaisher refined this approach.

This problem was used with the beginning of the year ninety, in the play on Ordinateur The 7th Guest (the Seventh Guest).

Development of a solution

There exists a simple algorithm turning over a simple solution for N ladies if N = 1 or N ≥ 4:

To divide N by 12. To remember remainder (they is 8 for the problem of the eight ladies).
To write in the order the list of the even numbers of 2 with N .
If the remainder is 3 or 9, to put 2 at the end of the list.
To write in the order the odd numbers of 1 with N , but, if the remainder is 8, to permute both to two (IE 3,1,7,5,11,9,…).
If the remainder is 2, to permute the places of 1 and 3, then to put 5 at the end of the list.
If the remainder is 3 or 9, to put 1 and 3 at the end of the list.
To place the queen of the first column in the line with the first number of the list, to place the queen of the second column in the line with the second number of the list, etc

For N = 8 this has as a consequence the solution shown above.

14 ladies (remains 2): 2,4,6,8,10,12,14,3,1,7,9,11,13,5.
15 ladies (remains 3): 4,6,8,10,12,14,2,5,7,9,11,13,15,1,3.
20 ladies (remains 8): 2,4,6,8,10,12,14,16,18,20,3,1,7,5,11,9,15,13,19,17.

Solutions

The problem of the eight ladies has 92 distinct solutions, or only 12 solutions by taking account of transformations such as rotations or reflections (via the Lemme of Burnside.)

Alternatives

; With different parts Thirty-two riders, fourteen insane or sixteen kings can be laid out on a traditional chess-board. The fairy-like parts of failures can replace the ladies. ; With different chess-boards

Pólya studied the problem of N - ladies on a toroidal chess-board . Other supports were used, like the three-dimensional chess-boards.

; The problem of the dominations

the problem is to find the number minimal ladies (or other parts) necessary to control all the boxes of a chess-board N × N . For example for a chess-board “8×8”, this number is worth five.

; The problem of the nine ladies (in English)

It is necessary to place nine ladies and a pawn on a traditional chess-board, by preventing that the ladies cannot be caught. This problem spreads by considering a chess-board N × N and R ladies ( R > N ) and it is necessary to find the number minimum of pawns, so that the ladies and the pawns can be placed on the chess-board without ladies not threatening themselves. The general problem is still not solved.

; The magic Square

In 1992, Demirörs, Rafraf and Tanik published a method of magic square conversion of into solutions of the problem of N - ladies, and reciprocally.

; The Square Latin ; The problems of failures ; Standard of problems of failures

The problem of the eight ladies in data processing

The problem of the eight ladies is an good example of simple but nonobvious problem. For this reason, it is often employed like support of implementation of various techniques of programming, including nontraditional approaches of the programming such as the Programmation by constraints, the logical Programmation or the genetic algorithms.

Generally, it is employed as example of a problem which can be solved with a recursive algorithm , while expressing that a solution of the problem of N - ladies can be obtained, by recurrence, starting from an unspecified solution of the problem of ( N -1) - ladies by the addition of a lady. The recurrence starts with the solution of the problem of 0-lady which rests on an empty chess-board.

This technique is much more effective than the naive algorithm of exhaustive Recherche, which traverses each 64⁸ = 2⁴⁸ = 281.474.976 710.656 possible placements of the eight ladies, to withdraw all those for which several ladies are on the same box (leaving only $A_ {64} ^8=64! /56! = 178.462.987 637.760$ possible arrangements) or for which ladies threaten themselves mutually.

This very “bad” algorithm, will on several occasions produce the same results by allotting various places to the eight ladies, and will start again same calculations several times for various parts of each solution. A slightly better algorithm of exhaustive research places only one lady per line, reducing to only 8⁸ = 2²⁴ = 16.777.216 possible placements.

It is possible to do much better than that. For example, the program of in-depth Recherche below examines only 15.720 possible placements of the ladies by building a tree of research and by traversing the lines of the chess-board one by one, eliminating the majority from the possible positions at a very primitive stage of their construction.

The Programmation by constraints is much more effective for this problem. An algorithm of “iterative repair” starts typically starting from a placement of all the ladies on the chess-board, for example with only one lady per column. It then counts the number of conflicts between ladies, and uses a discovery method to determine how to improve the placements of the ladies. Discovery method of less conflict, which consists in moving the part having the greatest number of conflicts, in the same column in a place where the number of conflicts is smallest, is particularly effective. It solves the problem of the million ladies (on a chess-board of 1.000.000× 1.000.000 boxes) in less than 50 stages on average!

Obtaining this average of 50 stages supposes that the initial configuration is reasonably good. So at the beginning, a million ladies are placed in the same line, the algorithm will take obviously more than 50 stages to solve the problem. A “reasonably good” starting point consists in placing each lady in a column such that it is in conflict with more the small number of ladies being already on the chess-board.

Notice that the method of iterative repair, unlike in-depth research described above, does not guarantee a solution. Like all the methods of deeper descent, it can be blocked on a local extremum (in this case the algorithm can be restarted with a different initial configuration.) On another side, it can solve problems of big sizes which are largely beyond the range of an in-depth research.

Program example in Python

This program written in computer programming language Python employs in-depth research combined with the following rules:

no pair of parts can share the same line;
any solution for N ladies on a chess-board of N × m must contain a solution for ( N -1) - ladies on a chess-board of ( N -1) × m ;
this procedure to follow will always maintain the ladies in the order, and will produce each solution only once.

# Turns over a list of solutions of the problem of N - ladies on one # chess-board of N by N . A solution is represented by a list of # positions of columns of the ladies, indexed by the lines. # the lines and the columns are indexed from zero. def n_dames (N, width): yew N == 0: return # a solution, the empty list else: return ajoute_dame (n-1, width, n_dames (n-1, width))

# Tests all the ways of adding a lady to a column of index the line nouvelle_ligne, and turns over # a list of solutions. precedentes_solutions must be a list of solutions # for the problem of the nouvelle_ligne-dames. def ajoute_dame (nouvelle_ligne, width, precedentes_solutions): solutions = for ground in precedentes_solutions: # Tries to place a lady on each column at the line nouvelle_ligne. for nouvelle_colonne in arranges (width): # print “tests”, nouvelle_colonne, “with the line”, nouvelle_ligne yew dame_sans_danger (nouvelle_ligne, nouvelle_colonne, ground): # No interference, therefore adds this solution to the list. solutions.append (ground +) return solutions

# can one add without danger a lady to ground in (nouvelle_ligne, nouvelle_colonne)? Turn over # true if it is the case. ground must be a solution with the problem of the nouvelle_ligne-dames. def dame_sans_danger (nouvelle_ligne, nouvelle_colonne, ground): # again Checks each part of each nouvelle_ligne existing lines. for line in arranges (nouvelle_ligne): yew (ground == nouvelle_colonne gold # conflict on the same column ground + line == nouvelle_colonne + nouvelle_ligne gold # conflict on a diagonal ground - line == nouvelle_colonne - nouvelle_ligne): # different diagonal return 0 return 1

for ground in n_dames (8, 8): print ground

Program example out of C

include

int is_valid (tank *tab, int line, int case) { int I, J, ret;

for (I = 0, ret = 0; I < line && (! = case || ++ret); i++) ; for (I = line - 1, J = case - 1; I >=0 && J >= 0 &&! ret && (! = J || ++ret); I--, J--) ; for (I = line - 1, J = case + 1; I >=0 && J < 8 &&! ret && (! = J || ++ret); I--, j++) ;

return (ret); }

void aff (tank *tab) { int I, J;

for (I = 0; I < 8; i++) { printf (" \ n"); for (J = 0; J < 8; j++) yew (== J) printf (" X "); else printf (" 0 "); }

printf (" \ n"); printf (" \ n"); }

int received (tank *tab, int line) { static int solution = 0; int case;

yew (line == 8) { aff (); return (++solution); }

for (case = 0; case < 8; cas++) { yew (! is_valid (, line, case)) { = case; received (, line + 1); = 9; } }

return (solution); }

int hand (void) { tank = {9, 9,9,9,9,9,9,9}; printf (" The 8 queens can resoudrent themselves of %d methods \ n" , received (, 0)); system (" PAUSE"); return (0); }

References

Watkins, John J. (2004). Across the Board: The Mathematics off Chess Problems . Princeton: Princeton University Near. ISBN 0-691-11503-6.

Bonds towards the solutions

Find your solution. (in English)
BASIC Atari (in English)
genetic Algorithms (in English)
Haskell/Java hybrid (in English)
Java (in English)
ml standardized (in English)
whole continuations (in English)
resolvor in Javascript (in German)

Random links: