Trying to solve N-Queensby jeffa (Chancellor)
|on Sep 08, 2002 at 21:18 UTC||Need Help??|
jeffa has asked for the
wisdom of the Perl Monks concerning the following question:
Howdy friends. First off, this is a homework question. I have been tasked with chore of solving the N Queens Problem. I feel like i am this close, but yet i just can't wrap my head around solving my problem. What follows is an explanation of my idea, followed by the broken code.
My idea is start with a 2-D array that contains all 1's.
Then, i start at (0,0) and mark off that row and the diagonals that the Queen can traval as zero:
Since i was able to place a Queen at (0,0), i store that row in a temporary array of possible solutions:
Next, i look at the next column and try to find an available row, which would be the third. Again, mark off that row and it's diagonals:
So now i have two queens (0,2). Move to the next column and try to find an available row. Since none are available, i remove the second Queen from my tempory array and return from the recursive sub. Upon return, i find that there are no more rows left, so i should remove the first Queen from the temporary array and return again.
Here is my broken code. Any help will be greatly appreciated, and if you feel that you would rather just give me hints than outright solve my problem i really understand. This is homework after all .... but do keep in mind that the final product will be C code that uses the pthread library so even if i get this Perl prototype to work, i still have another harder road to travel. :/ Thanks again! :)UPDATE:
Well, 2 hours later i almost have a solution ... i have elected to remove the original code (you can see it at http://perlmonks.thepen.com/196095_orig.html ). This is soooo close to working ... it outputs the correct number of solutions (and is horribly slow at that), but the solutions are ... not quite right. Here is the updated, not so broken code:
And here is sample output for a 5x5 board:
$ ./queens.pl 5 1 3 5 2 4 4 2 5 3 2 4 1 3 5 5 3 1 4 3 1 4 2 5 5 2 4 1 4 1 3 5 2 2 5 3 1 5 2 4 1 3 3 1 4 2 10 solutions foundGuessing at what is wrong, i would say that i am unecessarily popping @TEMP on line 45.
Originally, i stated that i could not understand why my 2-D board array was being modified when i was passing a copy of it to the next recursive call. The reason was because i was only copying the first dimension:
instead of performing a deep copy:
Almost there :) ... and i do appreciate dws's idea ... if i have enough time i will try a solution like that instead, as this one is not very fast by itself.
L-LL-L--L-LL-L--L-LL-L-- -R--R-RR-R--R-RR-R--R-RR B--B--B--B--B--B--B--B-- H---H---H---H---H---H--- (the triplet paradiddle with high-hat)