Pizza Pandemonium

Every year the British Informatics Olympiad run a competition in partnership with Lionhead Studios. The aim – to encourage young people interested in a career in computer games programming.

Each year they produce a poster which is sent out to schools to advertise the competition. The poster arrives with a puzzle that I always dream of finding the time to solve.

A rectangular pizza has been divided up into squares. Having been covered in tasty-brand cheese and tomato sauce, some of the squares have had olives placed on them leaving other squares free.

Write a program to find out how many ways anchovies can be placed onto the pizza assuming no square is allowed to contain both olives and anchovies and no row (or column) in the pizza is allowed to contain more than one anchovy.

The poster example shows one way in which anchovies can be placed on the pizza. Take them off and there are 113* other ways to garnish the pizza.

*There are 7 other ways to place four anchovies on the pizza, 46 ways to place three, 46 for two, 13 for one and don't forget putting no anchovies on the pizza!

Leave a Reply

Your email address will not be published. Required fields are marked *

This site uses Akismet to reduce spam. Learn how your comment data is processed.