Форум программистов, компьютерный форум, киберфорум
Matlab
Войти
Регистрация
Восстановить пароль
 
Рейтинг 4.89/9: Рейтинг темы: голосов - 9, средняя оценка - 4.89
2 / 2 / 2
Регистрация: 01.04.2014
Сообщений: 92
1

Закрасить все клетки доски ходами коня

09.01.2020, 23:02. Просмотров 1726. Ответов 4


Пытаюсь решить такую задачу, вот что набросал уже
Основная программа
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
clear;
clc;
 
n=input('Input quad size: ');
 
if n>=5
    quadrat = zeros(n,n); % создание доски
else
    disp('Need 5 and more for this task');
end
 
% стартовые координаты коня
x=input('Input the first position of horse by x: ');
y=input('Input the first position of horse by y: ');
 
if x>0 && y>0
    quadrat(x,y) = 1;
else
    disp('Horse cannot have a negative position');
end
 
disp(quadrat);
 
newcoord = checkturn(quadrat,n,x,y); % получение первых newcoord, то есть узнаем первый ход
 
disp(newcoord);
 
while ismember(0, quadrat) % пока есть незакрашенные клетки
    quadrat(newcoord.x,newcoord.y) = 1; % прыжок коня на новое поле
    newcoord = checkturn(quadrat,n,newcoord.x,newcoord.y); % получение новых координат для прыжка
    disp(quadrat);
end


Функция вычисления первого хода
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function newcoord = checkturn(quadrat,n,x,y)
weightofturn = zeros(8); % массив с кол-вом возможных ходов из данной клетки
coordsofturnx = [2 2 -2 -2 1 1 -1 -1]; %все возможные ходы коня
coordsofturny = [1 -1 1 -1 2 -2 2 -2];
 
weightofturn(1) = checksecondturn(quadrat,n,x,y,coordsofturnx(1),coordsofturny(1)); % вычисление кол-ва доступных ходов
weightofturn(2) = checksecondturn(quadrat,n,x,y,coordsofturnx(2),coordsofturny(2));
weightofturn(3) = checksecondturn(quadrat,n,x,y,coordsofturnx(3),coordsofturny(3));
weightofturn(4) = checksecondturn(quadrat,n,x,y,coordsofturnx(4),coordsofturny(4));
weightofturn(5) = checksecondturn(quadrat,n,x,y,coordsofturnx(5),coordsofturny(5));
weightofturn(6) = checksecondturn(quadrat,n,x,y,coordsofturnx(6),coordsofturny(6));
weightofturn(7) = checksecondturn(quadrat,n,x,y,coordsofturnx(7),coordsofturny(7));
weightofturn(8) = checksecondturn(quadrat,n,x,y,coordsofturnx(8),coordsofturny(8));
 
[minval,ind] = min(weightofturn); % отсечение вариантов, где нельзя походить и нахождение варианта с минимальным кол-вом возможных ходов
while minval == 0
    weightofturn(ind) = 10;
    [minval,ind] = min(weightofturn);
end
 
 
newcoord.x = x + coordsofturnx(ind); % получение новых координат как суммы старых + смещение
newcoord.y = y + coordsofturny(ind);
end


Функция вычисления второго хода
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
function [val] = checksecondturn(quadrat,n,x,y,qx,qy)
val = 0; % кол-во возможных ходов
if x+qx<=n && x+qx>=1 && y+qy<=n && y+qy>=1 && quadrat(x+qx,y+qy) == 0 % если возможен первый ход
    if x+qx+2<=n && y+qy+1<=n && quadrat(x+qx+2,y+qy+1) == 0 % проверяется возможность сделать второй ход
        val = val + 1; % увеличивается кол-во возможных ходов
    end
    if x+qx+2<=n && y+qy-1>=1 && quadrat(x+qx+2,y+qy-1) == 0
        val = val + 1;
    end
    if x+qx-2>=1 && y+qy+1<=n && quadrat(x+qx-2,y+qy+1) == 0
        val = val + 1;
    end
    if x+qx-2>=1 && y+qy-1>=1 && quadrat(x+qx-2,y+qy-1) == 0
        val = val + 1;
    end
    if x+qx+1<=n && y+qy+2<=n && quadrat(x+qx+1,y+qy+2) == 0
        val = val + 1;
    end
    if x+qx+1<=n && y+qy-2>=1 && quadrat(x+qx+1,y+qy-2) == 0
        val = val + 1;
    end
    if x+qx-1>=1 && y+qy+2<=n && quadrat(x+qx-1,y+qy+2) == 0
        val = val + 1;
    end
    if x+qx-1>=1 && y+qy-2>=1 && quadrat(x+qx-1,y+qy-2) == 0
        val = val + 1;
    end
