### Abstract

The knight's tour problem is an ancient puzzle whose goal is to find out how to construct a series of legal moves made by a knight so that it visits every square of a chessboard exactly once. In previous works, researchers have partially solved this problem by offering algorithms for subsets of chessboards. For example, among prior studies, Parberry proposed a divided-and-conquer algorithm that can build a closed knight's tour on an n×n, an n×(n+1) or an n×(n+2) chessboard in O(n2) (i.e., linear in area) time on a sequential processor. In this paper we completely solve this problem by presenting new methods that can construct a closed knight's tour or an open knight's tour on an arbitrary n×m chessboard if such a solution exists. Our algorithms also run in linear time (O(nm)) on a sequential processor.

Original language | English |
---|---|

Pages (from-to) | 219-232 |

Number of pages | 14 |

Journal | Discrete Applied Mathematics |

Volume | 146 |

Issue number | 3 |

DOIs | |

Publication status | Published - 2005 Mar 15 |

### Fingerprint

### Keywords

- Divide-and-conquer algorithm
- Knight's tour problem
- Optimal algorithm

### ASJC Scopus subject areas

- Discrete Mathematics and Combinatorics
- Applied Mathematics

### Cite this

*Discrete Applied Mathematics*,

*146*(3), 219-232. https://doi.org/10.1016/j.dam.2004.11.002