Tic-tac-toe in O(1): counters, and why they stop at K = N

transcript

Win detection in constant time. No scanning. Keep one number for every row, column and diagonal, for each player. A move then costs a handful of operations. Whatever the board size.

Place a mark. Add one to its row and its column. On a diagonal? Add one there too. A counter reaches N? That line is won. Three by three: a counter at three means three in a row. No scan.

And undo? Subtract the same numbers. Nothing else. That is why the win checker has a forget method. It mirrors record.

Counters need K to equal N. A row holds N cells. With K smaller, a row can hold K marks with gaps. So walk out from the move instead. Any K.

Counters for K equals N. A walk for any K. Both sit behind one interface, so the game never knows which one it has.

Full breakdown in the lecture.