programming forums Java Mobile Certification Databases Caching Books Engineering Micro Controllers OS Languages Paradigms IDEs Build Tools Frameworks Application Servers Open Source This Site Careers Other Pie Elite all forums
this forum made possible by our volunteer staff, including ...
Marshals:
• Campbell Ritchie
• Tim Cooke
• Devaka Cooray
• Ron McLeod
• Jeanne Boyarsky
Sheriffs:
• Liutauras Vilda
• paul wheaton
• Junilu Lacar
Saloon Keepers:
• Tim Moores
• Stephan van Hulst
• Piet Souris
• Carey Brown
• Tim Holloway
Bartenders:
• Martijn Verburg
• Frits Walraven
• Himai Minh

# Knight's Tour

Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:
Hi.

I have asked a question before regarding an assignment (I got helped greatly!) and I'm here again for some guidance for another one.

Basically I have to solve the chess puzzle by creating a Graph of a 5x5 or 8x8 board and then using Depth First Search.

I have no problem whatsoever understanding the assignment, the only thing I need guidance is on how create edges the Graph using this: http://algs4.cs.princeton.edu/41graph/Graph.java.html

I am not 100% sure how to achieve making the Graph similar to this board (by adding the edges):

Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:
hi Kevin,

to me it seems easiest to number the squares 0...24.
Then write a method that transforms a number to a chess field notation,
and a method that converts from a chess field notation to a number.

For instance, let's name the bottom squares, from left to right, 0, 1, 2, 3, 4
In chess the names are a1, b1, ..., e1, or in integer notation:

(0,0), (1,0), ... , (4,0);

Now, we can translate every integer 0 ... 24 to a chess square and back again.

Having this, a Knight on square 0 (i.e. (0,0)) can go to square (2, 1) and (1,2).
(2,1) is square 7, (1, 2) is square 11.

Translate (2,1) and (1,2) back to numbers, and we have the edges (0, 7) and (0, 11)

Or in terms of an adjacency map: key 0, List [ 7, 11].

Et cetera. I'm not sure what a Bag is, haven't encountered it in Java so far.

Bartender
Posts: 1464
32
• 1
• Number of slices to send:
Optional 'thank-you' note:
As the Princeton programmers have implemented it, a graph is a set of vertices (a lot of us would use the word "nodes" instead), and a set of edges. The vertices are just integers. They really don't mean anything (that is, the particular integer you pick to represent a vertex doesn't tell you anything about the vertex, so one vertex could be assigned the integer 5, while another could be assigned the integer 117, in a graph that had say, only two vertices in it). The important thing is that each vertex must be represented by a unique integer (that is, no two vertices can be represented by the same integer).

An edge is simply a pair of vertices. So, if your set of vertices, V is this: {1, 4, 8, 13, 2, 7}, then an edge is any pair of those integers, such as (1, 8), (13, 4), or (7, 1). (Note that some implementations won't let you make an edge out of the same vertex used twice, like (8, 8), though the Princeton version does appear to allow this. I doubt you'll need that ability for your assignment, however.)

Typically, an edge represents a path from one vertex to another. I'll add that, to a pure mathematician, that would probably seem like a dangerously limiting characterization, but it will do for now. In your problem, I expect you will just number each square on your board from 1 to 25 (or from 1 to 64). The edges are probably going to be paths from each square to every other square that a knight can reach in one move. So, a 5x5 board might have these vertices:

Let's say a knight is at vertex 17. What other vertices can it reach in one move? Well, it can reach vertex 6, so one edge would be the pair, (17, 6). You would add that to the graph with the addEdge method, simply addEdge(17, 6). However, note that this is an undirected graph, which means the edge {17, 6) is the same as the edge (6, 17). When you are computing possible moves that a knight can make from vertex 6, you will include the move to vertex 17, but you won't want to add the same edge later if you compute possible moves from vertex 6, then go on to compute moves from vertex 7, then vertex 8, and so on, until you get to vertex 17, where (17, 6) is an edge representing a possible move. You will already have included it when you computed the moves possible from vertex 6. Part of your problem, most likely, will be to avoid adding duplicate edges, as the Princeton code doesn't appear to stop you from doing that.

Once you've added all the possible moves from every square as edges, you will be in a position to use your graph to solve the "Knight's Tour" problem, which (if it's the same one everyone else considers) means figuring out how to start at any square, move once to every other square, and finish back where you started.

Does any of that help?

Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:. . .
Then write a method that transforms a number to a chess field notation,
and a method that converts from a chess field notation to a number.
. . .

