Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [knight-tours]

Use this tag to describe mathematics questions dealing with the knight's tour problem. A knight's tour is a series of legal knight moves in chess that visits all of the squares on the board exactly once.

2
votes
0answers
20 views

Number of open and closed rook's tours

Knight's tour is very well known problem, but what about rook's tour? On $n\times1$ chessboard there are obviously $n!$ open and $(n-1)!$ closed tours. Is there a way to easily compute number of open ...
2
votes
1answer
131 views

Hamiltonian Knight's (closed) walk for odd $\times$ odd chess board

I am taking a course on graph theory right now and we were posed the following question: Show that if $n$ is odd, a knight on an $n \times n$ chessboard can not make a closed tour of the chessboard ...
0
votes
0answers
26 views

Is there a simple way to discover all the paths in Knight's Tours? Or even just one path?

Is there a simple way to discover all the paths in Knight's Tours? Or even just one path? Since all tiles must be visited, then give a large enough board, this seems like a pretty exhausting thing to ...
1
vote
1answer
26 views

What's this kind of visualization of the Knight's Tour called? Connected rectangular graphs?

What's this kind of visualization of the Knight's Tour called? Connected rectangular graphs? This is on a 6x6 chessboard. Also, why are the rectangular regions separated like that? And why does one ...
0
votes
0answers
29 views

Number of knight cycle-free $n$-tours on an $n \times n$ modular chessboard?

Given an $n \times n$ modular (ie: the line resp. column after the last one is identified with the first) chessboard, I'd like to count the number of cycle-free $n$-paths a knight can do, starting ...
4
votes
1answer
181 views

Infinite Knight's Tour

Does there exists a one-to-one and onto map $f:\mathbb{N}\rightarrow \mathbb{Z}[i]$ such that $|f(n+1)-f(n)|=\sqrt{5}$? That is to get from $f(n)$ to $f(n+1)$ you have to move like a knight in chess: ...
0
votes
0answers
124 views

Properties of a general knight in the knight's tour problem.

I am currently investigating how the knight's tour problem differs when a general knight (m, n) is used instead of a traditional knight (2, 1), where m represents moving a number of squares along one ...
2
votes
0answers
28 views

Looking for a challenging task or variant related to the knight's tour problem

I recently took it upon my self to investigate the knight's tour problem for a math assessment. I decided to investigate how the problem differs with a general knight (m, n) that moves m squares along ...
1
vote
0answers
75 views

Minimum board size for knights tour to be possible

What is the minimum board size for a knight's tour: open or closed, to be possible. Edit: I want to write a program that can solve knight's tour for any board size. I want to implement a lower limit ...
0
votes
0answers
33 views

Knights Tour - What is the relationship between board size and number of tours? [duplicate]

I understand that the total number of Knights tours is known for boards up to 8 x 8. These are: 1, 0, 0, 0, 1728, 6637920, 165575218320, 19591828170979904 As found here: "http://oeis.org/A165134" ...
0
votes
0answers
273 views

Knight's tour problem existance proof

I'm preparing for a test next week about graph theory. One of the example exercises is about proving that a closed knight's tour exists on an 8-by-8 chess board by only using basic theorems such as ...
1
vote
3answers
519 views

How many different knight's moves are there on an $n \times n$ chessboard?

I have found there to be $48$ total moves on a $4 \times 4$ board... and $96$ on a $5 \times5$... but I can not see the relevance to each other in terms of a "$n \times n$" board. By "moves" I am ...
0
votes
2answers
125 views

Knights tour on a 4 x m board

Prove that on a chessboard that has dimension $4 \times m$ there doesn't exist a knights tour in which we return to square we started at. I know that we need to turn each square into a vertice and ...
17
votes
2answers
721 views

A variant of the Knight's tour problem

The knight's tour problem is a famous problem in chess and computer science which asks the following question: can we move the knight on an $n \ \times \ n$ chessboard such that it visits every ...
0
votes
0answers
420 views

Knight's open tour on 5X5 board

