An optimal algorithm for Reve's puzzle

DOI10.1016/0020-0255(88)90007-2MaRDI QIDQ1113675zbMATH OpenOpenAlexFDO

Authors M. C. Er

Publication date 1988

Published in Information Sciences (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/0020-0255(88)90007-2

zbMATH Keywords

Reve's puzzle

Mathematics Subject Classification ID

Enumerative combinatorics (05A99) Analysis of algorithms and problem complexity (68Q25) Discrete mathematics in relation to computer science (68R99)

Review text

This paper starts by showing that some recently published algorithms for Reve's puzzle are not optimal. Reve's puzzle is a generalization of the standard Towers of Hanoi whereby the number of pegs is extended from 3 to \(k\geq 2\). A simple and elegant recursive algorithm for solving Reve's puzzle is presented. Its optimality is assured by an algorithm for optimally splitting a tower of n discs into two subtowers. The theoretical basis for doing so is also discussed.

Recommendations

• scientific article; zbMATH DE number 1087226
• scientific article; zbMATH DE number 1380741
• Publication:3201756
• Solution for the tower of Hanoi problem with four pegs
• The complexity of an optimal algorithm for the generalized tower of hanoi problem

Cites work

• A problem-decomposition method using differences or equivalence relations between states
• A Representation Approach to the Tower of Hanoi Problem
• scientific article; zbMATH DE number 3763944 (Why is no real title available?)
• scientific article; zbMATH DE number 3518812 (Why is no real title available?)
• scientific article; zbMATH DE number 3435053 (Why is no real title available?)
• The Generalized Colour Towers of Hanoi: An Iterative Algorithm
• The multiway trees of hanoi^†

Cited in

(11)

• Shortest paths between regular states of the Tower of Hanoi
• A skeleton model to enumerate standard puzzle sequences
• scientific article; zbMATH DE number 4178767 (Why is no real title available?)
• scientific article; zbMATH DE number 7219428 (Why is no real title available?)
• Solving the Rubik's Cube Optimally is NP-complete
• Mathematical derivation of the multi-peg Tower of Hanoi algorithm
• Solution for the tower of Hanoi problem with four pegs
• scientific article; zbMATH DE number 1380741 (Why is no real title available?)
• The Reve's puzzle with an evildoer disc
• scientific article; zbMATH DE number 7527484 (Why is no real title available?)
• On a recurrence relation related to the Reve's puzzle

This page was built for publication: An optimal algorithm for Reve's puzzle

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1113675)