TicTacToe and Magic Squares

[dhayden]

Here's cool trick for determining a winner in tic-tac-toe with just 5 lines of code. It's from a 1978 letter by Mike Richter, page 8 of the PPC Journal V5 N1 where he describes a 74-step implementation for the HP-67 programmable calculator (https://www.hpmuseum.org/hp6797.htm)

"The mathematical interest stems from the concept of a Magic Square (see any text on Number Theory). The order m Magic Square has the property that each row, column and diagonal sums to a constant, m(m²+1)/2. For order 3, that is 15. This is the order-3 Magic Square:

8 1 6
3 5 7
4 9 2

(and it's obvious permutations).

"A corollary (not always developed in the texts) is that every set of m numbers summing to that value is a row, column, or diagonal of such a square; this can be proved by counting the possibilities and showing that there are 2m+2 of them, the same as the number of rows, columns and diagonals. Therefore, if the TicTacToe board were numbered as an order-3 Magic Square, a win would be exactly any three cells belonging to one player which sum to 15."

Here is a modified version of my program from https://urldefense.com/v3/__http://www.cplusplus.com/forum/beginner/181439/ . The check_winner() checks for a winning move.

//tic tac toe
#include "iostream"
#include "vector"
#include "math.h"
#include "stdio.h"
#include "string.h"
using namespace std;
//#include "std_lib_facilities.h"
char board[3][3];               // each cell is ' ', 'X' or 'O'

void display_table(){
    cout << "+-+-+-+\n";
    for (int i = 0; i < 3; ++i){
        for (int j = 0; j < 3; ++j){
            cout << '|' << board[i][j];
        }
        cout << "|\n";
    }
    cout << "+-+-+-+\n";
}


// Given a vector of previous moves by a player and the current move,
// all represented  as the values in a 3x3 magic square, return true
// if the player has a winning combination
bool check_winner(const vector<int> &prevMoves, int curMove){
    for (unsigned i=0; i+1< prevMoves.size(); ++i) {
	for (unsigned j=i+1; j<prevMoves.size(); ++j) {
	    if (prevMoves[i]+prevMoves[j]+curMove == 15) {
		return true;
	    }
	}
    }
    return false;
}

int main()
{
    for (int i = 0; i < 3; ++i)
        for (int j = 0; j < 3; ++j)
            board[i][j] = ' ';

    cout << "\nTic Tac toe\n\n";
    display_table();
    cout << '\n';
    bool tie = true;
    int x, y;
    int magicSquare[9] = {8,1,6,3,5,7,4,9,2};
    vector<int> magicMoves[2];	  // Players' moves so far, as numbers in magic square
    for (int i = 0; i < 9; ++i) { // even for X, odd for O
	int playerNum = i%2;
        char mark = (playerNum ? 'O' : 'X');
        cout << mark << " its your turn, enter co-ordinates : ";

        while (true) {
            cin >> x >> y;
            --x; --y;           // immediately convert 1-3 into 0-2

            if(x > 2 || y > 2 || x < 0 || y < 0) {
                cout << "Coordinates can only be an int in [1,3]!\nEnter correc\
t value : ";
            } else if (board[x][y] != ' ') {
                cout << "Filled box! Enter different values : ";
            } else {
                break;          // the values are good.
            }
        }

        board[x][y] = mark;
        display_table(); // display the table
	int square = magicSquare[3*x+y];
        if(check_winner(magicMoves[playerNum], square)) {
            cout << "We have a winner!\n";
            cout << mark << " the victor!\n";
            tie = false;
            break;
        }
	magicMoves[playerNum].push_back(square);
    }
    if( tie)cout << "Tie!\n";
    return 0;
}

[lastchance]

Not related to magic squares but maybe another way to check for completion in tic-tac-toe ("noughts and crosses" where I grew up!)

It uses the uniqueness of prime factorisation.

Map the tic-tac-toe board to the first 9 primes:

 2  3  5
 7 11 13
17 19 23

Consider the row, column and diagonal products:

                 935
               /
             /
 2    3    5 --> 30

 7   11   13 --> 1001

17   19   23 --> 7429
 |    |   |  \
 |    |   |    \
238  627 1495   506 

So, if you kept a player's position (uniquely defined) as the product of his positions on the board, then for a complete row, column or diagonal (and hence containing the corresponding primes as factors) you would simply have to test for divisibility against the numbers 30, 1001, 7429, 238, 627, 1495, 935, 506.

In code I think this would reduce to something like

for ( int i : { 30, 1001, 7429, 238, 627, 1495, 935, 506 } ) if ( prod % i == 0 ) return true;
return false;

[markyrocks]

@lastchace beastmode

[dutch]

Or you could use a single bit for each square (shown below in hex):

                54
  01  02  04    07
  08  10  20    38
  40  80 100   1C0
  49  92 124   111

#include <iostream>  

unsigned bit(int row, int col) { return 1u << (row * 3 + col); }

bool match(unsigned p, unsigned m) { return (p & m) == m; }

bool win(unsigned p) {
    for (unsigned m: { 0x07, 0x38, 0x49, 0x54, 0x92, 0x111, 0x124, 0x1C0 })
        if (match(p, m)) return true;
    return false;
}

int main() {
    unsigned p = bit(0,0) | bit(1,1) | bit(2,2) | bit(1,0);
    std::cout << win(p) << '\n';
}

[dhayden]

Lastchance and Dutch, those are nice solutions. Thanks.

The magic square method requires fewer comparisons, but that might not mean it's faster. In the worst case, the player has made 4 moves and we're checking the 5th. In that case there are COMB(4,2)=6 comparisons.

As an aside, in the HP-67 calculator, each digit in the numbers in your solutions would occupy one program step. Storing the numbers would be even worse since there were just 25 storage registers. So for that machine, the magic square method was probably still better. In 1974 this was state of the art and cost $450.