Last edited by Zukora
Wednesday, May 13, 2020 | History

2 edition of Perfect codes, NP-completeness, and towers of Hanoi graphs found in the catalog.

Perfect codes, NP-completeness, and towers of Hanoi graphs

Paul Cull

# Perfect codes, NP-completeness, and towers of Hanoi graphs

## by Paul Cull

Published by Oregon State University, Dept. of Computer Science in Corvallis, OR .
Written in English

Subjects:
• Error-correcting codes (Information theory),
• Graph theory.

The set of codewords for a standard error-correcting code can be viewed as subset of the vertices of a hypercube. Two vertices are adjacent in a hypercube exactly when their Hamming distance is 1. A code is a perfect-error-correcting code if no two codewords are adjacent and every non-codeword is adjacent to exactly one codeword. Since such a code can be described using only vertices and adjacency, the definition applies to general graphs rather than only to hypercubes. How does one decide if a graph can support a perfect 1-error-correcting code? The obvious way to show that such a code exists is to display the code. On the other hand, it seems difficult to show that a graph does not support such a code. We show that this intuition is correct by showing that to determine if a graph has a perfect 1-error-correcting code is an NP-complete problem. The proof is by reduction from 3-SAT. To show that perfect codes in graphs is not vacuous, we give an infinite family of graphs so that each graph in the family has a perfect 1-error-correcting code. Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a configuration of the puzzle and two vertices are adjacent when they are one legal move apart. We give a recursive construction which determines which vertices are codewords. There is a natural correspondence between the hypercube vertices and the binary strings, and there is a natural correspondence between Tower of Hanoi configuration and ternary strings. Our recursive construction also species which ternary strings are codewords. We characterize the codewords as the set of ternary strings with an even number of 1"s and an even number of 2"s. As part of this characterization, we show that there is essentially one perfect 1-error-correcting code for each n. There is a unique code when n is even, but the code is only unique up to a permutation of 0, 1, and 2 when n is odd. We show that error-correction can be accomplished by a finite state machine which passes over the ternary string twice, and that this machine is fixed independent of the length of the string. Encoding and decoding are the mappings between integers and codewords, and vice-versa. While algorithms for such mappings can be derived directly from the recursive construction, we show that encoding/decoding can be carried out by multiplication/division by 4 and error-correction. So error-correction, encoding, and decoding can all be done in time theta (n) for code strings of length n in these codes.

Edition Notes

The Physical Object ID Numbers Statement Paul Cull, Ingrid Nelson. Series Technical report -- 98-20-01., Technical report (Oregon State University. Dept. of Computer Science) -- 98-20-01. Contributions Nelson, Ingrid., Oregon State University. Dept. of Computer Science. Pagination [26] leaves : Number of Pages 26 Open Library OL15499956M

Presumably the game graph for the m-peg puzzle is most naturally drawn in m-1 dimensions, with the 1-disk graph consisting of a polytope with m vertices and m(m-1)/2 edges and the n-disk graph consisting of m (n-1)-disk polytopes connected by (m-2) n-1 edges. Drawing such graphs is . tower, refer to it as the "Colored Magnetic Tower of Hanoi" and study its properties. The Colored Magnetic Tower of Hanoi – the "" solution. Studying the N=3 MToH puzzle, I realized that what breaks the base 3 rule is the possibility of the smallest disk to move to a free post (step 5 in Table 2).Cited by: 1.

I originally encountered this problem in the book "Programming Challenges" from Skiena and Revilla where it is part of Chapter 9: "Graph Traversal" given a short hint: Can the constraints be usefully modeled using a DAG? Question 1. How to use this hint? Last but not least, I observed the solution seems to be always. Tower of Hanoi problem a problem involving moving discs from one set of pegs to another. It has been used to illustrate the process involved in means-end analysis, with its setting of subgoals, and this approach can be applied to real-life situations.

