STT e47: Ruby is Great

Stevey's Tech Talk

Hey folks!
This week I talk about Ruby, which is one of my Top 3 favorite programming languages (if you count "Lisp" as a single language), the third being Kotlin.
If you want to get straight to the hand-waving ranting, you can jump to around the 40 minute mark.
This week we're having a competition! We're going to re-do the Farmer, Dog, Chicken, Grain competition I held at Amazon.com around 18 years ago.
Sometime this week, if you have time, try writing a succinct and elegant solution to this problem, in the programming language of your choice, and post it here in the YT comment section.
The problem: A farmer (F) needs to get his dog (D), chicken (C) and bag of grain (G) across a river. He has a boat that allows him to carry exactly zero or one item across with him. Write a program that spits out a solution when you run the program with no input/arguments.
Example solution that your program might output:
carry chicken
carry nothing
carry grain
carry chicken
carry dog
carry nothing
carry chicken
You can model it however you like. Below I present an abstract model of the states of the system as it carries out the steps above, where | represents the river. Things on the left bank and right banks are placed before/after the '|', respectively:
FDCG| - start state, everyone on left; carry chicken to right bank
DG|FC - FC now on right; carry nothing back
FDG|C - FDG on left; carry grain
D|FCG - FCG on right; carry chicken back
FCD|G - FDC on left; carry dog
C|FDG - chicken on left; carry nothing back
FC|DG - FC on left; carry chicken across
|FDCG - end state
Keep in mind that your program must perform a SEARCH through the possible move space for a solution, and you cannot have any third-party library dependencies; only what the language provides built in with its distribution.
I am looking for solutions that are ELEGANT, by which I mean, short and to the point: ideally, without boilerplate or other stuff unrelated to the algorithm. This is a self-contained program and will not grow, so keep it small! Do not over-engineer it!
I will submit solutions in at least Ruby and Elisp, though you are welcome to do the same. But I'd like to see a variety of languages here! Multiple submissions are fine as well. This is a fun little problem to solve.
Most languages let you solve this problem in 20-30 lines of code or less.
I'll take solutions through next Saturday and then do the judging in Sunday's episode. Though of course you are all welcome to keep submitting solutions after I do the judging, and I can comment on them below.
Have fun!
Podcast listeners, you should participate as well! Just head over to my YT channel to comment with your solution.
NOTE: I may update this comment with a shared link if we can find a reasonable place to do this. Maybe someone can create a subreddit or Discourse or something?