March Madness - Eight Queens

This is the classic 8 queens problem solved with brute force on the Arduino. There are elegant recursive solutions but this one I wrote in assembly language on a 1 Mhz 6800 over 30 years ago. The problem is to put 8 queens on a chess board so that they cannot take another queen in 1 move.

The board is represented by 8 bytes/ The process is to put 1 queen in the left most position of each row. Then check to see if its valid. Then move the first row to the right 1 position. If it goes of the right side, move the next row one to the right and put this row back on the left.

This brute force method goes through 16777216 itterations of the board (8 to the 8th power). Each board is checked to make sure there is only one queen in each column and at most 1 on each diagonal.

This took 6 minutes 31 seconds to run.

This web page has a neat interactive 8 queens board

http://www.hbmeyer.de/backtrack/achtdamen/eight.htm

This page has some of the math theory and the proof that 92 solutions is the correct answer.

http://mathworld.wolfram.com/QueensProblem.html




Eight Queens brute force
The board starts out like this
+----------------+
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
|Q . . . . . . . |
+----------------+

loop= 1299852 solution count= 1
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . . . Q . . . |
|Q . . . . . . . |
+----------------+

loop= 1551565 solution count= 2
+----------------+
|. . . . Q . . . |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|Q . . . . . . . |
+----------------+

loop= 1695331 solution count= 3
+----------------+
|. . Q . . . . . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
+----------------+

loop= 1733355 solution count= 4
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
+----------------+

loop= 3077173 solution count= 5
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
|. Q . . . . . . |
+----------------+

loop= 3343852 solution count= 6
+----------------+
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. Q . . . . . . |
+----------------+

loop= 3355115 solution count= 7
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. Q . . . . . . |
+----------------+

loop= 3434453 solution count= 8
+----------------+
|. . . . Q . . . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
+----------------+

loop= 3645685 solution count= 9
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. Q . . . . . . |
+----------------+

loop= 3759876 solution count= 10
+----------------+
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
+----------------+

loop= 3829995 solution count= 11
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
+----------------+

loop= 4097332 solution count= 12
+----------------+
|. . . Q . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
+----------------+

loop= 4410974 solution count= 13
+----------------+
|. . . . . Q . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
+----------------+

loop= 5304734 solution count= 14
+----------------+
|. . . . . Q . . |
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
|. . Q . . . . . |
+----------------+

loop= 5307121 solution count= 15
+----------------+
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
|. . Q . . . . . |
+----------------+

loop= 5441150 solution count= 16
+----------------+
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . Q . . . . . |
+----------------+

loop= 5484942 solution count= 17
+----------------+
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . Q . . . . . |
+----------------+

loop= 5557812 solution count= 18
+----------------+
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5562621 solution count= 19
+----------------+
|. . . . Q . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5564476 solution count= 20
+----------------+
|. . . Q . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5607218 solution count= 21
+----------------+
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5611313 solution count= 22
+----------------+
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5736354 solution count= 23
+----------------+
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5736844 solution count= 24
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5740085 solution count= 25
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
+----------------+

loop= 5830686 solution count= 26
+----------------+
|. . . . . Q . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
+----------------+

loop= 5831365 solution count= 27
+----------------+
|. . . . Q . . . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
+----------------+

loop= 6152525 solution count= 28
+----------------+
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . Q . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. . . . . . . Q |
|. . Q . . . . . |
+----------------+

loop= 6452118 solution count= 29
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6453938 solution count= 30
+----------------+
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6715927 solution count= 31
+----------------+
|. . . . . . Q . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6761413 solution count= 32
+----------------+
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6761441 solution count= 33
+----------------+
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6767083 solution count= 34
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6802454 solution count= 35
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 6803623 solution count= 36
+----------------+
|. . . . . . Q . |
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
+----------------+

loop= 7619543 solution count= 37
+----------------+
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. . . Q . . . . |
+----------------+

loop= 7838741 solution count= 38
+----------------+
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
+----------------+

loop= 7840162 solution count= 39
+----------------+
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
+----------------+

loop= 7895147 solution count= 40
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
+----------------+

loop= 7959302 solution count= 41
+----------------+
|. . . . . Q . . |
|Q . . . . . . . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . Q . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
+----------------+

loop= 8002072 solution count= 42
+----------------+
|. . . . . . . Q |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|. . . Q . . . . |
+----------------+

loop= 8003962 solution count= 43
+----------------+
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|. . . Q . . . . |
+----------------+

loop= 8137333 solution count= 44
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
+----------------+

loop= 8146027 solution count= 45
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
+----------------+

loop= 8266126 solution count= 46
+----------------+
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. . . Q . . . . |
+----------------+

loop= 8511091 solution count= 47
+----------------+
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8631190 solution count= 48
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8639884 solution count= 49
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8773255 solution count= 50
+----------------+
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8775145 solution count= 51
+----------------+
|Q . . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . Q . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8817915 solution count= 52
+----------------+
|. . Q . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8882070 solution count= 53
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8937055 solution count= 54
+----------------+
|. . . . . . Q . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
+----------------+

