The Algorithm Design Manual (3rd) Exercise Solution 'E3-8'

Introduction

This series is my solutions for algorithm exercises in'The Algorithm Design Manual' 3rd edition.
It's my solutions, not model answers, so if you find some mistakes or more sophisticated solutions, please post in comment area below.

Repository

Here

Exercise 3-8

Question

Tic-tac-toe is a game played on an n × n board (typically $n = 3$) where two players take consecutive turns placing “O” and “X” marks onto the board cells. The game is won if n consecutive “O” or ‘X” marks are placed in a row, column, or diagonal. Create a data structure with $O(n)$ space that accepts a sequence of moves, and reports in constant time whether the last move won the game.

Solution

Precondition

The signature of the adopted data structure is:

array<pair<char, int>, 2n+2> (c++ notation.)

The concept:
Elements in the array contain a status for the corresponding position (row, column, diagonal lines).
The status is represented as pair<char, int>, which first data is the type of current status and the second is number of the type placed in the position.

The list of types:
E (Empty), O, X, B (Both).

The description of 'position':

• k-th row's status is denoted by (k-1)-th element in the array.
• l-th row's status is denoted by (n+(l-1))-th element.
• Rising diagonal line's status is denoted by (2n)-th element.
• Falling diagonal line's status is denoted by (2n+1)-th element.

Example of positions (n=3):

[
    status-row1, status-row2, status-row3,
    status-column1, status-column2, status-column3,
    status-rising-diagonal, status-falling-diagonal
]

Procedures

Game procedure:

Let placing_count=0
Let turn_flg=false
Loop while placing_count<9
    Select player to place by (turn_flg is false? 'O' : 'X')
    The player places their symbol to the position (R_x, C_y).
    Call Status-changing-procedure(symbol, R_x-1)
    Call Status-changing-procedure(symbol, n+C_y-1)
    If R_x+C_y==n+1 then
        Call Status-changing-procedure(symbol, 2n)
    If R_x==C_y then
        Call Status-changing-procedure(symbol, 2n+1)
    placing_count++
Announce the game ended in a draw.

Status-changing procedure:

Procedure(symbol, index for position)
    Let target_status=array[position]
    If target_status.first_data=='E' then ## The status is still empty.
        target_status.first_data=symbol
        target_status.second_data=1
        exit the procedure
    If target_status.first_data=='B' then ## the status already invalidated
        exit the procedure
    If target_status.first_data!=symbol then
        target_status.first_data='B' ## invalidate the status
        exit the procedure

    target_status.second_data++

    If target_status.second_data==n then ## achieve the winning condition
        Announce the winner is the player with the symbol
        End whole game