21 Feb '10 00:41

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

- Joined
- 06 Apr '08
- Moves
- 61289

- Joined
- 28 Dec '04
- Moves
- 52724

slatington, pa, usa- Joined
- 01 Apr '07
- Moves
- 29058

Behind the computer.- Joined
- 06 Apr '08
- Moves
- 61289

- Joined
- 16 Feb '06
- Moves
- 113388

Shanghai- Joined
- 06 Apr '08
- Moves
- 61289

- Joined
- 06 Apr '08
- Moves
- 61289

- Joined
- 26 Apr '03
- Moves
- 25839

- Joined
- 06 Apr '08
- Moves
- 61289

23 Feb '10 17:30Ah, 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?- Joined
- 18 Dec '03
- Moves
- 16018

127.0.0.123 Feb '10 18:123 edits

Any algorithm that takes 2^n time or space is pretty much unfeasible if n is not small.*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?

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

24 Feb '10 09:48Okay 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.- Joined
- 18 Dec '03
- Moves
- 16018

127.0.0.124 Feb '10 17:38

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

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

25 Feb '10 03:232 edits

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

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.- Joined
- 11 Nov '05
- Moves
- 43938

25 Feb '10 05:101 editWhy 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
- 61289

25 Feb '10 13:04Right 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?