8 Queens Problem (Chapter 4, Exercise 27)

Here is one possible outcome of using a brute force approach to the 8 queens problem.  "globalCounter" keeps track of how many squares are either occupied by a queen or attacked by a queen.  "numberQueens" keeps track of how many queens are placed.  As squares are chosen randomly and checked  for occupancy, the following patterns emerge in one (random) run.  The algorithm only terminates when an 8-queens solutions is struck upon.  The 11th attempt does the trick in this instance.

☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 7
Press any key to continue . . .

☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 7
Press any key to continue . . .

☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
globalCounter = 64
numberQueens = 7
Press any key to continue . . .

♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
globalCounter = 64
numberQueens = 6
Press any key to continue . . .

☺ ☺ ♣ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ♣ ☺ ☺ ☺
☺ ♣ ☺ ☺ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ☺ ♣
☺ ☺ ☺ ☺ ☺ ♣ ☺ ☺
☺ ☺ ☺ ♣ ☺ ☺ ☺ ☺
☺ ☺ ☺ ☺ ☺ ☺ ♣ ☺
♣ ☺ ☺ ☺ ☺ ☺ ☺ ☺
globalCounter = 64
numberQueens = 8
Press any key to continue . . .

Follow-up question: what is the probability that, choosing squares randomly and putting down a queen if you can, you will place k queens on an nXn board?  Can you come up with some empirical estimates?