Author |
Topic: Chessboard Conundrum (Read 2334 times) |
|
chetangarg
Newbie
Gender: 
Posts: 30
|
 |
Chessboard Conundrum
« on: May 5th, 2011, 12:17am » |
 Quote  Modify
|
What will be the total no. of ways to rearrange black and white squares on a chess board such that each row and each column has exactly Four white and Four black squares 
|
|
 IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Chessboard Conundrum
« Reply #1 on: May 5th, 2011, 12:27am » |
Quote Modify
|
I think I would need a computer program to answer this question.
I bet towr is already busy writing it  .
|
|
IP Logged |
|
|
|
towr
wu::riddles Moderator
Uberpuzzler
Some people are average, some are just mean.
Gender:
Posts: 13730
|
|
Re: Chessboard Conundrum
« Reply #2 on: May 5th, 2011, 8:45am » |
Quote Modify
|
on May 5th, 2011, 12:27am, Grimbal wrote:| I bet towr is already busy writing it . |
|
Not yet, I hadn't even seen it until moments ago. And attempting brute force would be a bit much for my computer.
|
|
IP Logged |
Wikipedia, Google, Mathworld, Integer sequence DB
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Chessboard Conundrum
« Reply #3 on: May 5th, 2011, 9:15am » |
Quote Modify
|
Anyway, here is my first unverified result: 116963796250.
PS: and it is verified. A simple search of my result took me to http://oeis.org/A058527.
|
| « Last Edit: May 5th, 2011, 9:22am by Grimbal » |
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Chessboard Conundrum
« Reply #4 on: May 5th, 2011, 1:11pm » |
Quote Modify
|
One might expect the number to be a function of n, but f(3) = 297200 = 743*400, and 743 is prime. 
|
|
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Chessboard Conundrum
« Reply #5 on: May 5th, 2011, 1:53pm » |
Quote Modify
|
on May 5th, 2011, 1:11pm, ThudnBlunder wrote:| One might expect the number to be a function of n, but f(3) = 297200 = 743*400, and 743 is prime. |
|
Why should a simple function of n need to be free of large prime factors? A function as simple as n!-1 quickly leads to terms with large prime factors.
Anyway, the function for these arrangements probably has to count different types of symmetries (and their combinations) seperately. There are not only rotational and reflective symmetries, but also interchanging black and white.
See for example these remarks and counts about different chess board symmetries for a similar type of counting question.
|
|
IP Logged |
|
|
|
ThudnBlunder
wu::riddles Moderator
Uberpuzzler
The dewdrop slides into the shining Sea
Gender:
Posts: 4489
|
|
Re: Chessboard Conundrum
« Reply #6 on: May 5th, 2011, 2:02pm » |
Quote Modify
|
on May 5th, 2011, 1:53pm, JohanC wrote:
Why should a simple function of n need to be free of large prime factors? A function as simple as n!-1 quickly leads to terms with large prime factors.
|
|
Yes, of course.  Sometimes I shoot from the lip. 
|
| « Last Edit: May 5th, 2011, 2:09pm by ThudnBlunder » |
IP Logged |
THE MEEK SHALL INHERIT THE EARTH.....................................................................er, if that's all right with the rest of you.
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Chessboard Conundrum
« Reply #7 on: May 5th, 2011, 2:04pm » |
Quote Modify
|
on May 5th, 2011, 9:15am, Grimbal wrote:Anyway, here is my first unverified result: 116963796250.
PS: and it is verified. A simple search of my result took me to http://oeis.org/A058527.
|
|
The solution not being a small number seems to indicate that quite some grouping is involved. Did you program this in something like c++, or something more exotic?
I already figured out that the 70 (8!/(4!*4!)) posibilities of the first line are a simple multiplication factor. And for each posibility of the second line, you can group depeding on whether you have 4x2, 3x2+2x1, 2x2+4x1, 1x2+6x1 or 8x1.
And after that, it keeps on growing complexity..
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Chessboard Conundrum
« Reply #8 on: May 6th, 2011, 12:31am » |
Quote Modify
|
It is a simple Java program.
The idea is to count row by row how many ways there are to get each possible set of partial totals by column.
An optimization was to reorder the array of partial totals, to group equivalent combinations.
Sorting the totals across columns makes the set of cases equivalent to what you suggest, i.e. group according to how many of each partial column total you have.
|
| « Last Edit: May 6th, 2011, 1:08am by Grimbal » |
IP Logged |
|
|
|
JohanC
Senior Riddler
Posts: 460
|
|
Re: Chessboard Conundrum
« Reply #9 on: May 6th, 2011, 2:33am » |
Quote Modify
|
on May 6th, 2011, 12:31am, Grimbal wrote:It is a simple Java program.
...
Sorting the totals across columns makes the set of cases equivalent to what you suggest, i.e. group according to how many of each partial column total you have. |
|
Interesting. Do you think the same approach is enough to calculate the immense numbers in OEIS? Someone claims to have calculated a 222 digit number for a 30x30 board. (Probably replacing Java with something more machine language friendly, and maybe using some distribution over a network. But even then is seems they must have used some additional insights.
|
|
IP Logged |
|
|
|
Grimbal
wu::riddles Moderator
Uberpuzzler
Gender:
Posts: 7527
|
|
Re: Chessboard Conundrum
« Reply #10 on: May 6th, 2011, 6:59am » |
Quote Modify
|
I don't know the complexity.
The max number of cases in the 2nx2n case would be halfway through. That is the number of ways to fill an array of n+1 integers (0..n) in such a way that that sum(i·Ai) = n2. Or something like that. That looks close to exponential to me.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print