• Skip to primary navigation
  • Skip to content
  • Skip to primary sidebar
  • Skip to secondary sidebar

GoHired

Interview Questions asked in Google, Microsoft, Amazon

Join WeekEnd Online Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

  • Home
  • Best Java Books
  • Algorithm
  • Internship
  • Certificates
  • About Us
  • Contact Us
  • Privacy Policy
  • Array
  • Stack
  • Queue
  • LinkedList
  • DP
  • Strings
  • Tree
  • Mathametical
  • Puzzles
  • Graph

Knight Tour Problem (Graph – Breadth First Search)

December 22, 2017 by Dhaval Dave

Knight Tour Problem : Given a chess board of size n x n, initial position of knight and final position of knight. We need to find the minimum number of steps required to reach final position, If it is impossible to reach final position then return -1. Knight moves according to following rules and is not allowed to leave chess board. Consider the diagram below 

Knight Tour Problem

In the above diagram initially the knight is at (2,3) and has to reach (5,0). The knight can reach to the final cell in two steps using the following paths (2,3) -> (3,1) -> (5,0) .

Problem Analysis

In this Knight Tour problem, knight is allowed to move in 8 directions and each move has unit cost associated with it. We can visualize this situation as a graph where the edges will represent possible moves and the vertices will represent possible positions of knight. This reduces the problem to standard problem of shortest path in unweighted graph. Hence we will be using Breadth First Search (BFS) to solve this problem.

Implementation

We will start with the initial position of knight and will push it in a queue. We will then iterate until our queue is empty. At each iteration we will pop out the front element of the queue and will then generate all the possible moves from this position. If the generated move is valid and we have not traversed it previously, then we will insert it into our queue. Also if the current position is the desired destination then we will just return the desired value. If we have iterated all the possible positions and still not reached the final position then we will return -1.

Code

The code for Knight Tour Problem is pretty simple to understand –

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

int n;

int dx[] = {1, 1, -1, -1, -2, 2, -2, 2};
int dy[] = {-2, 2, -2, 2, 1, 1, -1, -1};

// Function for checking if the move is valid or not .............

bool isSafe(int x, int y){

	if((x >= 0 && x < n) && (y >= 0 && y < n))
		return true;

	return false;

}

// Apply breadth first search ..............

int solveKnightOnChessBoard(vector<vector<bool> >& marked, int x1, int y1, int x2, int y2){

	queue<pair<pair<int,int>,int> > Queue;
	// Filling the intial cell in queue to start breadth first search .............
	Queue.push(make_pair(make_pair(x1,y1),0));

	// Standard breadth first search .............
	while(!Queue.empty()){

		pair<pair<int,int>,int > cell = Queue.front();
		int x = cell.first.first;
		int y = cell.first.second;
		int level = p.second;
		Queue.pop();

		// If we are at destination cell, then return the value of level .............
		if(x == x2 && y == y2)
			return level;

		for(int i = 0 ; i < 8 ; i ++){

			// Generating co-ordinate of new cell ...............
			int new_x = x + dx[i];
			int new_y = y + dy[i];

			if(isSafe(new_x,new_y) && !marked[new_x][new_y]){

				// If the move is valid and we have previously traversed new cell then push it into queue .........

				Queue.push(make_pair(make_pair(new_x,new_y),level + 1));
				marked[new_x][new_y] = true;

			}

		}

	}

	// If we were unable to reach destination cell return -1 .
	return -1;

}

// Driver function ..........

int main(){

	cin >> n;

	int x1, y1, x2, y2;
	cin >> x1 >> y1 >> x2 >> y2 ;

	vector<vector<bool> > marked(n,vector<bool>(n,false));

	cout << solveKnightOnChessBoard(marked,x1,y1,x2,y2) << endl;

}

Complexity

In the above solution we tres the problem to standard problem of shortest path in unweighted graph. So the worst case will be when we have to traverse each and every cell. So the overall complexity of above solution is O(n2).

This Article is Published by Abhey Rana.
If you want to be content writer with Gohired.in Please write at career@gohired.in or admin@gohired.in

Similar Articles

Filed Under: Algorithm, Amazon Interview Question, Flipkart Interview Questions, Graph, Microsoft Interview Questions Tagged With: algorithm, BFS, Graph

Reader Interactions

Primary Sidebar

Join WeekEnd Online/Offline Batch from 4-April-2020 on How to Crack Coding Interview in Just 10 Weeks : Fees just 20,000 INR

Join WeekEnd Online/Offline Batch from 4-April-2020

WhatsApp us

Secondary Sidebar

Custom Search

  • How I cracked AMAZON
  • LeetCode
  • Adobe
  • Amazon
  • Facebook
  • Microsoft
  • Hacker Earth
  • CSE Interview

Top Rated Questions

Print Power Set of a Set

Find Percentage of Words matching in Two Strings

Longest Increasing Subsequence

Reliance Jio Software Developer Interview Experience

strtok()

Python List

Find next greater number with same set of digits

Regular Expression Matching

Implement LRU Cache

Given a float number convert it into the string WITHOUT using any inbuilt Function

Amazon Interview Experience – SDE Chennai

‘N’ Story Building, with 1,2,3 steps how many ways can a person reach top of building.

System Design: Designing a LLD for Hotel Booking

Stickler thief

Mirror of Tree

Given a sorted array and a number x, find the pair in array whose sum is closest to x

Leetcode: Merge Intervals

Amazon Interview On-Campus For Internship – 1

SAP Off Campus Hiring_ March 2015 Sample Questions

Stock Buy Sell to Maximize Profit

LeetCode: Container With Most Water

Linked List V/S Binary Search Tree

Generate next palindrome number

Introduction To Number Theory ( Part 1 )

Find the element that appears once others appears thrice

Max Sum in circularly situated Values

Reverse a Linked List in groups of given size

Naurki.com Security Breach

Number of Islands BFS/DFS

Python String and numbers

Copyright © 2025 · Genesis Framework · WordPress · Log in