Knight's tour problem


  • 3
    S

    Given an mxn chessboard, if the position (x,y) of the knight is given, find the path which covers all the blocks of the chessboard without repeating.


  • 0
    R
    //
    // Created by richard on 16-2-28.
    //
    
    #include "point.h"
    #include <bits/stdc++.h>
    using namespace std;
    
    void dfs(int nowi, int nowj, int cnt);
    vector<Point> ans, cur;
    int m, n;
    int di[] = {-2,-2,-1,1,2,2,1,-1}, dj[] = {-1,1,2,2,1,-1,-2,-2};
    bool vis[10][10];
    vector<Point> knightTour(int m_, int n_, int si, int sj) {
        m = m_, n = n_;
        cur.clear();
        ans.clear();
        memset(vis, sizeof vis, 0);
        dfs(si, sj, 0);
        return ans;
    }
    
    
    void dfs(int nowi, int nowj, int cnt) {
        //cur cnt, next nowi, nowj,
        if(cnt == m * n) {
            ans = cur;
            return ;
        }
        vis[nowi][nowj] = 1;
        cur.push_back({nowi, nowj});
        for(int k = 0;  k < 8; k ++ ) {
            int nexti = nowi + di[k],
            nextj = nowj + dj[k];
            if(!vis[nexti][nextj]) {
                dfs(nexti, nextj, cnt+1);
            }
        }
        cur.pop_back();
        vis[nowi][nowj] = 0;
    }
    
    int main() {
        auto ans = knightTour(4,5, 3,2);
        for(Point p: ans) {
            cout <<p.x<<" "<<p.y<<endl;
        }
    }

  • 0
    S

    A simple code using backtracking in Java. The Time Complexity is O(8^(n*n-1)). Where n is the size of the board.

    Code Link: https://github.com/shivam-maharshi/Algorithms/blob/master/src/microsoft/KnightsTour.java

    /**

    • Given a starting position of a knight find the path via which it can travel

    • through the complete chess board without repetition.

    • Link: https://leetcode.com/discuss/73164/knights-tour-problem

    • @author shivam.maharshi
      */
      public class KnightsTour {

      private static int xa[] = new int[] { -1, -1, 1, 1, -2, -2, 2, 2 };
      private static int ya[] = new int[] { -2, 2, -2, 2, -1, 1, -1, 1 };

      public static void findPath(int n, int x, int y) {
      move(x, y, new int[n][n], new boolean[n][n], 1);
      }

      public static boolean move(int x, int y, int[][] board, boolean[][] visited, int count) {
      if (count == (board.length * board.length)) {
      board[x][y] = count;
      print(board);
      return true;
      }
      board[x][y] = count;
      visited[x][y] = true;
      for (int i = 0; i < 8; i++) {
      int nextX = x + xa[i];
      int nextY = y + ya[i];
      if (isValidMove(nextX, nextY, board) && !visited[nextX][nextY]) {
      if (move(nextX, nextY, board, visited, count + 1))
      return true;
      }
      }
      board[x][y] = 0;
      visited[x][y] = false;
      return false;
      }

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

      public static boolean isValidMove(int x, int y, int[][] board) {
      return x >= 0 && y >= 0 && x < board.length && y < board.length;
      }

      public static void main(String[] args) {
      findPath(8, 2, 2);
      }

    }


Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.