Enumerate 4x4 Tic-Tac-Toe Games

You are given an empty 4x4 board. Two players, `X` and `O`, alternate turns, with `X` moving first. A player wins as soon as they create **three consecutive marks** in a row, column, or diagonal. Once a player wins, the game stops immediately. Write a program that uses recursion and backtracking to enumerate all valid game sequences from the empty board to a terminal state. A terminal state is either: - a win for `X`, - a win for `O`, or - a full board with no winner. You may return either: 1. the total number of valid terminal game sequences, or 2. all terminal boards / move sequences themselves. Be prepared to explain: - how you represent the board, - how you detect a win efficiently, - how recursion explores the game tree, - how backtracking restores state after each move, and - what the time complexity looks like in the worst case.