Why does this solution for the given challenge doesn't work?

Question

A Tryst With Chess - A Backtracking Problem

You are given a 10X10 chessboard with a knight on coordinate (I,J). You have to find the number of blocks on the chessboard that the knight can be at in exactly N moves.

Input:
Input will consist of three space separated integers I,J,N . N is less than 10.

Output:
Print a single integer denoting the number of blocks on the chessboard that the knight can be at in exactly N move.

---

My solution:

#include <iostream>

using namespace std;

#define S 10

bool move_possible(int board[S][S], int x, int y,int i,int j) {
  if (((x - 2 == i || x + 2 == i) && (y - 1 == j || y + 1 == j)) ||
      ((x - 1 == i || x + 1 == i) && (y - 2 == j || y + 2 == j)) )
    return true;
  return false;
}


bool Knight_moves(int board[S][S], int x, int y, int n, int &b) {
  if (n > 0) {
    for (int i = 0; i < S; i++) {
      for (int j = 0; j < S; j++) {
        if (!move_possible(board, x, y, i, j)) continue;
        board[i][j]++;
        if (Knight_moves(board, i, j, n - 1, b)) return true; 
      }
    }
  }
  return false;
}

int main() {
  int board[S][S];

  for (int i = 0; i<S; i++) {
    for (int j = 0; j<S; j++) {
      board[i][j] = 0;
    }
  }

  int x, y, n, b;
  b = 0;
  cin >> x >> y >> n;
  Knight_moves(board, x - 1, y - 1, n, b);
  int moves = 0;
  for (int i = 0; i<S; i++) {
    for (int j = 0; j<S; j++) {
      moves += board[i][j];
    }
  }

  cout << moves;
  cin.get();
  cin.get();

  return 0;
}

This Solution is giving correct output for some inputs like:

• Input : 1 1 1 , Output: 2

• Input : 3 3 1 , Output: 8

• Input : 3 3 2 , Output: 50

But The Solution gives incorrect output for some inputs like :

• Input : 4 7 6 , My Output : 128382 , Correct Output : 50

• Input : 3 8 5 , My Output : 14364 , Correct Output : 50

Answer 1

Since nobody answered your question, i.e. why your code doesn't work, I suppose I might as well try.

The reason why

Your algorithm is faulty. It boils down to this:

function wander_on_the_board(x,y,n)
  if (n != 0)
    for each possible move from square(x,y) to square(i,j)
      increment board[i][j]
        wander_on_the_board (i,j,n-1)

wander_on_the_board(x,y,n)
result = sum of all board values

So this will add one to your solution each time the knight can move, for all possible moves from the start position.
This number roughly represents the number of distinct paths (i.e. chains of successive moves) the knight can follow in N moves, multiplied by N.

It will work for N=1 because each path will lead to a different square. It might work by chance for 2 moves because most of the paths will still lead to different squares and the counting errors might be compensated by the moves blocked by the board edges. For N>2, the number of overlapping paths will already be enough to produce a wrong result, and it will only get worse with each new value of N.

Some things to consider

A couple of rats you might have smelled (as others already mentioned):

• the result cannot possibly exceed 100 (there are only so many squares on a chessboard)
• you never use the counters you put in your board, except for the final sum. Incrementing a global counter would produce the same result. That means you don't take already visited squares into account.

By the way, your method for looking up possible moves is seriously inefficient. What you do is browse through the 100 squares of the board, checking every one of them for 8 possible moves in the off chance a given square would happen to be reachable by your knight. The usual method is rather to enumerate the 8 possible moves of the knight from its current position and eliminate those that land outside the board.

Seriously, using one-letter identifiers is pretty annoying for anyone trying to read your code (yourself included if you fancy to come back to it after a few days). It doesn't even impress the chicks anymore, they all fall for the Pure and Immutable knights of the Functional Table these days. So do everyone a favour and start naming your variables. Please? Pretty please?

If it's broken, do fix it

Now for making your algorithm work, all you have to do is count the relevant value. Simply put a 1 in the squares the knight ends up sitting on after exactly N moves, and the final sum will yield the proper result.

