При том, что алгоритм решения может быт очень простым многие не знают как подойти к решению задачи. Я рассмотрю пример проверки победы в игре крестики-нолики, но на поле 6х6 и блоком подряд заполненных значений равному 4-м.
На самом деле, здесь представлен универсальный алгоритм, только вместо переменных я использовал константы. И это практически не зависит от языка, котором эта проверка осуществляется. Я предлагаю начинающим программистам сначала решить задачу графически, а затем уже перевести ее на тот или иной язык. Для создания этого алгоритма подойдет листок в клетку и ручка.
Итак, у нас есть поле 6х6.
Блок последовательно заполненных элементов, который достаточен, чтобы выиграть, равен 4-м.
Думаю, что теперь (всего лишь поле двух рисунков) стало намного понятнее, как решить эту задачу.
Фактически мы должны решить 2 независимые задачи:
- Найти все заполненные последовательности в блоке 4х4.
- Найти все квадраты 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. Рекомендую смотреть его уже после того, как вы написали свои функции на основе этой статьи.
Комментарии (23)
Deosis
24.05.2017 06:34+3if (toright || toleft) return true; return false;
Код прямо из книги вредных советов.
Предложенный алгоритм представляет из себя тупой перебор.
Центральные линии проверяются по нескольку раз.Sinatr
24.05.2017 11:15+1Ага, в статье с заголовком «алгоритм», его-то и забыли завезти. Это конечно лучше, чем полная неспособность решить задачу (кто-бы спорил), но решить ее «как-нибудь» и запилить статью — даже не знаю. Отпишитесь ниже те, кто вникнул и нашел рассказанное полезным или интересным (хотя каюсь, первые абзацы захватили развитием сюжета). Прямо аж самому захотелось написать статью побесполезнее…
k0rsh
24.05.2017 17:15Вот, кстати, да. Тоже не очень понятно в чем принципиальная необходимость возврата true и отдельно false.
return ( toleft || toright )
Чем не вариант?
rodgar
24.05.2017 17:15-1Да, мне тоже кажется что алгоритмически лучше зайти с другой стороны. В блоке размером N есть N горизонтальных, N вертикальных и 2 диагональные линии. Заранее подготовим список этих линий [h1, h2,… hN, v1, v2,… vN, ld, rd]. Дальше пойдем по исходному блоку и для всех нулевых ячеек будем выбрасывать линии имеющие эту ячейки. Оставшиеся в списке после полного прохода: выигрышные. Можно оптимизировать, построив не только список возможных линий но и карту входимости ячеек в линии. Можно оптимизировать путь обхода блока, не последовательно строка за строкой а по спирали. Можно оптимизировать крайние случаи: когда обошли только треть блока, а в списке осталась одна линия, лучше проверить оставшиеся ячейки этой линии.
Так что дети, брать чужой код не разобравшись плохо еще и потому, что разобравшись в алгоритме вы поймете, что он не очень то и хорош. Перефразируя поговорку про золото, «Не все то O(n), что алгоритм».
GlukKazan
24.05.2017 09:50+2Если говорить о разработке настольных игр, на первый план выходит производительность. В более менее серьёзных играх (типа Рендзю), подобные проверки будут выполняться сотни тысяч раз за игру. Описанный в статье алгоритм сильно избыточен, в самой постановке задачи. Я не знаю ни одной игры в которой требовалось бы искать ряд из фигур, расположенный на доске неизвестно где. Ряд возникает не просто так, а с добавлением в него очередной фигуры. Это означает, что мы всегда знаем хотя бы одну позицию входящую в ряд (то поле, на котором завершила движение последняя сходившая фигура). Это верно и для тех игр, где фигуры могут убираться с доски (Пенте, Хасами Сёги) и для тех игр, где фигуры двигаются (Мельница, Хасами Сёги). В Мельнице может возникнуть задача поиска ряда противника, но опять же, мы ищем этот ряд в связи с правилом о том, что в первую очередь, должны удаляться фигуры не входящие в ряд. То есть мы снова знаем с какого поля начинать поиск ряда. Так что статья действительно из цикла вредных советов.
znalexej
24.05.2017 12:08+1Буквально неделю назад делал на заказ игру «Пять в ряд» на поле 15х15. GlukKazan верно указал, что проверять диагонали/вертикали/горизонтали надо от поставленного значка, а не искать последовательности каждый раз по всему полю. Код будет сложнее, но быстрее.
По коду автора невозможно определить выигрышную последовательность значков, чтобы потом как-то ее выделить на игровом поле (это требовалось в моем заказе).GlukKazan
24.05.2017 12:20Вообще говоря, можно пойти ещё дальше и хранить длины рядов (по 8 направлениям) в свойствах каждой фигуры на доске. Это незначительно замедлит выполнение хода, но значительно упростит поиск рядов (при постановке нового камня просто смотрим счётчики соседей и инкрементируем). Как-то вот так (этот код пока не протестирован!).
SecondUniverse
24.05.2017 17:08Я согласен. Статья для тех, кто вообще не понимает как подойти к проблеме. Надеюсь, что он просто поможет начать думать, какие подходы вообще могут быть.
GlukKazan
24.05.2017 17:34Как раз для таких статья максимально вредна.
SecondUniverse
24.05.2017 18:28Я не верю, что вы гениальны настолько, что вам в первом классе дали решать дифуры в частных производных или хотя бы уравнение с 3-мя неизвестными. Когда человек проверяет поле 3x3 через if (map[1][1] && ...) этот вариант как раз для него. Он на этом этапе больше не поймет. По-моему заголовок статьи это как раз отражает.
GlukKazan
24.05.2017 18:57Ваша статья — сборник плохих советов. Тот читатель на которого Вы ориентируетесь… да пусть он лучше сам до всего доходит, чем учится у Вас плохому. Впрочем, если ему (читателю) захочется, я не смогу ему в этом помешать, да и нет у меня такого желания. Но увидев подобную статью я просто обязан предупредить, насколько она плохая. Разумеется, это не относится к Вам лично. Речь идёт только о статье.
LoadRunner
25.05.2017 09:08Чтобы узнать правильный ответ — напиши неправильный.
Комментарии к статье — вот ради чего статье стоит жить :)
И добавлять в избранное.
kostus1974
24.05.2017 14:34а разве не все начинали программировать с игр типа «три в ряд»? ))
я не читал: в статье какой-то особый метод, считающий одинаковых соседей в 3 раза быстрей, чем что-либо?
P.S.: а почему бы и нет? завести рубрику «юные программисты», куда постить статьи школьников (в прямом смысле). может быть интересно, как они там яблочки считают или домики рисуют. я бы почитал )
zlowred
24.05.2017 17:09Если это решение именно задачи "определить, выигрышна ли заданная позиция в игре крестики-нолики", то решение не верное. Оно не учитывает "невозможные" ситуации, как та, которая представлена на второй иллюстрации (нолики ни разу не сходили, правильный ответ — "крестики мухлюют", а не "крестики выиграли"), не учитывает ситуации, когда кто-то выиграл дважды (две выигрышных ситуации на одном поле, за исключением частных случаев вроде пересекающихся выигрышных комбинаций), не учитывает ситуаций, когда игра была продолжена после выигрыша одной из сторон, или когда выиграли обе стороны.
tmnhy
Но… Но, зачем? Зачем это, какая практическая ценность от решения частной задачи?
Это вопрос не к автору, а к тем кто в избранное добавил…
gleber1
Что за снобизм
tmnhy
И вы столько всего увидели в простом вопросе о целесообразности?
Мне было бы интересно посмотреть решение-исследование для неограниченного поля и победной комбинации любой длины, зачем искусственные ограничения:
Почему именно такие условия, почему не использовать общее решение? В чём практическая ценность задачи? Она логично выглядела бы как часть общей задачи о, например, стратегии игры. Но вот так… Мне непонятно, поэтому и спросил, зачем читатели сохраняют в избранное, если это не боты, конечно.
dlf42
Автор таки представил универсальный алгоритм, но продемонстрировал его на этих значениях. Можно было бы сделать это более заметно.
tmnhy
Также, как и оценить сложность алгоритма.
SecondUniverse
Я не очень хотел публиковать в статье уж совсем готовое решение. Я пытался показать как можно графически сделать самое простое решение для двумерного массива и чтобы новичок увидел путь. Спасибо вам за комментарий. Пока, пожалуй, вы единственный кто высказался по делу.