Click here to Skip to main content
14,936,653 members
Please Sign up or sign in to vote.
0.00/5 (No votes)
See more:
Can somebody help me if what is the time and space complexity of this java code below, I found this one in the internet and I need to know if what its time and space complexity. By the way this code solves a knight's tour problem. Show some respect please, I am a beginner in learning programming lessons.

What I have tried:

import java.util.*;

public class FinalProject {
private final static int base = 12;
private final static int[][] moves =
{
{1,-2},{2,-1},{2,1},{1,2},{-1,2},
{-2,1},{-2,-1},{-1,-2}
};
private static int[][] grid;
private static int total;

public static void main(String[] args) {
System.out.println("Hello, welcome to the Knight's Tour Program!");

grid = new int[base][base];
total = (base - 4) * (base - 4);

for (int r = 0; r < base; r++)
for (int c = 0; c < base; c++)
if (r < 2 || r > base - 3 || c < 2 || c > base - 3)
grid[r][c] = -1;

int row;
int col;

System.out.println("Place the row number: (2-9) ");
Scanner in_row = new Scanner(System.in);
row = in_row.nextInt();

System.out.println("Place the column number: (2-9) ");
Scanner in_col = new Scanner(System.in);
col = in_col.nextInt();

grid[row][col] = 1;

if (solve(row, col, 2))
printResult();
else System.out.println("no result");

}

private static boolean solve(int r, int c, int count) {
if (count > total)
return true;

List<int[]> nbrs = neighbors(r, c);

if (nbrs.isEmpty() && count != total)
return false;

Collections.sort(nbrs, new Comparator<int[]>() {
public int compare(int[] a, int[] b) {
return a[2] - b[2];
}
});

for (int[] nb : nbrs) {
r = nb[0];
c = nb[1];
grid[r][c] = count;
if (!orphanDetected(count, r, c) && solve(r, c, count + 1))
return true;
grid[r][c] = 0;
}

return false;
}

private static List<int[]> neighbors(int r, int c) {
List<int[]> nbrs = new ArrayList<>();

for (int[] m : moves) {
int x = m[0];
int y = m[1];
if (grid[r + y][c + x] == 0) {
int num = countNeighbors(r + y, c + x);
nbrs.add(new int[]{r + y, c + x, num});
}
}
return nbrs;
}

private static int countNeighbors(int r, int c) {
int num = 0;
for (int[] m : moves)
if (grid[r + m[1]][c + m[0]] == 0)
num++;
return num;
}

private static boolean orphanDetected(int cnt, int r, int c) {
if (cnt < total - 1) {
List<int[]> nbrs = neighbors(r, c);
for (int[] nb : nbrs)
if (countNeighbors(nb[0], nb[1]) == 0)
return true;
}
return false;
}

private static void printResult() {
for (int[] row : grid) {
for (int i : row) {
if (i == -1) continue;
System.out.printf("%2d ", i);
}
System.out.println();
}
}
}
Posted
Updated 7-May-21 19:46pm
Comments
Richard MacCutchan 8-May-21 4:26am
   
Yes, it's quite complex in both. But maybe if you spent some time analysing it you could find the answer for yourself.

1 solution

Quote:
Show some respect please, I am a beginner in learning programming lessons.


Perhaps you could take your own advice instead of dumping code you didn't write on us and asking us to do your homework for you? That's not exactly respectful to us, the author of the code, your teacher, or your fellow students - is it?

We are more than willing to help those that are stuck: but that doesn't mean that we are here to do it all for you! We can't do all the work, you are either getting paid for this, or it's part of your grades and it wouldn't be at all fair for us to do it all for you.

So we need you to do the work, and we will help you when you get stuck. That doesn't mean we will give you a step by step solution you can hand in!
Start by explaining where you are at the moment, and what the next step in the process is. Then tell us what you have tried to get that next step working, and what happened when you did.

If you are having problems getting started at all, then this may help: How to Write Code to Solve a Problem, A Beginner's Guide[^]
   

This content, along with any associated source code and files, is licensed under The Code Project Open License (CPOL)




CodeProject, 20 Bay Street, 11th Floor Toronto, Ontario, Canada M5J 2N8 +1 (416) 849-8900