[chbot] Choc fish challenege 3

[Synco Reynders]

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).
Now, I've got another challenge, yet will post as new thread.
/s

On 1 September 2011 09:13, hamster <hamster at snap.net.nz> wrote:

> 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.
>
> _______________________________________________
> 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.
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://lists.ourshack.com/pipermail/chchrobotics/attachments/20110901/27f0ba4d/attachment.htm