Re: My C++ exercise for today (2017-03-30)

[Tim Rentsch]

r...@zedat.fu-berlin.de (Stefan Ram) writes:

> I was reading an article by N. Wirth about "Program
> Development by Stepwise Refinement" from 1971.
>
> It is discussing the Eight Queens Problem and says:
>
> >>The reader is strongly urged to try to find a
> solution by himself before embarking on the paper<<.
>
> Argh! So, now, I couldn't read on, but had to solve
> the silly Eight Queens Problem myself first!
>
> I read it mentioned so very often, but never actually
> programmed a solution myself IIRC. So here it is in C++:
>
> [... approximately 120 lines of C++ ...]

I'm at a loss for words. I hope you don't give this as an
example to students.

> I have not yet compared the output with solutions from the
> literature, so I don't know whether it's correct.
>
> Problem: The function >>conflict_with_other_position(int,int)<<
> is way too long, but I was not yet able to find a elegant
> decomposition into several smaller function with less than
> three parameters each.

This function is clumsy because the abstraction you have chosen
isn't very good. Instead try keeping track of a bitmap of what
squares are covered already (and so putting a queen on any such
square is not allowed). Also, if you always try every possible
position at each level of search, there will be an enormous
number of duplicate solutions (a factor of 8 factorial, IIANM).
One easy way around that problem is to put the k'th queen in
the k'th row, since any solution must have one queen in each row.

[Robert Wessel]

A better approach is to simply keep track of free rows, columns and
diagonals (both). One of the [rows,columns] gets handled by the
obvious loop (you don't try placing two queens on one of those). For
simplicity I'll assume columns. The others just need a bitmap for
each row or diagonal. There are 8* rows, and 15* (#rows*2-1)
diagonals in each of two directions.

Assume the columns are numbered 0-7, right-to-left, the rows 0-7,
top-to-bottom, and the diagonals (D1 and D2) are numbered 0-14,
top-to-bottom (D1 represents to upper-left to lower-right diagonals,
D2 the lower-left to upper-right). Assume you're working in column C,
and are attempting to place in queen in row R. You can just check the
row bitmap to check for a conflict on a row. You can trivially
compute the two diagonals the prospective queen is on (D1=(7-C)+R and
D2=C+R), and then just those two bits in each bitmap to check for
conflicts on the diagonals.

If you find a possible location, mark the appropriate row and (both)
diagonal bits, and move on to the next column. As you backtrack,
unmark the R/D1/D2 bits. Total storage is linear in the size of a
side of the board.

So you end up with something like:


Column[0..7] =0
Rbitmap[0..7]=0
D1bitmap[0..14]=0
D2bitmap[0..14]=0

main()
PlaceNextColumn(0)

PlaceNextColumn(C)
for(R=0..7)
Column[C]=R
Try(R,C)

Try(R,C)
D1=(7-C)+R
D2=C+R
if (Rbitmap[R]) return //conflict
if (D1bitmap[D1]) return //conflict
if (D2bitmap[D2]) return //conflict
// (no conflict)
Rbitmap[R]=1
D1bitmap[D1]=1
D2bitmap[D2]=1
if(C==7)
OutputSolution()
else
PlaceNextColumn(C+1)
Rbitmap[R]=0
D1bitmap[D1]=0
D2bitmap[D2]=0

OutputSolution()
printf("\nSolution: ")
for(C=0..7)
printf("Queen in column %i, on row %i ", C, Column[C])



*Assuming a standard chessboard - the approach generalizes to other
sizes, and rectangular boards

[Tim Rentsch]

Robert Wessel <robert...@yahoo.com> writes:

> On Sun, 16 Apr 2017 13:36:02 -0700, Tim Rentsch
> <t...@alumni.caltech.edu> wrote:
>

>>> [how to solve the 8 queens problem]
>>
>> [...] try keeping track of a bitmap of what

>> squares are covered already (and so putting a queen on any such
>> square is not allowed). Also, if you always try every possible
>> position at each level of search, there will be an enormous
>> number of duplicate solutions (a factor of 8 factorial, IIANM).
>> One easy way around that problem is to put the k'th queen in
>> the k'th row, since any solution must have one queen in each row.
>
> A better approach is to simply keep track of free rows, columns and

> diagonals (both). [..elaboration..]

Good idea. For larger board sizes I expect this approach scales
better than my suggestion. For boards of modest size using
bitmaps seems easier and probably also faster. Regular 8x8
boards, for example, fit nicely in a single unsigned long long.
Then checking to see if a square is covered (the more common
operation) is just an &, and placing a piece can be done with an
indexed lookup and an |. Also, because the covering state is
held in a small unit, updates can be done by value (passing the
board state down a recursive call) so no "undoing" is needed.
This scheme should scale reasonably up to two or four words, with
four words being enough for a 16x16 board.