Moore neighbourhood problem

[mhw]

If anyone doesn't know what the Moore neighbourhood is: it's the eight squares surrounding any square of a square grid.

I admit it, I'm feeling lazy. I could do it myself, with a bit of head-scratching, no doubt. But it's a nice little problem, particularly if you're au fait with a programming language that supports automatic backtracking, such as

Comments

[bethanthepurple]

That looks cool. I want to understand it.

But I totally don't.

[mhw]

OK, here it is with a little more expansion...

Imagine you have a chess board, a white queen, eight white pawns and eight black pawns.

Put the white queen on one of the squares in the middle of the chessboard (we don't actually need the queen as such, but she makes a convenient marker for the square that we've chosen).

There are eight squares that are adjacent to the queen, right? one at the top, one at the bottom, one on the left, one on the right, and the four corner squares. Those eight squares are called the Moore neighbourhood of the square with the queen on

[bethanthepurple]

Ah. I thought it might mean something like that, but I was confused by the infinite grid in my imagination.

Guess what I'm doing tomorrow with my Gifted & Talented year 5 maths group! I was bored of practicing calculator skills anyway.

(only need to work out for 3 & 4 and double it, right?)

[mhw]

I hope they enjoy tackling the problem!

Yes, the solutions for the cases w = n and w = 8-n, where w is the number of white pawns in an arrangement, are identical under interchange of white and black pawns, so you only really need to work out w = 0 through w = 4.

The thing that makes this problem worthwhile as a programming puzzle is that although it's perfectly possible to find all the solutions by trial and error, it's much nicer if you can discover a neat way of finding them.

If it turns out that your group likes this puzzle, you might like to try out the eight queens puzzle - I had a lot of fun with that, and variants of it, when I was about your maths group's age.

[drdoug]

Off the top of my head and quickly, didn't Wolfram do this in A New Kind Of Science?

(Sorry, terrible not-a-reference.)

[mhw]

He may well have done, but I confess to never having had much fun with ANKOS - it's far too thick and not well-enough indexed for me to be able to find what I want in it, and his writing style is, to put it mildly, unforgivingly terse.

I may get it out of the library again and try one more time :)

[xlerb]

I went and wrote a little program to do this (of which the printing looks like about half), but perhaps I'll hold off on posting it for a bit if others are trying. Gurer ner fhccbfrq gb or svsglbar bs gurz, evtug?

[mhw]

Thanks for holding off for a while - I'm particularly interested to see if Bethan's maths group have any fun with it first.

As to your question:

Vs lbh'ir sbhaq svsglbar, V'z zvffvat n srj, naq rvgure lbhe ernfbavat be zvar vf fperjl: fvapr rirel fgngr unf n qhny fgngr ol rkpunatvat juvgr cvrprf sbe oynpx naq ivpr irefn, V ernfba gung gurer zhfg or na rira ahzore bs qvfgvapg fgngrf :)

V'ir bayl hfrq crapvy-naq-cncre ybtvp sbe zl pnyphyngvbaf fb sne, ohg V'ir sbhaq bar qvfgvapg fgngr jvgu ab juvgr cvrprf (gevivny); gjb jvgu bar juvgr; fvk jvgu gjb juvgr; rvtug jvgu guerr juvgr; naq gjryir jvgu sbhe juvgr. Ol gur vagrepunatr vqrn tvira nobir, gurer zhfg nyfb or rvtug jvgu svir juvgr; fvk jvgu fvk juvgr; gjb jvgu frira juvgr; naq bar jvgu rvtug juvgr. Vs gur Fcvevg bs Nevguzrgvp unfa'g qrfregrq zr ragveryl, gung tvirf n gbgny bs sbheglfvk fgngrf.

V jbaqre sebz jurer lbhe rkgen svir unir zngrevnyvfrq?

[xlerb]

Keep in mind that swapping colors might not give you a different arrangement. But there are *two* of those that I can think of / see in the printout, so hm. I'll stare at things a bit more, I think.

[mhw]

Indeed, there are two four-white configurations that map to themselves under colour interchange:

www
bQw
bbb

and

wwb
bQb
bww

I've accounted for those in the numbers that I gave you.

[mattp]

This is a fun problem of the kind that I've been working on over the past few months with puzzles taken from projecteuler.net

I'll have a stab at it this weekend. Do you know the answer?

[mhw]

I think I know the answer. xlerb thinks he knows the answer.

Unfortunately, our answers are currently not in agreement, so it'll be fun to see what you come up with :)

[emperor]

Clearly, you should do this in postscript ;-)

[mhw]

Alas, PostScript is Not My Favourite Programming Language.

I once wrote a PostScript program that calculated the Ackermann function; unfortunately at that time the only PostScript interpreter that I had access to was the one built into the departmental laser printer. Tying up the printer like that wasn't much appreciated when someone had a pressing need to print their thesis :)

Yes, I suppose it could be done in PostScript, but it's much easier to implement a backtracking solver in Icon or Prolog (Icon would be my language of choice). Of course, if it's possible to find a nice representation of the problem, there may be no need for that kind of brute-force approach. Whether such a nice representation actually exists is another problem...