The Towers of Hanoi Puzzle (Illustrated) - Kindle edition by Lucas, Edouard. Download it once and read it on your Kindle device, PC, phones or tablets. Use features like bookmarks, note taking and highlighting while reading The Towers of Hanoi Puzzle (Illustrated).3/5(10). I am building a towers of hanoi game that can be played from the console or the command line. Note this isn't a recursive program; I am trying to build a GAME that can be played by the user. I am using an ArrayList of ArrayLists to store the pegs(1,2,3) and the discs(N) chosen by the user.

You might also like
gentlemans new pocket farrier : comprising a general description of ... the horse : with modes of management in all cases, and treatment in disease ...to which is added a prize essay on mules ...

gentlemans new pocket farrier : comprising a general description of ... the horse : with modes of management in all cases, and treatment in disease ...to which is added a prize essay on mules ...

The evolutionary strategies that shape ecosystems

The evolutionary strategies that shape ecosystems

Twenty-five years of S.T.A. history glorify the simple tools of an honourable craft.

Twenty-five years of S.T.A. history glorify the simple tools of an honourable craft.

Metabolic pathways

Metabolic pathways

Toronto planning maps]

Toronto planning maps]

Marxs social ontology

Marxs social ontology

Politics and the other scene

Politics and the other scene

Tomato Culture for Amateurs

Tomato Culture for Amateurs

short guide to St. Clements, Rome

short guide to St. Clements, Rome

R.E.D. Joint Service - Silver subscription.

R.E.D. Joint Service - Silver subscription.

Pecks bad boy and his pa

Pecks bad boy and his pa

An Air quality survey of the east coast of Ireland, north of Dublin, carried out by schoolchildren

An Air quality survey of the east coast of Ireland, north of Dublin, carried out by schoolchildren

AT ENTERTAINMENT, INC.

AT ENTERTAINMENT, INC.

The goblin

The goblin

### Perfect codes, NP-completeness, and towers of Hanoi graphs by Paul Cull Download PDF EPUB FB2

Perfect codes, NP-completeness, and towers of Hanoi graphs and towers of Hanoi graphs book report) [Paul Cull] on *FREE* shipping on qualifying : Paul Cull. The proof is by reduction from 3-SAT. To show that perfect codes in graphs is not vacuous, we give an in nite family of graphs so that each graph in the family has a perfect 1-error-correcting code.

Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a confi guration of the puzzle and two vertices are adjacent Cited by: 6.

Sierpiński graphs S (n, κ) generalise the Tower of Hanoi graphs—the graph S (n, 3) is isomorphic to the graph Hn of the Tower of Hanoi with n disks. A 1-perfect code (or an efficient dominating set) in a graph G is a vertex subset of G with the property that the closed neighbourhoods of its elements form a partition of V (G).Cited by: Perfect codes on the Towers of Hanoi graph Article (PDF Available) in Bulletin of the Australian Mathematical Society 57(03) June with Reads How we measure 'reads'.

To show that perfect codes in graphs is not vacuous, we give an in nite family of graphs so that each graph in the family has a perfect 1-error-correcting code.

Our graphs are based on the Towers of Hanoi puzzle, so that, each vertex is a confi guration of the puzzle and two vertices are adjacent when they are one legal move apart.

Cull, P., Nelson, I.: Perfect Codes, NP-Completeness, and Towers of Hanoi Graphs. Bull. Inst. Combin. Appl. 26, 13–38 () MathSciNet zbMATH Google ScholarAuthor: Paul Cull, Leanne Merrill, Tony Van, Celeste Burkhardt, Tommy Pitts.

