Thanks for the explanation Mike... I would otherwise have thought you'd cheated :-). Now that's a well deserved choc fish (unless someone else can beat it).<div>Now, I've got another challenge, yet will post as new thread.</div>
<div>/s</div><div><br></div><div><div class="gmail_quote">On 1 September 2011 09:13, hamster <span dir="ltr"><<a href="mailto:hamster@snap.net.nz">hamster@snap.net.nz</a>></span> wrote:<br><blockquote class="gmail_quote" style="margin:0 0 0 .8ex;border-left:1px #ccc solid;padding-left:1ex;">
It calculates each solution...<br>
<br>
I was thinking as I lay in the bath last night, and this is what came to<br>
me... (wreaking a perfectly good bath, I might add)<br>
<br>
Step 1. Build masks of if a queen is placed at (x), what moves are no<br>
longer valid on the board<br>
<br>
0 1 ... 4 (if N = 5)<br>
-xxxx x-xxx<br>
xx--- xxx--<br>
x-x-- -x-x-<br>
x--x- -x--x<br>
x---x -x---<br>
<br>
Step 2.<br>
procedure queens(depth)<br>
begin<br>
if(depth - n-1)<br>
begin<br>
solutions++;<br>
return;<br>
end<br>
<br>
look at board(depth-1), row depth<br>
<br>
for each bit in that row that is not 'x'<br>
begin<br>
board(depth) = board(depth-1) ANDed mask(i), offset by depth rows.<br>
qeeens(depth+1);<br>
end<br>
end<br>
<br>
For i = 0 to n-1<br>
copy mask(i) to board(0);<br>
queens(1)<br>
next i<br>
output number of solutions<br>
<br>
So here is the search for the first solution, n = 5.. '1' represents a<br>
playable square, '-' isn't.<br>
<br>
Placing 0 at depth 0<br>
Q----<br>
--111<br>
-1-11<br>
-11-1<br>
-111-<br>
<br>
Placing 2 at depth 1<br>
Q----<br>
--Q--<br>
----1<br>
-1---<br>
-1-1-<br>
<br>
Placing 4 at depth 2<br>
Q----<br>
--Q--<br>
----Q<br>
-1---<br>
-1-1-<br>
<br>
Placing 1 at depth 3<br>
Q----<br>
--Q--<br>
----Q<br>
-Q---<br>
---1-<br>
<br>
Placing 3 at depth 4<br>
Q----<br>
--Q--<br>
----Q<br>
-Q---<br>
---1-<br>
<br>
Solution 1<br>
Q----<br>
--Q--<br>
----Q<br>
-Q---<br>
---Q-<br>
<br>
There is an optimisation in this that drops the time by a significant<br>
amount (0m59, n = 16), n=17 takes 6m32, so maybe I could get n=18 in under<br>
an hour.<br>
<br>
Mike<br>
<br>
<br>
<br>
<br>
On Thu, 01 Sep 2011 08:37:16 +1200, Andre Renaud <<a href="mailto:andre@bluewatersys.com">andre@bluewatersys.com</a>><br>
wrote:<br>
<div><div></div><div class="h5">> Hi Mike,<br>
><br>
> Just a quick question on this - is your program calculating the actual<br>
> solutions, or just the count? I saw on the internet that there was an<br>
> algorithm to tell you the number of solutions available, without<br>
> actually working out what the solutions were.<br>
><br>
> Andre<br>
><br>
> On 31/08/11 22:07, hamster wrote:<br>
>> Hi Andre,<br>
>><br>
>> I can verify that and add a couple more...<br>
>><br>
>> [hamster@linuxdev q3]$ time ./q 14<br>
>> 365596 solutions found at 14<br>
>><br>
>> real 0m2.096s<br>
>> user 0m2.069s<br>
>> sys 0m0.006s<br>
>> [hamster@linuxdev q3]$ time ./q 15<br>
>> 2279184 solutions found at 15<br>
>><br>
>> real 0m13.189s<br>
>> user 0m13.133s<br>
>> sys 0m0.009s<br>
>> [hamster@linuxdev q3]$ time ./q 16<br>
>> 14772512 solutions found at 16<br>
>><br>
>> real 1m30.293s<br>
>> user 1m30.002s<br>
>> sys 0m0.042s<br>
><br>
> _______________________________________________<br>
> Chchrobotics mailing list <a href="mailto:Chchrobotics@lists.linuxnut.co.nz">Chchrobotics@lists.linuxnut.co.nz</a><br>
> <a href="http://lists.ourshack.com/mailman/listinfo/chchrobotics" target="_blank">http://lists.ourshack.com/mailman/listinfo/chchrobotics</a><br>
> Mail Archives: <a href="http://lists.ourshack.com/pipermail/chchrobotics/" target="_blank">http://lists.ourshack.com/pipermail/chchrobotics/</a><br>
> Web site: <a href="http://kiwibots.org" target="_blank">http://kiwibots.org</a><br>
> Meetings 3rd Monday each month at Tait Radio Communications, 175<br>
Roydvale<br>
> Ave, 6.30pm<br>
><br>
> When replying, please edit your Subject line to reflect new content.<br>
<br>
_______________________________________________<br>
Chchrobotics mailing list <a href="mailto:Chchrobotics@lists.linuxnut.co.nz">Chchrobotics@lists.linuxnut.co.nz</a><br>
<a href="http://lists.ourshack.com/mailman/listinfo/chchrobotics" target="_blank">http://lists.ourshack.com/mailman/listinfo/chchrobotics</a><br>
Mail Archives: <a href="http://lists.ourshack.com/pipermail/chchrobotics/" target="_blank">http://lists.ourshack.com/pipermail/chchrobotics/</a><br>
Web site: <a href="http://kiwibots.org" target="_blank">http://kiwibots.org</a><br>
Meetings 3rd Monday each month at Tait Radio Communications, 175 Roydvale Ave, 6.30pm<br>
<br>
When replying, please edit your Subject line to reflect new content.<br>
</div></div></blockquote></div><br></div>