end
end

Пример работы программы

Input quad size: 5
Input the first position of horse by x: 1
Input the first position of horse by y: 1
1 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0
0 0 0 0 0

x: [2 3 3 3 3 3 3 3]
y: [3 2 2 2 2 2 2 2]

Operands to the || and && operators must be convertible to logical scalar values.

Error in checksecondturn (line 3)
if x+qx<=n && x+qx>=1 && y+qy<=n && y+qy>=1 && quadrat(x+qx,y+qy) == 0

Error in checkturn (line 6)
weightofturn(1) = checksecondturn(quadrat,n,x,y,coordsofturnx(1),coordsofturny (1));

Error in quad (line 29)
newcoord = checkturn(quadrat,n,newcoord.x,newcoord.y);



Не могу понять
1) В чем суть выдаваемых ошибок?
2) Почему структура newcoord выводит 8 значений, когда прошёл только один цикл?

Может еще какие логические ошибки, если кто увидит - буду благодарен.
0
Лучшие ответы (1)
Programming
Эксперт
94731 / 64177 / 26122
Регистрация: 12.04.2006
Сообщений: 116,782
09.01.2020, 23:02
Ответы с готовыми решениями:

в клетке шахматной доски с координатами (х,у) стоит конь. Клетки, которые находятся под боем этого коня заполн
Ребят срочно нужно решить,40 минут есть помогите пожалйста!!!

Массивы. Необходимо заполнить ходами коня всю шахматную доску
Дана шахматная доска (матрица 8 × 8). Разработать программу, показывающую последовательность ходов...

Отметьте положение коня на доске и все клетки, которые бьет конь
На шахматной доске стоит конь. Отметьте положение коня на доске и все клетки, которые бьет конь....

Определить, возможно ли с помощью фигуры коня обойти все 64 клетки поля
иследование задачи математика Эйлера: возможно ли, с помощью фигуры коня обходить все 64 клетки...

4
851 / 621 / 289
Регистрация: 21.10.2012
Сообщений: 1,942
10.01.2020, 16:29 2
Лучший ответ Сообщение было отмечено Inuxoid как решение

Решение

Inuxoid, исправил чуть-чуть:
Кликните здесь для просмотра всего текста
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
clear;
clc;
 
n = input('Input quad size: ');
 
if n >= 5
    quadrat = zeros(n, n); % создание доски
else
    disp('Need 5 and more for this task');
end
 
% стартовые координаты коня
newcoord.x = input('Input the first position of horse by x: ');
newcoord.y = input('Input the first position of horse by y: ');
 
if newcoord.x > 0 && newcoord.y > 0
    quadrat(newcoord.x, newcoord.y) = 1;
else
    disp('Horse cannot have a negative position');
end
 
disp(quadrat);
 
while ismember(0, quadrat) % пока есть незакрашенные клетки
    newcoord = checkturn(quadrat, n, newcoord.x, newcoord.y); % получение новых координат для прыжка
    quadrat(newcoord.x, newcoord.y) = 1; % прыжок коня на новое поле    
    disp(quadrat);
end

Кликните здесь для просмотра всего текста
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
function newcoord = checkturn(quadrat,n,x,y)
weightofturn = zeros(1, 8); % массив с кол-вом возможных ходов из данной клетки
coordsofturnx = [2 2 -2 -2 1 1 -1 -1]; %все возможные ходы коня
coordsofturny = [1 -1 1 -1 2 -2 2 -2];
 
weightofturn(1) = checksecondturn(quadrat,n,x,y,coordsofturnx(1),coordsofturny(1)); % вычисление кол-ва доступных ходов
weightofturn(2) = checksecondturn(quadrat,n,x,y,coordsofturnx(2),coordsofturny(2));
weightofturn(3) = checksecondturn(quadrat,n,x,y,coordsofturnx(3),coordsofturny(3));
weightofturn(4) = checksecondturn(quadrat,n,x,y,coordsofturnx(4),coordsofturny(4));
weightofturn(5) = checksecondturn(quadrat,n,x,y,coordsofturnx(5),coordsofturny(5));
weightofturn(6) = checksecondturn(quadrat,n,x,y,coordsofturnx(6),coordsofturny(6));
weightofturn(7) = checksecondturn(quadrat,n,x,y,coordsofturnx(7),coordsofturny(7));
weightofturn(8) = checksecondturn(quadrat,n,x,y,coordsofturnx(8),coordsofturny(8));
 
