• 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

Sequence Finder Dynamic Programming

BlueStone E-commerce Interview Experience

Find the smallest window in a string containing all characters of another string

Python List

Naurki.com Security Breach

Printing Longest Common Subsequence

Find min element in Sorted Rotated Array (With Duplicates)

Find next greater number with same set of digits

Closed Parentheses checker

Hackerearth : Counting Subarrays

Coin Collection Dynamic Programming

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

Templates in C++

Print Power Set of a Set

Generate largest number arranging a no. of given non negative integer numbers

LeetCode : Word Search

C++ OOPs Part2

Print vertical sum of all the axis in the given binary tree

Cisco Hiring Event 21st – 22nd Feb 2015

Find two non repeating elements in an array of repeating elements

Maximum path sum between two leaves

Flipkart SDET Interview Experience

Convert number to words java

Minimum insertions to form a palindrome

How strtok() Works

VMWare Openings

Practo Hiring Experience

Sort Stack in place

Given Set of words or A String find whether chain is possible from these words or not

Spanning Tree

Copyright © 2025 · Genesis Framework · WordPress · Log in