Blog ## Eight Queens Problem, Part 3

• May 30, 2017

#### Tags: Algorithms

Recap

In part 2 of this series of articles on the Eight Queens Problem, I had presented a Java implementation to print all the 92 solutions (reproduced below), using a one-dimensional array of size 8.

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 `public` `class` `EightQueens {` `     `  `    ``private` `static` `int` `[] board = ``new` `int` `[``8``];` `    ``private` `static` `int` `solutionsCount = ``0``; ` ` `  `    ``public` `static` `void` `solution () {` `        ``tryQueenInRow (``0``);` `    ``}` ` `  `    ``private` `static` `void` `tryQueenInRow(``int` `row) {` `         `  `        ``for` `(``int` `col = ``0``; col < ``8``; col++) {` `            ``if` `(! attacksQueen (row, col)) {` `                ``board [row] = col;` `                ``if` `(row == ``7``)` `                    ``printSolution ();` `                ``else` `                    ``tryQueenInRow (row + ``1``);` `            ``}` `        ``}` `    ``}` ` `  `    ``private` `static` `void` `printSolution() {` `        ``solutionsCount ++;` `        ``System.out.print(``"Solution "` `+ solutionsCount + ``": "``);` `        ``for` `(``int` `i = ``0``; i <= ``7``; i++)` `            ``System.out.print(board [i] + ``" "``);` `        ``System.out.println();` `    ``}` ` `  `    ``private` `static` `boolean` `attacksQueen(``int` `row, ``int` `col) {` `        ``if` `(attacksInSameColumn (row, col) ||` `                ``attacksInLeftDiagonal (row, col) ||` `                ``attacksInRightDiagonal (row, col))` `            ``return` `true``;` `        ``else` `            ``return` `false``;` `    ``}` `     `  `    ``private` `static` `boolean` `attacksInRightDiagonal(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``1``; i <= row && i <= ``7` `- col; i++) {` `            ``if` `(board [row - i] == col + i)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}` ` `  `    ``private` `static` `boolean` `attacksInLeftDiagonal(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``1``; i <= row && i <= col; i++) {` `            ``if` `(board [row - i] == col - i)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}` ` `  `    ``private` `static` `boolean` `attacksInSameColumn(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``0``; i < row; i++) {` `            ``if` `(board [i] == col)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}` `}`

At the end of that article I had mentioned that out of these, only 12 are distinct solutions. The remaining solutions can be derived by rotating and / or mirroring the 12 distinct solutions.

In this article, we’ll modify the above program in a step-by-step manner, such that it prints the 12 distinct solutions, each of these immediately followed by the solutions derived from these.

An Example

Let us take an example. Given below is the first solution that the above program prints, as well as three derived configurations by rotating the first solution by 90, 180 and 270 degrees respectively (clockwise):    By taking the mirror image of the original solution, and then rotating that by 90, 180 and 270 degrees respectively (clockwise), we get the following solutions:    Array Representations of the Original and Derived Solutions

In our data structure using a one-dimensional array, the above solutions will be represented as follows:

Original solution:
{0, 4, 7, 5, 2, 6, 1, 3}
90 degrees rotation:
{7, 1, 3, 0, 6, 4, 2, 5}
180 degrees rotation:
{4, 6, 1, 5, 2, 0, 3, 7}
270 degrees rotation:
{2, 5, 3, 1, 7, 4, 6, 0}
Mirror image of the original:
{3, 1, 6, 2, 5, 7, 4, 0}
Mirror image, rotated 90 degrees:
{0, 6, 4, 7, 1, 3, 5, 2}
Mirror image, rotated 180 degrees:
{7, 3, 0, 2, 5, 1, 6, 4}
Mirror image, rotated 270 degrees:
{5, 2, 4, 6, 0, 3, 1, 7}

Writing Tests for Generating Derived Solutions

