• 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

1014 Practice Question of New GRE – Princeton

Amazon Interview Experience – SDE Chennai

Naurki.com Security Breach

25 horses 5 tracks Find 3 fastest puzzle

Possible sizes of bus to carry n groups of friends

Singly linked list

building with N steps, we can take 1,2,3 steps calculate number of ways to reach at top of building

Printing each word reverse in string

Leetcode: Edit Distance

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

Find if two rectangles overlap

Microsoft BING Interview Experience

TicTacToe Game As Asked in Flipkart

Subset Sum Problem Dynamic programming

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

Urban Ladder Written Test.

Binary Tree in Java

write a c program that given a set a of n numbers and another number x determines whether or not there exist two elements in s whose sum is exactly x

Skiing on Mountains Matrix

Check Binary Tree is Binary Search Tree or not

Rectangular chocolate bar Create at least one piece which consists of exactly nTiles tiles

VMWare SDEII Interview

Cisco Hiring Event 21st – 22nd Feb 2015

Templates in C++

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

BFS (Breath First Search)

Facebook Interview Question : Interleave List

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

Maximum occurred Smallest integer in n ranges

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

Copyright © 2023 · Genesis Framework · WordPress · Log in