You have a lot of nested code which looks very dense to me a lot of text without white-space , and this makes it less readable. In order to speed up the process, selecting to which field you have to jump first makes a huge difference in total performance. If you jump to the field which has the least options, you can speed up the total process by orders of magnitude.
You can use one board and encode the solution directly on the board. You don't need to keep a list, because all the information to mark a field as occupied and release it if the path fails is in the recursive method. I reused the Point class from java. I use a special value to encode the no-used state, and put that in a static variable so the intent of the code becomes more clear, without having to add additional documentation.
Basically, I run through the KingsTour. I check if they are on the board, and if so, recurse into them. There is an optimization that I took for knowing that we are done. This however, uses an additional argument in the recursive call. What I do to determine that I'm done is to check if I made levels of recursion without entering an invalid state. Of course, you could also check if the entire board is used. Sign up to join this community. The best answers are voted up and rise to the top.
Stack Overflow for Teams — Collaborate and share knowledge with a private group. Create a free Team What is Teams? Learn more. Asked 4 years, 7 months ago. Active 4 years, 7 months ago. Viewed 2k times.
ArrayList; import java. This is the field class for reference: import java. List; import java. Improve this question. Alexander Ivanov.
Alexander Ivanov Alexander Ivanov 33 7 7 bronze badges. Now you have a strange mix addZug , currentFeld etc. This makes it harder for non-german reviewers.
Sorry for not considering that and thanks for the tip. No matter how much you optimize your current code, if you don't change the algorithm you're using, you are going to run into the same problem one or two steps further: even if you are able to solve 6x6 in a reasonable amount of time, 7x7 or 8x8 will still take a huge amount of time. We keep the track of the moves in a matrix.
This matrix stores the step number in which we visited a cell. For example, if we visit a cell in the second step, it will have a value of 2. This matrix also helps us to know whether we have covered all the cells or not. Thus, our approach includes starting from a cell and then choosing a move from all the available moves. Then we check if this move will lead us to the solution or not. If not, we choose a different move.
Also, we store all the steps in which we are moving in a matrix. Now, we know the basic approach we are going to follow. So, let's develop the code for the same. As mentioned above, 'sol' is the matrix in which we are storing the steps we have taken. A move is valid if it is inside the chessboard i.
We will make the value of all the unoccupied cells equal to As stated above, there is a maximum of 8 possible moves from a cell i, j. Thus, we will make 2 arrays so that we can use them to check for the possible moves. Thus if we are on a cell i, j , we can iterate over these arrays to find the possible move i.
Now, we will make a function to find the solution. We will start by checking if the solution is found. Our next task is to move to the next possible knight's move and check if this will lead us to the solution. If not, then we will select the different move and if none of the moves are leading us to the solution, then we will return false. If this move is not leading us to the solution, then we will choose a different move loop will iterate to a different move.
So, let's do this. We will start the tour of the knight from the cell 1, 1 as its first step. We are not going into the full time complexity of the algorithm. Closed path on a 12x12 board: [1]. Open path on a 24x24 board: [2]. Knights Tour FreeBasic image. Moreover, there can be multiple visual representations of the same program. Even though it is possible to have textual representation —i.
By default remote servers are used, but they are limited in memory and processing power, since they are intended for demonstration and casual use.
A local server can be downloaded and installed, it has no limitations it runs in your own computer. In this page you can see the program s related to this task and their results. The following can be used when debugging to validate the board structure and to image the available moves on the board. Solution: The Knight's tour essay on the Jwiki shows a couple of solutions including one using Warnsdorffs algorithm.
You can test it here. Uses the Hidato puzzle solver module, which has its source code listed here in the Hadato task. It shows that Hidato and Knights Tour are essentially the same problem. Without this check, the program crashes with an IndexError as Nim in debug and in release modes generates code to insure that indexes are valid.
We have added a case to test the absence of solution. Note that, in this case, there is a lot of backtracking which considerably slows down the execution. Knight's tour using Warnsdorffs algorithm. It will even solve a x in 0. Knights tour using Warnsdorffs algorithm. There is a slight deviation to a strict interpretation of Warnsdorff's algorithm in that as a convenience, tuples of the length of the knight moves followed by the position are minimized so knights moves with the same length will try and break the ties based on their minimum x,y position.
In practice, it seems to give comparable results to the original algorithm. Based on a slight modification of Warnsdorff's algorithm , in that if a dead-end is reached, the program backtracks to the next best move. This is an open tour solution. See this task's discussion page for an explanation, the section is The 7x7 problem.
0コメント