Not a member of Pastebin yet?
Sign Up,
it unlocks many cool features!
- #include <iostream>
- #include <vector>
- using namespace std;
- // Checks if the given player has won the game
- bool check_win(const vector<char>& board, char player) {
- int win_lines[8][3] = {
- {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // Horizontal
- {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, // Vertical
- {0, 4, 8}, {2, 4, 6} // Diagonal
- };
- for (int i = 0; i < 8; ++i) {
- if (board[win_lines[i][0]] == player &&
- board[win_lines[i][1]] == player &&
- board[win_lines[i][2]] == player) {
- return true;
- }
- }
- return false;
- }
- // Recursively counts the number of valid sequences
- int count_games(vector<char>& board, bool is_x_turn, int moves) {
- // Determine who just played
- char prev_player = is_x_turn ? 'O' : 'X';
- // Base Case 1: The player who just moved won the game.
- // The sequence ends here.
- if (check_win(board, prev_player)) {
- return 1;
- }
- // Base Case 2: 9 moves have been made and no one won (Draw).
- // The sequence ends here.
- if (moves == 9) {
- return 1;
- }
- int total_games = 0;
- char current_player = is_x_turn ? 'X' : 'O';
- // Try making a move in every empty cell
- for (int i = 0; i < 9; ++i) {
- if (board[i] == '-') {
- // Make the move
- board[i] = current_player;
- // Recurse for the next turn
- total_games += count_games(board, !is_x_turn, moves + 1);
- // Backtrack to explore other sequences
- board[i] = '-';
- }
- }
- return total_games;
- }
- int main() {
- // Represent the 3x3 board as a 1D array of 9 characters
- vector<char> board(9, '-');
- // X always plays first (is_x_turn = true), starting with 0 moves
- int total = count_games(board, true, 0);
- // Output the final count
- cout << total << "\n";
- return 0;
- }
Advertisement
Add Comment
Please, Sign In to add comment