## Checkboard Trilogy #3

And now, the final question in Bobo The Bear’s Checkboard Trilogy:

**How many ways are there to arrange 4 checkers on the spaces of a standard 8×8 checkerboard so that they form the corners of a square (This includes squares that are “tilted” with respect to the edges of the board)?**

*Answers can be submitted below; will reveal sometime next week*

suineg| PUZZLE MASTER | Profile June 17th, 2010 - 11:08 amThis version of the puzzle is very very cool!!!! but very very hard also…

Here is my shot at it:

With 4 checekers you have the 204 aligned squares minus the individual squares (64)

—> 140

I found the “tilted” squares folowing this weird pattern:

1X1=0 (can get 4 checkers in it)

2X2=0 –> number of tilted squares in 1X1 + square(0)= 0

3X3=1 –> number of tilted squares in 2X2 + square (1)= 0 + 1= 1

4X4=5 –> number of tilted squares in 3X3 + square (2) = 1 + 4= 5

5X5=14–> number of tilted squares in 4X4 + square (3)= 5 + 9= 14

6X6=30–> ……………………. in 5X5 + square(4)= 14 + 16 = 30

and so on………..

its like you lose 2 dimensions….. so the formula for an 8X8 square will be:

square(1)+square(2)+square(3) +square(4)+square(5)+square(6)=1+4+9+16+25+36 = 91 tilted squares

so the total number position of checkers without importance in the order between checkers, like checkers 1,2,3,4… because they are identical is 231, I think, cool!!!….

munna| Profile June 21st, 2010 - 3:33 amAnswer = 336.

With some hit and trial, I got following formula to calculate the number of ways to arrange 4 checkers:

Number of ways = [ N * N * { ( N * N ) - 1 } ] / 12, where N = number of rows in a checker board (it is assumed to be a square board).

Putting N = 8, we get number of ways = [ 8 * 8 * { ( 8 * 8 ) - 1 } ] / 12

= [ 64 * { 64 - 1 } ] / 12

= [ 64 * 63 ] / 12

= 4032 / 12

= 336

Bobo The Bear| PUZZLE MASTER | Profile June 25th, 2010 - 4:40 pmEither this one was more difficult than I anticipated, or that many of you were “checkerboarded out” by the end.

I, too, came up with 336 arrangements for an 8×8 checkerboard, and I agree with the formula that munna posted for the general NxN board (My hat goes off to you – well done). Here’s how I came up with my results:

Each square, tilted or not, can be considered “bounded” by a regular, untilted square. For example, the arrangement in the diagram is bounded by the 6×6 square in the upper left hand corner of the board. Each regular square (larger than 1×1) bounds itself, and possibly other tilted squares.

There are 49 different 2×2 squares, and each one bounds exactly 1 square (itself).

There are 36 different 3×3 squares, and each one bounds exactly 2 squares (itself, and one tilted at 45 degrees).

There are 25 different 4×4 squares, and each one bounds exactly 3 squares (itself and two different tilted squares).

In general, the number of QxQ squares is (9-Q)^2 (or (N+1-Q)^2 in the general case). Each QxQ square bounds itself and exactly Q-2 tilted squares. The tilted squares correspond one-to-one with the unit squares in the top row of the QxQ square, excluding the corner squares.

Putting this to work for an 8×8 checkerboard, we have:

(7^2)*1 + (6^2)*2 + (5^2)*3 + (4^2)*4 + (3^2)*5 + (2^2)*6 + (1^2)*7 = 336.

For a general NxN, it’s

sum(i*(N-i)^2) for i=1 to N-1

And I confirmed that the formula (N^2 * (N^2)-1)/12 does calculate this sum correctly.

Thanks to everyone who participated and, hopefully, enjoyed the series.

suineg| PUZZLE MASTER | Profile June 28th, 2010 - 11:40 amI saw my mistake, man I never complete accurately what I do, thats a problem, a hat to both of you who found it in a formula man, incredibly, my approach was more visual and I failed to pass it to a decent mathematical version however I found my error:

My approach is a lot different to yours, however it yields the same solution:

Taking from my last explanation:

Normal Squares that can fit 4 checkers: 140… that was easy.

Tilted Squares :

the error in my explanation was that I did not acummulate the tilted squares that were different, I was counting the different tilted squares in each dimension so it was accumulative, man sooooo dumb … wow …

so: 1X1=0, 2X2=0, 3X3=1, 4X4= 5, 5X5= tilted squares in 4X4 + square(3)=14

6X6= tilted squares in 5X5 + square(4)=30, 7X7= tilted squares in 6X6 + square(5)= 55

8X8= tilted squares in 7X7 + square(6)= 91

now all tilted squares in the 8X8 are: 0+0+1+5+14+30+55+91= 196 tilted squares

TOTAL SQUARES: 140 + 196= 336

Now I would have post it again if I was not complety sure that this method was completely different to the one used, with that being said…

@BobotheBear: please give your feedback to my solution, do you found it valid or faulty, in less words do I have your blessing in my solution… cool man.. very nice puzzle by the way.

munna| Profile June 29th, 2010 - 12:19 amThis was a very nice series and I am glad to be a part of this Checkboard Trilogy. I frequently look for puzzles in this website and I have noticed that puzzles from Bobo The Bear are really hard to solve (especially The Involuting Goat).

My approach was little different. What I did was to find out all possible (and unique) ways to place first two points (A & B) of a square ABCD on the board, so that the square ABCD remains within the 8 * 8 Checkerboard.

Following this approach I found that there are:

7 + 6 + 5 + 4 + 3 + 2 + 1 = 28 squares when both points A & B are in row 1

6 + 5 + 4 + 3 + 2 + 1 = 21 squares when point A is in row 2 and point B is in row 1

6 + 6 + 5 + 4 + 3 + 2 + 1 = 27 squares when both points A & B are in row 2

5 + 4 + 3 + 2 + 1 = 15 squares when point A is in row 3 and point B is in row 1

5 + 5 + 4 + 3 + 2 + 1 = 20 squares when point A is in row 3 and point B is in row 2

5 + 5 + 5 + 4 + 3 + 2 + 1 = 25 squares when both points A & B are in row 3

and so on…

I found a patter in this series for general N x N board. Solving the patter I found that the total number of ways to arrange 4 checkers is:

Sum of [(N – i) * N * i] / 2 for i = 1 to N – 1

Solving above summation, I found the following formula that I posted in my first post:

Number of ways = [N^2 * (N^2 – 1)] / 12

Taking this a little further, I found a general formula for a rectangular Checker board:

Number of ways = [C * (2R – C) * (C^2 – 1)] / 12 provided R >= C

Here R = Number of rows; and C = Number of columns

Putting R = C = N, you will get general formula for square N x N board mentioned above.

I hope I was able to explain my approach. This was a great series, I enjoyed it and look forward for more.

munna| Profile June 29th, 2010 - 6:28 amThe Involuting Goat puzzle was posted by Bilbao. Please ignore the part in my last post where I mentioned Bobo The Bear instead of Bilbao.

Bobo The Bear| PUZZLE MASTER | Profile June 29th, 2010 - 5:39 pm@suineg and @munna: It’s great to see multiple valid approaches that all converge to provide the same resolution to a problem. I think you both did a great job in seeing and solving the problem in your individual ways. And thank you both for your words of encouragement – it’s always good to hear when one’s contributions are sincerely appreciated. Thank you!

Bobo The Bear| PUZZLE MASTER | Profile June 29th, 2010 - 5:43 pmI noticed that I erred in my order of operations when I (incorrectly) presented Munna’s formula as (N^2 * (N^2)-1)/12. He’s correct that it should be [N^2 * (N^2 – 1)]/12 instead. And very well done with extending the soluiton to rectangular boards as well. Wow!