Before I write the code for rotating a board by 90 degrees (and finding other variations), I decide to write a JUnit test class for generating all the seven derived solutions for a given board. My test class is as follows:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 `package` `tests;`   `import` `static` `org.junit.Assert.*;` `import` `org.junit.Test;`   `import` `app.EightQueens;`   `public` `class` `EightQueensTests {`   `    ``private` `int` `[] board = ``new` `int` `[] {``0``, ``4``, ``7``, ``5``, ``2``, ``6``, ``1``, ``3``};`   `    ``@Test` `    ``public` `void` `testRotate90Degrees() {` `        ``int` `[] expected = ``new` `int` `[] {``7``, ``1``, ``3``, ``0``, ``6``, ``4``, ``2``, ``5``};` `        ``assertArrayEquals (expected, EightQueens.rotate90Degrees(board));` `    ``}`   `    ``@Test` `    ``public` `void` `testRotate180Degrees () {` `        ``int` `[] expected = ``new` `int` `[] {``4``, ``6``, ``1``, ``5``, ``2``, ``0``, ``3``, ``7``};` `        ``assertArrayEquals (expected, EightQueens.rotate180Degrees (board));` `    ``}` `    `  `    ``@Test` `    ``public` `void` `testRotate270Degrees () {` `        ``int` `[] expected = ``new` `int` `[] {``2``, ``5``, ``3``, ``1``, ``7``, ``4``, ``6``, ``0``};` `        ``assertArrayEquals (expected, EightQueens.rotate270Degrees (board));` `    ``}` `    `  `    ``@Test` `    ``public` `void` `testMirror () {` `        ``int` `[] expected = ``new` `int` `[] {``3``, ``1``, ``6``, ``2``, ``5``, ``7``, ``4``, ``0``};` `        ``assertArrayEquals (expected, EightQueens.mirror (board));` `    ``}` `    `  `    ``@Test` `    ``public` `void` `testMirrorAndRotate90Degrees () {` `        ``int` `[] expected = ``new` `int` `[] {``0``, ``6``, ``4``, ``7``, ``1``, ``3``, ``5``, ``2``};` `        ``assertArrayEquals (expected, EightQueens.mirrorAndRotate90Degrees (board));` `    ``}` `    `  `    ``@Test` `    ``public` `void` `testMirrorAndRotate180Degrees () {` `        ``int` `[] expected = ``new` `int` `[] {``7``, ``3``, ``0``, ``2``, ``5``, ``1``, ``6``, ``4``};` `        ``assertArrayEquals (expected, EightQueens.mirrorAndRotate180Degrees (board));` `    ``}` `    `  `    ``@Test` `    ``public` `void` `testMirrorAndRotate270Degrees () {` `        ``int` `[] expected = ``new` `int` `[] {``5``, ``2``, ``4``, ``6``, ``0``, ``3``, ``1``, ``7``};` `        ``assertArrayEquals (expected, EightQueens.mirrorAndRotate270Degrees (board));` `    ``}` `    `  `}`

Rotating a Board by 90 Degrees Clockwise

Now the serious work begins. First of all I need to implement 90 degrees rotation of a board. This does not appear to be straightforward initially, but a bit of careful examination of the configurations leads me to the following implementation (in the class EightQueens):

 1 2 3 4 5 6 7 `public` `static` `int` `[] rotate90Degrees(``int``[] board) {` `    ``int` `[] newBoard = ``new` `int` `[``8``];` `    ``for` `(``int` `i = ``0``; i < ``8``; i++) {` `        ``newBoard [board [i]] = ``7` `- i;` `    ``}` `    ``return` `newBoard;` `}`

I run the tests, and the test method testRotate90Degrees() passes!

As it eventually turns out, this was the hardest part of the entire program. Rest is much easier, as we’ll see.

Rotating a Board by 180 and 270 Degrees Clockwise

These are easy to implement, by invoking rotate90Degrees() repetitively.

 1 2 3 4 5 6 7 `public` `static` `int``[] rotate180Degrees(``int``[] board) {` `    ``return` `rotate90Degrees(rotate90Degrees(board));` `}`   `public` `static` `int``[] rotate270Degrees(``int``[] board) {` `    ``return` `rotate180Degrees(rotate90Degrees(board));` `}`

Mirroring a Board

Mirroring a board also turns out to be easy; we simply have to reverse the original array:

 1 2 3 4 5 6 7 `public` `static` `int``[] mirror(``int``[] board) {` `    ``int` `[] newBoard = ``new` `int` `[``8``];` `    ``for` `(``int` `i = ``0``; i < ``8``; i++) {` `        ``newBoard [i] = board [``7` `- i];` `    ``}` `    ``return` `newBoard;` `}`

Mirroring and Rotating a Board

