### Magic Square

Let the tic-tac-toe board be represented by a map from int to Mark (some type that represents a mark, possibly an enum), and with its indexes organized as a magic square: http://en.wikipedia.org/wiki/Magic_square

 ``123456789101112131415161718192021`` ``````//(This has been translated from Java.) //Don't take too literally. Read as pseudo-code. //-- Christopher D'Angelo const int S = 3; //side const int N = S * S; //total number of squares const int SUM = S * (N + 1) / 2; bool hasWinner(map board, int move) { Mark mark = board[move]; int d = SUM - move; int n = (d - 1) / 2; for( int a = 1; a <= n; a++ ) { if( a == move ) continue; int b = d - a; if( b != move && b <= N && board.get(a) == mark && board.get(b) == mark ) return true; } return false; }``````

1. Does this algorithm work? (It seems to.)
2. Is it efficient? (Optimization?)
3. Can it be expanded to a more general case?

(Let me know if you have questions...)
Last edited on
1- Yes, for 3x3 squares.
2- No. b<=N is losing time.
3- But the disposition is not unique...
 b<=N is losing time
What do you mean? (That's little n == (d - 1) / 2, not big N.)

 But the disposition is not unique...
Care to elaborate?
Last edited on
About losing time, make a desk test.

About disposition, in bigger n you may test cells that make the sum but are not aligned.
 S * (N + 1) / 2
Is this supposed to be Gauss' expression for calculating
 ``123`` ``````int sum=0; for (int i=1;i<=n;i++) sum+=i;``````
?
If so, it's incorrect. You put a third degree polynomial in there. It should be either (S * (S + 1) / 2) or (N * (N + 1) / 2), depending on exactly what you're trying to sum.

Honestly, I don't get what SUM is supposed to be.
Last edited on
The sum of the magic square.
Like in a 3x3 every line sum 15.
I still don't see what you mean about losing time...

As for squares not being aligned in non-3x3 I'll look at it, but is there perhaps another condition (more general condition) that will keep that from happening, or is this just a fluke that it works for a 3x3?
You don't understand the algorithm.
I doubt that you have done a desk test.

In tic-tac-toe you need to check every row, column and the principal diagonals. This is done every time you make a play, only in the affected lines.
The `trick' with the magic 3x3 square is that every row, column or diagonal sum 15 and the reverse also holds. If there is a way to add up to 15 (with different numbers), then those cells are aligned.

Now losing time:
Suppose that we play the `1' position.
d: the difference that we need to get is 14.
n: is 6. That means that the loop will execute 6 times. However look at the magic square, the `1' is in just 2 lines.

Follow the loop. You'll realize that test every cell to try to get to the sum.
`1' repeated cell, by-pass
`2' will need a `12', too much
`3' will need a `11', too much
`4' will need a `10', too much
`5' will need a `9', OK they are aligned, test (1,5,9) for the same `figure'
`6' will need a `8', OK they are aligned, test (1,6,8) for the same `figure'

As you can see we are starting the loop too soon.
ne555 wrote:
As you can see we are starting the loop too soon.
I came up with this, based on what you pointed out:
 ``1234567891011121314151617181920`` ``````const int S = 3; //side const int N = S * S; //total number of squares const int SUM = S * (N + 1) / 2; bool hasWinner(map board, int move) { Mark mark = board[move]; int d = SUM - move; int n = (d - 1) / 2; int a = d - N; //new starting point if( a < 1 ) a = 1; int b = d - a; while( a <= n ) { if( a != move && b != move && board.get(a) == mark && board.get(b) == mark ) return true; a++; b--; } return false; }``````
I haven't run this yet though. Does it look like it will work? (It seems it will run faster.)

ne555 wrote:
You don't understand the algorithm.
I can up with it last semester in my AI class. (I wanted a more elegant way to check for a win in Tic-Tac-Toe.) What made you think that I didn't understand it?

ne555 wrote:
... the reverse also holds. If there is a way to add up to 15 (with different numbers), then those cells are aligned.
I found three criteria:
(1) a, b, c in [1,9] = [1,N]
(2) a, b, c are unique
(3) a + b + c = 15

I found by testing that win iff (1) and (2) and (3), but I really don't know how to prove it, other then by exhaustion. (Why does this happen?) I was searching for a discussion, and possibly a way to add new/more "criteria" so that the algorithm holds true for larger magic squares, (but I suspect that it doesn't.) For instance, what about Connect 4? (I know that's not a square.) I would also like to examine the efficiency of this algorithm compared to other Tic-Tac-Toe win-check algorithms: e.g. a chain of if statements, loop(s), etc...
(bump) Any other thoughts?
Topic archived. No new replies allowed.