Skip to main content

Knights Tour

Image
By Astrio Jather

1. You are given a number n, the size of a chess board.

2. You are given a row and a column, as a starting point for a knight piece.

3. You are required to generate the all moves of a knight starting in (row, col) such that knight visits 

     all cells of the board exactly once.

4. Complete the body of printKnightsTour function - without changing signature - to calculate and 

     print all configurations of the chess board representing the route

     of knight through the chess board. Use sample input and output to get more idea.


Note -> When moving from (r, c) to the possible 8 options give first precedence to (r - 2, c + 1) and 

               move in clockwise manner to

               explore other options.

Input Format

A number n

A number row

A number col

Output Format

All configurations of the chess board representing route of knights through the chess board starting in (row, col)

Use displayBoard function to print one configuration of the board.


Constraints

n = 5

0 <= row < n

0 <= col < n

Sample Input

5

2

0


Sample Output

25 2 13 8 23 

12 7 24 3 14 

1 18 15 22 9 

6 11 20 17 4 

19 16 5 10 21 


19 2 13 8 21 

12 7 20 3 14 

1 18 15 22 9 

6 11 24 17 4 

25 16 5 10 23 


25 2 13 8 19 

12 7 18 3 14 

1 24 15 20 9 

6 11 22 17 4 

23 16 5 10 21 


19 2 13 8 25 

12 7 18 3 14 

1 20 15 24 9 

6 11 22 17 4 

21 16 5 10 23 


21 2 17 8 19 

12 7 20 3 16 

1 22 13 18 9 

6 11 24 15 4 

23 14 5 10 25 


23 2 17 8 25 

12 7 24 3 16 

1 22 13 18 9 

6 11 20 15 4 

21 14 5 10 19 


25 2 17 8 23 

12 7 24 3 16 

1 18 13 22 9 

6 11 20 15 4 

19 14 5 10 21 


19 2 17 8 21 

12 7 20 3 16 

1 18 13 22 9 

6 11 24 15 4 

25 14 5 10 23 


25 2 15 8 19 

16 7 18 3 14 

1 24 11 20 9 

6 17 22 13 4 

23 12 5 10 21 


19 2 15 8 25 

16 7 18 3 14 

1 20 11 24 9 

6 17 22 13 4 

21 12 5 10 23 


21 2 15 8 19 

16 7 20 3 14 

1 22 11 18 9 

6 17 24 13 4 

23 12 5 10 25 


23 2 15 8 25 

16 7 24 3 14 

1 22 11 18 9 

6 17 20 13 4 

21 12 5 10 19 


23 2 13 8 21 

14 7 22 3 12 

1 24 9 20 17 

6 15 18 11 4 

25 10 5 16 19 


21 2 13 8 23 

14 7 22 3 12 

1 20 9 24 17 

6 15 18 11 4 

19 10 5 16 25 


25 2 13 8 19 

14 7 18 3 12 

1 24 9 20 17 

6 15 22 11 4 

23 10 5 16 21 


19 2 13 8 25 

14 7 18 3 12 

1 20 9 24 17 

6 15 22 11 4 

21 10 5 16 23 


21 2 11 16 19 

12 17 20 3 10 

1 22 7 18 15 

6 13 24 9 4 

23 8 5 14 25 


23 2 11 16 25 

12 17 24 3 10 

1 22 7 18 15 

6 13 20 9 4 

21 8 5 14 19 


23 2 11 16 21 

12 17 22 3 10 

1 24 7 20 15 

6 13 18 9 4 

25 8 5 14 19 


21 2 11 16 23 

12 17 22 3 10 

1 20 7 24 15 

6 13 18 9 4 

19 8 5 14 25 


21 2 9 14 19 

10 15 20 3 8 

1 22 5 18 13 

16 11 24 7 4 

23 6 17 12 25 


23 2 9 14 25 

10 15 24 3 8 

1 22 5 18 13 

16 11 20 7 4 

21 6 17 12 19 


25 2 9 14 23 

10 15 24 3 8 

1 18 5 22 13 

16 11 20 7 4 

19 6 17 12 21 


19 2 9 14 21 

10 15 20 3 8 

1 18 5 22 13 

16 11 24 7 4 

25 6 17 12 23 


23 2 7 12 21 

8 13 22 17 6 

1 24 3 20 11 

14 9 18 5 16 

25 4 15 10 19 


21 2 7 12 23 

8 13 22 17 6 

1 20 3 24 11 

14 9 18 5 16 

19 4 15 10 25 


25 2 7 12 23 

8 13 24 17 6 

1 18 3 22 11 

14 9 20 5 16 

19 4 15 10 21 


19 2 7 12 21 

8 13 20 17 6 

1 18 3 22 11 

14 9 24 5 16 

25 4 15 10 23 


25 4 15 10 23 

14 9 24 5 16 

1 18 3 22 11 

8 13 20 17 6 

19 2 7 12 21 


