Algoritmo para determinar Tic Tac Toe Game Over
https://stackoverflow.com/questions/1056316
-
20-08-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPergunta
Eu escrevi um jogo de tic-tac-toe em Java, e meu atual método de determinar o fim do jogo representa para os seguintes cenários possíveis para o jogo sendo mais:
- O conselho está cheio, e nenhum vencedor foi ainda declarou:. O jogo é um empate
- Cross ganhou.
- Círculo ganhou.
Infelizmente, a fazê-lo, lê-se através de um conjunto pré-definido desses cenários de uma tabela. Isso não é necessariamente ruim, considerando que existem apenas 9 espaços em uma placa e, assim, a tabela é um pouco pequeno, mas há uma maneira melhor algorítmica de determinar se o jogo acabou? A determinação de se alguém ganhou ou não é a carne do problema, uma vez que verificar se 9 espaços estão cheios é trivial.
O método de tabela pode ser a solução, mas se não, o que é? Além disso, o que se o conselho não eram n=9 tamanho? E se fosse uma placa muito maior, dizem n=16, n=25, e assim por diante, fazendo com que o número de itens consecutivamente colocados para ganhar a ser x=4, x=5, etc? Um algoritmo geral de usar para todos n = { 9, 16, 25, 36 ... }?
Solução
Você sabe que uma jogada vencedora só pode acontecer após X ou O fez seu movimento mais recente, assim você só pode pesquisar linha / coluna com diag opcional que estão contidos nesse movimento para limitar o seu espaço de busca quando se tenta determinar um vencedor borda. Também uma vez que há um número fixo de movimentos em um empate jogo tic-tac-toe uma vez que o último movimento é feito se não fosse uma jogada vencedora é por padrão um jogo de empate.
edit: esse código é para um n pelo conselho n com n em uma fila para ganhar (requries tabuleiro 3x3 3 em uma linha, etc)
edit: código adicionado para verificar anti diag, eu não poderia descobrir uma maneira não loop para determinar se o ponto estava no anti diag isso é assim porque esse passo está faltando
public class TripleT {
enum State{Blank, X, O};
int n = 3;
State[][] board = new State[n][n];
int moveCount;
void Move(int x, int y, State s){
if(board[x][y] == State.Blank){
board[x][y] = s;
}
moveCount++;
//check end conditions
//check col
for(int i = 0; i < n; i++){
if(board[x][i] != s)
break;
if(i == n-1){
//report win for s
}
}
//check row
for(int i = 0; i < n; i++){
if(board[i][y] != s)
break;
if(i == n-1){
//report win for s
}
}
//check diag
if(x == y){
//we're on a diagonal
for(int i = 0; i < n; i++){
if(board[i][i] != s)
break;
if(i == n-1){
//report win for s
}
}
}
//check anti diag (thanks rampion)
if(x + y == n - 1){
for(int i = 0; i < n; i++){
if(board[i][(n-1)-i] != s)
break;
if(i == n-1){
//report win for s
}
}
}
//check draw
if(moveCount == (Math.pow(n, 2) - 1)){
//report draw
}
}
}
Outras dicas
Você pode usar um quadrado mágico http://mathworld.wolfram.com/MagicSquare.html Se alguma linha, coluna ou diag acrescenta-se a 15, em seguida, um jogador ganhou.
Este é semelhante ao , mas comercializa constante do espaço e do tempo linear para linear-espaço e de tempo constante. Ou seja, não há nenhum looping após a inicialização.
Inicializar um (0,0) par para cada fileira, cada coluna, e as duas diagonais (diagonais e anti-diagonais). Estes pares representam o (sum,sum) acumulada das peças na linha, coluna correspondente, ou na diagonal, em que
A piece from player A has value (1,0) A piece from player B has value (0,1)
Quando um jogador coloca uma peça, actualizar o par correspondente fila, coluna par, e os pares diagonais (se nas diagonais). Se alguma linha recém-atualizada, coluna ou diagonal par é igual a qualquer (n,0) ou (0,n) seguida, A ou B ganhou, respectivamente.
análise assintótica:
O(1) time (per move) O(n) space (overall)
Para o uso de memória, você usar inteiros 4*(n+1).
two_elements*n_rows + two_elements*n_columns + two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers
Exercício: Você pode ver como teste para um empate em O (1) tempo de per-movimento? Se assim for, você pode terminar o jogo cedo em um empate.
Como sobre este pseudo-código:
Depois que um jogador põe um pedaço na posição (x, y):
col=row=diag=rdiag=0
winner=false
for i=1 to n
if cell[x,i]=player then col++
if cell[i,y]=player then row++
if cell[i,i]=player then diag++
if cell[i,n-i+1]=player then rdiag++
if row=n or col=n or diag=n or rdiag=n then winner=true
eu usar uma matriz de char [N, N], com O, X e espaço para o vazio.
- simples.
- Um loop.
- Cinco variáveis ??simples:. 4 inteiros e um boolean
- Escalas para qualquer tamanho de n.
- Só os controlos peça atual.
- Nenhuma mágica. :)
Aqui está a minha solução que eu escrevi para um projeto que estou trabalhando em javascript. Se você não se importa o custo de memória de algumas matrizes é provavelmente a solução mais rápida e mais simples que você vai encontrar. Ele assume que você sabe a posição da última jogada.
/*
* Determines if the last move resulted in a win for either player
* board: is an array representing the board
* lastMove: is the boardIndex of the last (most recent) move
* these are the boardIndexes:
*
* 0 | 1 | 2
* ---+---+---
* 3 | 4 | 5
* ---+---+---
* 6 | 7 | 8
*
* returns true if there was a win
*/
var winLines = [
[[1, 2], [4, 8], [3, 6]],
[[0, 2], [4, 7]],
[[0, 1], [4, 6], [5, 8]],
[[4, 5], [0, 6]],
[[3, 5], [0, 8], [2, 6], [1, 7]],
[[3, 4], [2, 8]],
[[7, 8], [2, 4], [0, 3]],
[[6, 8], [1, 4]],
[[6, 7], [0, 4], [2, 5]]
];
function isWinningMove(board, lastMove) {
var player = board[lastMove];
for (var i = 0; i < winLines[lastMove].length; i++) {
var line = winLines[lastMove][i];
if(player === board[line[0]] && player === board[line[1]]) {
return true;
}
}
return false;
}
Eu só escrevi isso para minha classe de programação C.
Estou postando isso porque nenhum dos outros exemplos aqui vai trabalhar com qualquer tamanho retangular grid, e qualquer número N -in-a-fila marcas consecutivos a vencer .
Você vai encontrar meu algoritmo, tal como ela é, na função checkWinner(). Ele não usa números mágicos ou fantasia nada para verificar se há um vencedor, ele simplesmente usa quatro loops -. O código está bem comentado por isso vou deixá-lo falar por si Acho
// This program will work with any whole number sized rectangular gameBoard.
// It checks for N marks in straight lines (rows, columns, and diagonals).
// It is prettiest when ROWS and COLS are single digit numbers.
// Try altering the constants for ROWS, COLS, and N for great fun!
// PPDs come first
#include <stdio.h>
#define ROWS 9 // The number of rows our gameBoard array will have
#define COLS 9 // The number of columns of the same - Single digit numbers will be prettier!
#define N 3 // This is the number of contiguous marks a player must have to win
#define INITCHAR ' ' // This changes the character displayed (a ' ' here probably looks the best)
#define PLAYER1CHAR 'X' // Some marks are more aesthetically pleasing than others
#define PLAYER2CHAR 'O' // Change these lines if you care to experiment with them
// Function prototypes are next
int playGame (char gameBoard[ROWS][COLS]); // This function allows the game to be replayed easily, as desired
void initBoard (char gameBoard[ROWS][COLS]); // Fills the ROWSxCOLS character array with the INITCHAR character
void printBoard (char gameBoard[ROWS][COLS]); // Prints out the current board, now with pretty formatting and #s!
void makeMove (char gameBoard[ROWS][COLS], int player); // Prompts for (and validates!) a move and stores it into the array
int checkWinner (char gameBoard[ROWS][COLS], int player); // Checks the current state of the board to see if anyone has won
// The starting line
int main (void)
{
// Inits
char gameBoard[ROWS][COLS]; // Our gameBoard is declared as a character array, ROWS x COLS in size
int winner = 0;
char replay;
//Code
do // This loop plays through the game until the user elects not to
{
winner = playGame(gameBoard);
printf("\nWould you like to play again? Y for yes, anything else exits: ");
scanf("%c",&replay); // I have to use both a scanf() and a getchar() in
replay = getchar(); // order to clear the input buffer of a newline char
// (http://cboard.cprogramming.com/c-programming/121190-problem-do-while-loop-char.html)
} while ( replay == 'y' || replay == 'Y' );
// Housekeeping
printf("\n");
return winner;
}
int playGame(char gameBoard[ROWS][COLS])
{
int turn = 0, player = 0, winner = 0, i = 0;
initBoard(gameBoard);
do
{
turn++; // Every time this loop executes, a unique turn is about to be made
player = (turn+1)%2+1; // This mod function alternates the player variable between 1 & 2 each turn
makeMove(gameBoard,player);
printBoard(gameBoard);
winner = checkWinner(gameBoard,player);
if (winner != 0)
{
printBoard(gameBoard);
for (i=0;i<19-2*ROWS;i++) // Formatting - works with the default shell height on my machine
printf("\n"); // Hopefully I can replace these with something that clears the screen for me
printf("\n\nCongratulations Player %i, you've won with %i in a row!\n\n",winner,N);
return winner;
}
} while ( turn < ROWS*COLS ); // Once ROWS*COLS turns have elapsed
printf("\n\nGame Over!\n\nThere was no Winner :-(\n"); // The board is full and the game is over
return winner;
}
void initBoard (char gameBoard[ROWS][COLS])
{
int row = 0, col = 0;
for (row=0;row<ROWS;row++)
{
for (col=0;col<COLS;col++)
{
gameBoard[row][col] = INITCHAR; // Fill the gameBoard with INITCHAR characters
}
}
printBoard(gameBoard); // Having this here prints out the board before
return; // the playGame function asks for the first move
}
void printBoard (char gameBoard[ROWS][COLS]) // There is a ton of formatting in here
{ // That I don't feel like commenting :P
int row = 0, col = 0, i=0; // It took a while to fine tune
// But now the output is something like:
printf("\n"); //
// 1 2 3
for (row=0;row<ROWS;row++) // 1 | |
{ // -----------
if (row == 0) // 2 | |
{ // -----------
printf(" "); // 3 | |
for (i=0;i<COLS;i++)
{
printf(" %i ",i+1);
}
printf("\n\n");
}
for (col=0;col<COLS;col++)
{
if (col==0)
printf("%i ",row+1);
printf(" %c ",gameBoard[row][col]);
if (col<COLS-1)
printf("|");
}
printf("\n");
if (row < ROWS-1)
{
for(i=0;i<COLS-1;i++)
{
if(i==0)
printf(" ----");
else
printf("----");
}
printf("---\n");
}
}
return;
}
void makeMove (char gameBoard[ROWS][COLS],int player)
{
int row = 0, col = 0, i=0;
char currentChar;
if (player == 1) // This gets the correct player's mark
currentChar = PLAYER1CHAR;
else
currentChar = PLAYER2CHAR;
for (i=0;i<21-2*ROWS;i++) // Newline formatting again :-(
printf("\n");
printf("\nPlayer %i, please enter the column of your move: ",player);
scanf("%i",&col);
printf("Please enter the row of your move: ");
scanf("%i",&row);
row--; // These lines translate the user's rows and columns numbering
col--; // (starting with 1) to the computer's (starting with 0)
while(gameBoard[row][col] != INITCHAR || row > ROWS-1 || col > COLS-1) // We are not using a do... while because
{ // I wanted the prompt to change
printBoard(gameBoard);
for (i=0;i<20-2*ROWS;i++)
printf("\n");
printf("\nPlayer %i, please enter a valid move! Column first, then row.\n",player);
scanf("%i %i",&col,&row);
row--; // See above ^^^
col--;
}
gameBoard[row][col] = currentChar; // Finally, we store the correct mark into the given location
return; // And pop back out of this function
}
int checkWinner(char gameBoard[ROWS][COLS], int player) // I've commented the last (and the hardest, for me anyway)
{ // check, which checks for backwards diagonal runs below >>>
int row = 0, col = 0, i = 0;
char currentChar;
if (player == 1)
currentChar = PLAYER1CHAR;
else
currentChar = PLAYER2CHAR;
for ( row = 0; row < ROWS; row++) // This first for loop checks every row
{
for ( col = 0; col < (COLS-(N-1)); col++) // And all columns until N away from the end
{
while (gameBoard[row][col] == currentChar) // For consecutive rows of the current player's mark
{
col++;
i++;
if (i == N)
{
return player;
}
}
i = 0;
}
}
for ( col = 0; col < COLS; col++) // This one checks for columns of consecutive marks
{
for ( row = 0; row < (ROWS-(N-1)); row++)
{
while (gameBoard[row][col] == currentChar)
{
row++;
i++;
if (i == N)
{
return player;
}
}
i = 0;
}
}
for ( col = 0; col < (COLS - (N-1)); col++) // This one checks for "forwards" diagonal runs
{
for ( row = 0; row < (ROWS-(N-1)); row++)
{
while (gameBoard[row][col] == currentChar)
{
row++;
col++;
i++;
if (i == N)
{
return player;
}
}
i = 0;
}
}
// Finally, the backwards diagonals:
for ( col = COLS-1; col > 0+(N-2); col--) // Start from the last column and go until N columns from the first
{ // The math seems strange here but the numbers work out when you trace them
for ( row = 0; row < (ROWS-(N-1)); row++) // Start from the first row and go until N rows from the last
{
while (gameBoard[row][col] == currentChar) // If the current player's character is there
{
row++; // Go down a row
col--; // And back a column
i++; // The i variable tracks how many consecutive marks have been found
if (i == N) // Once i == N
{
return player; // Return the current player number to the
} // winnner variable in the playGame function
} // If it breaks out of the while loop, there weren't N consecutive marks
i = 0; // So make i = 0 again
} // And go back into the for loop, incrementing the row to check from
}
return 0; // If we got to here, no winner has been detected,
} // so we pop back up into the playGame function
// The end!
// Well, almost.
// Eventually I hope to get this thing going
// with a dynamically sized array. I'll make
// the CONSTANTS into variables in an initGame
// function and allow the user to define them.
Se a placa é n × n , em seguida, existem n linhas, n colunas e 2 diagonais . Verifique cada um desses para todos-X de um ou todos-O de encontrar um vencedor.
Se ele só tem x < n quadrados consecutivos para ganhar, então é um pouco mais complicado. A solução mais óbvia é a de verificar cada x × x quadrado para um vencedor. Aqui está algum código que demonstra isso.
(eu não realmente testar essa tosse * *, mas se compilação na primeira tentativa, yay me!)
public class TicTacToe
{
public enum Square { X, O, NONE }
/**
* Returns the winning player, or NONE if the game has
* finished without a winner, or null if the game is unfinished.
*/
public Square findWinner(Square[][] board, int lengthToWin) {
// Check each lengthToWin x lengthToWin board for a winner.
for (int top = 0; top <= board.length - lengthToWin; ++top) {
int bottom = top + lengthToWin - 1;
for (int left = 0; left <= board.length - lengthToWin; ++left) {
int right = left + lengthToWin - 1;
// Check each row.
nextRow: for (int row = top; row <= bottom; ++row) {
if (board[row][left] == Square.NONE) {
continue;
}
for (int col = left; col <= right; ++col) {
if (board[row][col] != board[row][left]) {
continue nextRow;
}
}
return board[row][left];
}
// Check each column.
nextCol: for (int col = left; col <= right; ++col) {
if (board[top][col] == Square.NONE) {
continue;
}
for (int row = top; row <= bottom; ++row) {
if (board[row][col] != board[top][col]) {
continue nextCol;
}
}
return board[top][col];
}
// Check top-left to bottom-right diagonal.
diag1: if (board[top][left] != Square.NONE) {
for (int i = 1; i < lengthToWin; ++i) {
if (board[top+i][left+i] != board[top][left]) {
break diag1;
}
}
return board[top][left];
}
// Check top-right to bottom-left diagonal.
diag2: if (board[top][right] != Square.NONE) {
for (int i = 1; i < lengthToWin; ++i) {
if (board[top+i][right-i] != board[top][right]) {
break diag2;
}
}
return board[top][right];
}
}
}
// Check for a completely full board.
boolean isFull = true;
full: for (int row = 0; row < board.length; ++row) {
for (int col = 0; col < board.length; ++col) {
if (board[row][col] == Square.NONE) {
isFull = false;
break full;
}
}
}
// The board is full.
if (isFull) {
return Square.NONE;
}
// The board is not full and we didn't find a solution.
else {
return null;
}
}
}
Eu não sei Java muito bem, mas eu sei que C, então eu tentei magia ideia praça de ADK (juntamente com pesquisa restrição de Hardwareguy).
// tic-tac-toe.c
// to compile:
// % gcc -o tic-tac-toe tic-tac-toe.c
// to run:
// % ./tic-tac-toe
#include <stdio.h>
// the two types of marks available
typedef enum { Empty=2, X=0, O=1, NumMarks=2 } Mark;
char const MarkToChar[] = "XO ";
// a structure to hold the sums of each kind of mark
typedef struct { unsigned char of[NumMarks]; } Sum;
// a cell in the board, which has a particular value
#define MAGIC_NUMBER 15
typedef struct {
Mark mark;
unsigned char const value;
size_t const num_sums;
Sum * const sums[4];
} Cell;
#define NUM_ROWS 3
#define NUM_COLS 3
// create a sum for each possible tic-tac-toe
Sum row[NUM_ROWS] = {0};
Sum col[NUM_COLS] = {0};
Sum nw_diag = {0};
Sum ne_diag = {0};
// initialize the board values so any row, column, or diagonal adds to
// MAGIC_NUMBER, and so they each record their sums in the proper rows, columns,
// and diagonals
Cell board[NUM_ROWS][NUM_COLS] = {
{
{ Empty, 8, 3, { &row[0], &col[0], &nw_diag } },
{ Empty, 1, 2, { &row[0], &col[1] } },
{ Empty, 6, 3, { &row[0], &col[2], &ne_diag } },
},
{
{ Empty, 3, 2, { &row[1], &col[0] } },
{ Empty, 5, 4, { &row[1], &col[1], &nw_diag, &ne_diag } },
{ Empty, 7, 2, { &row[1], &col[2] } },
},
{
{ Empty, 4, 3, { &row[2], &col[0], &ne_diag } },
{ Empty, 9, 2, { &row[2], &col[1] } },
{ Empty, 2, 3, { &row[2], &col[2], &nw_diag } },
}
};
// print the board
void show_board(void)
{
size_t r, c;
for (r = 0; r < NUM_ROWS; r++)
{
if (r > 0) { printf("---+---+---\n"); }
for (c = 0; c < NUM_COLS; c++)
{
if (c > 0) { printf("|"); }
printf(" %c ", MarkToChar[board[r][c].mark]);
}
printf("\n");
}
}
// run the game, asking the player for inputs for each side
int main(int argc, char * argv[])
{
size_t m;
show_board();
printf("Enter moves as \"<row> <col>\" (no quotes, zero indexed)\n");
for( m = 0; m < NUM_ROWS * NUM_COLS; m++ )
{
Mark const mark = (Mark) (m % NumMarks);
size_t c, r;
// read the player's move
do
{
printf("%c's move: ", MarkToChar[mark]);
fflush(stdout);
scanf("%d %d", &r, &c);
if (r >= NUM_ROWS || c >= NUM_COLS)
{
printf("illegal move (off the board), try again\n");
}
else if (board[r][c].mark != Empty)
{
printf("illegal move (already taken), try again\n");
}
else
{
break;
}
}
while (1);
{
Cell * const cell = &(board[r][c]);
size_t s;
// update the board state
cell->mark = mark;
show_board();
// check for tic-tac-toe
for (s = 0; s < cell->num_sums; s++)
{
cell->sums[s]->of[mark] += cell->value;
if (cell->sums[s]->of[mark] == MAGIC_NUMBER)
{
printf("tic-tac-toe! %c wins!\n", MarkToChar[mark]);
goto done;
}
}
}
}
printf("stalemate... nobody wins :(\n");
done:
return 0;
}
Ele compila e testa também.
% gcc -o tic-tac-toe tic-tac-toe.c
% ./tic-tac-toe
| |
---+---+---
| |
---+---+---
| |
Enter moves as " " (no quotes, zero indexed)
X's move: 1 2
| |
---+---+---
| | X
---+---+---
| |
O's move: 1 2
illegal move (already taken), try again
O's move: 3 3
illegal move (off the board), try again
O's move: 2 2
| |
---+---+---
| | X
---+---+---
| | O
X's move: 1 0
| |
---+---+---
X | | X
---+---+---
| | O
O's move: 1 1
| |
---+---+---
X | O | X
---+---+---
| | O
X's move: 0 0
X | |
---+---+---
X | O | X
---+---+---
| | O
O's move: 2 0
X | |
---+---+---
X | O | X
---+---+---
O | | O
X's move: 2 1
X | |
---+---+---
X | O | X
---+---+---
O | X | O
O's move: 0 2
X | | O
---+---+---
X | O | X
---+---+---
O | X | O
tic-tac-toe! O wins!
% ./tic-tac-toe
| |
---+---+---
| |
---+---+---
| |
Enter moves as " " (no quotes, zero indexed)
X's move: 0 0
X | |
---+---+---
| |
---+---+---
| |
O's move: 0 1
X | O |
---+---+---
| |
---+---+---
| |
X's move: 0 2
X | O | X
---+---+---
| |
---+---+---
| |
O's move: 1 0
X | O | X
---+---+---
O | |
---+---+---
| |
X's move: 1 1
X | O | X
---+---+---
O | X |
---+---+---
| |
O's move: 2 0
X | O | X
---+---+---
O | X |
---+---+---
O | |
X's move: 2 1
X | O | X
---+---+---
O | X |
---+---+---
O | X |
O's move: 2 2
X | O | X
---+---+---
O | X |
---+---+---
O | X | O
X's move: 1 2
X | O | X
---+---+---
O | X | X
---+---+---
O | X | O
stalemate... nobody wins :(
%
Isso foi divertido, muito obrigado!
Na verdade, pensando nisso, você não precisa de um quadrado mágico, apenas uma contagem para cada linha / coluna / diagonal. Isto é um pouco mais fácil do que generalizar um quadrado mágico para n × matrizes n, já que você só precisa contar até n.
Eu estava a mesma pergunta em uma das minhas entrevistas. Meus pensamentos: Inicializar a matriz com 0. Mantenha 3 matrizes 1) sum_row (tamanho n) 2) sum_column (tamanho n) 3) diagonal (tamanho 2)
Para cada jogada de (X) diminuir o valor da caixa por 1 e para cada jogada de (0) incremento-lo por 1. Em qualquer momento, se a linha / coluna / diagonal que foi modificado em movimento actual tem soma quer -3 ou três meios alguém ganhou o jogo. Para um empate podemos usar acima abordagem para manter a variável MoveCount.
Você acha que eu estou faltando alguma coisa?
Editar: O mesmo pode ser usado para a matriz nxn. Soma deve ser ainda +3 ou -3.
uma forma não-loop para determinar se o ponto estava no anti diag:
`if (x + y == n - 1)`
Eu fiz alguma otimização na linha, col, cheques diagonais. Sua decidiu principalmente no primeiro loop aninhado, se é preciso verificar uma determinada coluna ou diagonal. Então, nós evitar a verificação de colunas ou diagonais economizando tempo. Isso faz com grande impacto quando o tamanho da placa é mais e um número significativo de células não são preenchidos.
Aqui está o código java para isso.
int gameState(int values[][], int boardSz) {
boolean colCheckNotRequired[] = new boolean[boardSz];//default is false
boolean diag1CheckNotRequired = false;
boolean diag2CheckNotRequired = false;
boolean allFilled = true;
int x_count = 0;
int o_count = 0;
/* Check rows */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
for (int j = 0; j < boardSz; j++) {
if(values[i][j] == x_val)x_count++;
if(values[i][j] == o_val)o_count++;
if(values[i][j] == 0)
{
colCheckNotRequired[j] = true;
if(i==j)diag1CheckNotRequired = true;
if(i + j == boardSz - 1)diag2CheckNotRequired = true;
allFilled = false;
//No need check further
break;
}
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
/* check cols */
for (int i = 0; i < boardSz; i++) {
x_count = o_count = 0;
if(colCheckNotRequired[i] == false)
{
for (int j = 0; j < boardSz; j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
//No need check further
if(values[i][j] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
}
x_count = o_count = 0;
/* check diagonal 1 */
if(diag1CheckNotRequired == false)
{
for (int i = 0; i < boardSz; i++) {
if(values[i][i] == x_val)x_count++;
if(values[i][i] == o_val)o_count++;
if(values[i][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
}
x_count = o_count = 0;
/* check diagonal 2 */
if( diag2CheckNotRequired == false)
{
for (int i = boardSz - 1,j = 0; i >= 0 && j < boardSz; i--,j++) {
if(values[j][i] == x_val)x_count++;
if(values[j][i] == o_val)o_count++;
if(values[j][i] == 0)break;
}
if(x_count == boardSz)return X_WIN;
if(o_count == boardSz)return O_WIN;
x_count = o_count = 0;
}
if( allFilled == true)
{
for (int i = 0; i < boardSz; i++) {
for (int j = 0; j < boardSz; j++) {
if (values[i][j] == 0) {
allFilled = false;
break;
}
}
if (allFilled == false) {
break;
}
}
}
if (allFilled)
return DRAW;
return INPROGRESS;
}
Eu estou atrasado a festa, mas eu queria salientar um benefício que eu encontrei para usar uma magia quadrado, ou seja, que ele pode ser usado para obter uma referência para a praça que faria com que o ganho ou perda na próxima vez, ao invés de apenas sendo usado para calcular quando um jogo termina.
Tome este quadrado mágico:
4 9 2
3 5 7
8 1 6
Em primeiro lugar, criar um array scores que é incrementado toda vez que um movimento é feito. Consulte este resposta para mais detalhes. Agora, se nós ilegalmente jogar X duas vezes seguidas em [0,0] e [0,1], então a aparência de matriz scores como este:
[7, 0, 0, 4, 3, 0, 4, 0];
E a aparência de tabuleiro como este:
X . .
X . .
. . .
Então, todos nós temos que fazer a fim de obter uma referência para qual quadrado para ganhar / bloco é:
get_winning_move = function() {
for (var i = 0, i < scores.length; i++) {
// keep track of the number of times pieces were added to the row
// subtract when the opposite team adds a piece
if (scores[i].inc === 2) {
return 15 - state[i].val; // 8
}
}
}
Na realidade, a implementação requer alguns truques adicionais, como lidar com as teclas numeradas (em JavaScript), mas eu achei bastante simples e se a matemática recreativa.
Eu gosto deste algoritmo como ele usa um 1X9 vs representação 3x3 da placa.
private int[] board = new int[9];
private static final int[] START = new int[] { 0, 3, 6, 0, 1, 2, 0, 2 };
private static final int[] INCR = new int[] { 1, 1, 1, 3, 3, 3, 4, 2 };
private static int SIZE = 3;
/**
* Determines if there is a winner in tic-tac-toe board.
* @return {@code 0} for draw, {@code 1} for 'X', {@code -1} for 'Y'
*/
public int hasWinner() {
for (int i = 0; i < START.length; i++) {
int sum = 0;
for (int j = 0; j < SIZE; j++) {
sum += board[START[i] + j * INCR[i]];
}
if (Math.abs(sum) == SIZE) {
return sum / SIZE;
}
}
return 0;
}
Outra opção: gerar sua mesa com o código. Até simetria, existem apenas três maneiras de ganhar: linha borda, linha do meio, ou diagonais. Leve os três e colocá-los em torno de todas as formas possíveis:
def spin(g): return set([g, turn(g), turn(turn(g)), turn(turn(turn(g)))])
def turn(g): return tuple(tuple(g[y][x] for y in (0,1,2)) for x in (2,1,0))
X,s = 'X.'
XXX = X, X, X
sss = s, s, s
ways_to_win = ( spin((XXX, sss, sss))
| spin((sss, XXX, sss))
| spin(((X,s,s),
(s,X,s),
(s,s,X))))
Estas simetrias pode ter mais usos em seu código-playing game: se você chegar a um conselho que você já viu uma versão rodada da, você pode simplesmente pegar o valor em cache ou armazenados em cache melhor jogada do que um (e isso unrotate costas). Este é geralmente muito mais rápido do que avaliar o sub jogo.
(lançando esquerda e direita pode ajudar da mesma forma, não foi necessário aqui porque o conjunto de rotações dos padrões vencedores é espelho-simétricos.)
Aqui está uma solução que eu vim com, este armazena os símbolos como caracteres e usa int valor do char para descobrir se X ou O ganhou (olhar no código do Árbitro)
public class TicTacToe {
public static final char BLANK = '\u0000';
private final char[][] board;
private int moveCount;
private Referee referee;
public TicTacToe(int gridSize) {
if (gridSize < 3)
throw new IllegalArgumentException("TicTacToe board size has to be minimum 3x3 grid");
board = new char[gridSize][gridSize];
referee = new Referee(gridSize);
}
public char[][] displayBoard() {
return board.clone();
}
public String move(int x, int y) {
if (board[x][y] != BLANK)
return "(" + x + "," + y + ") is already occupied";
board[x][y] = whoseTurn();
return referee.isGameOver(x, y, board[x][y], ++moveCount);
}
private char whoseTurn() {
return moveCount % 2 == 0 ? 'X' : 'O';
}
private class Referee {
private static final int NO_OF_DIAGONALS = 2;
private static final int MINOR = 1;
private static final int PRINCIPAL = 0;
private final int gridSize;
private final int[] rowTotal;
private final int[] colTotal;
private final int[] diagonalTotal;
private Referee(int size) {
gridSize = size;
rowTotal = new int[size];
colTotal = new int[size];
diagonalTotal = new int[NO_OF_DIAGONALS];
}
private String isGameOver(int x, int y, char symbol, int moveCount) {
if (isWinningMove(x, y, symbol))
return symbol + " won the game!";
if (isBoardCompletelyFilled(moveCount))
return "Its a Draw!";
return "continue";
}
private boolean isBoardCompletelyFilled(int moveCount) {
return moveCount == gridSize * gridSize;
}
private boolean isWinningMove(int x, int y, char symbol) {
if (isPrincipalDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, PRINCIPAL))
return true;
if (isMinorDiagonal(x, y) && allSymbolsMatch(symbol, diagonalTotal, MINOR))
return true;
return allSymbolsMatch(symbol, rowTotal, x) || allSymbolsMatch(symbol, colTotal, y);
}
private boolean allSymbolsMatch(char symbol, int[] total, int index) {
total[index] += symbol;
return total[index] / gridSize == symbol;
}
private boolean isPrincipalDiagonal(int x, int y) {
return x == y;
}
private boolean isMinorDiagonal(int x, int y) {
return x + y == gridSize - 1;
}
}
}
Também aqui são os meus testes unitários para validar ele realmente funciona
import static com.agilefaqs.tdd.demo.TicTacToe.BLANK;
import static org.junit.Assert.assertArrayEquals;
import static org.junit.Assert.assertEquals;
import org.junit.Test;
public class TicTacToeTest {
private TicTacToe game = new TicTacToe(3);
@Test
public void allCellsAreEmptyInANewGame() {
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, BLANK, BLANK },
{ BLANK, BLANK, BLANK } });
}
@Test(expected = IllegalArgumentException.class)
public void boardHasToBeMinimum3x3Grid() {
new TicTacToe(2);
}
@Test
public void firstPlayersMoveMarks_X_OnTheBoard() {
assertEquals("continue", game.move(1, 1));
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, 'X', BLANK },
{ BLANK, BLANK, BLANK } });
}
@Test
public void secondPlayersMoveMarks_O_OnTheBoard() {
game.move(1, 1);
assertEquals("continue", game.move(2, 2));
assertBoardIs(new char[][] { { BLANK, BLANK, BLANK },
{ BLANK, 'X', BLANK },
{ BLANK, BLANK, 'O' } });
}
@Test
public void playerCanOnlyMoveToAnEmptyCell() {
game.move(1, 1);
assertEquals("(1,1) is already occupied", game.move(1, 1));
}
@Test
public void firstPlayerWithAllSymbolsInOneRowWins() {
game.move(0, 0);
game.move(1, 0);
game.move(0, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(0, 2));
}
@Test
public void firstPlayerWithAllSymbolsInOneColumnWins() {
game.move(1, 1);
game.move(0, 0);
game.move(2, 1);
game.move(1, 0);
game.move(2, 2);
assertEquals("O won the game!", game.move(2, 0));
}
@Test
public void firstPlayerWithAllSymbolsInPrincipalDiagonalWins() {
game.move(0, 0);
game.move(1, 0);
game.move(1, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(2, 2));
}
@Test
public void firstPlayerWithAllSymbolsInMinorDiagonalWins() {
game.move(0, 2);
game.move(1, 0);
game.move(1, 1);
game.move(2, 1);
assertEquals("X won the game!", game.move(2, 0));
}
@Test
public void whenAllCellsAreFilledTheGameIsADraw() {
game.move(0, 2);
game.move(1, 1);
game.move(1, 0);
game.move(2, 1);
game.move(2, 2);
game.move(0, 0);
game.move(0, 1);
game.move(1, 2);
assertEquals("Its a Draw!", game.move(2, 0));
}
private void assertBoardIs(char[][] expectedBoard) {
assertArrayEquals(expectedBoard, game.displayBoard());
}
}
solução completa: https://github.com/nashjain/tictactoe/tree/master / java
Como sobre uma abordagem seguinte por 9 ranhuras? Declare 9 variáveis ??inteiras para uma matriz 3x3 (a1, a2 .... a9) onde a1, a2, a3 representam fileira-1 e A1, A4, A7 formariam coluna-1 (essa é a idéia). Use '1' para indicar Player-1 e '2' para indicar Player-2.
Existem 8 possíveis combinações de vitória: Win-1: A1 + A2 + A3 (resposta poderia ser 3 ou 6 com base em qual jogador venceu) Win-2: a4 + a5 + a6 Win-3: a7 + a8 + a9 Win-4: a1 + a4 + a7 .... Win-7: a1 + a5 + a9 Win-8: a3 + a5 + a7
Agora sabemos que se o jogador atravessa a1 então precisamos soma reavaliar de 3 variáveis: Win-1, Win-4 e Win-7. Qualquer que seja o 'Win-? variáveis ??atinge 3 ou 6 primeiros ganha o jogo. Se Win-1 variável atinge 6 primeiro e depois Player-2 vitórias.
Eu entendo que esta solução não é escalável facilmente.
Esta é uma maneira realmente simples de verificar.
public class Game() {
Game player1 = new Game('x');
Game player2 = new Game('o');
char piece;
Game(char piece) {
this.piece = piece;
}
public void checkWin(Game player) {
// check horizontal win
for (int i = 0; i <= 6; i += 3) {
if (board[i] == player.piece &&
board[i + 1] == player.piece &&
board[i + 2] == player.piece)
endGame(player);
}
// check vertical win
for (int i = 0; i <= 2; i++) {
if (board[i] == player.piece &&
board[i + 3] == player.piece &&
board[i + 6] == player.piece)
endGame(player);
}
// check diagonal win
if ((board[0] == player.piece &&
board[4] == player.piece &&
board[8] == player.piece) ||
board[2] == player.piece &&
board[4] == player.piece &&
board[6] == player.piece)
endGame(player);
}
}
Se você tem campo boarder 5 * 5, por exemplo, eu uso o seguinte método de verificação:
public static boolean checkWin(char symb) {
int SIZE = 5;
for (int i = 0; i < SIZE-1; i++) {
for (int j = 0; j <SIZE-1 ; j++) {
//vertical checking
if (map[0][j] == symb && map[1][j] == symb && map[2][j] == symb && map[3][j] == symb && map[4][j] == symb) return true; // j=0
}
//horisontal checking
if(map[i][0] == symb && map[i][1] == symb && map[i][2] == symb && map[i][3] == symb && map[i][4] == symb) return true; // i=0
}
//diagonal checking (5*5)
if (map[0][0] == symb && map[1][1] == symb && map[2][2] == symb && map[3][3] == symb && map[4][4] == symb) return true;
if (map[4][0] == symb && map[3][1] == symb && map[2][2] == symb && map[1][3] == symb && map[0][4] == symb) return true;
return false;
}
Eu acho, é mais clara, mas provavelmente não é a forma mais adequada.
Aqui está a minha solução usando uma matriz de 2 dimensões:
private static final int dimension = 3;
private static final int[][] board = new int[dimension][dimension];
private static final int xwins = dimension * 1;
private static final int owins = dimension * -1;
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
int count = 0;
boolean keepPlaying = true;
boolean xsTurn = true;
while (keepPlaying) {
xsTurn = (count % 2 == 0);
System.out.print("Enter i-j in the format:");
if (xsTurn) {
System.out.println(" X plays: ");
} else {
System.out.println(" O plays: ");
}
String result = null;
while (result == null) {
result = parseInput(scanner, xsTurn);
}
String[] xy = result.split(",");
int x = Integer.parseInt(xy[0]);
int y = Integer.parseInt(xy[1]);
keepPlaying = makeMove(xsTurn, x, y);
count++;
}
if (xsTurn) {
System.out.print("X");
} else {
System.out.print("O");
}
System.out.println(" WON");
printArrayBoard(board);
}
private static String parseInput(Scanner scanner, boolean xsTurn) {
String line = scanner.nextLine();
String[] values = line.split("-");
int x = Integer.parseInt(values[0]);
int y = Integer.parseInt(values[1]);
boolean alreadyPlayed = alreadyPlayed(x, y);
String result = null;
if (alreadyPlayed) {
System.out.println("Already played in this x-y. Retry");
} else {
result = "" + x + "," + y;
}
return result;
}
private static boolean alreadyPlayed(int x, int y) {
System.out.println("x-y: " + x + "-" + y + " board[x][y]: " + board[x][y]);
if (board[x][y] != 0) {
return true;
}
return false;
}
private static void printArrayBoard(int[][] board) {
for (int i = 0; i < dimension; i++) {
int[] height = board[i];
for (int j = 0; j < dimension; j++) {
System.out.print(height[j] + " ");
}
System.out.println();
}
}
private static boolean makeMove(boolean xo, int x, int y) {
if (xo) {
board[x][y] = 1;
} else {
board[x][y] = -1;
}
boolean didWin = checkBoard();
if (didWin) {
System.out.println("keep playing");
}
return didWin;
}
private static boolean checkBoard() {
//check horizontal
int[] horizontalTotal = new int[dimension];
for (int i = 0; i < dimension; i++) {
int[] height = board[i];
int total = 0;
for (int j = 0; j < dimension; j++) {
total += height[j];
}
horizontalTotal[i] = total;
}
for (int a = 0; a < horizontalTotal.length; a++) {
if (horizontalTotal[a] == xwins || horizontalTotal[a] == owins) {
System.out.println("horizontal");
return false;
}
}
//check vertical
int[] verticalTotal = new int[dimension];
for (int j = 0; j < dimension; j++) {
int total = 0;
for (int i = 0; i < dimension; i++) {
total += board[i][j];
}
verticalTotal[j] = total;
}
for (int a = 0; a < verticalTotal.length; a++) {
if (verticalTotal[a] == xwins || verticalTotal[a] == owins) {
System.out.println("vertical");
return false;
}
}
//check diagonal
int total1 = 0;
int total2 = 0;
for (int i = 0; i < dimension; i++) {
for (int j = 0; j < dimension; j++) {
if (i == j) {
total1 += board[i][j];
}
if (i == (dimension - 1 - j)) {
total2 += board[i][j];
}
}
}
if (total1 == xwins || total1 == owins) {
System.out.println("diagonal 1");
return false;
}
if (total2 == xwins || total2 == owins) {
System.out.println("diagonal 2");
return false;
}
return true;
}
tempo O Constant (8), em média, 4 curto e de. Jogador = número curto. Precisa de verificações adicionais para certificar-se de movimento é válido.
// O(8)
boolean isWinner(short X) {
for (int i = 0; i < 8; i++)
if ((X & winCombinations[i]) == winCombinations[i])
return true;
return false;
}
short[] winCombinations = new short[]{
7, 7 << 3, 7 << 6, // horizontal
73, 73 << 1, 73 << 2, // vertical
273, // diagonal
84 // anti-diagonal
};
for (short X = 0; X < 511; X++)
System.out.println(isWinner(X));
I desenvolvido um algoritmo para isso como parte de um projeto de ciência uma vez.
Você basicamente recursivamente dividir a placa em um monte de sobreposição rects 2x2, testando diferentes combinações possíveis para ganhar em um quadrado de 2x2.
É um processo lento, mas tem a vantagem de trabalhar em qualquer placa de tamanho, com requisitos de memória bastante linear.
Eu gostaria de poder encontrar minha implementação
