He escrito un juego de tres en raya en Java, y mi método actual para determinar el final del juego tiene en cuenta los siguientes escenarios posibles para que el juego termine:
Desafortunadamente, para hacerlo, lee un conjunto predefinido de estos escenarios de una tabla. Esto no es necesariamente malo teniendo en cuenta que sólo hay 9 espacios en un tablero, y por lo tanto la tabla es algo pequeña, pero ¿hay una mejor manera algorítmica de determinar si el juego ha terminado? La determinación de si alguien ha ganado o no es el meollo del problema, ya que comprobar si 9 espacios están llenos es trivial.
El método de la mesa podría ser la solución, pero si no lo es, ¿cuál? Además, ¿qué pasaría si el tablero no fuera de tamaño n=9
? ¿Y si fuera un tablero mucho más grande, digamos n=16
, n=25
, etc., haciendo que el número de elementos colocados consecutivamente para ganar fuera x=4
, x=5
, etc? ¿Un algoritmo general para todo n = { 9, 16, 25, 36 ... }
?
Sabes que un movimiento ganador sólo puede ocurrir después de que X u O haya hecho su movimiento más reciente, así que sólo puedes buscar filas/columnas con diag opcionales que estén contenidas en ese movimiento para limitar tu espacio de búsqueda cuando intentes determinar un tablero ganador. Además, dado que hay un número fijo de movimientos en una partida de tres en raya, una vez que se ha hecho el último movimiento, si no ha sido un movimiento ganador, es por defecto una partida en raya.
edit: este código es para un tablero de n por n con n en una fila para ganar (tablero de 3x3 requiere 3 en una fila, etc)
edit: añadido código para comprobar el anti diag, no pude encontrar una manera de determinar si el punto estaba en el anti diag, por eso falta ese paso.
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
}
}
}
puedes usar un cuadrado mágico http://mathworld.wolfram.com/MagicSquare.html si cualquier fila, columna o diag suma 15 entonces un jugador ha ganado.
Si el tablero es n &veces; n entonces hay n filas, n columnas y 2 diagonales. Compruebe cada uno de ellos para todos-X's o todos-O's para encontrar un ganador.
Si sólo se necesitan x < n casillas consecutivas para ganar, entonces es un poco más complicado. La solución más obvia es comprobar cada x < veces; x cuadrado para un ganador. Aquí'hay algo de código que lo demuestra.
(En realidad no lo he probado, pero compiló a la primera, ¡bien por mí!).
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;
}
}
}