loop= 8938476 solution count= 55
+----------------+
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
+----------------+

loop= 9157674 solution count= 56
+----------------+
|. Q . . . . . . |
|. . . . . Q . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. . . . . . . Q |
|. . Q . . . . . |
|. . . . Q . . . |
+----------------+

loop= 9973594 solution count= 57
+----------------+
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 9974763 solution count= 58
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 10010134 solution count= 59
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 10015776 solution count= 60
+----------------+
|. . . . . . . Q |
|. . . Q . . . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 10015804 solution count= 61
+----------------+
|. . . Q . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 10061290 solution count= 62
+----------------+
|. Q . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
+----------------+

loop= 10323279 solution count= 63
+----------------+
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
+----------------+

loop= 10325099 solution count= 64
+----------------+
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
+----------------+

loop= 10624692 solution count= 65
+----------------+
|. . . Q . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . Q . . |
+----------------+

loop= 10945852 solution count= 66
+----------------+
|. . . Q . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
+----------------+

loop= 10946531 solution count= 67
+----------------+
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11037132 solution count= 68
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11040373 solution count= 69
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11040863 solution count= 70
+----------------+
|. . . . . . Q . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11165904 solution count= 71
+----------------+
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11169999 solution count= 72
+----------------+
|. . . . . . Q . |
|. Q . . . . . . |
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11212741 solution count= 73
+----------------+
|. . . . Q . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11214596 solution count= 74
+----------------+
|. . . Q . . . . |
|Q . . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11219405 solution count= 75
+----------------+
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
|. . Q . . . . . |
|. . . . . Q . . |
+----------------+

loop= 11292275 solution count= 76
+----------------+
|. . Q . . . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
+----------------+

loop= 11336067 solution count= 77
+----------------+
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
+----------------+

loop= 11470096 solution count= 78
+----------------+
|. . . . . . . Q |
|. Q . . . . . . |
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. . . . . Q . . |
+----------------+

loop= 11472483 solution count= 79
+----------------+
|. . Q . . . . . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . . . . Q . |
|. . . Q . . . . |
|. . . . . Q . . |
+----------------+

loop= 12366243 solution count= 80
+----------------+
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
+----------------+

loop= 12679885 solution count= 81
+----------------+
|. . . . Q . . . |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . Q . |
+----------------+

loop= 12947222 solution count= 82
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|Q . . . . . . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . Q . |
+----------------+

loop= 13017341 solution count= 83
+----------------+
|. . . . Q . . . |
|. . . . . . . Q |
|. . . Q . . . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . Q . . |
|. Q . . . . . . |
|. . . . . . Q . |
+----------------+

loop= 13131532 solution count= 84
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . Q . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . Q . |
+----------------+

loop= 13342764 solution count= 85
+----------------+
|. . . Q . . . . |
|. . . . . Q . . |
|Q . . . . . . . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . Q . . . . . |
|. . . . . . Q . |
+----------------+

loop= 13422102 solution count= 86
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . . . Q |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
+----------------+

loop= 13433365 solution count= 87
+----------------+
|. . . . Q . . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . . . Q . . |
|. . . . . . . Q |
|. Q . . . . . . |
|. . . Q . . . . |
|. . . . . . Q . |
+----------------+

loop= 13700044 solution count= 88
+----------------+
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
|. . . . . Q . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
+----------------+

loop= 15043862 solution count= 89
+----------------+
|. . . . . Q . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . . Q . . . . |
|. Q . . . . . . |
|. . . . . . . Q |
+----------------+

loop= 15081886 solution count= 90
+----------------+
|. . . . . Q . . |
|. . . Q . . . . |
|. . . . . . Q . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . . . Q |
+----------------+

loop= 15225652 solution count= 91
+----------------+
|. . . Q . . . . |
|. . . . . . Q . |
|. . . . Q . . . |
|. Q . . . . . . |
|. . . . . Q . . |
|Q . . . . . . . |
|. . Q . . . . . |
|. . . . . . . Q |
+----------------+

loop= 15477365 solution count= 92
+----------------+
|. . . . Q . . . |
|. . . . . . Q . |
|. Q . . . . . . |
|. . . . . Q . . |
|. . Q . . . . . |
|Q . . . . . . . |
|. . . Q . . . . |
|. . . . . . . Q |
+----------------+

----------------------------------
All done
loop= 16777215

This is what the board ends up looking like
+----------------+
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
|. . . . . . . Q |
+----------------+

----------------------------------
total seconds=391
hours=0
minutes=6
seconds=31




//************************************************************************
//*	Eight Queens
//*	
//*		(C) 2010 by Mark Sproul
//*		Open source as per standard Arduino code
//*	
//************************************************************************

#include <stdio.h>
#include <ctype.h>
#include <string.h>
#include <stdlib.h>
#include <inttypes.h>
#include "WProgram.h"

#include "HardwareSerial.h"

unsigned long	gChessBoard[8];
unsigned long	gLoopCounter;
int				gValidCount;
//long			gShiftedChessBoard[8];


