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

[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.

What my problem asks you to do is to use the white pawns and the black pawns to completely surround the queen, one pawn on each square of the Moore neighbourhood, and to find how many different ways there are that you can do it.

Here's the only way that you can use all the black pawns:

bbb
bQb
bbb

If you don't count rotations and reflections (you do know about those?), there are only two distinct ways to use one white pawn and seven black ones:

wbb
bQb
bbb

and

bwb
bQb
bbb

The white pawn can be only either at a corner square of the region or in the middle square of a side. If we weren't disregarding reflections and rotations, there'd be eight ways instead (four corner-square arrangements and four side-square arrangements), but it makes sense to disregard the rotated and reflected versions, because in a way they're not interestingly different from the two examples I have shown above.

And the rest of the problem is to find the rest of the arrangements! :)

All clear now?

[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.