That is unnecessary. You can move to ±(2 × row ±1) or ±(row ± 2), where row means length of a row, e.g. 8.
On an 8×8 board that is -17, -15, -10, -6, 6, 10, 15, 17. You can have up to 8 moves from a square. There is no need to calculate row and column separately, but you can calculate the row number from sq ÷ row and the column number from sq % row where sq is the number of the square from 0…63 (for 8×8 board) and you are using integer arithmetic.

When you move, if the square reached is < 0 you have fallen off the board at the bottom. If the square is > n where n is the total number of squares on the board, you have fallen off the board at the top.
If you calculate remainder dividing the old square and the new square by the row, if
newSq % row > 5 ∧ oldSq % row < 2 ∨ oldSq % row > 5 ∧ newSq % row < 2 (for 8×8 board)
(I think) then you have fallen off the board on the left or the right. Those numbers will be different for a 5×5 board.

Campbell Ritchie
Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:

Stevens Miller wrote:. . . "Knight's Tour" problem, . . . start at any square, move once to every other square, and finish back where you started.

Does any of that help?

That is one version of the Knight's Tour, the closed tour. There is a simpler version, the open tour, which is this:-
start at any square, move once to every other square, and stop.

I have a backtracking version; unfortunately I can't persuade it to give me a closed tour.
Unless you use very small boards (e.g. 5×5) there is a combinatorial explosion; the number of different tours on an 8×8 board has about 11 digits in.

Stevens Miller
Bartender
Posts: 1464
32
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:Unless you use very small boards (e.g. 5×5) there is a combinatorial explosion; the number of different tours on an 8×8 board has about 11 digits in.

I suspect those two sets of dimensions were chosen for the purpose of demonstrating how a working algorithm can, despite the fact that it "works," become computationally impractical as a result of only a very moderate increase in the size of a problem.

Kevin Garcia
Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:
Thank you all! I think I can do it now.

But now I am not sure if I have the open tour or closed tour?

Here is my assignment:

The object is to move a knight from one square to another on an otherwise empty chess board until it has visited every square exactly once. Write a program that solves this puzzle using a depth-first search.

Campbell Ritchie
Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:
Possibly. I chose 8×8 because previous work in our group used that size and it is the same as what you actually play chess on. They probably chose 5×5 because it is big enough to have lots of tours without taking longer than the likely lifetime of the universe to calculate them all

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:That is unnecessary. (...)

Of course it is, but I've found my wat the easiest way by far.
Adding simple numers like plus or minus 7 or 11 does not qork very well at
the edges of a board.

Stevens Miller
Bartender
Posts: 1464
32
• Number of slices to send:
Optional 'thank-you' note:

Kevin Garcia wrote:Thank you all! I think I can do it now.

But now I am not sure if I have the open tour or closed tour?

Here is my assignment:

The object is to move a knight from one square to another on an otherwise empty chess board until it has visited every square exactly once. Write a program that solves this puzzle using a depth-first search.

I'd call that open tour. Do that first and, if you succeed, rewrite for closed tour. (Campbell's right: that's harder.)

Campbell Ritchie
Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:
For a closed tour, the last square should be one of the 8 (or fewer) reachable from the start square. Then you can add the start square to the end and get a closed tour.

Campbell Ritchie
Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:. . . Of course it is, but I've found my wat the easiest way by far. . . .

I suspect working out when you have fallen off the edges of the board is the same difficulty for both approaches.

Kevin Garcia
Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:
OK, I found out that I did not necessarily need to use the Graph. So I managed to display the chess board in GUI and give every move an ID. But right now it does violate the rule of the Knight Tour which is I can only visit every square once.

I would really appreciate some more guidance on how to "backtrack". I ran in some trouble doing this where I get an ArrayIndexOutOfBoundsException. So basically when the Knight is stuck and has nowhere else to go make a square unvisited and retry a different path..

StdDraw class: http://introcs.cs.princeton.edu/java/stdlib/StdDraw.java.html

Saloon Keeper
Posts: 14501
325
• Number of slices to send:
Optional 'thank-you' note:
You should separate your concerns more. Right now you're mixing GUI and business logic. Make a class that represents the board and which is responsible for keeping track of what squares were visited. All that the GUI code should do is look at a Board instance and update its cells to reflect the board.

To do backtracking, you must find out if the move you tried leads to success. That means that the solve() method should return a boolean value to reflect that the problem can be solved given the current state of the board.

For each possible move, you visit the according square, and then try to recursively solve the rest of the board. If you can't solve it, then you "unvisit" the square, and try the next move, until you reach the solved state.

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:
hi Kevin,

apart from Stephans remarks:

have a look at lines 18 and 19, the righ most assignment.

And: you correctly set visited[x][y] to true.
Suppose you find no legal 'next' squares. If you're not
done then, you must do the backtracking. What about the visited[x][y]?

