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:

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

Programming using Java Hands On - Control Structures | Print Username

By Anonymous
  Print Username Jeffy, who is going to complete the higher education in this year needs to create a simple application which accept the name of a person and welcome them with a message along with their name. She wants to read the data using the class "Scanner". Implement this scenario using Java. Sample Input 1:   Enter the name: Johson Sample Output 1: Welcome Johnson. Sample Input 2:   Enter the name: Stain Polson Sample Output 2: Welcome Stain Polson. Result Description Summary of tests *Note: All the test cases might not have same weightage +------------------------------+ | 2 tests run/ 2 tests passed | +------------------------------+
Post a Comment
Read more

Unbounded Knapsack

By Astrio Jather
1. You are given a number n, representing the count of items. 2. You are given n numbers, representing the values of n items. 3. You are given n numbers, representing the weights of n items. 3. You are given a number "cap", which is the capacity of a bag you've. 4. You are required to calculate and print the maximum value that can be created in the bag without      overflowing it's capacity. Note: Each item can be taken any number of times. You are allowed to put the same item again                    and again. Input Format A number n v1 v2 .. n number of elements w1 w2 .. n number of elements A number cap Output Format A number representing the maximum value that can be created in the bag without overflowing it's capacity Constraints 1 <= n <= 20 0 <= v1, v2, .. n elements <= 50 0 < w1, w2, .. n elements <= 10 0 < cap <= 10 Sample Input 5 15 14 10 45 30 2 5 1 3 4 7 Sample Output 100 Solution: im...
Post a Comment
Read more

RDBMS Data Definition Language | Create Distributor table

By Astrio Jather
  Write a query to create Distributor table with constraints mentioned.  Refer the below schema  Result Description Summary of tests +------------------------------+ | 3 tests run / 3 test passed | +------------------------------+
Post a Comment
Read more

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD for Persons

By Astrio Jather
  Generate XSD for Persons Generate XSD for the following XML. XYZ organization wants to store the details of persons in an xml file. The following scenario helps in designing the XML document. Here PersonList  is the root tag. PersonList contains the entry of each person with adhaarno, name, age and address. <?xml version="1.0"  encoding="UTF-8"?> <PersonList xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance" xsi:noNamespaceSchemaLocation="PersonList.xsd">     <Person>         <adhaarno>414356782345</adhaarno>         <name>             <firstname>Zeenath</firstname>         </name>         <age>28</age>         <address>             <doorno...
Post a Comment
Read more

Mock 3 Slot3 - Handson - 21st July RDBMS (20 Marks) 1.1 Owner Details

By Astrio Jather
  Write a query to display Owner id, Owner name and Contact details of owner from 'Coimbatore' or 'Bangalore'. For contact details, display the Email ID, if it is not available, display phone number. If both are not available, display ‘NA’. Give alias name as CONTACT_DETAILS. Sort the result based on Owner name in descending order. ( Hint : Retrieve data from Owners table , Data is  case sensitive) Evaluation Result: Result Description Summary of tests:(Note:Your query is evaluated against different datasets. Kindly do not Hardcode) +------------------------------+ | 2 tests run / 2 test passed | +------------------------------+
Post a Comment
Read more

Mock 3 Slot3 - Quiz - 21st July Quiz Quiz

By Astrio Jather
Mock 3 Slot3        Quiz - 21st July          Important Questions
Post a Comment
Read more

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD for Students

By Astrio Jather
  Generate XSD for Students   Generate XSD for the following XML. XYZ School wants to store the details of students in an xml file. The following scenario helps in designing the XML document. Here StudentList  is the root tag. StudentList contains the entry of each student with rollno, name, age, address and department. <?xml version="1.0" encoding="UTF-8"?> <StudentList  xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"  xsi:noNamespaceSchemaLocation="StudentList.xsd">     <Student rollno="2017CSE0055">         <name>             <firstname>Savitha</firstname>         </name>         <age>20</age>         <address>             <doorno>35</doorno>     ...
Post a Comment
Read more

Subscribe to Get's Answer by Email