Задача всегда имеет решение, если меньшая из сторон не меньше 3, если обе стороны равны 3, то решения не будет только в случае если координаты одной из клеток (2,2). Если меньшая сторона равна 1, то решения не будет, остается рассмотреть вариант при К (N) равной 2. В таком случае надо учитывать в одной строке (столбце) находяться клетки или нет. Если клетки расположены в одной строке(столбце), то разница координат по столбцу (строке) должна делиться на 4 без остатка, или если в разных строках (столбцах), и остаток от деления разницы координат на 4 равен 2. то решение есть, а иначе решения нет.