//************************************************************************
boolean	CheckCurrentBoard(void)
{
int		ii;
int		jj;
int		theRow;
long	theLongRow;
long	theLongColumns;
int		bitCount;

	//*	we know we have 1 in each row,
	//*	Check for 1 in each column
	theRow	=	0;
	for (ii=0; ii<8; ii++)
	{
		theRow	|=	gChessBoard[ii];
	}
	if (theRow != 0x0ff)
	{
		return(false);
	}

	//*	we have 1 in each column, now check the diagonals
	theLongColumns	=	0;
	for (ii=0; ii<8; ii++)
	{
		theLongRow	=	gChessBoard[ii] & 0x0ff;
		theLongRow	=	theLongRow << ii;
		
		theLongColumns	|=	theLongRow;
	}
	
	//*	now count the bits
	bitCount	=	0;
	for (ii=0; ii<16; ii++)
	{
		if ((theLongColumns & 0x01) == 0x01)
		{
			bitCount++;
		}
		theLongColumns	=	theLongColumns >> 1;
	}
	if (bitCount != 8)
	{
		return(false);
	}

	
	//*	we now have to check the other diagonal
	theLongColumns	=	0;
	for (ii=0; ii<8; ii++)
	{
		theLongRow	=	gChessBoard[ii] & 0x0ff;
		theLongRow	=	theLongRow << 8;
		theLongRow	=	theLongRow >> ii;
		
		theLongColumns	|=	theLongRow;
	}

	//*	now count the bits
	bitCount	=	0;
	for (ii=0; ii<16; ii++)
	{
		if ((theLongColumns & 0x01) == 0x01)
		{
			bitCount++;
		}
		theLongColumns	=	theLongColumns >> 1;
	}
	if (bitCount != 8)
	{
		return(false);
	}


	return(true);
}


//************************************************************************
boolean	CheckForDone(void)
{
int		ii;
boolean	weAreDone;
int		theRow;

	weAreDone	=	false;

	//*	we know we have 1 in each row,
	//*	Check for 1 in each column
	theRow	=	0;
	for (ii=0; ii<8; ii++)
	{
		theRow	|=	gChessBoard[ii];
	}
	if (theRow == 0x01)
	{
		weAreDone	=	true;
	}

	return(weAreDone);
}


//************************************************************************
void	RotateQueens(void)
{
int		ii;
boolean	keepGoing;
int		theRow;

	ii			=	0;
	keepGoing	=	true;
	while (keepGoing && (ii < 8))
	{
		theRow	=	gChessBoard[ii] & 0x0ff;
		theRow	=	(theRow >> 1) & 0x0ff;
		if (theRow != 0)
		{
			gChessBoard[ii]	=	theRow;
			keepGoing		=	false;
		}
		else
		{
			gChessBoard[ii]	=	0x080;
		}
		ii++;
	}
}


//************************************************************************
void	PrintChessBoard(void)
{
int		ii;
int		jj;
int		theRow;
char	textString[32];

	Serial.print("loop= ");
	Serial.print(gLoopCounter);
	Serial.print(" solution count= ");
	Serial.println(gValidCount);
	
//	sprintf(textString, "LOOP= %ld", gLoopCounter);
//	Serial.println(textString);
	
	Serial.println("+----------------+");
	for (ii=0; ii<8; ii++)
	{
		theRow	=	gChessBoard[ii];
		
		Serial.print("|");
		for (jj=0; jj<8; jj++)
		{
			if (theRow & 0x080)
			{
				Serial.print("Q ");
			}
			else
			{
				Serial.print(". ");
			}
			theRow	=	theRow << 1;
		}
		Serial.println("|");
	}
	Serial.println("+----------------+");
	Serial.println();
}


//************************************************************************
void setup()
{
int	ii;

	Serial.begin(9600);
	Serial.println();
	Serial.println("Eight Queens brute force");

	//*	put the 8 queens on the board, 1 in each row
	for (ii=0; ii<8; ii++)
	{
		gChessBoard[ii]	=	0x080;
	}
	PrintChessBoard();
	
	gLoopCounter	=	0;
	gValidCount		=	0;
}

//************************************************************************
void loop()
{
	gLoopCounter++;
	
	if (CheckCurrentBoard())
	{
		gValidCount++;
		PrintChessBoard();
	}
	else if ((gLoopCounter % 1000) == 0)
	{
//		PrintChessBoard();
	}

	RotateQueens();
	if (CheckForDone())
	{
	long	elapsedSeconds;
	long	elapsedMinutes;
	long	elapsedHours;
	
		elapsedSeconds	=	millis() / 1000;
		elapsedMinutes	=	elapsedSeconds / 60;
		elapsedHours	=	elapsedMinutes / 60;
		
		Serial.println("----------------------------------");
		Serial.println("All done");

		PrintChessBoard();
		Serial.println("----------------------------------");

		Serial.print("total seconds=");
		Serial.println(elapsedSeconds);

		Serial.print("hours=");
		Serial.println(elapsedHours);

		Serial.print("minutes=");
		Serial.println(elapsedMinutes % 60);

		Serial.print("seconds=");
		Serial.println(elapsedSeconds % 60);

		while (1);
	}
}