WP-34S N-Queens Benchmark Based on Patrice Torchet's BITMAP Solution

[Claudio L.]

(10-23-2014 10:11 PM)Claudio L. Wrote:  These results are on a 50g at normal speed:

1) Original code = 90 seconds
2) Stack code = 60.6 seconds
3) Original w/no indirection = 67.6 seconds
4) Stack code w/no indirection = 57.7 seconds
5) Bitmap code = 54.3 seconds

Add to that:
6) New in-stack recursive algorithm = < 30 seconds

Still working on cleaning up the sources for publication. I messed up and inadvertently overwrote a subroutine of my bitmap solution (was trying to improve it and STOred in the wrong name), so I have to see if I can write it back from scratch now.
But then I thought of starting an algorithm from scratch that uses the stack. The new algorithm uses the fact that queens can't share the same column, so it removes it from the possible locations of the next queens, being significantly faster than the bitmap solution.

The idea is: for the first queen, you have 8 possible locations (1 thru 8), which are numbers left in the stack. The first queen takes a number, leaving the other 7 positions in the stack, and recursively calls for the next queen to do the same. Of course, each queen takes a number from the list and verifies that doesn't conflict with any diagonals of previous queens (only the diagonals need to be checked since the column is guaranteed not to be occupied by another queen). If there's no conflict with the diagonals, recurses into the next queen, passing the remainder positions in the stack. If there is a conflict, it returns that position to the list (to the top) and pulls the next one.
For example, the second queen receives 1 2 3 4 5 6 7 (after the first queen takes the 8). Pulls a 7, checks that it's in the diagonal of the previous queen (in the 8), so it returns the 7 to the top of the list, leaving now 7 1 2 3 4 5 6, and now pulls the 6 and does the same. This list of available positions keeps "rotating" in the stack. If none of the N positions is good, then it returns failure to the previous queen. The previous queen will then rotate her own list and proceed to the next position.
For this to work, each queen needs to make her own duplicate of the list, which is kept also in the stack. So when you reach the last queen, the stack contains:
8 positions (1st queen) + 7 positions (2nd) + 6 positions (3rd) + 5 + 4 + 3 + 2 + 1 =36 numbers in the stack, plus the 8 selected positions of the queens = 44 stack levels needed (actually, 45 if you need to measure the speed, I leave the TICKS there too).
As is evident, the algorithm makes good use (and requires) the infinite stack from the 48/49/50 series (even the 28 should work).

Why so fast? Because even in the bitmap solution, each queen scans through the 8 positions, checking for a conflict in the bitmap. In this case, the last queen only has one possible position (all others were taken from the list) for which only has to check the diagonals. The second last only checks 2 possible positions, etc. This saves significant time.

I have to clean it up as well, but this one clocked at 29.8 seconds, a third of the original algorithm on the list, and half the time vs. the same algorithm using the stack.
Of course, this is not the same algorithm, so it's not directly comparable and cannot go in the list (although it follows the same solution path and explores the same nodes, producing the exact same solution). It's just to see how far we can go with this.

Claudio