0

I am trying to solve the knight's tour problem, but it's getting stuck in an infinite loop. I tried debugging but no change. Could someone please help me out? Thank you.

#include <iostream>
#include <bits/stdc++.h>

using namespace std;

void knightMove(int x, int y, vector<vector<int>> chess, int moves) {
    // check if the cell is valid to make a move
    if(x<0 || x>=8 || y<0 || y>=8 || chess[x][y]!=-1) return;
    // if it is valid, we put the current move number in place
    chess[x][y] = moves;
    // base condition to print the final answer and return
    if(moves==63) {
        for(int p=0; p<8; p++) {
          for(int q=0; q<8; q++) {
            cout << chess[p][q] << " ";
          }
          cout << endl;
        }
        chess[x][y]=-1;
        return;
    }
    // traversal arrays
    int i[] = {2,2,-2,-2,1,1,-1,-1};
    int j[] = {1,-1,1,-1,2,-2,2,-2};

    for(int k=0; k<8; k++) {
        knightMove(x+i[k], y+j[k], chess, moves+1);
    }
    // backtracking
    chess[x][y]=-1;
    return;
}

int main() {
    vector<vector<int>> chess (8, vector<int> (8,-1));
    knightMove(0,0,chess, 0);
}
Sridev
  • 1
  • in the line "for(int k=0; k<8; k++)", I notice that if you change the condition to "k < 4", then the code won't get stuck in an infinite loop. Maybe, you want to look further into that for loop. – Job_September_2020 May 30 '21 at 18:57
  • How are you checking for an infinite loop? Could it just be taking a while to process all of the recursions? – mattlangford May 30 '21 at 18:58
  • 1
    @Sridev, I think there is a way to fix or stop the infinite loop. If you change the line "if( moves == 63)" to "if ( moves <= 63 )", then the code exits just fine and prints out some outputs. (Note: I don't know if this change is the correct algorithm though). – Job_September_2020 May 30 '21 at 19:03
  • Probably going to find [this Q&A](https://stackoverflow.com/questions/19214109/how-to-optimize-knights-tour-algorithm) worth reading. – WhozCraig May 30 '21 at 19:03
  • @mattlangford my visual studio code just gives up after few seconds, I checked for an infinite loop by putting the visiting coordinates in a console log, and it just stops after reaching around 55 moves out of 63 required. I tried running it on other systems/IDE as well, only to yield the same result. – Sridev May 30 '21 at 19:17
  • @WhozCraig Thank you for the thread link. I'll check it right now. – Sridev May 30 '21 at 19:18
  • This code is correct, in that it doesn't run an infinite loop, and will eventually finish. It just takes a very long time exploring every dead end by brute force. I can't reproduce "stop at 55 moves" - it consistently reaches 61 for me, but the remaining two squares are always unreachable, so it has to backtrack. – Igor Tandetnik May 30 '21 at 19:19
  • Thank you @IgorTandetnik for the confirmation. I was worried that my logic had some error, and needed to be rectified. Perhaps my IDE/system has its limitations and hence not going beyond 55-56. – Sridev May 30 '21 at 19:21
  • You can improve the performance easily with `void knightMove(int x, int y, vector>& chess, int moves) {...}` Note the ampersand. You are passing the board by value, thus making lots of copies. Passing by reference avoids those copies. It's still too slow to find a solution in a reasonable time, but it should be able to get to 61 this way. – Igor Tandetnik May 30 '21 at 19:26
  • Do you have special reasons for those code-golfing antipatterns? – Yunnosch May 30 '21 at 19:28
  • @Yunnosch I am sorry but I didn't get you. I am a noob at this, could you please let me know any errors in the code? – Sridev May 30 '21 at 19:34
  • The only reason I know for doing these things `#include using namespace std; ` is code golfing. Do you attempt to code-golf this? – Yunnosch May 30 '21 at 19:58
  • 1
    @Yunnosch it can't be code golf. The only other header he needs is vector and `#include ` is longer than `#include ` I think he has been taught to include bits/stdc++.h as a convenience so that he doesn't have to remember which headers things are in (although vector is pretty easy to figure out) – Jerry Jeremiah May 31 '21 at 01:10
  • As far as `#include ` is concerned: https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h https://stackoverflow.com/questions/31816095/why-should-i-not-include-bits-stdc-h – Jerry Jeremiah May 31 '21 at 01:11
  • As far as `using namespace std;` is concerned: https://stackoverflow.com/questions/1452721/why-is-using-namespace-std-considered-bad-practice – Jerry Jeremiah May 31 '21 at 01:12
  • Regarding your runtime, you might try a different motion vector set. Ex: `int i[] = { 2, 1, -1, -2, -2, -1, 1, 2 }; int j[] = { 1, 2, 2, 1, -1, -2, -2, -1 };` Complexity-wise everything is just the same, but the fill-pattern should complete much earlier when starting at origin 0,0. – WhozCraig May 31 '21 at 02:24
  • As far as I can tell the code is working - but, in the worst case, it has to check trillions (or more!) board positions so it may need to run for days to find anything. If you want to check that it is working use a 5x5 board and it will complete faster. – Jerry Jeremiah May 31 '21 at 02:40
  • The other thing is, I don't think it stops when it finds an answer - it looks like it returns the same way in that case as when it is backtracking... – Jerry Jeremiah May 31 '21 at 02:46
  • @JerryJeremiah I am not questioning whether it is successful code golf. I question whether it is a conscious attempt to code golf. Because if it is not, then it indicates bad habits from trying to learn programming from challenge communities. I would have linked to the same things you provided in that case. – Yunnosch May 31 '21 at 05:16

0 Answers0