- As I pondered my initial failure
with the N-Queens program,
I thought about how to fix it.
I believe the approach to check for attacks is sound,
but the method of tracking a queen's attack was wrong.
So I reversed the method.
Instead of setting attacks,
I'd be defensive,
and scan a square for potential attacks from elsewhere.
The key to doing that
is to find a queen's location on the board.
And the key to that is to store the queen's location
specifically as a row-column pair.
Then I thought about a two-dimensional array.
One element for the row, and another for the column.
Given that, the first element would always be sequential.
Row one through N.
And that's the same values as an element in an array.
So, all that's truly needed is
a one-dimensional array of integers.
Each element gives the queen's column position
for a certain row.
Working with my original code,
I combined the set queen function
with the find square function.
The function takes as an argument
the board array, the current row,
which is where the queen will be set.
And then the number of squares on the board.
I named the variables as descriptively as possible.
Both for code readability,
and to keep them handy in my brain.
I can find the row and column thing
to be confusing enough already.
So, the first "if" test is to determine
whether the whole board has been scanned.
If so, the board solution is displayed
with the show board routine.
And the recursive routine returns
to plot another queen position on that same row.
The remainder of the function scans columns and rows
above the current row.
It's the top part of the board, if you can visualize it.
If a row above holds a queen in the current column,
then the next column is checked.
A break statement right here
skips over the checking subsequent rows,
which isn't necessary.
The column check is the easiest part.
The tough part was figuring out
how to check for diagonal attacks.
So I plotted things out on graph paper.
Filling out several pages of my notebook
to divine how to back up and check for an attack.
I tracked all of the variables,
and eventually came up with this scheme.
The vertical distance from the current row
to the row being examined must equal
the horizontal offset left and right
to any potential queen position.
These two lines caused me massive brain cramps.
It was a whole row-column thing,
which I got wrong many times.
Vertical was okay.
The vertical variable I could easily figure out.
But whether to add or subtract from the column,
and the row, or the other way around,
it drove me nuts.
I confess, this solution was derived
purely by experimentation.
And not any overall genius of logic.
When a square has been determined not to be under attack,
then the queen is set.
This can only happen for the current row
which is tested right here.
So, the queen is set,
and the next row down is examined recursively.
That way, when the recursion pops off a row,
the code returns to this spot
and keeps examining the current row
for additional queen placements.
While the end result worked,
I was unhappy because I had to experiment
to find the solution.
My goal was to achieve the solution in another way.
One that I could try without experimentation.
And I will show you that solution in the next movie.