• 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

SAP Interview Questions

Leetcode: Merge Intervals

Convert number to words java

Implement LRU Cache

simple sql injection

Subset Sum Problem Dynamic programming

Reversal of LinkedList

Stock Buy Sell to Maximize Profit

Inorder and Preorder traversals of a Binary Tree given. Output the Postorder traversal of it.

Get K Max and Delete K Max in stream of incoming integers

The Magic HackerEarth Nirvana solutions Hiring Challenge

Implement a generic binary search algorithm for Integer Double String etc

Templates in C++

Introduction To Number Theory ( Part 1 )

Binary Tree in Java

Check if an array has duplicate numbers in O(n) time and O(1) space

Find and print longest consecutive number sequence in a given sequence in O(n)

CodeChef Code SGARDEN

Wrong Directions given find minimum moves so that he can reach to the destination

SAP Hiring Off-Campus General Aptitude

Given array of 0’s and 1’s. All 0’s are coming first followed by 1’s. find the position of first 1

Circular Linked List

strtok()

Top 10 Interviews Techniqes for Campus Interview in IIT NIT BITS for MTech

LeetCode: Binary Tree Maximum Path Sum

Connect n ropes with minimum cost

Printing each word reverse in string

Given a string, find the first character which is non-repetitive

Check a String is SUBSEQUENCE of another String Find Minimum length for that ( DNA Matching )

Microsoft BING Interview Experience

Copyright © 2025 · Genesis Framework · WordPress · Log in