# Knight's tour problem

• Given an mxn chessboard, if the position (x,y) of the knight is given, find the path which covers all the blocks of the chessboard without repeating.

• ``````//
// Created by richard on 16-2-28.
//

#include "point.h"
#include <bits/stdc++.h>
using namespace std;

void dfs(int nowi, int nowj, int cnt);
vector<Point> ans, cur;
int m, n;
int di[] = {-2,-2,-1,1,2,2,1,-1}, dj[] = {-1,1,2,2,1,-1,-2,-2};
bool vis[10][10];
vector<Point> knightTour(int m_, int n_, int si, int sj) {
m = m_, n = n_;
cur.clear();
ans.clear();
memset(vis, sizeof vis, 0);
dfs(si, sj, 0);
return ans;
}

void dfs(int nowi, int nowj, int cnt) {
//cur cnt, next nowi, nowj,
if(cnt == m * n) {
ans = cur;
return ;
}
vis[nowi][nowj] = 1;
cur.push_back({nowi, nowj});
for(int k = 0;  k < 8; k ++ ) {
int nexti = nowi + di[k],
nextj = nowj + dj[k];
if(!vis[nexti][nextj]) {
dfs(nexti, nextj, cnt+1);
}
}
cur.pop_back();
vis[nowi][nowj] = 0;
}

int main() {
auto ans = knightTour(4,5, 3,2);
for(Point p: ans) {
cout <<p.x<<" "<<p.y<<endl;
}
}``````

• A simple code using backtracking in Java. The Time Complexity is O(8^(n*n-1)). Where n is the size of the board.

/**

• Given a starting position of a knight find the path via which it can travel

• through the complete chess board without repetition.

• @author shivam.maharshi
*/
public class KnightsTour {

private static int xa[] = new int[] { -1, -1, 1, 1, -2, -2, 2, 2 };
private static int ya[] = new int[] { -2, 2, -2, 2, -1, 1, -1, 1 };

public static void findPath(int n, int x, int y) {
move(x, y, new int[n][n], new boolean[n][n], 1);
}

public static boolean move(int x, int y, int[][] board, boolean[][] visited, int count) {
if (count == (board.length * board.length)) {
board[x][y] = count;
print(board);
return true;
}
board[x][y] = count;
visited[x][y] = true;
for (int i = 0; i < 8; i++) {
int nextX = x + xa[i];
int nextY = y + ya[i];
if (isValidMove(nextX, nextY, board) && !visited[nextX][nextY]) {
if (move(nextX, nextY, board, visited, count + 1))
return true;
}
}
board[x][y] = 0;
visited[x][y] = false;
return false;
}

public static void print(int[][] board) {
for (int i = 0; i < board.length; i++) {
for (int j = 0; j < board.length; j++)
if (board[i][j] < 10)
System.out.print("0" + board[i][j] + " ");
else
System.out.print(board[i][j] + " ");
System.out.println("");
}
}

public static boolean isValidMove(int x, int y, int[][] board) {
return x >= 0 && y >= 0 && x < board.length && y < board.length;
}

public static void main(String[] args) {
findPath(8, 2, 2);
}

}

• @ruichang Hi, may I ask how can we come up with the direction here?

int di[] = {-2,-2,-1,1,2,2,1,-1}, dj[] = {-1,1,2,2,1,-1,-2,-2};

Thanks

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.