Massive Algorithms: Backtracking | Set 1 (The Knight's tour problem)

Backtracking | Set 1 (The Knight's tour problem) | GeeksforGeeks

Backtracking | Set 1 (The Knight's tour problem) | GeeksforGeeks
The knight is placed on the first block of an empty board and, moving according to the rules of chess, must visit each square exactly once.

Problems which are typically solved using backtracking technique have following property in common. These problems can only be solved by trying every possible configuration and each configuration is tried only once.

Backtracking works in incremental way and is an optimization over the Naive solution where all possible configurations are generated and tried.
http://www.tri.org.au/knightframe.html

Backtracking works in an incremental way to attack problems. Typically, we start from an empty solution vector and one by one add items (Meaning of item varies from problem to problem. In context of Knight’s tour problem, an item is a Knight’s move). When we add an item, we check if adding the current item violates the problem constraint, if it does then we remove the item and try other alternatives. If none of the alternatives work out then we go to previous stage and remove the item added in the previous stage. If we reach the initial stage back then we say that no solution exists. If adding an item doesn’t violate constraints then we recursively add items one by one. If the solution vector becomes complete then we print the solution.

If all squares are visited 
    print the solution
Else
   a) Add one of the next moves to solution vector and recursively 
   check if this move leads to a solution. (A Knight can make maximum 
   eight moves. We choose one of the 8 moves in this step).
   b) If the move chosen in the above step doesn't lead to a solution
   then remove this move from the solution vector and try other 
   alternative moves.
   c) If none of the alternatives work then return false (Returning false 
   will remove the previously added item in recursion and if false is 
   returned by the initial call of recursion then "no solution exists" )

Java code from http://www.sanfoundry.com/java-program-implement-knights-tour-problem/

private boolean isSafe(int x, int y)
{
 if (x >= 0 && x < N && y >= 0 && y < N && soln[x][y] == -1)
  return true;
 return false;
}
private boolean solveKTUtil(int x, int y, int movei, int xMove[],int yMove[])
{
 int k, next_x, next_y;
 if (movei == N * N)
  return true;
 for (k = 0; k < N; k++)
 {
  next_x = x + xMove[k];
  next_y = y + yMove[k];
  if (isSafe(next_x, next_y))
  {
   soln[next_x][next_y] = movei;
   if (solveKTUtil(next_x, next_y, movei + 1, xMove, yMove))
    return true;
   else
    soln[next_x][next_y] = -1;
  }
 }
 return false;
}

public boolean solveKnightTour()
{
 for (int x = 0; x < N; x++)
 {
  for (int y = 0; y < N; y++)
  {
   soln[x][y] = -1;
  }
 }
 int xMove[] = { 2, 1, -1, -2, -2, -1, 1, 2 };
 int yMove[] = { 1, 2, 2, 1, -1, -2, -2, -1 };
 soln[0][0] = 0;
 if (!solveKTUtil(0, 0, 1, xMove, yMove))
 {
  System.out.println("the solution does not exist");
  return false;
 }
 else
 {
  printSolution();
 }
 return true;
}

Java code: http://en.algoritmy.net/article/39907/Knights-tour

public void solve() {

066.for (int i = 0; i < ySize; i++) {

067.for (int j = 0; j < xSize; j++) {

068.takeTurn(j, i, 0);

069.solutionBoard[i][j] = NOT_VISITED; //reset the square

070.}

071.}

072.}

private void takeTurn(int x, int y, int turnNr) {

108.solutionBoard[y][x] = turnNr;

109.if (turnNr == (xSize * ySize) - 1) {

110.solutionsCount++;

111.printSolution();

112.return;

113.} else {

114.for (Coords c : getFields(x, y)) {

115.if (solutionBoard[c.getY()][c.getX()] == NOT_VISITED) {

116.takeTurn(c.getX(), c.getY(), turnNr + 1);

117.solutionBoard[c.getY()][c.getX()] = NOT_VISITED; //reset the square

118.}

119.}

120.}

121.}

private List<Coords> getFields(int x, int y) {

081.List<Coords> l = new ArrayList<Coords>();

082.if (x + 2 < xSize && y - 1 >= 0)

083.l.add(new Coords(x + 2, y - 1)); //right and upward

084.if (x + 1 < xSize && y - 2 >= 0)

085.l.add(new Coords(x + 1, y - 2)); //upward and right

086.if (x - 1 >= 0 && y - 2 >= 0)

087.l.add(new Coords(x - 1, y - 2)); //upward and left

088.if (x - 2 >= 0 && y - 1 >= 0)

089.l.add(new Coords(x - 2, y - 1)); //left and upward

090.if (x - 2 >= 0 && y + 1 < ySize)

091.l.add(new Coords(x - 2, y + 1)); //left and downward

092.if (x - 1 >= 0 && y + 2 < ySize)

093.l.add(new Coords(x - 1, y + 2)); //downward and left

094.if (x + 1 < xSize && y + 2 < ySize)

095.l.add(new Coords(x + 1, y + 2)); //downward and right

096.if (x + 2 < xSize && y + 1 < ySize)

097.l.add(new Coords(x + 2, y + 1)); //right and downward

098.return l;

099.}

Also check http://rosettacode.org/wiki/Knight's_tour#Java

public class KnightsTour {
    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) {
        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 = 2 + (int) (Math.random() * (base - 4));
        int col = 2 + (int) (Math.random() * (base - 4));
 
        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();
        }
    }
}