Alternatively: using a Queue (and no recursion) might be a little easier to follow.

Saloon Keeper
Posts: 9742
80
• Number of slices to send:
Optional 'thank-you' note:
The logic in isLegit() is incorrect.

Kevin Garcia
Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:
Alright, thank you all for your input. I believe I am nearly done.

And indeed my isLegit (now renamed to isLegitMove) method was not working how it should. I think it is correct now.

The only issue I am having right now is that is looping infinitely. The method does not know when it has visited all the squares. Even though I do check for it if every value in the two-dimensional boolean array, visited, is set to true. Any further guidance is very appreciated.

Carey Brown
Saloon Keeper
Posts: 9742
80
• Number of slices to send:
Optional 'thank-you' note:
isLegitMove() almost right. still needs a tweak.

Kevin Garcia
Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:

Carey Brown wrote:isLegitMove() almost right. still needs a tweak.

Plus if the next square is unvisited?

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:
Yes, but also what about x > 0?

What is your moves-array currently (see lines 25, 26 and 27)?

Did you test your solve method? For instance on a 3x3 board?

A possibility that might make the solution a bit easier:

Kevin Garcia
Greenhorn
Posts: 15
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:Yes, but also what about x > 0?

What is your moves-array currently (see lines 25, 26 and 27)?

Did you test your solve method? For instance on a 3x3 board?

A possibility that might make the solution a bit easier:

Oh, I'm sorry. That might be a good approach when I need to rewrite it for readability. I did test it on a 5x5 board, and I believe it worked. And what about x > 0?

Campbell Ritchie
Marshal
Posts: 76870
366
• Number of slices to send:
Optional 'thank-you' note:

Piet Souris wrote:. . . Did you test your solve method? For instance on a 3x3 board?
. . .

Can you find a Knight's Toiur on a 3×3 board at all? I thought it was impossible for that size. Try 4×4.

Stephan van Hulst
Saloon Keeper
Posts: 14501
325
• Number of slices to send:
Optional 'thank-you' note:
I think you can make the solve() method a lot more clear if you use a Jump enum. If you then follow Piet's suggestion to create a Position class, you can apply a Jump to a Position and end up with a new Position. The Board can take a Position and return if it's been visited. Here's an outline:

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:

Kevin Garcia wrote:(...)
And what about x > 0?

See your latets isLegit-method. Is index 0 not valid?

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:
Can you find a Knight's Toiur on a 3×3 board at all? I thought it was impossible for that size. Try 4×4.

Indeed, there is no solution for a 3x3 board, but
1) solve() should be able to deal with that too!
2) but my purpose was that OP could check his 'isLegit'-method, and a 3x3 keeps the (non)solution short.

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:(...)

Nice, but it is a bit premature. Let Kevin first get his current method working!

And actually, I had a slightly different picture in mind. With my 'generateNewPositions()'
method I envisage a stream of an initial List<Position>, combined with an iterate and a flatmap,
a filter on the length of List<Integer> and a findFirst. But that is for (much) later, if at all.

Stephan van Hulst
Saloon Keeper
Posts: 14501
325
• Number of slices to send:
Optional 'thank-you' note:
I disagree. Refactoring is an important step during software development. If you find it's hard to write a method because you're getting stuck in a mire of variables, you need to refactor so you can think about the concepts you're working with more easily.

Right now Kevin's Board consists of variables visited, done, board and total, which all need to be in a consistent state before and after each method call. This is made more difficult because it's not immediately clear what the board and total variables exactly keep track of.

Look at how complex the solve method is: It has to validate a position, it's using nested for loops to check if the board is full, it has to extract x and y coordinates from a weak type (an int[]). That's too much logic that doesn't directly relate to solving the problem. These are responsibilities that should be taken up by other classes and methods. After doing this, the logic of solve() becomes much more apparent.

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:
Be it as it may, but your point of view is that of someone with great knowledge
and experience. Kevin is very close to a solution, so why not let him get to
that first?

Stephan van Hulst
Saloon Keeper
Posts: 14501
325
• 1
• Number of slices to send:
Optional 'thank-you' note:
Because the trouble he has reaching the solution is because of the lack of separation of concerns.

I thank you for the compliment, but my experience did not come from stumbling through problems, it came from looking at how more experienced people solved similar problems.

Carey Brown
Saloon Keeper
Posts: 9742
80
• Number of slices to send:
Optional 'thank-you' note:
If you want to look for solutions for all starting positions, realize that only a triangle's worth of positions are unique positions and that all others are either a mirror or rotation of the unique positions. For instance, for a 5x5 board:

