Chess Board Maths problem

Chess Board Maths problem

Posers and Puzzles

Cookies help us deliver our Services. By using our Services or clicking I agree, you agree to our use of cookies. Learn More.

Joined
06 Apr 08
Moves
88278
21 Feb 10

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

s
Fast and Curious

slatington, pa, usa

Joined
28 Dec 04
Moves
53223
21 Feb 10

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πŸ™‚

rb

Behind the computer.

Joined
01 Apr 07
Moves
29058
21 Feb 10

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? 😲

Joined
06 Apr 08
Moves
88278
21 Feb 10

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.

Keeps

Shanghai

Joined
16 Feb 06
Moves
131172
21 Feb 10

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

Joined
06 Apr 08
Moves
88278
21 Feb 10

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

Joined
06 Apr 08
Moves
88278
21 Feb 10

...or how about 10 x 10?

Joined
26 Apr 03
Moves
26771
23 Feb 10

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

Joined
06 Apr 08
Moves
88278
23 Feb 10

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?

f
Defend the Universe

127.0.0.1

Joined
18 Dec 03
Moves
16687
23 Feb 10
3 edits

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

Joined
06 Apr 08
Moves
88278
24 Feb 10

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.

f
Defend the Universe

127.0.0.1

Joined
18 Dec 03
Moves
16687
24 Feb 10

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.

Joined
26 Apr 03
Moves
26771
25 Feb 10
2 edits

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.

F

Joined
11 Nov 05
Moves
43938
25 Feb 10
1 edit

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

Joined
06 Apr 08
Moves
88278
25 Feb 10

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?