Sierpiński graphs S(n, k) generalise the Tower of Hanoi graphs-the graph S(n, 3) is isomorphic to the graph Hn of the And towers of Hanoi graphs book of Hanoi with n disks. A 1-perfect code (or an efficient dominating set. An Efficient Implementation of Tower of Hanoi using Gray Codes (GRDJE / CONFERENCE / NCCISâ€&#x;17 / ) bit is the largest.

Counting moves from 1 and identifying the disks by numbers. Tower of Hanoi graphs model the classical Tower of Hanoi puzzle with 3 pegs and n discs.

Their nice fractal structure enables to observe many nice properties. In particular, Cull and Nelson [5] proved that they contain (essentially) unique perfect codes, see also [17]. The Tower of Hanoi graphs extend naturally to graphs S(n,k). Graphs S(n,k) were introduced in as a two-parametric generalization of the Hanoi graphs and named Sierpiński graphs introduction was motivated by topological studies of certain generalizations of the Sierpiński gasket.For our purposes we recall that for any n∈ N, the graph S n ≔S(n,3) is isomorphic to the Hanoi graph on n discs (cf.

[17, Theorem 2]) and is defined as by: Theorem 1. Every Hanoi graph is hamiltonian, Proof. o) For n = 0, this is trivial. On the Planarity of Hanoi Graphs i) By induction on n N we show that there is a hamiltonian path starting and ending in distinct perfect states.

This is trivial for n = by:   Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. 1) Only one disk can be moved at a time. 2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack/5.

Dismiss Join GitHub today. GitHub is home to over 50 million developers working together to host and review code, manage projects, and build software together.

C.-K. Li and I. Nelson, Perfect codes on the towers of Hanoi graph, Bulletin of the Australian Mathematical Society 57 (3) (), –DOI: /s D. Arett and S. Doree, Colouring and counting on the tower of Hanoi graphs, Mathematical Association of America 83(3) (), –DOI: /xAuthor: R.

Daisy Singh, R. Murali. We show that our graphs have Hamiltonian paths and perfect one-error-correcting codes. (Properties that are $\mathcal{NP}$ -complete for general graphs.) We also discuss computational complexity and show that many properties of our graphs and puzzles can be calculated by finite state machines.

The Tower of Hanoi (TH) is a classic puzzle that was invented by Éduard Lucas () using the alias N. Claus (de Siam), an anagram of Lucas d' three pegs, two of them empty, and a pile of disks of decreasing size is stacked on the third one.

The problem is to move the stack to another peg, moving one disk at a time from one peg to another, but never putting a larger disk on. Wooden Colorful Hanoi Tower Educational Toys Children's Puzzle Brain Teaser Intellectual Toy, Safe and Non-toxic, Stacking & Plugging Toys for Developing Kids'.

A bachelor's thesis project at Faculty of Electrical Engineering and Computing, University of Zagreb. In this project, machine learning algorithm "qlearning" is used to solve the Towers of Hanoi problem. After off-line learning, Baxter robot is used to physically play all the moves required to optimally solve the problem.

Tower of Hanoi is a mathematical puzzle. It consists of three poles and a number of disks of different sizes which can slide onto any poles.

The puzzle starts with the disk in a neat stack in ascending order of size in one pole, the smallest at the top thus making a conical shape/5. For any n ≥ 1 and any k ≥ 1, a graph S(n, k) is introduced.

Vertices of S(n, k) are n-tuples over {1, 2, k} and two n-tuples are adjacent if they are in a certain relation. These graphs are graphs of a particular variant of the Tower of Hanoi problem.

Namely, the graphs S(n, 3) are isomorphic to the graphs of the Tower of Hanoi by:. Assuming you have n bricks and 3 towers denoted by 0,1,2. Denote the current state by a n trinary numbers, for example (in the case n=9): (current state) meaning that brick 9,8,5,3 and 1 are in the 0:th tower.

Brick 7 and 6 in the 1:th tower and brick 4 and 2 in the 2:nd tower.in the Tower of Hanoi game. One can construct a graph modeling the Tower of Hanoi problem with kpegs and ndisks, commonly called the Hanoi graph and denoted Hk n.

The Hanoi graph consists of vertices, or legal states, connected by This work was undertaken at the Columbia University REU program supported by NSF grant DMS 1.In their paper Perfect Codes, NP Completeness, and Towers of Hanoi Graphs, Cull and Nelson present an inﬁnite family of labelled graphs inspired by the Towers of Hanoi puzzle.