Если разработчик не может написать четкие, лаконичные и грамматически правильные комментарии, он должен вернуться и взять английский язык 101.
У нас есть разработчики и (ужасы) архитекторы, которые не могут писать связно. Когда их документы проверяются, они говорят что-то вроде «о, не беспокойтесь о грамматических ошибках или орфографии - это не важно». Затем они задаются вопросом, почему их запутанные мусорные документы превращаются в запутанный глючный код.
Я говорю стажерам, что наставляю, что если вы не можете донести свои великие идеи в устной или письменной форме, у вас также может не быть их.
Вы знаете, что выигрышный ход может произойти только после того, как X или O сделали свой последний ход, поэтому вы можете искать строку / столбец только с необязательной диагональю которые содержатся в этом движении, чтобы ограничить ваше пространство поиска при попытке определить выигрышную доску. Кроме того, поскольку в игре в крестики-нолики с ничьей есть фиксированное количество ходов, после того как был сделан последний ход, если он не был выигрышным, по умолчанию это игра с ничьей.
edit: этот код предназначен для n n доска с n в строке для победы (3x3 платы 3 подряд и т. д.)
edit: добавлен код для проверки анти-диагноза, я не мог найти способ без цикла, чтобы определить, была ли точка антидиаг, поэтому этот шаг отсутствует
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
}
}
}
Если размер платы n × n , то имеется n строк, n столбцов, и 2 диагонали. Чтобы найти победителя, проверьте каждое из них на все-X или все-O.
Если для победы требуется только x < n последовательных квадратов, тогда все будет немного сложнее . Наиболее очевидное решение - проверить каждый квадрат x × x на победителя. Вот код, который это демонстрирует.
(Я на самом деле не тестировал этот * кашель *, но он скомпилировал с первой попытки, ура!)
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;
}
}
}
Как насчет этого псевдокода:
После того, как игрок кладет кусок в позицию (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
Я бы использовал массив char [n, n], с O, X и пробелом для пустого.
вы можете использовать магический квадрат http://mathworld.wolfram.com/MagicSquare.html , если любая строка, столбец или диагональ в сумме дают 15, тогда игрок выиграла.
Я не очень хорошо знаю Java, но я знаю C, поэтому я попробовал идею магического квадрата adk (вместе с ограничением поиска 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;
}
Он хорошо компилируется и тестируется.
% 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 :( %
Это было весело, спасибо!
На самом деле, если подумать, вам не нужен магический квадрат, просто счет для каждой строки / столбца / диагонали. Это немного проще, чем обобщение магического квадрата до матриц n
× n
, поскольку вам просто нужно посчитать до n
.
Я однажды разработал алгоритм для этого в рамках научного проекта.
Вы, по сути, рекурсивно делите доску на кучу перекрывающихся прямоугольников 2x2, проверяя различные возможные комбинации для выигрыша на Квадрат 2x2.
Это медленно, но у него есть преимущество, заключающееся в том, что он работает на плате любого размера с довольно линейными требованиями к памяти.
Хотел бы я найти свою реализацию
This is similar to Osama ALASSIRY's answer, but it trades constant-space and linear-time for linear-space and constant-time. That is, there's no looping after initialization.
Initialize a pair (0,0)
for each row, each column, and the two diagonals (diagonal & anti-diagonal). These pairs represent the accumulated (sum,sum)
of the pieces in the corresponding row, column, or diagonal, where
A piece from player A has value (1,0) A piece from player B has value (0,1)
When a player places a piece, update the corresponding row pair, column pair, and diagonal pairs (if on the diagonals). If any newly updated row, column, or diagonal pair equals either (n,0)
or (0,n)
then either A or B won, respectively.
Asymptotic analysis:
O(1) time (per move) O(n) space (overall)
For the memory use, you use 4*(n+1)
integers.
two_elements*n_rows + two_elements*n_columns + two_elements*two_diagonals = 4*n + 4 integers = 4(n+1) integers
Exercise: Can you see how to test for a draw in O(1) time per-move? If so, you can end the game early on a draw.