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 | 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

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

Accenture TFA Quiz | Part 2

By Astrio Jather
  Question  26 Correct Marked out of 1 Flag question Question text What will be the output of the following Java code? public class ApplicationTester { public static void main(String[] args) { int[] array = {11,22,33,44,55,11}; int searchNumber = 11, position=999; for(int index=0; index < array.length; index++) { if(searchNumber == array[index]) { position = index; } } System.out.println(position); } } Choose the most appropriate option. Select one: a.  0 b.  5   c.  1 d.  6 Feedback The correct answer is: 5 Question  27 Incorrect Marked out of 1 Flag question Question text Predict the line of code Abstract class Base1 { protected void getDetails() { System.out.println("Base method"); } public Abstract void demomethod(); } Abstract class Base2 extends Base1 { public Abstract void samplemethod(); } class Derived extends Base2 { //Line1 } Select one: ...
Post a Comment
Read more

Data Formats ( XML & JSON ) XML AND JSON | Generate XSD 2

By Astrio Jather
  Generate XSD 2 Generate XSD for the following XML document <?xml version="1.0" encoding="UTF-8"?> <!--  <!DOCTYPE  hotels  SYSTEM "hotel.dtd"> --> <hotels> <hotel> <ID>1</ID> <Name> TAJ GANJ </Name> <Stars>3</Stars> <Facilities>Restaurant,Parking,Internet</Facilities> <Address>Taj Ganj,FFatehabad Road Agra Uttar Pradesh 282001</Address> <Type>budget</Type> <Available>true</Available> </hotel> <hotel> <ID>2</ID> <Name> TAJ EXOTICA </Name> <Stars>5</Stars> <Facilities>Indian therapies,Yoga and meditation,Spaindulges,Parking</Facilities> <Address>CalwaddoBenaulim, Salcete Goa 403716</Address> <Type>luxury</Type> <Available>false</Available> </hotel> <hotel> <ID>3</ID> <Name> VIVANTA by TAJ </Name> <Stars>3<...
Post a Comment
Read more

Software Engineering Concepts Configuration Management And Version Control Configuration Management And Version Control Quiz 1

By Astrio Jather
 
Post a Comment
Read more

Web Technology HTML 5 HTML 2 | Quiz 1

By Astrio Jather
 Web Technology       HTML 5            HTML 2               Quiz 1  
Post a Comment
Read more

UNIX Introduction to Unix | Post-Quiz

By Astrio Jather
 UNIX  Introduction to Unix  Post-Quiz  Feedback Congratulations! You have passed by securing more that 80%. Question  1 Correct Mark 1.00 out of 1.00 Flag question Question text  What is the default maximum number of processes that can exist in Unix? Select one: a.  unlimited b.   32768           c.   4096        d.  1024          Feedback Your answer is correct. The correct answer is:  32768         Question  2 Correct Mark 1.00 out of 1.00 Flag question Question text Single user mode shell has _____ prompt.  Select one: a.   $ Normal user  b.  % Admin user c.  ~ Home user d.  # Root user    Feedback Your answer is correct. The correct answer is: # Root user  Question  3 Correct Mark 1.00 out of 1.00 Flag question Question text Predict the output for the following...
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

Accenture TFA Quiz | Part 1

By Astrio Jather
  Question  1 Correct Marked out of 1 Flag question Question text The employee table contains EmployeeNumber, EmployeeName, Salary and DeptCode Columns. Which is the CORRECT SQL query to display DeptCode and average salary of each department? Choose most appropriate option. Select one: a.  SELECT DeptCode,avg(salary) FROM Employee GROUP BY DeptCode;   b.  SELECT DeptCode,avg(salary) FROM Employee GROUP BY EmployeeNumber; c.  SELECT DeptCode,avg(salary) FROM Employee; d.  SELECT DeptCode,avg(salary) FROM Employee GROUP BY Salary; Feedback The correct answer is: SELECT DeptCode,avg(salary) FROM Employee GROUP BY DeptCode; Question  2 Correct Marked out of 1 Flag question Question text Which is the CORRECT SQL Query to display names of employees which has only 3 letters that starts with 'A' and ends with 'e'? Choose most appropriate option. Select one: a.  SELECT EmployeeName FROM Employee WHERE EmployeeName LIKE 'A_e';   b.  SELECT Em...
Post a Comment
Read more

Subscribe to Get's Answer by Email