Hashing every combination of tic tac toe table

Question

I'm working on an algorithm to determine if a tic tac toe model has a winner or not. There's a little twist though-- the function has_won? is being called multiple times. Consequently, the author of the algorithm problem in the book I'm reading (Cracking the Coding Interview) suggests generating each of the 2^9 possible tables and hashing them to a table.

To generate unique keys for each permutation, she represents each board as an integer (board is initially a char array). The integer is generated as such: (3^0)v0 + (3^1)v1 + (3^2)v2+...+(3^8)v8 where v is a 0 if the space is empty, 1 if it's an X, and 2 if it's a O.

Here's what I'm not following. I understand why she did what she did. But what's the guarantee that there won't be another board in the roughly 20,000 possible boards that won't share the same integer key value with that representation? She didn't provide a proof, and I'm not able to intuitively grasp why that's a unique number.

Answer 1

Let's try to see how it works with a simple example. Suppose the board has only two spaces. I know that's not a good game, but just as a first step use it to show how the number code works. In this case the integer is in your notation

(3^0)v0 + (3^1)v1

where v0 and v1 tell us whether the two spaces are empty (0) have a X (1) or have a O (2). Now enumerate the cases:

_ _ (3^0) 0 + (3^1) 0 = 0
X _ (3^0) 1 + (3^1) 0 = 1
O _ (3^0) 2 + (3^1) 0 = 2

Notice that filling up the left space only generates numbers less than 3. Now fill up the right hand space.

_ X (3^0) 0 + (3^1) 1 = 3
_ O (3^0) 0 + (3^1) 2 = 6

Notice that in filling the right hand space we only get multiples of three. Now do the rest.

X X (3^0) 1 + (3^1) 1 = 4
O X (3^0) 2 + (3^1) 1 = 5
X O (3^0) 1 + (3^1) 2 = 7
O O (3^0) 2 + (3^1) 2 = 8

Now we can see that each configuration corresponds to one and only one integer. Further, we can get the configuration out of the integer by integer division. Take the second last case, 7. Divide it by three to get 2 with a remainder of 1. 2 is the configuration of the right hand square and 1 is the configuration of the left. This works for all of the examples above.

If you try this with more than two squares, you'll get the same result. The reason I know that's true, and the way you can get the proof you ask for in your post is to realise that a base three number system keeps the state of each square in one of its digits. That's how the encoding you describe works and that's why each term in the integer encoding has a power of three. This is sufficient I think to show that the integer generated is unique.

One more possible clarification might be to imagine squares that can be in any one of ten states. Call these 0 to 9. Then any ordinary base ten number, for example

234

keeps the state of one and only one square in each digit, and each configuration of squares gives you one and only one base ten number. Write this number in the notation you give in your post

(10^0) 4 + (10^1) 3 + (10^2) 2 = 234

and we have v0=4, v1=3, and v2=2.