Skip to content

Instantly share code, notes, and snippets.

@olivia-banks
Created April 10, 2020 18:27
Show Gist options
  • Select an option

  • Save olivia-banks/7ff6708b4a2ecb58515ca01cd8f63cdc to your computer and use it in GitHub Desktop.

Select an option

Save olivia-banks/7ff6708b4a2ecb58515ca01cd8f63cdc to your computer and use it in GitHub Desktop.
Generalized tower of hanoi in Prolog!
/* README!
* The below prolog code (commented) is the original prolog code before I remembered
* that I had to make it work with six pillars, so I just spent a small bit of time
* (~1.5 hours) making the uncommented code accept any number of pillars.
*
* move(1, X, _, Z, [[X, Z]]). % Base case
* move(N, X, Y, Z, P) :- % To move N disks from X to Z
* M is (N - 1), % we first must move the smaller N-1 disks
* move(M, X, Z, Y, P1), % from X to Y
* move(1, X, Y, Z, P2), % then move the largest disk from X to Z
* move(M, Y, X, Z, P3), % then move the smaller N-1 disks form Y to Z
* append(P1, P2, Q), % we get the corresponding solution
* append(Q, P3, P). % by appding all the steps.
*
*/
/* Here is the actual logic. */
move(1, A, _, Z, [[A, Z]]).
move(N, A, [H|T], Z, P) :-
M1 is (N - floor(sqrt(2*N + 1)) + 1),
M2 is (N - M1),
move(M1, A, [Z|T], H, P1),
move(M2, A, T , Z, P2),
move(M1, H, [A|T], Z, P3),
append(P1, P2, Q),
append(Q, P3, P).
@olivia-banks
Copy link
Author

I really hope old gists don't get taken down. This one means a lot to me now.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment