KnightL on a Chessboard

Sort by

recency

|

127 Discussions

|

  • + 0 comments

    Java with optimisations: do only half, as output is symmetrical, special cases i==j, greatest common factor of i,j does not divide n-1.

    import java.io.*;
    import java.math.*;
    import java.security.*;
    import java.text.*;
    import java.util.*;
    import java.util.concurrent.*;
    import java.util.function.*;
    import java.util.regex.*;
    import java.util.stream.*;
    import static java.util.stream.Collectors.joining;
    import static java.util.stream.Collectors.toList;
    
    class Result {
    
        /*
         * Complete the 'knightlOnAChessboard' function below.
         *
         * The function is expected to return a 2D_INTEGER_ARRAY.
         * The function accepts INTEGER n as parameter.
         */
    
        public static int[][] states;
        public static int[] tmp;
        
    
        public static int gcf(int i, int j) {
            int k = (i > j)? j : i;
            int m = (i > j)? i : j;
            while (k > 1) {
              int q = m - k;
              if (q == 0) {
                 return k;
              }
              if (q == 1) {
                return 1;
              }
              if (q > k) {
                m = q;
              } else {
                int w = k;
                k = q;
                m = w;
              }
            }
            return k;
        }
    
    
        public static Integer ket(int i, int j, int d) {
            return i * 65536  + j * 256 +  d;
        }
        
        public static  void fromk(Integer k) {
            int a = k / 65536;
            int b = (k - a * 65536 )  / 256;
            int c = k - a * 65536 - b * 256;
            tmp[0] = a;
            tmp[1] = b;
            tmp[2] = c;
        }
    
        public static void setstates(int i, int j) {
            states[0][0] = -i;
            states[0][1] = -j;
            
            states[1][0] = -i;
            states[1][1] = j;
            
            states[2][0] = i;
            states[2][1] = -j;
            
            states[3][0] = i;
            states[3][1] = j;
            
            states[4][0] = -j;
            states[4][1] = -i;
            
            states[5][0] = -j;
            states[5][1] = i;
            
            states[6][0] = j;
            states[6][1] = -i;
            
            states[7][0] = j;
            states[7][1] = i;
        }
        
        public static boolean checkpos(int x, int y, int n) {
            return (x >= 0 && y >= 0 && x < n && y < n);
        }
        
    
        public static Integer getk(int i, int j) {
            return i * 256 + j;
        }
    
        public static int bfs(int i, int j, int n) {        
            Set<Integer> seen = new HashSet<>();
            Queue<Integer> todo = new LinkedList<>();
    
            todo.add(ket(0, 0, 0));
            seen.add(getk(0, 0));
            while (! todo.isEmpty()) {
                fromk(todo.remove());
                int x  = tmp[0];
                int y = tmp[1];
                int d = tmp[2];
                if (x == n - 1 && y == n - 1) {
                    return d;
                }
                for (int q = 0; q < 8; q++) {
                    int xx = x + states[q][0];
                    int yy  = y + states[q][1];
                    if (checkpos(xx, yy, n)) {
                        Integer kk = getk(xx, yy);
                        if (! seen.contains(kk)) {
                            seen.add(getk(xx, yy));
                            todo.add(ket(xx, yy, d+1));
                        }
                    }
                }
            }
            return -1;
        }
    
        public static List<List<Integer>> knightlOnAChessboard(int n) {
            // BFS.
            tmp = new int[3];
    
            // Since output is symmetrical, do upper half:
            states = new int[8][2];
            int[][] resulti = new int[n][n];
            for (int i = 1; i < n; i++) {
                for (int j = i; j < n; j++) {
                    // optimize if i==j
                    if (i == j && ((n - 1) % i == 0 || i ==1) ) {
                            resulti[i][j] = (n  - 1)/ i; 
                    } else {
                        int f = gcf(i, j);
                        // optimize greatest common factor cannot reach (n-1, n-1):
                        if (f != 1 && (n - 1) % f != 0) {
                            resulti[i][j] = -1;
                        } else {
                            setstates(i, j);
                            resulti[i][j] = bfs(i, j, n);
                        }
                    }
                }
            }
    
            // Since output is symmetrical, copy upper half to lower half:
            List<List<Integer>> result = new ArrayList<>();
            for (int i = 1; i < n; i++) {
                List<Integer> row = new ArrayList<>();
                for (int j = 1; j < n; j++) {
                   int x = (i > j) ? i : j;
                   int y = (i > j) ? j : i;
                   row.add(resulti[y][x]);
                }
                result.add(row);
            }
            return result;
        }
    }
    
    public class Solution {
        public static void main(String[] args) throws IOException {
            BufferedReader bufferedReader = new BufferedReader(new InputStreamReader(System.in));
            BufferedWriter bufferedWriter = new BufferedWriter(new FileWriter(System.getenv("OUTPUT_PATH")));
    
            int n = Integer.parseInt(bufferedReader.readLine().trim());
    
            List<List<Integer>> result = Result.knightlOnAChessboard(n);
    
            result.stream()
                .map(
                    r -> r.stream()
                        .map(Object::toString)
                        .collect(joining(" "))
                )
                .map(r -> r + "\n")
                .collect(toList())
                .forEach(e -> {
                    try {
                        bufferedWriter.write(e);
                    } catch (IOException ex) {
                        throw new RuntimeException(ex);
                    }
                });
    
            bufferedReader.close();
            bufferedWriter.close();
        }
    }
    
  • + 0 comments

    I can't help but feel like there's some mathematical way to figure this out without doing BFS, but I'm not quite able to get there.

  • + 0 comments

    Promotional merchandise for "KnightL on a Chessboard" can bring the classic strategy of chess to life. Custom chess sets featuring your brand’s logo or personalized pieces add a touch of sophistication. Branded chessboards, stylish keychains shaped like knights, or limited-edition chess piece stress balls can make thoughtful giveaways. Engage enthusiasts with these elegant items, perfect for corporate events or promotions that highlight strategy, skill, and timeless appeal.

  • + 0 comments

    The Knight's unique movement in chess, leaping in an "L" shape, allows it to control both near and distant squares, making it a versatile piece on the board; you can read more about the fascinating strategies involving the Knight at https://awomansjourney.com.

  • + 0 comments
    def knightlOnAChessboard(n):
        def bfs(n, a, b):
            directions = [(a, b), (a, -b), (-a, b), (-a, -b),
                          (b, a), (b, -a), (-b, a), (-b, -a)]
            queue = deque([(0, 0, 0)])
            visited = set([(0, 0)])
            
            while queue:
                x, y, dist = queue.popleft()
                if x == n-1 and y == n-1:
                    return dist
                
                for dx, dy in directions:
                    nx, ny = x + dx, y + dy
                    if 0 <= nx < n and 0 <= ny < n and (nx, ny) not in visited:
                        visited.add((nx, ny))
                        queue.append((nx, ny, dist + 1))
            
            return -1
    
        result = []
        for i in range(1, n):
            row = []
            for j in range(1, n):
                row.append(bfs(n, i, j))
            result.append(row)
        
        return result