19 4 15 10 21 

14 9 20 5 16 

1 18 3 22 11 

8 13 24 17 6 

25 2 7 12 23 


25 4 15 10 19 

14 9 18 5 16 

1 24 3 20 11 

8 13 22 17 6 

23 2 7 12 21 


19 4 15 10 25 

14 9 18 5 16 

1 20 3 24 11 

8 13 22 17 6 

21 2 7 12 23 


21 6 17 12 19 

16 11 20 7 4 

1 22 5 18 13 

10 15 24 3 8 

23 2 9 14 25 


23 6 17 12 25 

16 11 24 7 4 

1 22 5 18 13 

10 15 20 3 8 

21 2 9 14 19 


25 6 17 12 23 

16 11 24 7 4 

1 18 5 22 13 

10 15 20 3 8 

19 2 9 14 21 


19 6 17 12 21 

16 11 20 7 4 

1 18 5 22 13 

10 15 24 3 8 

25 2 9 14 23 


25 8 5 14 19 

6 13 18 9 4 

1 24 7 20 15 

12 17 22 3 10 

23 2 11 16 21 


19 8 5 14 25 

6 13 18 9 4 

1 20 7 24 15 

12 17 22 3 10 

21 2 11 16 23 


21 8 5 14 19 

6 13 20 9 4 

1 22 7 18 15 

12 17 24 3 10 

23 2 11 16 25 


23 8 5 14 25 

6 13 24 9 4 

1 22 7 18 15 

12 17 20 3 10 

21 2 11 16 19 


21 12 5 10 19 

6 17 20 13 4 

1 22 11 18 9 

16 7 24 3 14 

23 2 15 8 25 


23 12 5 10 25 

6 17 24 13 4 

1 22 11 18 9 

16 7 20 3 14 

21 2 15 8 19 


23 12 5 10 21 

6 17 22 13 4 

1 24 11 20 9 

16 7 18 3 14 

25 2 15 8 19 


21 12 5 10 23 

6 17 22 13 4 

1 20 11 24 9 

16 7 18 3 14 

19 2 15 8 25 


21 14 5 10 19 

6 11 20 15 4 

1 22 13 18 9 

12 7 24 3 16 

23 2 17 8 25 


23 14 5 10 25 

6 11 24 15 4 

1 22 13 18 9 

12 7 20 3 16 

21 2 17 8 19 


25 14 5 10 23 

6 11 24 15 4 

1 18 13 22 9 

12 7 20 3 16 

19 2 17 8 21 


19 14 5 10 21 

6 11 20 15 4 

1 18 13 22 9 

12 7 24 3 16 

25 2 17 8 23 


23 16 5 10 21 

6 11 22 17 4 

1 24 15 20 9 

12 7 18 3 14 

25 2 13 8 19 


21 16 5 10 23 

6 11 22 17 4 

1 20 15 24 9 

12 7 18 3 14 

19 2 13 8 25 


25 16 5 10 23 

6 11 24 17 4 

1 18 15 22 9 

12 7 20 3 14 

19 2 13 8 21 


19 16 5 10 21 

6 11 20 17 4 

1 18 15 22 9 

12 7 24 3 14 

25 2 13 8 23 


23 10 5 16 21 

6 15 22 11 4 

1 24 9 20 17 

14 7 18 3 12 

25 2 13 8 19 


21 10 5 16 23 

6 15 22 11 4 

1 20 9 24 17 

14 7 18 3 12 

19 2 13 8 25 


25 10 5 16 19 

6 15 18 11 4 

1 24 9 20 17 

14 7 22 3 12 

23 2 13 8 21 


19 10 5 16 25 

6 15 18 11 4 

1 20 9 24 17 

14 7 22 3 12 

21 2 13 8 23 


Solution:

import java.io.*;
import java.util.*;

public class Main {

    public static void main(String[] args) throws Exception {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        int x = sc.nextInt(), y = sc.nextInt();
        int[][] chess = new int[n][n];
        printKnightsTour(chess,x,y,1);
    }

    public static void printKnightsTour(int[][] chess, int r, int c, int upcomingMove) {
        int n = chess.length;
        if(r<0 || c<0 || r >= n || c >= n || chess[r][c] != 0)   return;
        
        
        if(upcomingMove >= (n*n)){
            if(upcomingMove == (n*n)){
                chess[r][c] = upcomingMove;
                displayBoard(chess);
                chess[r][c] = 0;
            }
            return;
        }
        
        chess[r][c] = upcomingMove;
        
        printKnightsTour(chess,r-2,c+1,upcomingMove+1);
        
        printKnightsTour(chess,r-1,c+2,upcomingMove+1);
        printKnightsTour(chess,r+1,c+2,upcomingMove+1);
        
        printKnightsTour(chess,r+2,c+1,upcomingMove+1);
        printKnightsTour(chess,r+2,c-1,upcomingMove+1);
        
        printKnightsTour(chess,r+1,c-2,upcomingMove+1);
        printKnightsTour(chess,r-1,c-2,upcomingMove+1);
        
        printKnightsTour(chess,r-2,c-1,upcomingMove+1);
        
        chess[r][c] = 0;
    }

