## Editorial for Knight Moves

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.

Submitting an official solution before solving the problem yourself is a bannable offence.
by: donchominkov

Sample solutions:

Video in BG

#### JavaScript

const n = +gets();

let matrix = []
for (let i = 0; i < n; i++) {
matrix.push([]);
}

const drows = [-2, -2, -1, -1, +1, +1, +2, +2];
const dcols = [-1, +1, -2, +2, -2, +2, -1, +1];
const dirsCounts = drows.length;

let count = 1;

for (let r = 0; r < n; r += 1) {
for (let c = 0; c < n; c += 1) {
if (matrix[r][c]) {
continue;
}

let cellFound = true;
let row = r;
let col = c;

while (cellFound) {
cellFound = false;

matrix[row][col] = count;
count += 1;

let direction = 0;
while (direction < dirsCounts && !cellFound) {
const nextRow = row + drows[direction];
const nextCol = col + dcols[direction];
direction += 1;
if (nextRow < 0 || n <= nextRow) {
continue;
}
if (nextCol < 0 || n <= nextCol) {
continue;
}

if (matrix[nextRow][nextCol]) {
continue;
}

cellFound = true;
row = nextRow;
col = nextCol;
break;

}
}
}
}

for (const row of matrix) {
print(row)
}


#### Java

import java.util.Scanner;

public class Main {
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int n = in.nextInt();
int[][] matrix = new int[n][n];

// All possible horse moves (8) ordered by priority (top most, left most)
int[] horseMovesHorizontal = {-2, -2, -1, -1, +1, +1, +2, +2};
int[] horseMovesVertical = {-1, +1, -2, +2, -2, +2, -1, +1};

int movesCounter = 1;
// For each cell in the matrix that is not used try to make horse moves
for (int r = 0; r < n; r++) {
for (int c = 0; c < n; c++) {
int currentRow = r;
int currentCol = c;

// Make moves while cell is not visited
while (matrix[currentRow][currentCol] == 0) {
matrix[currentRow][currentCol] = movesCounter;
movesCounter++;

// Search for possible move
for (int move = 0; move < horseMovesHorizontal.length; move++) {
int nextRow = currentRow + horseMovesHorizontal[move];
int nextCol = currentCol + horseMovesVertical[move];

// Check if move goes out of the matrix
if (nextRow < 0 || nextRow >= matrix.length ||
nextCol < 0 || nextCol >= matrix.length) {
continue;
}

// Check if the cell is visited
if (matrix[nextRow][nextCol] != 0) {
continue;
}

currentRow = nextRow;
currentCol = nextCol;
break;
}
}
}
}

// Print the output
for (int[] row : matrix) {
String result = "";
for (int cell : row) {
result += cell + " ";
}
System.out.println(result.trim());
}
}
}