• 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

Handle duplicates in Binary Search Tree

Common Ancestor in a Binary Tree or Binary Search Tree

Search element in a matrix with all rows and columns in sorted order

Find min element in Sorted Rotated Array (Without Duplicates)

Test Cases for Round Function

Binary Tree Isomorphic to each other

Maximum sum contiguous subarray of an Array

K’th Largest Element in BST when modification to BST is not allowed

Advanced SQL Injection

Daughter’s Age VeryGood Puzzle

In Given LinkedList Divide LL in N Sub parts and delete first K nodes of each part

Closed Parentheses checker

HackeEarth Flipkart’s Drone

Find an index i such that Arr [i] = i in array of n distinct integers sorted in ascending order.

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

C++ OOPs Part1

VMWare SDEII Interview

Code Chef PRGIFT Solution

Count Possible Decodings of a given Digit Sequence

Find two non repeating elements in an array of repeating elements

Print all nodes that are at distance k from a leaf node

BlueStone E-commerce Interview Experience

Maximum path sum between two leaves

Connect n ropes with minimum cost

Amazon Interview On-Campus For Internship – 1

strtok()

Find position of the only set bit

ADOBE Aptitude C Language Test

C++ OOPs Part2

Introduction To Number Theory ( Part 1 )

Copyright © 2025 · Genesis Framework · WordPress · Log in