{ "cells": [ { "cell_type": "markdown", "id": "7106077d-9600-4f09-8c79-7d423fec0365", "metadata": {}, "source": [ "###
San Jose State University
Department of Applied Data Science

**DATA 200
Computational Programming for Data Analytics**

Spring 2024
Instructor: Ron Mak
" ] }, { "cell_type": "markdown", "id": "eb411d20-bbca-4589-b5ea-c3728dd69901", "metadata": {}, "source": [ "# The Towers of Hanoi Puzzle\n", "#### This is a puzzle that is solved very simply and elegantly with a short recursive function, and is much much difficult to solve nonrecursively.\n", "#### The puzzle has three pegs. At the start, one peg has disks stacked on it in increasing size order (smallest on top). The goal is to move all the disks to a designated destination peg. A third peg serves as a temporary holding place for disks. The rules:\n", "- #### You can move only one disk at a time from one peg to another.\n", "- #### You cannot place a larger disk on top of a smaller disk.\n", "#### **Base case:** Only one disk: simply move it from its peg to the desgination peg.\n", "#### **Smaller but similar problem:** If the puzzle has *n* disks, the smaller but similar problem is the move *n*-1 disks from their peg to the destination peg. As the problems become smaller and smaller, they approach the base case." ] }, { "cell_type": "code", "execution_count": 6, "id": "b1ac55c1-7cd1-48cd-9661-9edba066e99a", "metadata": {}, "outputs": [], "source": [ "def solve(n, from_peg, temp_peg, to_peg):\n", " \"\"\"\n", " Recursively solve the Towers of Hanoi puzzle with n disks \n", " stacked on from_peg to to_peg, Use temp_peg as the temporary\n", " holding place.\n", " \"\"\"\n", " if n == 1: # base case:\n", " print(f'Move disk from {from_peg} to {to_peg}')\n", " else: # smaller but similar problem:\n", " solve(n - 1, from_peg, to_peg, temp_peg)\n", " solve(1, from_peg, temp_peg, to_peg)\n", " solve(n - 1, temp_peg, from_peg, to_peg)" ] }, { "cell_type": "code", "execution_count": 7, "id": "e4133fb4-3842-44e1-81a8-38be9393d0ac", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n" ] } ], "source": [ "solve(2, 'A', 'B', 'C')" ] }, { "cell_type": "code", "execution_count": 8, "id": "9a819acd-4a63-4d06-b3f7-1f4f61dd58c3", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Move disk from A to C\n", "Move disk from A to B\n", "Move disk from C to B\n", "Move disk from A to C\n", "Move disk from B to A\n", "Move disk from B to C\n", "Move disk from A to C\n" ] } ], "source": [ "solve(3, 'A', 'B', 'C')" ] }, { "cell_type": "code", "execution_count": 9, "id": "ec528fb0-c8d1-4c8e-baa3-e1e164e047bd", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n" ] } ], "source": [ "solve(4, 'A', 'B', 'C')" ] }, { "cell_type": "code", "execution_count": 10, "id": "d851329a-5eeb-4d9a-a4f6-4173c450ba21", "metadata": {}, "outputs": [ { "name": "stdout", "output_type": "stream", "text": [ "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from C to A\n", "Move disk from C to B\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n", "Move disk from B to A\n", "Move disk from C to A\n", "Move disk from B to C\n", "Move disk from A to B\n", "Move disk from A to C\n", "Move disk from B to C\n" ] } ], "source": [ "solve(6, 'A', 'B', 'C')" ] }, { "cell_type": "markdown", "id": "b2adf770-ac51-49f8-acf8-68abc58c0061", "metadata": {}, "source": [ "#### (c) 2023 by Ronald Mak" ] }, { "cell_type": "code", "execution_count": null, "id": "394d470d-770f-4902-b93b-1e3dcbfad6ad", "metadata": {}, "outputs": [], "source": [] } ], "metadata": { "kernelspec": { "display_name": "Python 3 (ipykernel)", "language": "python", "name": "python3" }, "language_info": { "codemirror_mode": { "name": "ipython", "version": 3 }, "file_extension": ".py", "mimetype": "text/x-python", "name": "python", "nbconvert_exporter": "python", "pygments_lexer": "ipython3", "version": "3.11.5" } }, "nbformat": 4, "nbformat_minor": 5 }