Mobile phone tracking is a process for identifying the location of a mobile phone, whether stationary or moving. Localisation may occur either via multilateration of radio signals between several cell towers and the phone, or simply via GPS.

Mobile positioning is used by telecommunications companies to approximate the location of a mobile phone and enables to offer location-based services and/or information to the mobile user.

Cell Phone Trilateration / Multilateration

Cell tower trilateration (sometimes referred as triangulation) is used to identify the location of the phone. A cell phone constantly emits roaming radio signals that may be picked up by three or more cell towers enabling the triangulation to work. Trilateration calculations estimate the coordinates of a mobile device using the coordinates (longitude,latitude) of nearby cell towers as well as the estimated distance of the device from the cell towers (e.g. either based on signal strength or by measuring the time delay that a signal takes to return back to the towers from the phone).

In this challenge we will investigate the math equations used in trilateration calculations. We will simplify the process by using a 2D model of the problem based on (x,y) coordinates (as an alternative to longitude/latitude coordinates).

On the diagram above, each circle represents all the possible locations of a mobile phone at a given distance (radius) of a cell tower. The aim of a trilateration algorithm is to calculate the (x,y) coordinates of the intersection point of the three circles. Each circle is defined by the coordinates of its center e.g. (x₁,y₁) and its radius e.g. r₁.

The following steps will help us calculate these (x,y) coordinates:

Step 1
The three equations for the three circles are as follows:

Step 2:
We can expand out the squares in each of these three equations:

Step 3:
Now let’s subtract the second equation from the first:

Likewise, we can now subtract the third equation from the second:

Step 4:
Let’s rewrite these two equations using A, B, C, D, E, F values. This would result in the following system of 2 equations:

Step 5:
The solution of this system is:

Python Implementation

Now that we understand the math needed in a trilateration calculation, let’s implement these equations in a Python algorithm using a function that will take 9 parameters (x₁,y₁r₁,x₂,y₂r₂,x₃,y₃r₃) and return the (x,y) coordinates of the intersection point of the three circles.

Your task is to complete the code of the trackPhone() function that we have started for you:

GPS Positioning

Note that GPS satnav systems use a similar approach but need to be more accurate by:

• Estimating the distance between a GPS satnav device and at least three GPS satellites. This is done by measuring the time delay that a signal takes to be sent from the satellite to the GPS satnav, and converting this time delay into a distance,
• Using more advanced multilateration formulas based on a 3D model rather than a 2D model.

Lissajous curves are a family of curves described by the following parametric equations:

Lissajous curves have applications in physics, astronomy, and other sciences. Below are a few examples of Lissajous curves that you will be able to reproduce in the Python Trinket provided below by changing the values of constant A and B in the Python code.

Lissajous Curve using Python Turtle

Spirographs?

When tracing different Lissajous curves, you will notice that these curves are enclosed in a rectangular shape.

Spirographs are very similar to Lissajous curve but instead of being enclosed by rectangular boundaries, spirographs are generally enclosed by a circular boundary.

You can trace your own spirographs using Python Turtle by completing this Python Turtle challenge.

Rose Curves

Your task is to adapt the above Python script to draw different Rose curves. You can find out more about rose curves and about their parametric equations on the following wikipedia page.

Your task is to design an algorithm used to create a Sudoku Grid. The generated Sudoku grid should have enough clues (numbers in cells) to be solvable resulting in a unique solution.

Sudoku?

A Sudoku game is number-placement puzzle. The objective is to fill a 9×9 grid with digits so that each column, each row, and each of the nine 3×3 subgrids that compose the grid (also called “boxes”, “blocks”, or “regions”) contain all of the digits from 1 to 9. The puzzle setter provides a partially completed grid, which for a well-posed puzzle has a single solution.

Our aim for this challenge is not to generate a Sudoku solver algorithm but instead to create an algorithm to be used by a puzzle setter to produce a well-posed Sudoku grid: a grid with a unique solution. For instance the output of our algorithm could be a grid such as this one:

Did You Know?

Sudoku fanatics have long claimed that the smallest number of starting clues a Sudoku puzzle can contain is 17. There are effectively numerous examples of grids with 17 clues that have a unique solution but we have never found a well-posed grid with only 16 clues. This suggests that the minimum number of clues to provide in a grid is 17.

This key fact might be useful to help you solve this challenge more effectively.

Sudoku Solver Algorithm

Your Sudoku Generator algorithm may need to use a Sudoku Solver Algorithm in order to test whether a generated grid is solvable and to check that it only gives a single solution.

The most common type of Sudoku Solver Algorithm is based on a backtracking algorithm used to investigate all possible solutions of a given grid.

You can find an example of such an algorithm by investigating the code provided in this Python Challenge: Sudoku Solver using a Backtracking Algorithm

Extension Task:

Sudoku puzzles are often given a difficulty level such as “Beginner – Intermediate – Advanced – Expert”.

How could your algorithm be adapted to estimate the difficulty level of a Sudoku grid?
Should different algorithms be used to generate Sudoku grids for a specific difficulty level?

Solution

Our solution is based on 5 steps:

1. Generate a full grid of numbers (fully filled in). This step is more complex as it seems as we cannot just randomly generate numbers to fill in the grid. We have to make sure that these numbers are positioned on the grid following the Sudoku rules. To do so will use a sudoku solver algorithm (backtracking algorithm) that we will apply to an empty grid. We will add a random element to this solver algorithm to make sure that a new grid is generated every time we run it.
2. From our full grid, we will then remove 1 value at a time.
3. Each time a value is removed we will apply a sudoku solver algorithm to see if the grid can still be solved and to count the number of solutions it leads to.
4. If the resulting grid only has one solution we can carry on the process from step 2. If not we will have to put the value we took away back in the grid.
5. We can repeat the same process (from step 2) several times using a different value each time to try to remove additional numbers, resulting in a more difficult grid to solve. The number of attempts we will use to go through this process will have an impact on the difficulty level of the resulting grid.

Full Python Code