Solving the Most Complex Lock Patterns

3×3	4×4
distance: 22*	distance: 61*

5×5	6×6
distance: 119	distance: 207

7×7	7×7
distance=315	distance=317

About

In this repository, we present solutions for the most complex lock patterns using the MiniZinc modeling language and the powerful Google OR-Tools solver. Additionally, we use the Julia Language to generate the input data and analyze the results.

This repository was inspired by the video What Is The Most Complicated Lock Pattern? by Dr. Zye. I highly recommend watching it! Also, you can try out lock patterns with lock pattern demo by @tympanix.

We use a generalized definition of maximum complexity for a lock pattern, presented in Dr. Zye's video, such that it has solutions for all n×n grids while preserving the original solutions. Our definition requires all lines in the pattern to have a unique "type" (slope), and we maximize the total "taxicab" distance of the pattern, which results in greater visual complexity for the patterns. The problem is a combinatorial optimization problem. The documentation covers the theoretical aspect of the problem.

Structure

The source code in this repository is structured as follows.

• The src/ directory contains Julia code.
• The models/ directory contains the MiniZinc models.
• The models/instances/ contains the datafiles for different grid sized instances of the model.
• The models/fzn/ contains FlatZinc files generated from each model instances. These are useful to understand the size of a model instance and verify that variables have sensible bounds.
• The scripts/ directory contains scripts for generating data files for instances, running the model, and plotting the results.

The output is located in the following directories.

• The results/ directory contains the text output from the models.
• The plots/ directory contains the generated SVG plots for each grid size and taxicab distance in format <grid>/<distance>/<id>.svg. The <id> is a unique identified generated using hash of the pattern.

Instructions

To begin, we need to install MiniZinc and Google OR-Tools. On Linux, we can use the following shell scripts for the installation. After the installation, we can run shell scripts from the scripts directory and write the output to the results/3x3.txt file. For example, we can run the optimization model using the following command.

./scripts/nxn_opt.sh 3 results/3x3.txt

The output generated by the solver will appear to the results/ directory.

Open Questions

Can we find a max complexity pattern for a 4×4 grid that provably maximizes the taxicab distance?

Can we find a max complexity pattern for a 5×5 grid that provably maximizes the taxicab distance?

Can we find a max complexity pattern for a 7×7 grid?