How Many Shapes On A Chessboard

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

My friend's cousin (a math professor) posed this problem: How many shapes can be made using the squares of a chessboard? This is like the problems of how many squares can be constructed on a chessboard, but it includes any closed shape regardless of the number of sides. The shape's area consists of the selected squares.

The professor said that he didn't know the answer to this puzzle, and was unaware of any elegant (mathematical) solution. Does anyone know of a solution to this problem, short of constructing every possibility on a supercomputer, storing them all, and comparing them for replicated shapes?

DarkerLine · Posted: 03 Jan 2008 01:27:24 pm Post subject:

Does the shape have to be connected? If not, the answer is 2^64 - for each square, you have the option of including it in the shape or not.

JoostinOnline · Active Member Joined: 22 Aug 2007 Posts: 559

He said they have to be an enclosed shape.

DarkerLine · Posted: 03 Jan 2008 01:35:58 pm Post subject:

Right. Sorry. That does make the problem a bit harder.

Are holes allowed? And are two squares that share a corner connected?

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

I'm not sure about holes; I can ask my friend if he knows tomorrow in school. As for corners, I'm pretty sure they aren't considered connected.

Do you know if this is a puzzle that might have been attempted before? A lesser-known but still classic puzzle? Or did my friend's cousin just make it up with no solving method in mind?

DarkerLine · Posted: 03 Jan 2008 02:58:45 pm Post subject:

It's probably been posed before, though I haven't found anything about it so far. For reference, such connected shapes are called "polyominoes" (as a generalization of "dominoes").

Recursive Acronym · Advanced Member Joined: 11 Dec 2006 Posts: 499

DarkerLine · Posted: 03 Jan 2008 05:40:05 pm Post subject:

Recursive Acronym · Advanced Member Joined: 11 Dec 2006 Posts: 499

That could be true. magicdanw, could you give us more information?

DarkerLine · Posted: 03 Jan 2008 06:41:50 pm Post subject:

A side note: I really need a whiteboard. I've probably killed half a tree working on this problem so far.

elfprince13 · Posted: 03 Jan 2008 07:21:48 pm Post subject:

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

I don't understand your concerns about color. Color of shapes is irrelevant. You just need to try making a single shape on the chessboard, and see how many single shapes can be made on the chessboard, not at the same time. I'll try to find out more specifics from my friend tomorrow at school, but he may not know them either.

elfprince13 · Posted: 03 Jan 2008 09:42:12 pm Post subject:

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

I think you've got it. Like, if I gave you infinite chessboards, and on each one you could color in adjacent squares to form a solid shape on the board, how many boards could you color until you run out of unique shapes. And I'm assuming that rotations and reflections count as different shapes.

DarkerLine · Posted: 03 Jan 2008 10:55:50 pm Post subject:

What about translations?

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

You mean the same shape shifted across the board? Also different, because they use different squares. It's not about cutting a unique shape out of the board, but it is about identifying shapes found on the board.

Weregoose · Posted: 04 Jan 2008 04:23:16 am Post subject:

What if one repeatedly "splatters" a chessboard with this color, records whether or not there is an island made up of it, continues on until there is a decent enough approximation of the odds of this happening, and then multiplies those odds by the possible number of colorings? Analogously, create a random binary array and see if each "one" is mimicked by any elements located at a distance of ±1 or ±√length(array) indices from it; if not, then it represents an island. Find out the numbers for general board sizes and then pray that Sloane's Encyclopedia has already listed them—it's not mathematically beautiful, but it's a way to find out.

simonzack · Advanced Newbie Joined: 25 Dec 2007 Posts: 71

This can be simplified to (the 'with holes' situation):
with a[8] ( a cloumn), find all b[8] that with each b column joins to an a column, and start working here. I'll try this now...

magicdanw · **pcGuru()** Calc Guru Joined: 14 Feb 2007 Posts: 1110

simonzack: I'm afraid I don't understand what you're talking about here...Could you explain?

Weregoose: Also, I'm not fully understanding your suggestion. What I got out of it is that you're saying I should randomly select squares on a board, check if it forms a closed shape (I found out that holes can exist in the shape), and compare those to the total number of possible combinations. I don't really see how this would work...

JoostinOnline · Active Member Joined: 22 Aug 2007 Posts: 559

I am sorry if you already said this, but I can't find it. Do the dimensions of the shape matter (i.e. are a 1x1 square and a 2x2 square count as different shapes?)?