Timeline for Optimizing Recursion in Knight's Tour
Current License: CC BY-SA 3.0
16 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Jun 9, 2017 at 11:43 | history | edited | Rob Audenaerde | CC BY-SA 3.0 |
added 1300 characters in body
|
| Jun 9, 2017 at 11:41 | comment | added | Rob Audenaerde | I'll update the answer. | |
| Jun 9, 2017 at 11:28 | comment | added | Rob Audenaerde | I was wrong performance-wise :) There is a simple heuristic that makes it much much more efficent: take the direction with ends up on a square that has the least options. This is called the Warnsdorff’s algorithm. See here, for example: interactivepython.org/runestone/static/pythonds/Graphs/… | |
| Jun 3, 2017 at 10:26 | vote | accept | Alexander Ivanov | ||
| May 31, 2017 at 6:21 | comment | added | Rob Audenaerde | Stack is synchronized, you might not need that. Oracle advises to use Deque as well, see also stackoverflow.com/questions/12524826/… | |
| May 31, 2017 at 5:47 | comment | added | mtj | Just one little point: "If you need a stack, use a Deque [...]" - what is wrong with using a java.util.Stack if you need a Stack? | |
| May 30, 2017 at 19:38 | comment | added | Alexander Ivanov | Thank you for the tip! I'll try it out, but I guess it'll take some time at first, because I'm not familiar with it. If I'm still not able to improve the method, I'll leave it as it is and close the question. You've been really helpful. | |
| May 30, 2017 at 18:54 | comment | added | Rob Audenaerde | There is not that much to gain (performance wise at least) anymore I think. You might want to attach a profiler and check where most time is spent, maybe I am overlooking something. It is worthwhile knowing how to work with a profiler (for example visualvm) | |
| May 30, 2017 at 18:41 | comment | added | Alexander Ivanov | That's a good idea, I might try that later on. I decided to make a seperate method for the bigger board. It's basically the same without the Strings. Starting at "a1" I found 524486 solutions for about 572 seconds. Do you think there's any room for improvement, bearing in mind I must solve this recursively? | |
| May 30, 2017 at 16:35 | comment | added | Rob Audenaerde |
You are welcome :) You only need to be able to convert an int[][] board that contains a valid solution to a String representation (opposite to string manipulation in each recursion step, which happens many many times more). This would be a nice exercise for the astute reader :)
|
|
| May 30, 2017 at 16:20 | comment | added | Alexander Ivanov | Thank you for all of the information! I am quite the beginner actually, and as a result my code is not always so readable :D. Regarding String manipulation: The thing is that my assignment requires also all of the possible tours to be dispalyed in chess notation(sorry for not clearing that up) for chessboards smaller than 6x6. For the latter only the number of tours should be displayed. Maybe I should create a separate method for bigger boards? | |
| May 30, 2017 at 15:39 | comment | added | Rob Audenaerde |
Re-reading out quesion, I saw you needed to count all possible tours. There are many! See math.stackexchange.com/a/820362/53495 . I guess my solution for 6x6 will take about 6637920 seconds :/
|
|
| May 30, 2017 at 15:31 | history | edited | Rob Audenaerde | CC BY-SA 3.0 |
added 653 characters in body
|
| May 30, 2017 at 15:24 | history | edited | Rob Audenaerde | CC BY-SA 3.0 |
added 653 characters in body
|
| May 30, 2017 at 15:17 | history | edited | Rob Audenaerde | CC BY-SA 3.0 |
added 653 characters in body
|
| May 30, 2017 at 15:04 | history | answered | Rob Audenaerde | CC BY-SA 3.0 |