[chbot] Choc fish challenege 3

[hamster]

It calculates each solution...

I was thinking as I lay in the bath last night, and this is what came to
me... (wreaking a perfectly good bath, I might add)

Step 1. Build masks of if a queen is placed at (x), what moves are no
longer valid on the board

    0    1   ... 4 (if N = 5)
  -xxxx  x-xxx
  xx---  xxx--
  x-x--  -x-x-
  x--x-  -x--x
  x---x  -x---

Step 2.
  procedure queens(depth)
  begin  
    if(depth - n-1)
    begin
       solutions++;
       return;
    end
    
    look at board(depth-1), row depth

    for each bit in that row that is not 'x'
    begin
       board(depth) = board(depth-1) ANDed mask(i), offset by depth rows.
       qeeens(depth+1);
    end 
  end

  For i = 0 to n-1
    copy mask(i) to board(0);
    queens(1)
  next i
  output number of solutions

So here is the search for the first solution, n = 5.. '1' represents a
playable square, '-' isn't. 

Placing 0 at depth 0
Q----
--111
-1-11
-11-1
-111-

Placing 2 at depth 1
Q----
--Q--
----1
-1---
-1-1-

Placing 4 at depth 2
Q----
--Q--
----Q
-1---
-1-1-

Placing 1 at depth 3
Q----
--Q--
----Q
-Q---
---1-

Placing 3 at depth 4
Q----
--Q--
----Q
-Q---
---1-

Solution 1
Q----
--Q--
----Q
-Q---
---Q-

There is an optimisation in this that drops the time by a significant
amount (0m59, n = 16), n=17 takes 6m32, so maybe  I could get n=18 in under
an hour.

Mike 




On Thu, 01 Sep 2011 08:37:16 +1200, Andre Renaud <andre at bluewatersys.com>
wrote:
> Hi Mike,
> 
> Just a quick question on this - is your program calculating the actual
> solutions, or just the count? I saw on the internet that there was an
> algorithm to tell you the number of solutions available, without
> actually working out what the solutions were.
> 
> Andre
> 
> On 31/08/11 22:07, hamster wrote:
>> Hi Andre,
>> 
>> I can verify that and add a couple more...
>> 
>> [hamster at linuxdev q3]$ time ./q 14
>> 365596 solutions found at 14
>> 
>> real	0m2.096s
>> user	0m2.069s
>> sys	0m0.006s
>> [hamster at linuxdev q3]$ time ./q 15
>> 2279184 solutions found at 15
>> 
>> real	0m13.189s
>> user	0m13.133s
>> sys	0m0.009s
>> [hamster at linuxdev q3]$ time ./q 16
>> 14772512 solutions found at 16
>> 
>> real	1m30.293s
>> user	1m30.002s
>> sys	0m0.042s
> 
> _______________________________________________
> Chchrobotics mailing list Chchrobotics at lists.linuxnut.co.nz
> http://lists.ourshack.com/mailman/listinfo/chchrobotics
> Mail Archives: http://lists.ourshack.com/pipermail/chchrobotics/
> Web site: http://kiwibots.org
> Meetings 3rd Monday each month at Tait Radio Communications, 175
Roydvale
> Ave, 6.30pm
> 
> When replying, please edit your Subject line to reflect new content.