How Combinatorics Can Improve Logic Problem Solving in AI Models Like GPT-4

Hello everyone,

I wanted to share an observation that might bridge the gap between classical mathematics and AI reasoning. During my experiments with models like GPT-4 and Claude 3.5, I stumbled upon something intriguing: combinatorics—the branch of mathematics dealing with combinations, permutations, and state spaces—can significantly enhance a language model’s ability to solve logic problems.

Let me explain how I arrived at this.

The Problem

I’ve been testing large language models with classic puzzles, such as the Wolf, Goat, and Cabbage problem:

A farmer must transport a wolf, goat, and cabbage across a river using a small boat. The boat can carry only one item at a time. If left alone, the wolf eats the goat, or the goat eats the cabbage. How does the farmer transport all items safely?

While seemingly simple, this problem poses significant challenges for many language models:

They often fail to track the state of the items (e.g., which bank each is on).
They struggle to reason through backtracking moves (e.g., taking the goat back to the starting bank).

The Breakthrough

To address this, I modified the way I described the problem. Instead of leaving it in plain English, I explicitly framed it as a combinatorial state space problem:

Defined each state as a tuple (Farmer, Wolf, Goat, Cabbage), where each value is either Left or Right.
Highlighted valid state transitions, considering the constraints (e.g., wolf and goat cannot be left alone).
Clarified that the farmer could return to a prior state if needed.

When I presented the problem this way, other models (Claude Sonnet, O1-mini) solved it correctly. Structuring the problem with combinatorics made the steps explicit, eliminating ambiguity.

FULL-PROMPT-BEGIN

Problem Description:

A farmer is on the left riverbank with a wolf, a goat, and a cabbage. The farmer must transport all three items to the right riverbank using a small boat. However:

The boat can only hold the farmer and one item at a time.
If the wolf and the goat are left alone on the same bank, the wolf will eat the goat.
If the goat and the cabbage are left alone on the same bank, the goat will eat the cabbage.

Key Considerations:

The farmer can return to the starting bank with or without an item after crossing.
To solve the puzzle, the farmer needs to make multiple trips across the river, carefully planning the order in which items are transported.
The problem requires explicitly tracking:
- The location of each item (wolf, goat, cabbage, farmer) at all times.
- The rule that no dangerous pair can be left together on the same bank without the farmer.

Step-by-Step Solution (Generalized for Simplicity):

The farmer begins on the left bank with all three items.
On each trip:
- The farmer may take one item to the opposite bank.
- The farmer may return to the original bank with or without an item.
The farmer’s goal is to:
- Transfer all three items safely to the right bank.
- Avoid leaving the wolf and goat or the goat and cabbage alone on any bank.

Hints for Simplification:

To emphasize the farmer’s ability to return:

Use language like: "The farmer is not restricted to moving forward only; they can always go back to adjust the arrangement."
Break the task into discrete states:
- State 1: Farmer and all items on the left bank.
- State 2: Farmer and one item on the right bank, while ensuring no rule is broken.
Encourage checking all possible moves:
- "If moving an item creates a problem, the farmer can reverse the move and try a different strategy."

Simplified Rules Summary:

The farmer can only transport one item at a time.
The farmer must always be present to supervise the wolf and goat or the goat and cabbage.
The farmer can make as many trips as necessary, including returning to the starting bank.

Testing Simplification:

Ask the model to solve one step at a time, keeping track of the following:

Where each item (wolf, goat, cabbage) is after each trip.
Whether the rules are followed after each move.
If the farmer is returning, ensure it is acknowledged as a valid action.

Please tell me what you think the answer is to this puzzle.

FULL PROMPT END

Why Combinatorics Works

Logic puzzles like this involve navigating state spaces, which is essentially a combinatorial problem:

There are ( 2^4 = 16 ) possible states (Farmer + 3 items, each on one of two banks).
Only a subset of these states is valid, due to constraints.
The problem boils down to finding a path through this state space.

By explicitly defining states and transitions, models can reason systematically rather than relying on inferred logic from plain English descriptions. This approach seems to align more naturally with how AI processes structured data.

Implications

While combinatorics is a well-known mathematical tool, I suspect its explicit integration into language model problem-solving has been underexplored. Here are a few takeaways:

Structured Prompts Matter: Framing problems mathematically enables even less advanced models to perform complex reasoning.
AI + Classical Math: Bridging natural language understanding with combinatorics (or similar tools) could significantly enhance AI’s logical capabilities.
Potential Applications:
- Teaching AI to reason through multi-step problems systematically.
- Solving combinatorial optimization problems in logistics, planning, or game AI.

Closing Thoughts

This discovery felt accidental—I wasn’t even familiar with the term "combinatorics" until GPT-4 mentioned it. But it has opened my eyes to how structured thinking can unlock AI’s potential. I hope sharing this here sparks new ideas and discussions.

Looking forward to your insights!

In order to do this, I have been collaborating with a custom GPT I made called Hexel, which has a custom prompt and RAG knowledge source that includes various pieces of information relating to the FORTH programming language and mathematics, among other things. I want to provide this information to someone who is both formally trained, and generally better at this than I am, so that they can carry it forward.