Tic tac toe kiểm tra người chiến thắng C++

Gần đây tôi đã được hỏi một câu hỏi để kiểm tra xem người chơi X có thắng trò chơi Tic Tac Toe không. Đây là cách triển khai mà tôi đã cung cấp, một cách tiếp cận vũ phu

1. Kiểm tra tất cả các hàng cho X
2. Kiểm tra tất cả các cột cho X
3. Kiểm tra 2 đường chéo cho X

// Giả sử Trình xây dựng của lớp khởi tạo mọi thứ đúng cách. Tất cả các giá trị được đặt thành // null

bool?[][] board; // X = true, O = false, empty space = null
bool XWon(){// Check All Rows for truefor(int i=0;i    if(board[i].All(x=>x) return true;
}// Check All Columns for true

for(int i=0; i   bool check = true;
   for(int y=0;y       if(board[i][y]==false) check=false;
   }
   if(check) return true;
}check = true;for(int i=0;i   if(board[i][i]==false)return false;
}for(int i=0;i   if(board[i][board[0].Length-i]==false) return false;
}return check;
}

Vì vậy, đoạn mã trên có thể sạch hơn một chút, nhưng điểm mà mọi người nên thấy ở đây là giải pháp này là giải pháp O(n²). Nó không hoạt động tốt cho các bảng Tic Tac Toe có kích thước lớn

Sự đồng thuận chung để giảm độ phức tạp thời gian của vấn đề là đưa ra một số độ phức tạp không gian. Hãy nhớ rằng, nó luôn luôn là một sự đánh đổi

1. Mỗi lần người chơi đánh dấu X trên bảng, chúng ta cần theo dõi vị trí đánh dấu X
2. Giữ số lượng X trong hàng và cột (2 mảng)
3. Giữ số lượng X trong Đường chéo (2 mảng)
4. Nếu bất kỳ chỉ số nào của mảng bằng chiều dài của bàn cờ, x sẽ thắng

bool?[][] board; // X = true, O = false, empty space = null
int[] row;
int[] column;
int[] diag;
int[] antiDiag;bool XWon(int r, int c){ // Call this function when player moves
     int boardSize = board[0].Length;
     row[r]++;
     column[c]++;
     if(r==c) diag[r]++;
     if(r+c==boardSize) antiDiag[r]++;     if(row[r]==boardSize || column[c]==boardSize || diag[r]==boardSize || antiDiag[r]==boardSize) return true;     else return false;
}

Ở đây chúng tôi có nó, một giải pháp O(1) yêu cầu độ phức tạp không gian O(n). Mặc dù giải pháp này phải theo dõi nhiều thứ hơn, nhưng nó đơn giản hơn để viết và gỡ lỗi và quan trọng hơn là không có vòng lặp

