Eight Queens

Kata

This kata is based on the classic chess rules. You must put eight chess queens on an 8×8 chessboard such that none of them is able to capture any other using the standard chess queen’s moves.

Tips: you could have only one queen by row and column.

Step 1

Use multiple TDD loops to build a programm they find all solutions.

Tree traversal

Rewrite a new programm to use a Depth-first walk.
Rewrite a new programm to use a Breadth-first walk.
Compare performances and lisibility

Nontraditional approaches

In this part we whant to find only one solution.

Use a genetic algorithms to solve this puzzle.
Use a minimum-conflicts heuristic to solve this puzzle.
Use other metaheuristic algorithms like Simulated annealing or random to solve this puzzle.
Compare performances

Brute-force

Build a programm they use brute-force and compare performances

⚠️ Spoiler: the next part is a technical solution ⚠️

Brute-force

Vertical and horizontal rules

Given a chessboard, you can code each line of board by one byte of 8 bits, with 0 for empty cell and 1 for a queen.

+---+---+---+---+---+---+---+---+
| ♛ |   |   |   |   |   |   |   |
+---+---+---+---+---+---+---+---+

Could be encoded by 10000000 i.e 128. To know if 2 row contains 2 quens, it’s possible to use the OR operator. For a 8×8 chessboard, you must have only 1 in the result i.e. 255.

Sample with a 4×4 board

+---+---+---+---+
|   | ♛ |   |   |
+---+---+---+---+
|   |   |   | ♛ |
+---+---+---+---+
| ♛ |   |   |   |
+---+---+---+---+
|   |   | ♛ |   |
+---+---+---+---+

0100 OR 0001 OR 1000 OR 0010 = 1111

Diagonals rules

Diagonals could be check with 16bits with one shift by line :

+---+---+---+---+                    +---+---+---+---++---+---+---+---+
|   |   |   | ♛ | Line 0 => no shift |   |   |   |   ||   |   |   | ♛ |
+---+---+---+---+                    +---+---+---+---++---+---+---+---+
|   | ♛ |   |   | Line 1 => 1 shift  |   |   |   |   || ♛ < . |   |   |
+---+---+---+---+                    +---+---+---+---++---+---+---+---+
|   |   | ♛ |   | Line 2 => 2 shifts |   |   |   |   || ♛ <   < . |   |
+---+---+---+---+                    +---+---+---+---++---+---+---+---+
| ♛ |   |   |   | Line 3 => 3 shifts |   | ♛ <   <   << . |   |   |   |
+---+---+---+---+                    +---+---+---+---++---+---+---+---+

Could be test with :

00000001 OR 00001000 OR 00001000 OR 01000000 = 01001001

Implement a programm they use this optimized check solution to find all solutions by brute-force.
Compare performance with others implementations

Edit