Iam_Sandeep

Untitled

Mar 27th, 2026
54
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.96 KB | None | 0 0
  1. #include <iostream>
  2. #include <vector>
  3.  
  4. using namespace std;
  5.  
  6. // Checks if the given player has won the game
  7. bool check_win(const vector<char>& board, char player) {
  8.     int win_lines[8][3] = {
  9.         {0, 1, 2}, {3, 4, 5}, {6, 7, 8}, // Horizontal
  10.         {0, 3, 6}, {1, 4, 7}, {2, 5, 8}, // Vertical
  11.         {0, 4, 8}, {2, 4, 6}             // Diagonal
  12.     };
  13.    
  14.     for (int i = 0; i < 8; ++i) {
  15.         if (board[win_lines[i][0]] == player &&
  16.             board[win_lines[i][1]] == player &&
  17.             board[win_lines[i][2]] == player) {
  18.             return true;
  19.         }
  20.     }
  21.     return false;
  22. }
  23.  
  24. // Recursively counts the number of valid sequences
  25. int count_games(vector<char>& board, bool is_x_turn, int moves) {
  26.     // Determine who just played
  27.     char prev_player = is_x_turn ? 'O' : 'X';
  28.    
  29.     // Base Case 1: The player who just moved won the game.
  30.     // The sequence ends here.
  31.     if (check_win(board, prev_player)) {
  32.         return 1;
  33.     }
  34.    
  35.     // Base Case 2: 9 moves have been made and no one won (Draw).
  36.     // The sequence ends here.
  37.     if (moves == 9) {
  38.         return 1;
  39.     }
  40.  
  41.     int total_games = 0;
  42.     char current_player = is_x_turn ? 'X' : 'O';
  43.  
  44.     // Try making a move in every empty cell
  45.     for (int i = 0; i < 9; ++i) {
  46.         if (board[i] == '-') {
  47.             // Make the move
  48.             board[i] = current_player;
  49.            
  50.             // Recurse for the next turn
  51.             total_games += count_games(board, !is_x_turn, moves + 1);
  52.            
  53.             // Backtrack to explore other sequences
  54.             board[i] = '-';
  55.         }
  56.     }
  57.  
  58.     return total_games;
  59. }
  60.  
  61. int main() {
  62.     // Represent the 3x3 board as a 1D array of 9 characters
  63.     vector<char> board(9, '-');
  64.    
  65.     // X always plays first (is_x_turn = true), starting with 0 moves
  66.     int total = count_games(board, true, 0);
  67.    
  68.     // Output the final count
  69.     cout << total << "\n";
  70.    
  71.     return 0;
  72. }
  73.  
Advertisement
Add Comment
Please, Sign In to add comment