Here is a modified version of your code, with the tiny tweak needed to make it work (only the modified function is shown, I didn't touch anything else):

bool Knight_moves(int board[S][S], int x, int y, int n, int& b) {
    if (n > 0) {
        for (int i = 0; i < S; i++) {
            for (int j = 0; j < S; j++) {
                if (!move_possible(board, x, y, i, j)) continue;
                if (n == 1) board[i][j] = 1; // <------------------ there you go
                if (Knight_moves(board, i, j, n - 1, b)) return true;
            }
        }
    }
    return false;
}

All is well that ends well, but...

Apparently you're only asked to compute results for N <= 10 so, given the obscene amount of computing power available in your average desktop processor, you can get away with the most horribly inefficient code and don't need to implement any heuristics or cuts in the search tree.

I fail to see the point in this limitation, it only deprives you of an opportunity to experience the classic problem of all board game exploration algorithms (an exponential growth of the computation time) and cut your teeth on the captivating problems of optimization they spark off.

I'll spare you the details but, based on some advanced guestimation, considering that my debug build of your code needs a couple seconds to produce a result for N=10 and assuming a(n optimistic) factor 4 in the exponential growth of the computation time, it would take a few years to produce a result for N=20, and a few millions for N=30. If the late Professor Hawking is to be trusted, the last black hole in the universe would have long evaporated before we knew the first answer for N=40...

This is also true for the two other answers that provide working pieces of code. They follow the same brute-force pattern with no decisive optimization. The one in JavaScript actually brought my poor Firefox to its knees when I foolishly called it for N=20.

As for the answer you selected, it doesn't provide a working code and seems a bit fishy to me. I don't see the point in keeping track of each intermediate move. As long as it is not used to optimize the algorithm, it looks more like extra bookkeeping that complicates the problem and is more likely to cause bugs for no obvious gain.

Now for some optimization

The number of possible values for the result is very limited. It cannot be more than 50 because a knight can only reach at most half the squares of a board, no matter where it starts.

Moreover, this number is guaranteed to reach 50 for a sufficiently high value of N, because the surface covered by a knight is a repeating pattern that will always end up filling a 9x9 subpart of the board regardless of the starting position.

Lastly, the number of reachable positions can never decrease as N increases, simply because granting the knight one more move can only allow it to cover more ground. Therefore, once the result reaches 50, you know for a fact it will remain equal to 50 for any greater value of N.

So we got our optimization now: keep computing solutions for all values of N until the requested N is reached or the result becomes equal to 50.

The worst possible value of N needed to reach 50 can easily be computed by checking every possible starting position. As it happens, the needed number of moves varies between 3 (for squares near the centre) and 6 (for squares near the corners).

Any result for N=6 can be computed in an instant by your average desktop computer, which means this optimization is enough to produce a result in the blink of an eye for any value of X, Y and N.

A somewhat dirty but trivial trick is to clamp the value of N to 6 and let the brute force algorithm run its course.
That will perform some useless computations for the squares that reach 50 for smaller values of N, but the difference is so minuscule the extra complexity of a more subtle solution is hardly justified.

So here is the optimized version of your original code. Only the relevant part is shown, I didn't touch anything else (except the previous bug fix, of course).

int x, y, n, b;
b = 0;
cin >> x >> y >> n;
if (n > 6) n = 6; // <---- jump off the one-way train to the end of the universe
Knight_moves(board, x - 1, y - 1, n, b);
int moves = 0;
for (int i = 0; i < S; i++) {
    for (int j = 0; j < S; j++) {
        moves += board[i][j];
    }

Answer 2

function followKnight(x,y,move) {
  let obj = {};

  console.log(knight(x - 1, y - 1, move, 10, obj));

  function knight(x, y, move, z, obj) {
    if (move === 0 && obj[`${x},${y}`] === undefined) {
      obj[`${x},${y}`] = 1;
      return 1;
    }
    let total = 0;
    if (move > 0) {
      let xSide = [1, 1, 2, 2, -1, -1, -2, -2];
      let ySide = [-2, 2, -1, 1, -2, 2, -1, 1];
      for (let i = 0; i < 8; i++) {
        if (
          xSide[i] + x >= 0 &&
          xSide[i] + x <= z - 1 &&
          ySide[i] + y >= 0 &&
          ySide[i] + y <= z - 1
        ) {
          total += knight(xSide[i] + x, ySide[i] + y, move - 1, z, obj);
        }
      }
    }

    return total;
  }
}

followKnight(3,3,1)

Answer 3

My solution:

#include<cmath>


#include<iostream>


#include<vector>

using namespace std;

static int A[11][11]={0};

static int count;

int chess(int A[11][11],int i,int j,int step,int n)

{

     int p;
     if(i<=0 || i>=11 || j<=0 || j>=11)
    {
        return 0;
    }

     if(n==step)
   {
    if(A[i][j]==0)

       {
           A[i][j]++;

           count++;

       }
       return 0;
   }
    
   
else{
    
for(p=step;p<=n;p++)
   
 {
   

 chess(A,i-2,j-1,p+1,n);
   

 chess(A,i-2,j+1,p+1,n);
   
 chess(A,i+2,j+1,p+1,n);
   
 chess(A,i+2,j-1,p+1,n);
   
 chess(A,i-1,j+2,p+1,n);
   
 chess(A,i-1,j-2,p+1,n);
   
 chess(A,i+1,j+2,p+1,n);
   
 chess(A,i+1,j-2,p+1,n);
   
 return 0;
   
 }
}

}

int main()

{
    

  int i,j,n;

  cin>>i>>j>>n;

  chess(A,i,j,0,n);

  cout<<count;
}

Answer 4

Here's one algorithm you can try.

First, create the 10x10 array and set each element to -1. This marks the square as not-attacked.

Next, get the input and mark the starting position with a 0.

Now, mark every square the knight is attacking with a 1:

.  1  .  1  .  .  .  .  .  .  
1  .  .  .  1  .  .  .  .  .  
.  .  X  .  .  .  .  .  .  .  
1  .  .  .  1  .  .  .  .  .  
.  1  .  1  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  

(I've replaced -1 with . and start with X for clarity). Here, I = 3, J = 3, and N = 1. So just add up the squares with N (there are 8 of them).

For N > 1, repeat. Each iteration, check every square on the board. If it was marked in the previous iteration, then mark every square it is attacking.

Example: 3 3 2

.  .  2  .  .  .  2  .  .  .  
.  2  .  2  .  2  .  .  .  .  
2  .  2  .  2  .  2  .  .  .  
.  2  .  2  .  2  .  .  .  .  
.  .  2  .  .  .  2  .  .  .  
.  2  .  2  .  2  .  .  .  .  
2  .  2  .  2  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  

Every square that was being attacked by a 1 is now marked with a 2. There are 20 of these. Repeat.

And 3 3 3:

.  3  .  3  .  3  .  3  .  .  
3  .  3  .  3  .  3  .  3  .  
.  3  .  3  .  3  .  3  .  .  
3  .  3  .  3  .  3  .  3  .  
.  3  .  3  .  3  .  3  .  .  
3  .  3  .  3  .  3  .  3  .  
.  3  .  3  .  3  .  3  .  .  
3  .  3  .  3  .  3  .  .  .  
.  3  .  3  .  3  .  .  .  .  
.  .  .  .  .  .  .  .  .  .  

Every space attacked by 2 is now marked with a 3.