As expected, these methods are quite simple to implement:

 1 2 3 4 5 6 7 8 9 10 11 `public` `static` `int``[] mirrorAndRotate90Degrees(``int``[] board) {` `    ``return` `rotate90Degrees (mirror (board));` `}`   `public` `static` `int``[] mirrorAndRotate180Degrees(``int``[] board) {` `    ``return` `rotate180Degrees (mirror (board));` `}`   `public` `static` `int``[] mirrorAndRotate270Degrees(``int``[] board) {` `    ``return` `rotate270Degrees (mirror (board));` `}`

At this stage, all the tests pass. So now, if you have a solution, printing it and its derivations is not hard.

On Finding a Solution

The only other (somewhat) challenging part is how to identify whether a new solution found is a distinct one, or a derivation of another solution that has already been printed.

The approach that I take is as follows:

• For any distinct solution that I find, I store it along with all its derived solutions in an ArrayList, called allSolutions, and print all such solutions together.
• Whenever I find any solution, I check if that solution already exists in allSolutions. If it does, skip this solution; if it does not, it is a new, distinct solution, and we print it and its derivations.

First I modify the tryQueenInRow (int row) method as follows:

 1 2 3 4 5 6 7 8 9 10 11 `private` `static` `void` `tryQueenInRow(``int` `row) {` `    ``for` `(``int` `col = ``0``; col < ``8``; col++) {` `        ``if` `(! attacksQueen (row, col)) {` `            ``board [row] = col;` `            ``if` `(row == ``7``)` `                ``foundASolution (board);` `            ``else` `                ``tryQueenInRow (row + ``1``);` `        ``}` `    ``}` `}`

Next, I implement the new method foundASolution (int [] board) as follows:

 1 2 3 4 5 6 `private` `static` `void` `foundASolution(``int` `[] board) {` `    ``if` `(!matchesAnEarlierSolution (board)) {` `        ``saveAndPrintSolutionAndVariations (board);` `    ``}` `}` `   `

Data Structure for a Solution

I can simply store the array (one-dimensional, size eight) that represents a solution in allSolutions. But I choose to create a simple Value Object class, consisting of the array as well as a text description (such as “90 degrees rotation of solution 1”), as follows:

 1 2 3 4 5 6 7 `package` `app;`   `public` `class` `SolutionRecord` `{` `    ``public` `int` `[] solution;` `    ``public` `String description;` `}`

Though I end up not using the description field in the final version of my program, I find it useful for debugging purposes.

Do We Have a New Distinct Solution?

I now implement the method to check whether a given solution matches an earlier solution, or is a new, distinct solution:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 `private` `static` `boolean` `matchesAnEarlierSolution(``int` `[] board) {` `    ``for` `(``int` `i = ``0``; i < allSolutions.size(); i++) {` `        ``if` `(haveSameContents(allSolutions.get(i).solution, board))` `            ``return` `true``;` `    ``}` `    ``return` `false``;` `}`   `private` `static` `boolean` `haveSameContents(``int``[] a, ``int``[] b) {` `    ``if` `(a.length != b.length)` `        ``return` `false``;` `    ``for` `(``int` `i = ``0``; i < a.length; i++)` `        ``if` `(a[i] != b[i])` `            ``return` `false``;` `    ``return` `true``;` `}`

Printing a Distinct Solution and Its Derivations, and Saving Them

This is actually an easy part, though somewhat tedious and unexciting. When I find a new distinct solution, I print it, and save it in allSolutions. Then I generate its distinct derived solutions, and save and print those too. It is possible (and is indeed the case) that

• a derived solution may be the same as an original solution (180 degrees rotation being the same as original)
• a derived solution may be the same as another derived solution (mirror or an original solution == mirror and 180 degrees rotation)

