Простой алгоритм проверки победы в крести-нолики на не стандартном поле

в 15:45, , рубрики: крестики-нолики, проверка победы, Учебный процесс в IT

Столкнулся с такой проблемой, что молодым программистам, которые только начинают изучение языков, алгоритмы вызывают больше трудностей, чем синтаксис языка. Если сам синтаксис и концепцию объяснит преподаватель по конкретному языку, то алгоритмы вам придется придумывать самим. Исключением из правил могут быть только специализированные технические специальности в ВУЗах, где преподают именно алгоритмы.

При том, что алгоритм решения может быт очень простым многие не знают как подойти к решению задачи. Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 6х6 и блоком подряд заполненных значений равному 4-м.

На самом деле, здесь представлен универсальный алгоритм, только вместо переменных я использовал константы. И это практически не зависит от языка, котором эта проверка осуществляется. Я предлагаю начинающим программистам сначала решить задачу графически, а затем уже перевести ее на тот или иной язык. Для создания этого алгоритма подойдет листок в клетку и ручка.

Итак, у нас есть поле 6х6.

image

Блок последовательно заполненных элементов, который достаточен, чтобы выиграть, равен 4-м.

image

Думаю, что теперь (всего лишь поле двух рисунков) стало намного понятнее, как решить эту задачу.

Фактически мы должны решить 2 независимые задачи:

  1. Найти все заполненные последовательности в блоке 4х4.
  2. Найти все квадраты 4х4 в квадрате 6х6.

1. Найти все заполненные последовательности в блоке 4х4

Почему проверяем блок 4х4? Все просто в нем возможно только 2 диагонали такой размерности, которая нам нужна.

Используя двоичную логику (1&1=1 и 1&0=0) мы можем легко сделать проверку циклами. Для этого нам нужна 1 переменная для каждой диагонали. Пусть toright – логическая переменная в которую пишем результат проверки диагонали сверху слева вниз направо. И toleft для проверки диагонали сверху справа вниз налево.

Первоначально выставим значение true для этих переменных. Дальше мы сравниваем каждую клетку в диагонали с символом «Х» или «О». Конечно, мы делаем это 2-мя вызовами либо все сравниваем с «Х», либо все с «О».

Каждую клеточку диагонали мы сравниваем с нашим символом и получаем результат (true) или (false). Затем делам логическую операцию (&) между полученным результатом и нашей toright. Результат этой операции пишем опять в toright. Если на каком-то этапе мы получим результат (false), то все дальнейшие toright всегда будут равны (false). Это следует из правила логических операций (1&0=0).

Напишем это на Jave:

boolean checkDiagonal(char symb) { 
	boolean toright = true; // установили логическое значение 1
	for (int i=0; i<4; i++) { // Блок от 0 до 3
		toright = toright & (map[i][i] == symb); 
	}
	
	// Дальше мы вернули (true), если во всех клетках нам встретились символы symb
	if (toright) return true;	

	// или вернули (false), если встретился хоть один символ, отличный от symb
	return false; 
}

Собственно вот в этой строчке

toright = toright & (map[i][i] == symb))

и есть вся логика.

Краткая запись выглядит так:

toright &= (map[i][i] == symb))

Получаются только 2 результата работы условия:

toright = toright & 0
или
toright = toright & 1

Для 2-х диагоналей, полный код функции будет выглядеть так:

/** Проверяем диагонали */
boolean checkDiagonal(char symb) { 
	boolean toright, toleft;
	toright = true;
	toleft = true;
	for (int i=0; i<4; i++) {
		toright &= (map[i][i] == symb);
		toleft &= (map[4-i-1][i] == symb);
	}
		
	if (toright || toleft) return true;
		
	return false; 
}

Полный аналог делается для проверки вертикалей и горизонталей, только циклы меняются.

/** Проверяем горизонтальные и вертикальные линии */
boolean checkLanes(char symb) { 
	boolean cols, rows;
	for (int col=0; col<4; col++) {
		cols = true;
		rows = true;
		for (int row=0; row<4; row++) {
			cols &= (map[col][row] == symb);
			rows &= (map[row][col] == symb);
		}
			
		// Это условие после каждой проверки колонки и столбца
		// позволяет остановить дальнейшее выполнение, без проверки 
		// всех остальных столбцов и строк.
		if (cols || rows) return true; 
	}
		
	return false; 
}

Собственно это и есть решение для блока 4х4. Как видно из кода, для другого блока нужно только поменять 4 в цикле на другое число, или написать вместо числа имя переменной. Причем эту переменную вы можете сделать как глобальной видимости, так и передать в функцию, например так:

boolean checkLanes(char symb, int block)…..

2. Найти все квадраты 4х4 в квадрате 6х6

Собственно, их не так много. Начиная с позиции [0,0], [1,0] и [2,0] для первой строки квадрата, [0,1], [1,1] и [2,1] для второй, [0,2], [1,2] и [2,2] для третьей. Дальше квадрат 4х4 выйдет за границы квадрата 6х6.

Такой перебор координат вполне можем сделать циклами:

boolean checkWin(char symb) { 
	for (int col=0; col<3; col++) { 
		for (int row=0; row<3; row++) {
			// Вызываем методы проверки и если хоть один блок заполнен,
			// то игрок, который проставляет это символ, выиграл
			// иначе продолжаем для другого смещения
			if (checkDiagonal(symb, col, row) || checkLanes(symb, col, row)) return true;
		}	
	}
	// Все подквадраты в квадрате проверены. 4-х последовательностей
	// подряд не выявлено. Значит еще не победа.
	return false; 
}

Тут нам придется немного модифицировать методы checkDiagonal и checkLanes, поскольку мы должны проверять квадрат 4х4 с соответствующим смещением.

int size = 6; // размер квадратного поля
int block = 4; // размер блока

boolean checkLanes(char symb, int offsetX, int offsetY) { 
	boolean cols, rows;
	for (int col=offsetX; col<block+offsetX; col++) {
		cols = true;
		rows = true;
		for (int row=offsetY; row<block+offsetY; row++) {
			cols &= (map[col][row] == symb);
			rows &= (map[row][col] == symb);
		}
		
		if (cols || rows) return true;
	}
		
	return false; 
}

Начинающим программистам я бы рекомендовал самим модифицировать код checkDiagonal, т.к. это позволит лучше понять принцип работы.

И еще один совет. В настоящий момент имеется огромное количество реализаций различных алгоритмов в сети на разных языках. Если вы хотите научиться думать, то смотрите именно принципы решений (алгоритмы), не привязанные к языкам. Готовые решения не позволят вам быстро научиться выбирать наиболее оптимальный вариант решения. Очень часто, переписать готовое решение с одного языка на другой, можно не понимая принципа решения задачи. Где-то это вам поможет, а где-то может сделать дальнейшее развитие программы невозможным без изменения ее логики.

Сначала я рекомендую попробовать написать проверку самостоятельно. Шаблон игры можно забрать здесь. Там уже есть заголовки функций, которые я описал в статье. Осталось скопировать в шаблон часть моего кода и чуть-чуть его модифицировать. А вот здесь можно скачать полный рабочий код на Java. Рекомендую смотреть его уже после того, как вы написали свои функции на основе этой статьи.

Автор: SecondUniverse

Источник


* - обязательные к заполнению поля


https://ajax.googleapis.com/ajax/libs/jquery/3.4.1/jquery.min.js