Piet Souris
Saloon Keeper
Posts: 5177
207
• Number of slices to send:
Optional 'thank-you' note:
Well, that depends. When you took your very first steps, as a very young Stephan,
I bet you had not studied first how grown ups walked. I mean, every one has
his own way of learning. But let's give the word to Kevin, to see how far he is
now.

Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Stephan van Hulst wrote:The Board can take a Position and return if it's been visited...

I don't want to pile too much onto this, but it strikes me that this could be determined more easily if a Board was made up of a grid of Squares, viz:
Just a thought.

Winston

Stevens Miller
Bartender
Posts: 1464
32
• 1
• Number of slices to send:
Optional 'thank-you' note:
I wish Winston would comment, Piet and Stephan, because his oft-spoken words would apply here: what Kevin needs to do is stop coding. He's working on a classic problem that all programmers need (or ought) to solve. The point of the problem is not to learn best practices for naming variables, nor how to encapsulate, nor to detect optimal moments for refactoring. The point is to learn how a seemingly challenging problem can be addressed in a formalized way that makes the process of finding a solution subject to an automatic method. That is, to show how an algorithm can be the answer to a question that can be posed in multiple forms. For some folks, deriving the algorithm that solves The Knight's Tour (or The Towers of Hanoi, or Hexapawn, or The Sieve of Eratosthenes, or any of the other classic problems for the novice programmer) is how they recognize the potential of a finite state automaton to be as awesome as it really is.

Kevin, you're on the verge of seeing greatness here. Pause, take a deep breath, find a quiet place, and sit there with a pencil and a pad of paper. Think this through before you write any more code. The point is the solution to the problem, not the program the solution will enable you to write.

Stevens Miller
Bartender
Posts: 1464
32
• Number of slices to send:
Optional 'thank-you' note:
Oh, for the love of...

Winston wrote his comment while I was writing mine, saying I wished he would comment. (Alas, I have presumed upon him wrongly, as he did not suggest what I thought he would. My apologies for speaking out of my place.)

Stephan van Hulst
Saloon Keeper
Posts: 14501
325
• Number of slices to send:
Optional 'thank-you' note:
I'm sure Winston agrees with you though ;)

Winston Gutkowski
Bartender
Posts: 10780
71
• Number of slices to send:
Optional 'thank-you' note:

Stevens Miller wrote:I wish Winston would comment, Piet and Stephan, because his oft-spoken words would apply here: what Kevin needs to do is stop coding...

But you've said it so eloquently, what do you need me for?

@Kevin: The only thing I can add is that at the early stages of a problem like this (which is not simple), you need to separate what you need to do from how you are going to do it (see WhatNotHow ←click). Right now you are focused on the code (the 'how') to the exclusion of everything else and, while you may get something that works out of it, it is likely to be very 'procedural'.

Stevens also made another important point: how to address [this] problem in a way that makes the process of finding a solution subject to an automatic method.

So you actually have two problems:
1. Writing a program that represents the "game" - ie, the board, squares (or positions), valid moves and (presumably) the Knight itself.

2. Working out a solution to the challenge. Now since there are something like 2⁵¹ possible combinations for an 8 x 8 board, one would hope that your solution is better than "brute force", which is likely to take years, even on a Cray.

So, with that in mind, you might want to check out Warnsdorff's Rule (if you haven't already), because that will help you to a solution that works in roughly linear time.

HIH

Winston

Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

Campbell Ritchie wrote:

Stevens Miller wrote:. . . "Knight's Tour" problem, . . . start at any square, move once to every other square, and finish back where you started. ...

As an aside...
A closed tour is impossible on a 5x5 board or indeed on any (odd)x(odd) board. Right?

(The diagram provided in the original post gives a hint why it's easy to make this assertion.)

Stevens Miller
Bartender
Posts: 1464
32
• Number of slices to send:
Optional 'thank-you' note:

Winston Gutkowski wrote:

Stevens Miller wrote:I wish Winston would comment, Piet and Stephan, because his oft-spoken words would apply here: what Kevin needs to do is stop coding...

But you've said it so eloquently, what do you need me for?

All things are easy for the student of the perfect master.

Ryan McGuire
Bartender
Posts: 1205
22
• Number of slices to send:
Optional 'thank-you' note:

Ryan McGuire wrote:

Campbell Ritchie wrote:

Stevens Miller wrote:...

...

...

Darn... I got my quote tags in my previous message messed up. It was me posing the "As an aside" assertion.

(This time using Preview before Submit.)

Campbell Ritchie
Marshal
Posts: 76870
366
• 1
• Number of slices to send:
Optional 'thank-you' note:
A closed tour requires the finish square be the same colour as the start square; that is only possible when there are an even number of squares.

 My, my, aren't you a big fella. Here, have a tiny ad: the value of filler advertising in 2021 https://coderanch.com/t/730886/filler-advertising