Go back
Chess Board Maths problem

Chess Board Maths problem

Posers and Puzzles

Vote Up
Vote Down

...If I had a chess board which was 100 x 100 and each square could be either black or white - how many combitions of boards are there?

Vote Up
Vote Down

Originally posted by Campaigner
...If I had a chess board which was 100 x 100 and each square could be either black or white - how many combitions of boards are there?
Sounds like 2^100* 100^2 which works out to 1.26 E34 possible square combitions, whatever that is🙂

Vote Up
Vote Down

Originally posted by sonhouse
Sounds like 2^100* 100^2 which works out to 1.26 E34 possible square combitions, whatever that is🙂
Why not 2^10000? 😲

Vote Up
Vote Down

It seems accurate but I need more information, if you have a look at:

http://www.fontico.com/hitler/ you'll see what I'm after though (2^100) * (100^2) seems really neat.

Vote Up
Vote Down

does this take into account boards that are rotations of each other?

Vote Up
Vote Down

...not sure what you mean, I just need the figure that an all black board would be if you started with an all white board and worked through every combination.

Vote Up
Vote Down

...or how about 10 x 10?

Vote Up
Vote Down

The number of boards, not taking out rotations and reflections, is 2^n, where n is the number of squares, it's analogous to counting in binary. So the number of 100*100 boards is 2^10000

Vote Up
Vote Down

Ah, thanks, sorry I know what you mean now by reflections and rotations. No that's great as long as I can give each one its own number (i.e. value - thats fine).
Now an each 'image' of each combination took up 1K of hard disk space, how much space would I need to store them all? - Is it physically possible in todays world or if it isn't will it one day be possible?

3 edits
Vote Up
Vote Down

Originally posted by Campaigner
Ah, thanks, sorry I know what you mean now by reflections and rotations. No that's great as long as I can give each one its own number (i.e. value - thats fine).
Now an each 'image' of each combination took up 1K of hard disk space, how much space would I need to store them all? - Is it physically possible in todays world or if it isn't will it one day be possible?
Any algorithm that takes 2^n time or space is pretty much unfeasible if n is not small.

For example, in your case, if each case only took 1 bit (not 1kB, not 1B), then the storage of all 2^10000 combinations of boards would take up 2.26 x 10^2997 TB of space on a computer.

*edit*
I don't know if you have any concept of how big that number is, but if you filled the OBSERVABLE UNIVERSE with 1TB HDDs, you would fit the equivalent of 0% of the required data necessary to store all of those boards.

*edit 2*
http://en.wikipedia.org/wiki/Observable_universe
(with by back-of-the-hand calculations, you can fit ~4.9 x 10^84 1TB HDDs in the observable universe.)

Vote Up
Vote Down

Okay we can't do that, but it would be still possible to store all the values between these extremeties i.e. 1 would be an all white board and 1^10000 would be an all black board. But I don't know how HDD space the number 1 with 10000 noughts takes up - I suppose I could work it out and then factorial that number.

Vote Up
Vote Down

Originally posted by Campaigner
Okay we can't do that, but it would be still possible to store all the values between these extremeties i.e. 1 would be an all white board and 1^10000 would be an all black board. But I don't know how HDD space the number 1 with 10000 noughts takes up - I suppose I could work it out and then factorial that number.
Is this for a class project of some sort? I've been presented these types of questions before as an example of problems that are unsolvable by computational or iterative methods.

I don't quite follow your last question here, but I would reiterate that the magnitude of the numbers we're talking about here are almost incomprehensible.

2 edits
Vote Up
Vote Down

Originally posted by Campaigner
Okay we can't do that, but it would be still possible to store all the values between these extremeties i.e. 1 would be an all white board and 1^10000 would be an all black board. But I don't know how HDD space the number 1 with 10000 noughts takes up - I suppose I could work it out and then factorial that number.
One way to think about it is that the addressable memory space by a binary computer is 2^n, where n is the number of bits in the operating system's addresses.

To describe the pattern of squares on one of your boards, in the most compressed form would require 10000 bits. We would still have 2^10000 of them to store. So it looks like we might need a "10000 bit" operating system to do it.

In 1985, Windows was "16 bit", in 1992 it was "32 bit" and in 2005 the first "64 bit" Windows was released. So it looks like the number of bits roughly doubles every seven years. Note that this progression can also be written as "2^4 bit" .. "2^5 bit" .. "2^6 bit"

"10000 bit" is about "2^14" bit (rounding up), so we need 8 more doublings before we can process this problem. Given the rate of doubling we calculated above, that will take about 8*7 = 56 years from 2005.

i.e. we might be able to deal with these chessboards in the year 2060.

1 edit
Vote Up
Vote Down

Why store all permutations, all at once, in a giant table?
Why not just produce one at a time? Doesn't take much time.

Give me the nomuber of any configuration (10 k bits) and I give you a graph how that looks like, just converting any zero to a white square, and any one with a black square, align nicely to form a 100x100 'chessboard'.

Vote Up
Vote Down

Right it's quite simple what I want, if I have an recognisible image of myself and the image is 100 pixels by 100 pixels, how many other images are there of similar similar resolution? Okay we've answered that; it's 2^10000, now can we store them all (at any memory size)? We've answered that; apparently not.
But we can store the sum total of their numeric values - can't we?