Backtracking search, pt1

I give you a puzzle and I tell you that this puzzle has a million solutions to it. Furthermore, I want you to find all one million solutions. How would you accomplish this? It would likely be a very time-consuming task, and there would be well, quite a bit of things to keep track of.

Let's get a little more specific. I have a chessboard, and I want to know how many configurations of queens I can have, so that one queen occupies a row, and no queen is able to attack one another. Let's go a little simpler. I have a chessboard that is 1x1. How many solutions are there? One, and this is a pretty trivial case. There are no solutions for a 2x2 board and there are no solutions for a 3x3 board, but there are two solutions for a 4x4 board.

How would we find them?

Let's start with an empty board.
....
....
....
....

Let's place a queen in the first row, first column.
Q...
....
....
....

Now, let's go to the second row. Since we cannot place a queen in the first or second column, let's place a queen in the third column.
Q...
..Q.
....
....

Now, for the third row. Where can we place a queen?
The first, second, third, and fourth columns are right now. So we must backtrack. We will take off our queens, and start by placing one at the second column.
.Q..
....
....
....

Our next possible place is the fourth column, second row.
.Q..
...Q
....
....

Now, our next possible place is the first column, third row.
.Q..
...Q
Q...
....

Our last place to check is the 3rd column, last row.
.Q..
...Q
Q...
..Q.

And now we have a solution. This took about seven steps. Quite awhile. There is one more solution to a 4x4 board, but it's just a mirror image. I won't get solving this as you should see the pattern.

So, how would we find all solutions for an 8x8 or even an NxN problem set?

With a computer that can do what we did. Of course.