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

@Inuxoid · Регистрация: 01.04.2014

Пытаюсь решить такую задачу, вот что набросал уже

Основная программа

Matlab M

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

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

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 значений, когда прошёл только один цикл?

Может еще какие логические ошибки, если кто увидит - буду благодарен.

@АлександрКом · 10.01.2020, 16:29

Inuxoid, исправил чуть-чуть:

Кликните здесь для просмотра всего текста

Matlab M

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

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

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

@u235 · 10.01.2020, 17:55

Я бы для начала создал граф (разреженая логическая матрица) возможных ходов с линейной индексацией.
Дальше задача поиска (гамильтонова?) пути на графе.
Когда путь будет найден ind2sub переводим линейные координаты в двумерные.
P.s. конь в шахматах это Knight, а не Horse
В относительно новых версиях Matlab добавили средства работы с графами.

@Inuxoid · 10.01.2020, 20:58 **[ТС]**

АлександрКом, спасибо, очень выручили. Может подскажете еще в какую сторону копать, чтобы сделать маломальскую графику, что-то вроде таблицы, где на месте нулей - белые клетки, а на месте единичек - закрашенные?

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

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

Добавлено через 26 минут
heatmap(quadrat) выглядит куда лучше, только шкала мешается справа xd

@АлександрКом · 13.01.2020, 09:13

Сообщение от Inuxoid

где на месте нулей - белые клетки, а на месте единичек - закрашенные?

Matlab M

1	image(255ones(n,n,3).~quadrat);

@u235 1054 / 644 / 177 Регистрация: 07.11.2019 Сообщений: 1,479
	10.01.2020, 17:55	3
	Я бы для начала создал граф (разреженая логическая матрица) возможных ходов с линейной индексацией. Дальше задача поиска (гамильтонова?) пути на графе. Когда путь будет найден ind2sub переводим линейные координаты в двумерные. P.s. конь в шахматах это Knight, а не Horse В относительно новых версиях Matlab добавили средства работы с графами. 0

@Inuxoid 2 / 2 / 2 Регистрация: 01.04.2014 Сообщений: 92
	10.01.2020, 20:58 [ТС]	4
	АлександрКом, спасибо, очень выручили. Может подскажете еще в какую сторону копать, чтобы сделать маломальскую графику, что-то вроде таблицы, где на месте нулей - белые клетки, а на месте единичек - закрашенные? u235, да, с графами решение красивее моего, конечно, но графы я только на бумаге изучал, так что накодить с ними что-то было бы трудно) Добавлено через 1 час 10 минут Функция pcolor(quadrat) выполняет схожую задачу, но она дает на одну клетку меньше, чем используется в матрице. Добавлено через 26 минут heatmap(quadrat) выглядит куда лучше, только шкала мешается справа xd 0

Опции темы

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

Решение