    public static void displayBoard(int[][] chess){
        for(int i = 0; i < chess.length; i++){
            for(int j = 0; j < chess[0].length; j++){
                System.out.print(chess[i][j] + " ");
            }
            System.out.println();
        }

        System.out.println();
    }
}
Labels:

Comments

Post a Comment

Must Read:

Data Formats ( XML & JSON ) XML AND JSON XML AND JSON | Quiz 2 & 3

By Astrio Jather
Data Formats ( XML & JSON )  XML AND JSON  XML AND JSON Quiz 2 & 3  
Post a Comment
Read more

Programming using Java Hands On - Control Structures | Print Customer Details

By Anonymous
Print Customer Details Help Mr.Ben who is a programmer, in developing a registration form on console. Customers will not just input data, but also view the details once he/she finishes the registration.  Sample Input 1: Enter your name:Jany Enter age:25 Enter gender:Female Hailing from:Mexico Sample Output 1: Welcome, Jany Age:25 Gender:Female City:Mexico Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 5 tests run/ 5 tests passed | +------------------------------+
Post a Comment
Read more

Data Formats ( XML & JSON ) XML AND JSON | Pre-Quiz

By Astrio Jather
Data Formats ( XML & JSON )  XML AND JSON  Pre-Quiz  
Post a Comment
Read more

RDBMS Data Definition Language | Drop Mobile Specification table (parent)

By Astrio Jather
  RDBMS  Data Definition Language  Drop Mobile Specification table (parent) Refer the following schema and drop Mobile Specification table. (Hint: To drop parent table all associate tables need to be dropped or Use 'cascade constraints' command) Evaluation Result: Result Description Summary of tests +------------------------------+ | 1 tests run / 1 test passed | +------------------------------+
Post a Comment
Read more

UNIX Introduction to Unix

By Astrio Jather
  Calendar1 Display the previous, current and next month calendar of the  year 1987 august Calendar2 Display and see what is the specialty of September 1752. Calendar 5 Write a command to display the previous, current and next month calendar of the year 2015 December.
Post a Comment
Read more

Min Cost In Maze Traversal

By Astrio Jather
1. You are given a number n, representing the number of rows. 2. You are given a number m, representing the number of columns. 3. You are given n*m numbers, representing elements of 2d array a, which represents a maze. 4. You are standing in top-left cell and are required to move to bottom-right cell. 5. You are allowed to move 1 cell right (h move) or 1 cell down (v move) in 1 motion. 6. Each cell has a value that will have to be paid to enter that cell (even for the top-left and bottom-       right cell). 7. You are required to traverse through the matrix and print the cost of path which is least costly. Input Format A number n A number m e11 e12.. e21 e22.. .. n * m number of elements Output Format The cost of least costly path. Constraints 1 <= n <= 10^2 1 <= m <= 10^2 0 <= e1, e2, .. n * m elements <= 1000 Sample Input 6 6 0 1 4 2 8 2 4 3 6 5 0 4 1 2 4 1 4 6 2 0 7 3 2 2 3 1 5 9 2 4 2 7 0 8 5 1 Sample Output 23 Solution: import java.io.*; import...
Post a Comment
Read more

Programming using Java Hands On - Control Structures | Check for Leap Year

By Astrio Jather
  Given a year, check if the year is leap year or not.  If yes, the output should be “Leap Year”.  Else output should be “Not a Leap Year”.  The input should be a positive four digit number.  Else,  the output should be “Invalid Year”. Sample Input  1 : Enter the Year 2016 Sample Output  1 : Leap Year Sample Input  2 : Enter the Year 2001 Sample Output  2 : Not a Leap Year Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 12 tests run/12 tests passed | +------------------------------+
Post a Comment
Read more

Programming using Java Hands On - Control Structures | Bill Generation

By Astrio Jather
Bill Generation Tom went to a movie with his friends in a multiplex theatre and during break time he bought pizzas, puffs and cool drinks.  Consider   the following prices :  Rs.100/pizza Rs.20/puffs Rs.10/cooldrink Generate a bill for What Tom has bought. Sample Input 1: Enter the no of pizzas bought:10 Enter the no of puffs bought:12 Enter the no of cool drinks bought:5 Sample Output 1: Bill Details No of pizzas:10 No of puffs:12 No of cooldrinks:5 Total price=1290 ENJOY THE SHOW!!! Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 6 tests run/ 6 tests passed | +------------------------------+
Post a Comment
Read more

Software Engineering Concepts Software Maintenance Test Your Understanding

By Astrio Jather
  Software Engineering Concepts       Software Maintenance            Test Your Understanding
Post a Comment
Read more

Subscribe to Get's Answer by Email