https://advancedoptimizationatharvard.wordpress.com/2014/05/16/knights-tour-and-warnsdorffs-rule/

Warnsdorff’s Rule

It stipulates that we move the knight such that it advances to a square which has the fewest onward moves from that particular starting location.

Chess: What is the proof for Warnsdorff's rule of the Knight's tour?

The heuristic is to visit a square which has less number of non-visited neighbors. This is quite intuitive because if we have to visit all the squares in a tour, we better visit those squares which are remote and are difficult to be reached.
As with any heuristic, there is no mathematical proof for Warnsdoff's rule that it will always produce a valid tour.

http://en.wikipedia.org/wiki/Knight's_tour

This rule may also more generally be applied to any graph. In graph-theoretic terms, each move is made to the adjacent vertex with the least degree. Although the Hamiltonian path problem is NP-hard in general, on many graphs that occur in practice this heuristic is able to successfully locate a solution in linear time.[13] The knight's tour is a special case.

Warnsdorff’s Rule applies to boards of size 50 or less but experiences difficulty finding an tour past that point. Two improvements (W+ and W2) have been introduced as better methods that draw on the same principles as Warnsdorff’s Rule.

Additionally, in the event of a tie between two squares, various tie-breaking algorithms have been developed to address that situation.

http://www.simplecode.in/famous-problems/knights-tour/#ffs-tabbed-392

Knight’s Tours Using a Neural Network

http://mccxj.github.io/blog/20120712_horse-riding-chessboard.html
在每个结点对其子结点进行选取时，优先选择‘出口’最小的进行搜索，‘出口’的意思是在这些子结点中它们的可行子结点的个数，也就是‘孙子’结点越少的越优先跳，为什么要这样选取，这是一种局部调整最优的做法，如果优先选择出口多的子结点，那出口少的子结点就会越来越多，很可能出现‘死’结点（顾名思义就是没有出口又没有跳过的结点），这样对下面的搜索纯粹是徒劳，这样会浪费很多无用的时间，反过来如果每次都优先选择出口少的结点跳，那出口少的结点就会越来越少，这样跳成功的机会就更大一些。这种算法称为为贪心算法，也叫贪婪算法或启发示算法，它对整个求解过程的局部做最优调整，它只适用于求较优解或者部分解，而不能求最优解。这样的调整方法叫贪心策略
http://bosshida.iteye.com/blog/729854

public class HorseStep {
static final int[] dx = { -1, -2, -2, -1, 1, 2, 2, 1 }; // x方向的增量
static final int[] dy = { 2, 1, -1, -2, -2, -1, 1, 2 }; // y方向的增量
static final int N = 8;
static int[][] board = new int[N][N]; // 棋盘
// 计算结点出口
int waysOut(int x, int y) {
int tx, ty;
int count = 0;
// 结点位置非法或已踏过，返回-1
if (x < 0 || y < 0 || x >= N || y >= N || board[x][y] > 0) {
return -1;
}
for (int i = 0; i < N; ++i) {
tx = x + dx[i];
ty = y + dy[i];
if (tx < 0 || ty < 0 || tx >= N || ty >= N) {
continue;
}
if (board[tx][ty] == 0) {
count++;
}
}
return count;
}
// 按结点出口数，从小到大排序
void sortnode(HorseNode[] hn, int n)// 采用简单排序法，因为子结点数最多只有8
{
int i, j, t;
HorseNode temp;
for (i = 0; i < n; ++i) {
for (t = i, j = i + 1; j < n; ++j)
if (hn[j].waysOutNum < hn[t].waysOutNum)
t = j;
if (t > i) {
temp = hn[i];
hn[i] = hn[t];
hn[t] = temp;
}
}
}
// 搜索函数,count代表当前第几步
void dfs(int x, int y, int count) {
int i, tx, ty;
HorseNode[] tExit = new HorseNode[N]; // 记录出口结点的出口数
if (count > N * N) {
output();
return;
}
// 计算[x,y]的出口结点和出口结点的出口数
for (i = 0; i < N; i++) {
tx = x + dx[i];
ty = y + dy[i];
HorseNode h = new HorseNode();
tExit[i] = h;
tExit[i].x = tx;
tExit[i].y = ty;
tExit[i].waysOutNum = waysOut(tx, ty);
}
sortnode(tExit, N);
for(i = 0; tExit[i].waysOutNum < 0; ++i)
;
for(; i < N; ++i){
tx = tExit[i].x;
ty = tExit[i].y;
board[tx][ty] = count;
dfs(tx, ty, count + 1);
board[tx][ty] = 0;
}
}
public static void main(String[] args) {
int x = 1;
int y = 3;
HorseStep test = new HorseStep();
board[x][y] = 1;
test.dfs(x, y, 2);
}
//打印结果
void output(){
for(int i = N - 1; i >= 0; --i){
for(int j = 0; j < N; ++j){
System.out.printf("%2d ", board[i][j]);
}
System.out.println();
}
System.exit(0);
}
}
class HorseNode {
int x;
int y;
int waysOutNum;
}

http://jradley.com/knightstour/
The Knight's Tour problem is ideal for multithreading. Consider that we are evaluating potential moves for a knight at a particular depth. We can kick off a separate thread to evaluate an individual jump for us. When the application is started the number of threads which are to be run by the application can be specified, else the application defaults to running on 8 threads;

Read full article from Backtracking | Set 1 (The Knight's tour problem) | GeeksforGeeks

Backtracking | Set 1 (The Knight's tour problem) | GeeksforGeeks

Labels

Popular Posts