Đây là một câu hỏi đã được hỏi trên StackOverflow ( https. // stackoverflow. com/câu hỏi/1056316/algorithm-for-dinating-tic-tac-toe-game-over) trong đó câu trả lời được đánh dấu là được chấp nhận/chính xác đã sử dụng các vòng lặp để kiểm tra từng cột/hàng/đường chéo

Giải pháp được cung cấp là thời gian O(n) với một vài mảng bổ sung. Tôi sẽ lập luận rằng vì bộ nhớ không phải lúc nào cũng là yếu tố giới hạn và thời gian có thể là như vậy, nên tốt hơn hết là sử dụng thêm bộ nhớ (nếu có) và chạy trong thời gian O(1). Tôi không sử dụng điều này như một quy tắc phổ quát, mà giống như cách tiếp cận 'mèo vừa thì mèo ngồi' để giải quyết vấn đề.

Tôi đã học được động thời gian/không gian từ việc giải bài toán này, và tôi hy vọng bạn cũng vậy

Ồ, vâng, có thể có lỗi trong đoạn mã trên, nhưng tôi không lo lắng, ý tưởng chính xác mới là vấn đề

Điều đó sẽ kiểm tra xem có ai đã giành chiến thắng trên tất cả các hàng hay không, nhưng có vẻ như chức năng này không hoạt động. Điều gì có thể là vấn đề?

Tôi không thể đăng nhập vào trang web này mà không thấy 2 hoặc 3 câu hỏi tic-tac-toe trong tuần này. Phải có một bài tập đến hạn hoặc một cái gì đó cho một khóa học tham khảo trang web này rất nhiều

http. //cplusplus. com/forum/người mới bắt đầu/58046/

Tôi nghĩ chỉ vì nó là một trò chơi đơn giản và những người mới bắt đầu như tôi muốn luyện tập. Vì vậy, bạn có thấy những gì có thể sai với chức năng của tôi?

if( spaces[i] == spaces[i+1] == spaces[i+2] == 'X')

không hoạt động trong C++

if( spaces[i] == 'X' && spaces[i+1] == 'X' && spaces[i+2] == 'X')

là những gì bạn cần

Phiên bản đầu tiên được đánh giá từ trái sang phải, vì vậy -- giả sử tất cả đều là 'X' (ascii 88) -- nó kết thúc bằng (mỗi lần đánh giá hai thuật ngữ ngoài cùng bên trái)

Đưa ra một mảng di chuyển trong đó mỗi phần tử là một mảng khác có kích thước 2 tương ứng với hàng và cột của lưới nơi chúng đánh dấu ký tự tương ứng theo thứ tự mà A và B chơi. Trả lại người chiến thắng của trò chơi nếu nó tồn tại (A hoặc B), trong trường hợp trò chơi kết thúc với tỷ số hòa, hãy trả lại “Hòa”, nếu vẫn còn các chuyển động để chơi, hãy trả về “Đang chờ xử lý”

Bạn có thể cho rằng các nước đi là hợp lệ (Nó tuân theo các quy tắc của Tic-Tac-Toe), lưới ban đầu trống và A sẽ chơi trước

ví dụ 1
Đầu vào. di chuyển = [[0,0],[2,0],[1,1],[2,1],[2,2]]
đầu ra. "MỘT"

Giải trình. “A” thắng, anh ấy luôn chơi trước

"X  "    "X  "    "X  "    "X  "    "X  "
"   " -> "   " -> " X " -> " X " -> " X "
"   "    "O  "    "O  "    "OO "    "OOX"

ví dụ 2
Đầu vào. di chuyển = [[0,0],[1,1],[0,1],[0,2],[1,0],[2,0]]
đầu ra. “B”
Giải trình. “B” thắng

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

ví dụ 3

Đầu vào. di chuyển = [[0,0],[1,1],[2,0],[1,0],[1,2],[2,1],[0,1],[0,2]
đầu ra. "Vẽ tranh"
Giải trình. Trò chơi kết thúc với tỷ số hòa vì không có nước đi nào để thực hiện

1
2
3

"XXO"
"OOX"
"XOX"

"XXO"
"OOX"
"XOX"

Ví dụ 4

Đầu vào. di chuyển = [[0,0],[1,1]]
đầu ra. "Chưa giải quyết"
Giải trình. Trò chơi vẫn chưa kết thúc

1
2
3

"X  "
" O "
"   "

"X  "
" O "
"   "

Hạn chế
1 <= di chuyển. chiều dài <= 9
di chuyển [i]. chiều dài == 2
0 <= di chuyển[i][j] <= 2
Không có yếu tố lặp lại khi di chuyển
di chuyển theo các quy tắc của tic tac toe

gợi ý
Thật đơn giản để kiểm tra xem A hoặc B có thắng hay không, kiểm tra từng hàng/cột/đường chéo nếu cả ba đều giống nhau
Sau đó, nếu không ai thắng, trò chơi là hòa khi và chỉ khi bàn cờ đầy người, tôi. e. di chuyển. chiều dài = 9 nếu không thì đang chờ xử lý

Hàm C++ để xác định người chiến thắng trong Trò chơi Tic-Tac-Toe

Chỉ cần kiểm tra (bruteforce) nếu có 3 phần được kết nối. 3 hàng, 3 cột và 2 đường chéo

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25

bool win(char board[3][3], string &result) {
     for (int i = 0; i < 3; ++ i) {
        if ((board[i][0] != 0) && (board[i][0] == board[i][1]) 
                        && (board[i][1] == board[i][2])) {
            result = board[i][0];
            return true;
        }
        if ((board[0][i] != 0) && (board[0][i] == board[1][i]) 
                        && (board[1][i] == board[2][i])) {
            result = board[0][i];
            return true;
        }            
    }
    if ((board[1][1] != 0) && (board[0][0] == board[1][1]) 
                        && (board[1][1] == board[2][2])) {
        result = board[1][1];
        return true;
    }
    if ((board[1][1] != 0) && (board[0][2] == board[1][1]) 
                        && (board[1][1] == board[2][0])) {
        result = board[1][1];
        return true;
    }        
    return false;
}

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Bảng đã được khởi tạo thành ma trận 3×3 với các giá trị bằng không

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Ngoài ra, chúng ta có thể sử dụng std. lấp đầy()

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

Tìm người chiến thắng trong trò chơi Tic Tac Toe

Một trường hợp đặc biệt là kiểm tra xem còn chỗ cho lần chơi tiếp theo hay không – có thể là Hòa hoặc Đang chờ xử lý nếu không có người chiến thắng

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

"X  "    "X  "    "XX "    "XXO"    "XXO"    "XXO"
"   " -> " O " -> " O " -> " O " -> "XO " -> "XO " 
"   "    "   "    "   "    "   "    "   "    "O  "

–EOF (Blog máy tính & công nghệ cơ bản) —

Xếp hạng sao GD
Đang tải

bài viết liên quan

• Làm thế nào để thiết kế một trò chơi Tic-Tac-Toe?

  Thiết kế một trò chơi Tic-tac-toe được chơi giữa hai người chơi trên một n x n…

• Áp dụng thuật toán Naive Bayes trong trò chơi Rock-Scissor-Paper

  Thứ Sáu tuần trước, @justyy đã tổ chức cuộc thi oẳn tù tì nhóm wechat cho cộng đồng CN và cuộc thi…

• Thuật toán 24 trò chơi sử dụng Tìm kiếm theo chiều sâu

  Bạn có 4 thẻ mỗi thẻ chứa một số từ 1 đến 9. Bạn cần phải…

• Dạy Lập Trình Cho Bé - Giải Game Nhảy Bằng Thuật Toán Tìm Kiếm Theo Chiều Sâu

  Hôm qua, chúng ta đã nói về Thuật toán tìm kiếm theo chiều rộng đầu tiên. Chúng tôi đang giải cùng một Jump…

• Độ phức tạp của thuật toán

  Độ phức tạp của thuật toán có thể được biểu thị bằng ký hiệu Big O, ví dụ: đoạn sau của…

• Thuật toán để tìm sự ám chỉ dài nhất

  Đưa ra một danh sách các từ chuỗi chữ cái viết thường, trả về độ dài của từ liền kề dài nhất…

• Thuật toán giao nhau giữa các khoảng

  Đưa ra một khoảng thời gian danh sách số nguyên hai chiều có dạng [bắt đầu, kết thúc] đại diện cho các khoảng thời gian (bao gồm), trả về…

  Mẹo để chiến thắng tic tac toe là gì?

  Khi bạn là người đầu tiên tham gia, có một chiến lược đơn giản để giành chiến thắng trong trò tic tac toe. đặt dấu 'X' của bạn vào bất kỳ góc nào . Nước đi này gần như sẽ đưa bạn đến vòng tròn của người chiến thắng mọi lúc, miễn là đối thủ của bạn không đặt chữ 'O' đầu tiên của họ vào ô trung tâm.

  Làm cách nào để kiểm tra người chiến thắng trong tic tac toe Java?

  Trong tic tac toe, người chơi thắng nếu họ có 3 biểu tượng trong một hàng, cột hoặc đường chéo . Hãy bắt đầu với các hàng. Chúng ta có thể sử dụng vòng lặp for để lặp qua từng hàng i. Bên trong vòng lặp for, chúng ta có thể sử dụng một điều kiện để kiểm tra xem board[i][0] có bằng board[i][1] không và board[i][1] có bằng board[i][2] không.

  Bạn có thể đảm bảo giành chiến thắng trong trò tic tac toe không?

  Hầu hết những người chơi tic tac toe có kinh nghiệm đều đặt chữ "X" đầu tiên vào một góc khi họ bắt đầu chơi lần đầu tiên. Điều này tạo cho đối thủ nhiều cơ hội nhất để phạm sai lầm. Nếu đối thủ của bạn phản ứng bằng cách đặt một chữ O ở bất kỳ đâu ngoài tâm, bạn có thể đảm bảo chiến thắng .

  Tic tac toe có bao nhiêu kết thúc?

  Trên thực tế, người chơi tic-tac-toe điền vào mỗi mục trong số chín mục bằng một trong ba giá trị duy nhất. dấu X, O hoặc để trống. Đó là tổng cộng 3*3*3*3*3*3*3*3*3 = 3^9 = 19.683 các cách khác nhau của lưới 3x3 .