I’m trying to make a program that goes through all squares of a chessboard (size doesn’t really matter, but for now it’s 6×6) with a knight, called a “Knight’s Tour” check it out on wiki.
The tour is supposed to be closed, which means the knight on the last visited square can “attack” the square he started at. The code works fine for some squares, for example, input ‘traverse(1,1,1)’ in main generates output that shows not only is he traversing but backtracking and going back to traversing towards the goal successfully. However, would I input ‘traverse(1,0,0)’ instead, I get a StackOverflowError. Since it is successful sometimes, backtracking and traversing, I know the code works, I just have no idea how to get rid of the errors. I assume I’m making too many calls, but I have no idea how to get around that, there’s alot of squares to visit 🙂 Edited out the code, mostly because the teacher could find it an say I cheated.
Advertisement
Answer
You are trying to solve an exponential complexity problem with recursion. That’s not going to work outside of very small inputs. The stack size grows way faster than the size of the problem. It will not take a very large problem size to blow through the stack.
You are not going to get StackOverflowErrors to go away. You need to re-think your algorithm to be loop-based instead of recursion based.