How to Build a Puzzle Solver Using Logic Programming

The concept of programming paradigms arises owing to the need to classify programming languages. It refers to the way computer programs solve problems through code.

Logic programming is a programming paradigm, which basically is a particular way to approach programming.

Solving problems using logic programming

Logic programming looks for solutions by using facts and rules. You need to specify a goal for each program. In the case where a logic program and a goal don’t contain any variables, the solver comes up with a tree that constitutes the search space for solving the problem and getting to the goal.

One of the most important things about logic programming is how you treat the rules. Rules can be viewed as logical statements. Here are a few examples:

  1. Kathy likes chocolate => Alexander loves Kathy

This can be read as an implication that says, If Kathy likes chocolate, then Alexander loves Kathy. It can also be construed as Kathy likes chocolate implies Alexander loves Kathy.

  1. Crime movies, English => Martin Scorsese

This can be read as an implication If you like crime movies in English, then you would like movies made by Martin Scorsese.

This construction is used in various forms throughout logic programming to solve various types of problems. Now, it’s time to solve these problems in Python.


Installing Python packages

Before you start logic programming in Python, you need to install a couple of packages. The logpy package is a Python package that enables logic programming in Python. So, you can go ahead and install logpy using pip:

$ pip3 install logpy

If you get an error during the installation process for logpy, you can install it from the source https://github.com/logpy/logpy . Once you have successfully installed these packages, you can start your puzzle solver project.


Building a puzzle solver

An interesting application of logic programming is in solving puzzles. You can specify the conditions of a puzzle and the program will come up with a solution. In this section, you will see how to specify various bits and pieces of information about four people and ask for the missing piece of information.

In the logic program, you can specify the puzzle as follows:

  • Steve has a blue car
  • The person who owns the cat lives in Canada
  • Matthew lives in the USA
  • The person with the black car lives in Australia
  • Jack has a cat
  • Alfred lives in Australia
  • The person who has a dog lives in France
  • Who has a rabbit?

The goal is to find the person who has a rabbit. Here are the full details about the four people:

pz1

Create a new Python file and import the following packages:

from logpy import *
from logpy.core import lall

Declare the variable people:

# Declare the variable
people = var()

Define all the rules using lall. The first rule is that there are four people:

# Define the rules
rules = lall(
    # There are 4 people
    (eq, (var(), var(), var(), var()), people),

The person named Steve has a blue car:

    # Steve's car is blue
    (membero, ('Steve', var(), 'blue', var()), people),

The person who has a cat lives in Canada:

    # Person who has a cat lives in Canada
    (membero, (var(), 'cat', var(), 'Canada'), people),

The person named Matthew lives in USA:

    # Matthew lives in USA
    (membero, ('Matthew', var(), var(), 'USA'), people),

The person who has a black car lives in Australia:

    # The person who has a black car lives in Australia
    (membero, (var(), var(), 'black', 'Australia'), people),

The person named Jack has a cat:

    # Jack has a cat
    (membero, ('Jack', 'cat', var(), var()), people),

The person named Alfred lives in Australia:

    # Alfred lives in Australia
    (membero, ('Alfred', var(), var(), 'Australia'), people),

The person who has a dog lives in France:

    # Person who owns the dog lives in France
    (membero, (var(), 'dog', var(), 'France'), people),

One of the people in this group has a rabbit. Who is that person?

    # Who has a rabbit?
    (membero, (var(), 'rabbit', var(), var()), people)
)

Run the solver with the preceding constraints:

# Run the solver
solutions = run(0, people, rules)

Extract the output from the solution:

# Extract the output
output = [house for house in solutions[0] if 'rabbit' in house][0][0]

Print the full matrix obtained from the solver:

# Print the output

print('\n' + output + ' is the owner of the rabbit')

print('\nHere are all the details:')

attribs = ['Name', 'Pet', 'Color', 'Country']

print('\n' + '\t\t'.join(attribs))

print('=' * 57)

for item in solutions[0]:

    print('')

    print('\t\t'.join([str(x) for x in item]))

If you run the code, you will see the following output:

pz3

The preceding figure shows all the values obtained using the solver. Some of them are still unknown as indicated by numbered names. Even though the information was incomplete, the solver was able to answer your question. But in order to answer every single question, you may need to add more rules.

This program was to demonstrate how to solve a puzzle with incomplete information. You can play around with it and see how you can build puzzle solvers for various scenarios.


Now that you have learned how to write a Python program using logic programming to solve an interesting puzzle, you might like to explore more real-world scenarios. Just pick up a copy of Artificial Intelligence with Python to learn about various algorithms that can add an intelligence layer for building exciting applications.

For more updates you can follow me on Twitter on my twitter handle @NavRudraSambyal

Thanks for reading, please share it if you found it useful 🙂

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s