History and Theories Behind the n-Queens Problem

The n-Queens Problem

History and Theories Behind the n-Queens Problem

It has been said that Carl Gauss first introduced the n-queens problem in the year 1850.  The objective of this problem is to find a placement of n queens on an n×n chessboard, so that no one queen can be taken by any other. Despite the fact that it has been recognized that the answer to the n-queens problem is n, several solutions have been published from the time when the original problem was put forward. A lot of these solutions depend on giving an exact formula for placing queens or transposing smaller solutions sets to offer solutions for larger values of n (Bernhardsson, 1991).

Shagrir (1992) said that the n-queens problem is a classical search problem, utilized as a test bed for the benchmarking and development of search algorithms. Traditional search methods include backtracking. Since the difficulty of backtracking more often than not increases exponentially with the size of the problem, it is advantageous to come up with alternatives to backtracking search. To surmount the flaws and limitations of backtracking, local search methods have been developed in late 1987, using the n-queens problem as a test bed.  Some of these local search methods are as follows:

§  Constraint Satisfaction Problem

Bernhardsson (1991) said that the n-queens problem has been assessed in relationship to the study on the constraint satisfaction problem. The objective of the study is to come up with practical and fast solutions to large-scale constraint satisfaction problems.

§  Local Search Optimization

Bernhardsson (1991) stated that local search methods are frequently approximative. The progress in the quality of the solution needs more computational time. One of the questions is how long an algorithm must run for a given quality of solution.

Meanwhile, according to Sosi and Gu (1994), experimental observations of smaller-size problems illustrate that the number of solutions increases exponentially with increasing n.  On the other hand, search-based algorithms have been expounded. For instance, a backtracking search, will methodically produce all probable solution sets for a given n×n board.  Sosi and Gu (1994) added that in reality, Nevertheless, backtracking methods offer an extremely limited class of solutions for large size boards for the reason that it is hard and complex for a backtracking search to discover solutions that are considerably distinct in the solution space. Quite a lot of authors have recommended other effective search techniques to conquer this problem. Kale (1990) claimed that these methods consist of search heuristic methods and local search and conflict minimization approaches as well. In recent times, advances in research in the field of neural networks have brought about a number of papers suggesting solutions to the n-queens problem by means of neural networks (Shagrir, 1992). Particularly, Mandziuk (1995) has applied the Hopfield networks to the n-queens problem. Mandziuk (1995) asserted that the Hopfield neural network is a simple artificial network, which is able to keep a number of patterns in a way similar to the brain in that the full pattern for a specified problem can be retrieved if the network is presented with just limited information.

Lastly, the n-Queens problem has been maintained as an integer programming comparable to the assignment problem.

Solutions to the 8-Queens Problem

An apparent amendment of the 8 by 8 problem is to take into account an N by N “chess board” and ask if one can put N queens on such a board. It is pretty easy to observe that this is not possible if N is 2 or 3, and it is logically simple to find solutions when N is 4, 5, 6, or 7. The problem starts to become difficult for manual solution exactly when N is 8. Most likely the reality that this number inadvertently equals the dimensions of an ordinary chessboard has added to the popularity of the problem.

If given the problem of placing 8 queens on the chess board so that they do not check each other and we want to find a single solution, it is not hard as I will show to you now. However, if we like to look for all probable solutions, the problem will be hard and complex and the backtrack method is the lone known method for solving this problem. For 8-queen, we have 92 solutions, but if we will exclude symmetry, there are 12 solutions.

The 12 basic solutions can be constructed using the following table. For example, if you are constructing solution number 1, then the Queen for chessboard row 1 should be placed in column 1, the Queen for row 2 should be placed in column 5, etc. A diagram showing solution number 1 appears below the table.

Sol.    Elements show which column to use per chessboard row
Nbr.    Row 1  Row 2  Row 3  Row 4  Row 5  Row 6  Row 7  Row 8
————————————————————–
1         1      5      8      6      3      7      2      4
2         1      6      8      3      7      4      2      5
3         2      4      6      8      3      1      7      5
4         2      5      7      1      3      8      6      4
5         2      5      7      4      1      8      6      3
6         2      6      1      7      4      8      3      5
7         2      6      8      3      1      4      7      5
8         2      7      3      6      8      5      1      4
9         2      7      5      8      1      4      6      3
10        3      5      2      8      1      7      4      6
11        3      5      8      4      1      7      2      6
12        3      6      2      5      8      1      7      4

   ———————————
8 |   |   |   | Q |   |   |   |   |
———————————
7 |   | Q |   |   |   |   |   |   |
———————————
6 |   |   |   |   |   |   | Q |   |
———————————
5 |   |   | Q |   |   |   |   |   |
Rows     ———————————
4 |   |   |   |   |   | Q |   |   |
———————————
3 |   |   |   |   |   |   |   | Q |
———————————
2 |   |   |   |   | Q |   |   |   |
———————————
1 | Q |   |   |   |   |   |   |   |
———————————
1   2   3   4   5   6   7   8
Columns

If we rotate and reflect any solution so that the entry on row 1 is as far left as possible, then we can group solutions by this leftmost column. The above example is a “Column 1” solution. Of the 12 basic solutions, two are “Column 1” solutions, seven are “Column 2” solutions, and three are “Column 3” solutions.

            Here are the 12 solutions to the 8-Queens problem, which you can demonstrate or show in class by drawing them on the whiteboard:

References

Bernhardsson, B. (1991), “Explicit solutions to the n-queens problems for all n,” ACM SIGART Bulletin, Vol. 2, No. 7.

Kale, L.V. (1990), “An almost perfect heuristic for the n non-attacking queens problem,” Information Processing Letter, Vol.34, pp.173-78.

Mandziuk, J. (1995), “Solving the n-queens problem with a binary Hopfield-type network. Synchronous and asynchronous model,” Biological Cybernetics, Vol. 72, No. 5.

Shagrir, O. (1992), “A neural net with self-inhibiting units for the n-queens problem,” International Journal of Neural Systems, Vol. 3, No. 3.

Sosi, R. and J. Gu (1994), “Efficient local search with conflict minimization: A case study of the n-queens problem,” IEEE Transactions on Knowledge and Data Engineering, Vol. 6, No. 5.