I take care of these possibilities in my code: I don’t save such a duplicate derived solution, though I still print it. Here is the code:

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 `private` `static` `void` `saveAndPrintSolutionAndVariations(``int` `[] board) {` `    ``distinctSolutionsCount ++;` `    ``addSolutionRecord (board.clone(), ``"Original solution "` `+ distinctSolutionsCount);`   `    ``System.out.print(``"Distinct solution "` `+ distinctSolutionsCount + ``" : "``);` `    ``printBoard(board);` `    ``System.out.println();` `        `  `    ``int` `[] variation;` `    ``String description;` `        `  `    ``variation = rotate90Degrees(board);` `    ``description = ``"90 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `        `  `    ``variation = rotate180Degrees(board);` `    ``description = ``"180 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `        `  `    ``variation = rotate270Degrees(board);` `    ``description = ``"270 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `        `  `    ``variation = mirror(board);` `    ``description = ``"mirror of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `        `  `    ``variation = mirrorAndRotate90Degrees(board);` `    ``description = ``"mirror, 90 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `    ``variation = mirrorAndRotate180Degrees(board);` `    ``description = ``"mirror, 180 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `    ``variation = mirrorAndRotate270Degrees(board);` `    ``description = ``"mirror, 270 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `    ``saveAndPrintVariation (variation, description);` `    ``System.out.println(``"+++++++++++++++++++++++++++++++"``);` `    ``System.out.println();` `        `  `}`   `private` `static` `void` `addSolutionRecord(``int``[] board, String description) {` `    ``SolutionRecord record = ``new` `SolutionRecord ();` `    ``record.solution = board;` `    ``record.description = description;` `    ``allSolutions.add(record);` `}`   `private` `static` `void` `saveAndPrintVariation(``int``[] variation, String description) {` `    ``if` `(!matchesAnEarlierSolution(variation))` `        ``addSolutionRecord (variation, description);` `    ``System.out.print(description + ``" : "``);` `    ``printBoard (variation);` `    ``System.out.println();` `}`   `private` `static` `void` `printBoard(``int` `[] board) {` `    ``for` `(``int` `i = ``0``; i <= ``7``; i++)` `        ``System.out.print(board [i] + ``" "``);` `}`

The Complete Code

So finally, here is the complete code:

EightQueens.java

 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 180 181 182 183 184 `package` `app;`   `import` `java.util.ArrayList;`   `public` `class` `EightQueens {`   `    ``private` `static` `int` `[] board = ``new` `int` `[``8``];` `    ``private` `static` `int` `distinctSolutionsCount = ``0``;` `    ``private` `static` `ArrayList allSolutions = ``new` `ArrayList ();` `    `  `    ``public` `static` `void` `solution () {` `        ``tryQueenInRow (``0``);` `    ``}`   `    ``private` `static` `void` `tryQueenInRow(``int` `row) {`   `        ``for` `(``int` `col = ``0``; col < ``8``; col++) {` `            ``if` `(! attacksQueen (row, col)) {` `                ``board [row] = col;` `                ``if` `(row == ``7``)` `                    ``foundASolution (board);` `                ``else` `                    ``tryQueenInRow (row + ``1``);` `            ``}` `        ``}` `    ``}`   `    ``private` `static` `boolean` `attacksQueen(``int` `row, ``int` `col) {` `        ``if` `(attacksInSameColumn (row, col) ||` `                ``attacksInLeftDiagonal (row, col) ||` `                ``attacksInRightDiagonal (row, col))` `            ``return` `true``;` `        ``else` `            ``return` `false``;` `    ``}`   `    ``private` `static` `boolean` `attacksInRightDiagonal(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``1``; i <= row && i <= ``7` `- col; i++) {` `            ``if` `(board [row - i] == col + i)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}`   `    ``private` `static` `boolean` `attacksInLeftDiagonal(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``1``; i <= row && i <= col; i++) {` `            ``if` `(board [row - i] == col - i)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}`   `    ``private` `static` `boolean` `attacksInSameColumn(``int` `row, ``int` `col) {` `        ``for` `(``int` `i = ``0``; i < row; i++) {` `            ``if` `(board [i] == col)` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}`   `    ``private` `static` `void` `foundASolution(``int` `[] board) {` `        ``if` `(!matchesAnEarlierSolution (board)) {` `            ``saveAndPrintSolutionAndVariations (board);` `        ``}` `    ``}`   `    ``private` `static` `boolean` `matchesAnEarlierSolution(``int` `[] board) {` `        ``for` `(``int` `i = ``0``; i < allSolutions.size(); i++) {` `            ``if` `(haveSameContents(allSolutions.get(i).solution, board))` `                ``return` `true``;` `        ``}` `        ``return` `false``;` `    ``}`   `    ``private` `static` `boolean` `haveSameContents(``int``[] a, ``int``[] b) {` `        ``if` `(a.length != b.length)` `            ``return` `false``;` `        ``for` `(``int` `i = ``0``; i < a.length; i++)` `            ``if` `(a[i] != b[i])` `                ``return` `false``;` `        ``return` `true``;` `    ``}`   `    ``private` `static` `void` `saveAndPrintSolutionAndVariations(``int` `[] board) {` `        ``distinctSolutionsCount ++;` `        ``addSolutionRecord (board.clone(), ``"Original solution "` `+ distinctSolutionsCount);`   `        ``System.out.print(``"Distinct solution "` `+ distinctSolutionsCount + ``" : "``);` `        ``printBoard(board);` `        ``System.out.println();` `        `  `        ``int` `[] variation;` `        ``String description;` `        `  `        ``variation = rotate90Degrees(board);` `        ``description = ``"90 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);` `        `  `        ``variation = rotate180Degrees(board);` `        ``description = ``"180 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);` `        `  `        ``variation = rotate270Degrees(board);` `        ``description = ``"270 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);` `        `  `        ``variation = mirror(board);` `        ``description = ``"mirror of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);` `        `  `        ``variation = mirrorAndRotate90Degrees(board);` `        ``description = ``"mirror, 90 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);`   `        ``variation = mirrorAndRotate180Degrees(board);` `        ``description = ``"mirror, 180 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);`   `        ``variation = mirrorAndRotate270Degrees(board);` `        ``description = ``"mirror, 270 degrees rotation of solution "` `+ Integer.toString(distinctSolutionsCount);` `        ``saveAndPrintVariation (variation, description);`   `        ``System.out.println(``"+++++++++++++++++++++++++++++++"``);` `        ``System.out.println();` `        `  `    ``}`   `    ``private` `static` `void` `addSolutionRecord(``int``[] board, String description) {` `        ``SolutionRecord record = ``new` `SolutionRecord ();` `        ``record.solution = board;` `        ``record.description = description;` `        ``allSolutions.add(record);` `    ``}`   `    ``private` `static` `void` `saveAndPrintVariation(``int``[] variation, String description) {` `        ``if` `(!matchesAnEarlierSolution(variation))` `            ``addSolutionRecord (variation, description);` `        ``System.out.print(description + ``" : "``);` `        ``printBoard (variation);` `        ``System.out.println();` `    ``}`   `    ``private` `static` `void` `printBoard(``int` `[] board) {` `        ``for` `(``int` `i = ``0``; i <= ``7``; i++)` `            ``System.out.print(board [i] + ``" "``);` `    ``}`   `    ``public` `static` `int` `[] rotate90Degrees(``int``[] board) {` `        ``int` `[] newBoard = ``new` `int` `[``8``];` `        ``for` `(``int` `i = ``0``; i < ``8``; i++) {` `            ``newBoard [board [i]] = ``7` `- i;` `        ``}` `        ``return` `newBoard;` `    ``}`   `    ``public` `static` `int``[] rotate180Degrees(``int``[] board) {` `        ``return` `rotate90Degrees(rotate90Degrees(board));` `    ``}`   `    ``public` `static` `int``[] rotate270Degrees(``int``[] board) {` `        ``return` `rotate180Degrees(rotate90Degrees(board));` `    ``}`   `    ``public` `static` `int``[] mirror(``int``[] board) {` `        ``int` `[] newBoard = ``new` `int` `[``8``];` `        ``for` `(``int` `i = ``0``; i < ``8``; i++) {` `            ``newBoard [i] = board [``7` `- i];` `        ``}` `        ``return` `newBoard;` `    ``}`   `    ``public` `static` `int``[] mirrorAndRotate90Degrees(``int``[] board) {` `        ``return` `rotate90Degrees (mirror (board));` `    ``}`   `    ``public` `static` `int``[] mirrorAndRotate180Degrees(``int``[] board) {` `        ``return` `rotate180Degrees (mirror (board));` `    ``}`   `    ``public` `static` `int``[] mirrorAndRotate270Degrees(``int``[] board) {` `        ``return` `rotate270Degrees (mirror (board));` `    ``}` `    `  `}`

SolutionRecord.java

 1 2 3 4 5 6 7 `package` `app;` ` `  `public` `class` `SolutionRecord` `{` `    ``public` `int` `[] solution;` `    ``public` `String description;` `}`

Application.java

 1 2 3 4 5 6 7 8 9 `package` `app;` ` `  `public` `class` `Application {` ` `  `    ``public` `static` `void` `main(String[] args) {` `        ``EightQueens.solution();` `    ``}` ` `  `}`

The Output

```Distinct solution 1 : 0 4 7 5 2 6 1 3
90 degrees rotation of solution 1 : 7 1 3 0 6 4 2 5
180 degrees rotation of solution 1 : 4 6 1 5 2 0 3 7
270 degrees rotation of solution 1 : 2 5 3 1 7 4 6 0
mirror of solution 1 : 3 1 6 2 5 7 4 0
mirror, 90 degrees rotation of solution 1 : 0 6 4 7 1 3 5 2
mirror, 180 degrees rotation of solution 1 : 7 3 0 2 5 1 6 4
mirror, 270 degrees rotation of solution 1 : 5 2 4 6 0 3 1 7
+++++++++++++++++++++++++++++++

Distinct solution 2 : 0 5 7 2 6 3 1 4
90 degrees rotation of solution 2 : 7 1 4 2 0 6 3 5
180 degrees rotation of solution 2 : 3 6 4 1 5 0 2 7
270 degrees rotation of solution 2 : 2 4 1 7 5 3 6 0
mirror of solution 2 : 4 1 3 6 2 7 5 0
mirror, 90 degrees rotation of solution 2 : 0 6 3 5 7 1 4 2
mirror, 180 degrees rotation of solution 2 : 7 2 0 5 1 4 6 3
mirror, 270 degrees rotation of solution 2 : 5 3 6 0 2 4 1 7
+++++++++++++++++++++++++++++++

Distinct solution 3 : 1 3 5 7 2 0 6 4
90 degrees rotation of solution 3 : 2 7 3 6 0 5 1 4
180 degrees rotation of solution 3 : 3 1 7 5 0 2 4 6
270 degrees rotation of solution 3 : 3 6 2 7 1 4 0 5
mirror of solution 3 : 4 6 0 2 7 5 3 1
mirror, 90 degrees rotation of solution 3 : 5 0 4 1 7 2 6 3
mirror, 180 degrees rotation of solution 3 : 6 4 2 0 5 7 1 3
mirror, 270 degrees rotation of solution 3 : 4 1 5 0 6 3 7 2
+++++++++++++++++++++++++++++++

Distinct solution 4 : 1 4 6 0 2 7 5 3
90 degrees rotation of solution 4 : 4 7 3 0 6 1 5 2
180 degrees rotation of solution 4 : 4 2 0 5 7 1 3 6
270 degrees rotation of solution 4 : 5 2 6 1 7 4 0 3
mirror of solution 4 : 3 5 7 2 0 6 4 1
mirror, 90 degrees rotation of solution 4 : 3 0 4 7 1 6 2 5
mirror, 180 degrees rotation of solution 4 : 6 3 1 7 5 0 2 4
mirror, 270 degrees rotation of solution 4 : 2 5 1 6 0 3 7 4
+++++++++++++++++++++++++++++++

Distinct solution 5 : 1 4 6 3 0 7 5 2
90 degrees rotation of solution 5 : 3 7 0 4 6 1 5 2
180 degrees rotation of solution 5 : 5 2 0 7 4 1 3 6
270 degrees rotation of solution 5 : 5 2 6 1 3 7 0 4
mirror of solution 5 : 2 5 7 0 3 6 4 1
mirror, 90 degrees rotation of solution 5 : 4 0 7 3 1 6 2 5
mirror, 180 degrees rotation of solution 5 : 6 3 1 4 7 0 2 5
mirror, 270 degrees rotation of solution 5 : 2 5 1 6 4 0 7 3
+++++++++++++++++++++++++++++++

Distinct solution 6 : 1 5 0 6 3 7 2 4
90 degrees rotation of solution 6 : 5 7 1 3 0 6 4 2
180 degrees rotation of solution 6 : 3 5 0 4 1 7 2 6
270 degrees rotation of solution 6 : 5 3 1 7 4 6 0 2
mirror of solution 6 : 4 2 7 3 6 0 5 1
mirror, 90 degrees rotation of solution 6 : 2 0 6 4 7 1 3 5
mirror, 180 degrees rotation of solution 6 : 6 2 7 1 4 0 5 3
mirror, 270 degrees rotation of solution 6 : 2 4 6 0 3 1 7 5
+++++++++++++++++++++++++++++++

Distinct solution 7 : 1 5 7 2 0 3 6 4
90 degrees rotation of solution 7 : 3 7 4 2 0 6 1 5
180 degrees rotation of solution 7 : 3 1 4 7 5 0 2 6
270 degrees rotation of solution 7 : 2 6 1 7 5 3 0 4
mirror of solution 7 : 4 6 3 0 2 7 5 1
mirror, 90 degrees rotation of solution 7 : 4 0 3 5 7 1 6 2
mirror, 180 degrees rotation of solution 7 : 6 2 0 5 7 4 1 3
mirror, 270 degrees rotation of solution 7 : 5 1 6 0 2 4 7 3
+++++++++++++++++++++++++++++++

Distinct solution 8 : 1 6 2 5 7 4 0 3
90 degrees rotation of solution 8 : 1 7 5 0 2 4 6 3
180 degrees rotation of solution 8 : 4 7 3 0 2 5 1 6
270 degrees rotation of solution 8 : 4 1 3 5 7 2 0 6
mirror of solution 8 : 3 0 4 7 5 2 6 1
mirror, 90 degrees rotation of solution 8 : 6 0 2 7 5 3 1 4
mirror, 180 degrees rotation of solution 8 : 6 1 5 2 0 3 7 4
mirror, 270 degrees rotation of solution 8 : 3 6 4 2 0 5 7 1
+++++++++++++++++++++++++++++++

Distinct solution 9 : 1 6 4 7 0 3 5 2
90 degrees rotation of solution 9 : 3 7 0 2 5 1 6 4
180 degrees rotation of solution 9 : 5 2 4 7 0 3 1 6
270 degrees rotation of solution 9 : 3 1 6 2 5 7 0 4
mirror of solution 9 : 2 5 3 0 7 4 6 1
mirror, 90 degrees rotation of solution 9 : 4 0 7 5 2 6 1 3
mirror, 180 degrees rotation of solution 9 : 6 1 3 0 7 4 2 5
mirror, 270 degrees rotation of solution 9 : 4 6 1 5 2 0 7 3
+++++++++++++++++++++++++++++++

Distinct solution 10 : 2 4 1 7 0 6 3 5
90 degrees rotation of solution 10 : 3 5 7 1 6 0 2 4
180 degrees rotation of solution 10 : 2 4 1 7 0 6 3 5
270 degrees rotation of solution 10 : 3 5 7 1 6 0 2 4
mirror of solution 10 : 5 3 6 0 7 1 4 2
mirror, 90 degrees rotation of solution 10 : 4 2 0 6 1 7 5 3
mirror, 180 degrees rotation of solution 10 : 5 3 6 0 7 1 4 2
mirror, 270 degrees rotation of solution 10 : 4 2 0 6 1 7 5 3
+++++++++++++++++++++++++++++++

Distinct solution 11 : 2 4 7 3 0 6 1 5
90 degrees rotation of solution 11 : 3 1 7 4 6 0 2 5
180 degrees rotation of solution 11 : 2 6 1 7 4 0 3 5
270 degrees rotation of solution 11 : 2 5 7 1 3 0 6 4
mirror of solution 11 : 5 1 6 0 3 7 4 2
mirror, 90 degrees rotation of solution 11 : 4 6 0 3 1 7 5 2
mirror, 180 degrees rotation of solution 11 : 5 3 0 4 7 1 6 2
mirror, 270 degrees rotation of solution 11 : 5 2 0 6 4 7 1 3
+++++++++++++++++++++++++++++++

Distinct solution 12 : 2 5 1 4 7 0 6 3
90 degrees rotation of solution 12 : 2 5 7 0 4 6 1 3
180 degrees rotation of solution 12 : 4 1 7 0 3 6 2 5
270 degrees rotation of solution 12 : 4 6 1 3 7 0 2 5
mirror of solution 12 : 3 6 0 7 4 1 5 2
mirror, 90 degrees rotation of solution 12 : 5 2 0 7 3 1 6 4
mirror, 180 degrees rotation of solution 12 : 5 2 6 3 0 7 1 4
mirror, 270 degrees rotation of solution 12 : 3 1 6 4 0 7 5 2
+++++++++++++++++++++++++++++++
```

As we can see, in solution 10, the 180 degrees rotation is the same as the original solution. Similarly, its mirrored solution is the same as its mirrored AND 180 degrees rotation.

What Next?

How about changing the earlier program (from part 2 of the series, reproduced at the start of this article) to find solutions for an n x n board instead of just 8 x 8? We’ll attempt that in a later article.