I'm trying to write a program that finds an open knight's tour on 5X5 board starting from every point. I So the question is does every point actually has a solution. I found this answer that says that ...
0
votes
0answers
4k views

Knight's tour on 4x4 and 8x8 chess board

Prove that:- $\bullet$A (open or closed) knight's tour is not possible on a $4\times4$ chess board. $\bullet$A (open or closed) knight's tour exists on a $8\times8$ chess board. I want a ...
2
votes
2answers
1k views

A closed Knight's Tour does not exist on some chessboards

It is generally difficult to determine whether a (large) graph have no Hamilton cycle (As opposed to determining whether it has any Euler circuit). This example illustrates a method (which sometimes ...
1
vote
0answers
129 views

Knights tour dfs search with look ahead

After Using a basic depth first search I was wondering if there was any way to predict a dead end before one becomes apparent? As I know I can stop there becoming multiple dead ends as in a single ...
0
votes
1answer
549 views

Knight tour on 5x5 incongruence

I cannot seem to understand something, it has been puzzling me for days. There exists 304 tours from a corner in a 5x5 board based on an exhaustive search algorithm. 304 is a multiple of 19!! How is ...
1
vote
1answer
418 views

Chess King Tour 8x8 problem

Two squares on a chessboard are said to be neighbours if they have an edge or a corner on the board in common. This means that squares on the edge have 5 neighbours, on the corner have 3 neigbours, ...
2
votes
1answer
226 views

What does it mean to “unfold” a graph?

edit: more complicated graph source (problem on pg.21): http://press.princeton.edu/chapters/s7714.pdf I couldn't find any resources online explaining the unfolding process of a graph in layman's ...
1
vote
2answers
152 views

Knight's Tour with Obstacles

Found a game related to knight's tour Knight's Score The basic idea is to gather as much points as possible, avoiding some cells. What is the math of this? Can algorithm be constructed to visit all ...
6
votes
4answers
2k views

Chess knight move in 8x8 chessboard

I've recently shown some interests in chess, and I wonder if there is a solution for the following problem: In a 8x8 chessboard, labeling the cells with numbers from 1 to 8, is there any way to find ...
2
votes
0answers
266 views

How many open knight's tours are possible in a 3×16 chessboard? [closed]

According to the following page (http://magictour.free.fr/enum), 17269264 open knight's tours are possible in a 3×16 chessboard. I compute the number by using the following code(C) and the number is ...
0
votes
0answers
44 views

How many closed knight's tour are possible in a $8\times 8$ chessboard? [duplicate]

How many closed knight's tour are possible in a $8\times 8$ chessboard? I hae no such idea. Please give me the proof of it.
7
votes
1answer
162 views

Is there a name for graphs with the following property?

The property of the graph is the following: For any vertex, there is a hamiltonian path starting with this vertex, but the graph is not hamiltonian. The following graph is a small example: Important ...
6
votes
1answer
1k views

Proof that there is no closed knight tour on a $3\ \times\ 8$ - board

I want to prove that there is no closed knight tour on a $3\ \times\ 8$ - board by deleting $s$ vertices of the corresponding knight graph to get a graph with more than $s$ connected components (...
0
votes
2answers
223 views

Are there semimagic knight tours from any starting square?

There are $140$ distinct semimagic knight tours on a normal chessboard ($8\ \times\ 8$). A semimagic knight tour is a knight tour (not necessarily closed) such that a semimagic square appears if the ...
0
votes
1answer
124 views

Are there magic knight tours on a $6\times6$ or $10\times10$ board?

In mathworld, magic tour, it is mentioned that for odd $n$, only semimagic knight tours are possible on a $n\times\ n$ - board. For $n = 8$, it has been verified that there are no magic knight tours,...
20
votes
3answers
6k views

How many knight's tours are there?

The knight's tour is a sequence of 64 squares on a chess board, where each square is visted once, and each subsequent square can be reached from the previous by a knight's move. Tours can be cyclic, ...