Farmer, Fox, Goose, Grain Puzzle

When I was a child, I picked up a book that was my fathers, called The Scientific American Book Of Projects For The Amateur Scientist. I still have the book, and my understanding is that it's a hard book to come by these days. But you can read it online now. This book served to introduce me to a lot of things but the chapter that piqued my interest was the one on Mathematical Machines. It may very well be the thing that set me off on my eventual career of software development.

In this chapter are descriptions of puzzle solving machines using circuits of the time... which predated modern integrated circuits or even transistors (using relays). But some of the same concepts were there, that of logic devices that are essentially the same thing that modern computers still use today.

These days, you can easily and cheaply get entire computer systems for a few dollars, and just program your puzzle or game. But you can also do a lot of things at a lower level, using the logic gates that computers are built from, to create customized hardware for your puzzle. While this may not be practical or ideal, it does let you learn how computers really work. It's also kind of fun.

You can build this entirely in Tinkercad Circuits, and simulate the actual functioning of the puzzle.

If you want to build it physically, here's what you will need:

4 toggle or slide switches.

1 push button (momentary)

2 small breadboards.

9 LED's.

9 1K resistors.

1 7475 quad latch chip

2 7408 quad AND gates

1 7432 quad OR gate

1 battery pack holding 3 AA or AAA cells.

set of jumper wires.

For the 74xx series chips, you can use any variation of these. IE, the 74xx versions are the original TTL, but you can also use the 74LSxx versions (lower power useage), or the 74HCxx (even lower power cmos versions) etc. Just remember that the 74xx and 74LSxx versions are easy to handle, but all the other variations are sensitive static electricity.

Boolean logic may sound scary but its actually pretty simple. Boolean just means you are dealing with only 1s and 0s, or True and False. Or in electronics, + and -. The logic part of it just boils down to a lot of "if this then that". The most basic logic operations are simply these three things: AND, OR and NOT. These are called gates, because they essentially act as literal gates to the flow of electricity through a circuit.

The AND gate works as follows. It has two inputs, and one output. The two inputs can be a 1 or 0, and the output is a 1 or 0. For the AND gate, if both the inputs are 1, then the output is 1. Otherwise, it outputs a 0.

For the OR gate, it also has two inputs and one output. If one or the other input is a 1, then the output is a 1.

The final gate is the NOT gate, and it only has one input and one output. If the input is a 1, then the output is 0. If the input is 0, it outputs a 1.

The OR and AND gates can also have more than 2 inputs. For simplification, they can be shown with 2 or more lines going into one gate, but really, a 3 input gate is just two 2 input gates with one feeding into the other.

You now know everything you need to know to build a computer. Even the most modern computers just use these three things, although they may use millions of them.

So let's build a puzzle.

The first thing in the book is a logic circuit to create the classic puzzle of the Farmer, the Fox, the Goose and the Grain. This puzzle has been around for hundreds of years in different forms. Its a basic puzzle of logic with just a few rules. The puzzle is as follows.

A farmer has a fox, a goose, and some grain. He comes to a river he must cross, and there is a boat, but it can only hold him and one other thing at a time.

He cannot leave the fox with the goose, because the fox will eat the goose. Thats what foxes do, it's just their nature.

He cannot leave the goose with the grain, because the goose will eat it.

How can he get all three of them across to the other side of the river safely?

To create this puzzle we need a few things. First, with start with four switches, one for each of the farmer, the fox, the goose and the grain. This is how we will set which goes onto the boat.

Secondly, we need the puzzle to remember where everything is from step to step.

Then we need a button to tell it when to move the boat.

Finally, we need some logic to enforce the rules.

To remember the locations of the objects in this puzzle, we'll use something more advanced than the relays used in the original circuit. Back when this book was written, there were no transistors, but they had relays. These relays were wired such that when you pushed a button, they would close and then stay closed until you pushed the button on the other side.

Today we'll use a common and inexpensive part called a 4 bit latch. A 'bit' in computer logic just refers to a single 1 or 0. It's the same thing as a digit. This Integrated Circuit (or "IC" or "Chip") contains 4 logic components known as flip flops. A flip flop is just a couple of gates configured so that when you give it a 1 or 0 as an input, it will output a 1 or 0 and then stay 'stuck'. Hence the name flip / flop. It will flip from a 1 to 0 or flop from a 0 to a 1 (or is it the other way around?) and then stay there. This basically does the same thing as the four relays in the old circuit.

You can make a simple flip flop with only two gates, but the ones in this latch have an extra feature (requiring a few more gates). Instead of immediately having the output change with the input changing, it has an another input that enables or disables the inputs. Normally, it stays disabled. This lets you set two of the switches (the farmer and one other) before it tries to 'send' the boat to the other side. Our circuit is already smarter than the old one.

We now have the ability to set and remember the locations of all the principles in our puzzle.

Here's our circuit so far: 4 bit latch

To enforce the rules and indicate when there's a problem, we'll use some boolean logic gates to implement the constraints we need.

We'll need four tests to determine if there's a problem - if any one of these are true, then light the warning signal.

1. If the grain and the goose are on the other side of the river and not the farmer.

2.If the fox and the goose are on the other side of the river and not the farmer.

3.If the farmer crosses the river and no fox and with no goose are with him.

4. If the farmer crosses the river and no grain and no goose are with him.

Note the way in which I have phrased this to exactly match the logic we will use, which are AND gates with either the normal or the inverted outputs from the latch, the inverted ones acting like a "no" or a "NOT".

Since any of them can be true, causing a problem, they all feed into an OR gate.

The completed logic, including the 4 bit latch, is shown in the screen shot. This is from a program called logicaly. This program is excellent for showing the flow of logic as you manipulate the switches, highlighting in blue the connections with a '1' value. I've attached the file you can load into logically.

Now we can create a real working circuit. Using Tinkercad circuits, we can do this with simulation of the real look and functionality of hardware.

Tinkercad has built in a 7475 4 bit latch, so that part is easy. For the gates, I've chosen to use two chips with 4 AND gates each (the 7408). To create four, 3 input AND gates we use two AND gates with the output of one going into 1 input of the other. This leaves 1 input on the second, and 2 inputs on the first, creating a 3 input AND gate. For the OR gate, I do the same thing. A four OR gate chip uses two OR gates with the outputs going into a third OR gate. One gate is left unused.

Run the simulation on Tinkercad circuits