[minval,ind] = min(weightofturn); % отсечение вариантов, где нельзя походить и нахождение варианта с минимальным кол-вом возможных ходов
while minval == 0
    weightofturn(ind) = 10;
    [minval,ind] = min(weightofturn);
end
 
 
newcoord.x = x + coordsofturnx(ind); % получение новых координат как суммы старых + смещение
newcoord.y = y + coordsofturny(ind);
end


Кликните здесь для просмотра всего текста
Matlab M
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
function [val] = checksecondturn(quadrat,n,x,y,qx,qy)
val = 0; % кол-во возможных ходов
if x+qx<=n && x+qx>=1 && y+qy<=n && y+qy>=1 && quadrat(x+qx,y+qy) == 0 % если возможен первый ход
    val = val + 1;
    if x+qx+2<=n && y+qy+1<=n && quadrat(x+qx+2,y+qy+1) == 0 % проверяется возможность сделать второй ход
        val = val + 1; % увеличивается кол-во возможных ходов
    end
    if x+qx+2<=n && y+qy-1>=1 && quadrat(x+qx+2,y+qy-1) == 0
        val = val + 1;
    end
    if x+qx-2>=1 && y+qy+1<=n && quadrat(x+qx-2,y+qy+1) == 0
        val = val + 1;
    end
    if x+qx-2>=1 && y+qy-1>=1 && quadrat(x+qx-2,y+qy-1) == 0
        val = val + 1;
    end
    if x+qx+1<=n && y+qy+2<=n && quadrat(x+qx+1,y+qy+2) == 0
        val = val + 1;
    end
    if x+qx+1<=n && y+qy-2>=1 && quadrat(x+qx+1,y+qy-2) == 0
        val = val + 1;
    end
    if x+qx-1>=1 && y+qy+2<=n && quadrat(x+qx-1,y+qy+2) == 0
        val = val + 1;
    end
    if x+qx-1>=1 && y+qy-2>=1 && quadrat(x+qx-1,y+qy-2) == 0
        val = val + 1;
    end
end
end
1
1054 / 644 / 177
Регистрация: 07.11.2019
Сообщений: 1,479
10.01.2020, 17:55 3
Я бы для начала создал граф (разреженая логическая матрица) возможных ходов с линейной индексацией.
Дальше задача поиска (гамильтонова?) пути на графе.
Когда путь будет найден ind2sub переводим линейные координаты в двумерные.
P.s. конь в шахматах это Knight, а не Horse
В относительно новых версиях Matlab добавили средства работы с графами.
0
2 / 2 / 2
Регистрация: 01.04.2014
Сообщений: 92
10.01.2020, 20:58  [ТС] 4
АлександрКом, спасибо, очень выручили. Может подскажете еще в какую сторону копать, чтобы сделать маломальскую графику, что-то вроде таблицы, где на месте нулей - белые клетки, а на месте единичек - закрашенные?

u235, да, с графами решение красивее моего, конечно, но графы я только на бумаге изучал, так что накодить с ними что-то было бы трудно)

Добавлено через 1 час 10 минут
Функция pcolor(quadrat) выполняет схожую задачу, но она дает на одну клетку меньше, чем используется в матрице.

Добавлено через 26 минут
heatmap(quadrat) выглядит куда лучше, только шкала мешается справа xd
0
851 / 621 / 289
Регистрация: 21.10.2012
Сообщений: 1,942
13.01.2020, 09:13 5
Цитата Сообщение от Inuxoid Посмотреть сообщение
где на месте нулей - белые клетки, а на месте единичек - закрашенные?
Matlab M
1
image(255*ones(n,n,3).*~quadrat);
1
IT_Exp
Эксперт
87844 / 49110 / 22898
Регистрация: 17.06.2006
Сообщений: 92,604
13.01.2020, 09:13

Заказываю контрольные, курсовые, дипломные и любые другие студенческие работы здесь или здесь.

Выяснить все ли клетки шахматной доски одного цвета
Здраствуйте, нам на оллимпиаду задали сделать 1 из програм но сколько бы во мне не было стремления...

Узнать все ли клетки шахматной доски одного цвета
Удалено

Вывести все возможные ходы шахматного коня из данной позиции, для трехмерной шахматной доски 8*8*8
Sub asd() Dim x As Integer, y As Integer, xx As Integer, yy As Integer, s As String Do x =...

Обойти шахматным конем все клетки шахматной доски, побывав на каждой клетке по одному разу
Здравствуйте, помогите пожалуйста Рекурсия, нужно обойти шахматным конем все клетки шахматной...


Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
5
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2021, vBulletin Solutions, Inc.