Table of contents:

1. Introduction: The Penniless Pilgrim Riddle

1.1. Informal description of the riddle

After months of travel, you’ve arrived at Duonia, home to the famous temple that’s the destination of your pilgrimage. The walk from the welcome center to the temple is some blocks walking away, and you were handed the brochure about the city rules. This city is… unique, in that:

• There’s a strange tax: The tax begins at 0, increases by 2 silvers for every block you walk east (right), doubles for every block you walk south (down). A walk west-bound (left) or north-bound (up) will however decreases it by 2 and by half, respectively.
• The city’s rule, as per the temple’s religion, also forbids you treading back any path you’ve walked, but crossing is allowed.

You just realized you did not bring any silver at all. Even worse, arriving at the welcome center already sets you back some silvers. As a pilgrim, you do not want to enter citizen’s blocks, nor break any rules. How would you reach the temple, located at the very lower-right intersection, without paying any tax?

In this project:

• The board size is randomized, the initial walked road is randomized.
• If multiple solutions are found, a solution is considered better if the final tax is lower.

1.2. Images

The game we researched is inspired by the video “Can you solve the penniless pilgrim riddle? - Daniel Finkel” of TED-Ed: https://youtu.be/6sBB-gRhfjE

The initial state of the game in the video

Its best solution we found using pure brute-force, which is considered better than the solution provided in the video

The tax fluctuate differently based on direction

One of the randomized initial states

2. Description of the problem

2.1. Purpose of the problem

The Penniless Pilgrim Riddle is performed by a mapping gameplay. We classify it as a problem solving by searching, specifically Single-state problem (The environment is known, observable, discrete and deterministic).

Help us to understand basic techniques of AI and advance more technical skills: building a program using Python, game developing, computational thinking, observation and statistics,...

2.2. Search problem formulation