54

A Snake Egg Puzzle Solver

 2 years ago
source link: https://github.com/tuzz/snake-egg-puzzle
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.

Snake Egg puzzle

A Sentient program to solve Snake Egg puzzles. The puzzle is explained in this YouTube video .

Sentient is a programming language I wrote a few years ago to solve difficult combinatorial problems. This seemed like a fun and unusual problem so I thought I'd try using Sentient to solve it. It was definitely a challenge and required thinking hard about some tricky constraints but it works!

The example puzzle from the YouTube video is in the example/ directory. You can solve this puzzle with Sentient by providing assignments that specify the head/tail positions of the snake and the two numbers given to you for this puzzle. Here's how you'd do that:

sentient --run snake-egg.json --machine lingeling --assign-file example/assignments.json \
         | ruby pretty_print.rb

This produces the following output after about two minutes:

9 9 █ █ █ 7 █ █ █ █
9 9 9 9 █ 7 █ 5 5 █
█ █ █ 9 █ 7 █ █ 5 █
2 2 █ 9 █ 7 7 █ 5 █
█ █ █ 9 █ 7 █ █ 5 █
█ 8 8 █ █ 7 █ 4 █ █
█ █ 8 █ 1 █ █ 4 █ 6
3 █ 8 █ █ █ 4 4 █ 6
3 █ 8 8 8 8 █ █ █ 6
3 █ █ █ █ █ █ 6 6 6

Alternatively, you can create your own assignments to solve different puzzles or run Sentient with no assignments at all to generate finished puzzles! Check out the comments in the snake-egg.snt file for a general overview of how the constraints are specified.

There's also a search_minimal.rb script that takes, as input, a finished puzzle and tries to find the minimal sets of numbers that produce it as a unique solution. This is very time consuming - it iteratively solves the puzzle over and over.

Gallery

Here are some finished puzzles generated by Sentient:

1) Smiley Face                 2) TWO!                     3) THREE!                  4) Squirrel

█ █ █ 2 █ █ █ █ █ █         █ █ █ █ 1 █ █ █ 4 4         █ █ █ █ █ █ █ █ █ 8         █ █ █ 8 8 █ █ █ █ 1
█ 9 █ 2 █ 5 5 5 5 █         █ 2 2 █ █ 7 7 █ 4 4         █ 9 9 9 9 9 9 9 █ 8         █ 6 █ 8 8 █ 5 5 █ █
█ 9 █ █ █ 5 █ █ █ █         █ █ █ 9 █ █ 7 █ █ █         █ █ █ 9 9 █ █ █ █ 8         █ 6 █ 8 █ █ 5 5 5 █
█ 9 9 9 9 █ █ 8 8 8         9 9 █ 9 9 █ 7 7 7 █         6 6 █ █ █ 8 8 8 8 8         █ 6 █ 8 █ 9 █ █ █ █
█ █ █ █ 9 █ 8 8 8 8         9 9 9 9 █ █ 7 █ █ █         6 6 6 6 █ █ █ █ █ █         █ 6 █ 8 █ 9 █ 3 3 3
7 7 7 █ 9 █ 8 █ █ █         █ █ █ █ █ 8 █ █ 5 5         █ █ █ █ 7 7 7 7 7 █         █ 6 █ 8 █ 9 █ █ █ █
7 7 7 █ 9 █ █ █ 1 █         █ 8 8 8 8 8 █ 5 5 5         █ 2 2 █ █ 7 █ █ 7 █         █ 6 █ █ █ 9 9 9 9 █
█ █ 7 █ █ 6 6 6 █ █         █ 8 █ █ █ 8 █ █ █ █         █ █ █ 5 █ █ █ 1 █ █         █ █ 4 4 4 █ █ █ 9 9
3 █ █ 6 6 6 █ █ █ 4         █ █ █ 6 █ █ 3 3 3 █         4 4 █ 5 5 5 5 █ █ 3         2 █ 4 █ █ █ 7 █ █ █
3 3 █ █ █ █ █ 4 4 4         6 6 6 6 6 █ █ █ █ █         4 4 █ █ █ █ █ █ 3 3         2 █ █ █ 7 7 7 7 7 7



    5) FIVE!                  6) Raised Hands                7) Poodle                  8) Doberman

6 6 6 6 █ █ █ █ █ █         2 █ █ █ 1 █ █ █ 3 3         █ █ █ █ 6 6 █ █ █ █         6 6 6 6 6 █ 4 █ █ █
6 6 █ █ █ 4 4 4 4 █         2 █ 5 █ █ 4 4 █ █ 3         █ 7 7 █ 6 6 █ 3 3 █         █ █ █ 6 █ █ 4 █ 3 █
█ █ █ 7 7 █ █ █ █ █         █ █ 5 5 █ █ 4 4 █ █         █ 7 7 █ 6 █ █ 3 █ █         █ 1 █ █ █ 4 4 █ 3 █
█ 7 7 7 7 █ 5 5 5 5         █ 8 █ 5 5 █ █ █ 7 █         █ 7 7 █ 6 █ 8 █ █ 9         █ █ 9 9 9 █ █ █ 3 █
█ █ █ █ 7 █ █ █ █ 5         █ 8 █ █ █ 9 9 █ 7 █         █ █ 7 █ █ █ 8 █ 9 9         2 █ 9 █ █ █ 7 7 █ █
3 3 3 █ █ 9 9 9 █ █         █ 8 8 8 █ 9 █ █ 7 █         1 █ █ 8 8 8 8 █ 9 9         2 █ 9 █ 8 8 █ 7 █ 5
█ █ █ 1 █ █ █ 9 9 █         █ █ █ 8 █ 9 █ 7 7 █         █ 4 █ 8 █ █ 8 █ █ 9         █ █ 9 █ 8 █ █ 7 █ 5
█ 8 █ █ 2 2 █ 9 9 █         6 6 █ 8 █ 9 █ █ 7 █         █ 4 █ █ 5 █ █ 2 █ 9         █ 9 9 █ 8 █ 7 7 █ 5
█ 8 8 █ █ █ █ 9 9 █         6 6 █ 8 █ 9 9 █ 7 █         █ 4 4 █ 5 5 █ 2 █ 9         █ 9 █ █ 8 █ █ 7 █ 5
█ █ 8 8 8 8 8 █ █ █         6 6 █ █ █ 9 9 █ █ █         █ █ █ █ 5 5 █ █ █ 9         █ █ █ 8 8 8 █ █ █ 5



  9) Angry Face              10) Confused Face            11) MechWarrior             12) Tall Boots

7 7 █ █ █ 3 3 █ █ █         █ █ █ 4 4 4 █ █ █ █         3 3 3 █ █ █ 4 █ █ █         6 6 █ █ █ 1 █ █ █ █
7 7 █ 9 █ █ 3 █ 2 █         █ 9 █ 4 █ █ █ 6 6 █         █ █ █ █ 7 █ 4 █ 6 █         6 6 █ 8 █ █ █ 4 4 █
7 7 █ 9 9 █ █ █ 2 █         █ 9 █ █ █ 6 6 6 6 █         █ 7 7 7 7 █ 4 █ 6 █         6 6 █ 8 8 8 8 █ 4 █
7 █ █ 9 9 9 9 9 █ █         █ 9 9 9 9 █ █ █ █ █         █ █ █ 7 7 █ 4 █ 6 █         █ █ █ 8 █ 8 █ █ 4 █
█ █ 8 █ █ █ 9 █ █ 4         █ █ █ █ 9 █ 8 8 8 8         8 8 █ █ █ 9 █ █ 6 █         █ 7 7 █ █ 8 █ 9 █ █
█ 8 8 █ 6 █ █ █ 4 4         7 7 7 █ 9 █ 8 8 8 8         8 8 8 8 █ 9 █ 6 6 █         █ 7 7 █ 5 █ █ 9 █ 2
█ 8 █ █ 6 6 6 6 █ 4         7 7 7 █ 9 █ █ █ █ █         8 8 █ █ █ 9 █ █ █ 5         █ █ 7 █ 5 █ 9 9 █ 2
█ 8 8 8 █ █ █ 6 █ █         █ █ 7 █ █ 5 5 5 5 █         █ █ █ 9 9 9 9 9 █ 5         3 █ 7 █ 5 █ 9 9 █ █
█ 8 █ █ █ 5 █ █ 1 █         3 █ █ 2 2 █ █ █ 5 █         █ 2 2 █ █ █ 9 █ █ 5         3 █ 7 █ 5 █ 9 9 9 █
█ █ █ 5 5 5 5 █ █ █         3 3 █ █ █ █ 1 █ █ █         █ █ █ █ 1 █ █ █ 5 5         3 █ █ █ 5 █ █ █ █ █



  13) Octopus                  14) Werewolf                15) Antennae               16) Steam Train

█ █ █ 4 █ █ █ █ █ 9         █ █ █ 8 █ █ █ 5 5 5         █ █ █ 3 █ █ █ █ 6 6         7 7 █ █ █ 1 █ █ █ █
█ 4 4 4 █ 6 6 6 █ 9         █ 9 █ 8 8 8 █ █ 5 5         █ 9 █ 3 █ 4 4 █ 6 6         7 7 █ 9 █ █ █ 2 2 █
█ █ █ █ █ 6 █ 6 █ 9         █ 9 █ 8 █ 8 8 █ █ █         █ 9 █ 3 █ █ 4 █ 6 6         7 7 █ 9 9 9 9 █ █ █
7 7 7 7 7 █ █ 6 █ 9         █ 9 █ 8 █ █ █ 7 7 █         █ 9 █ █ 2 █ 4 █ █ █         7 █ █ 9 9 █ █ █ 8 8
█ █ █ █ 7 █ 8 █ █ 9         █ 9 █ █ 6 6 █ 7 █ █         █ 9 9 █ 2 █ █ 5 5 █         █ █ 9 9 █ █ 8 8 8 8
█ 3 3 █ 7 █ 8 █ 9 9         █ 9 9 █ 6 6 █ 7 █ 1         █ █ 9 █ █ 8 █ █ 5 █         █ 6 █ █ █ 8 8 █ █ █
█ █ 3 █ █ █ 8 █ 9 9         █ 9 9 █ 6 6 █ 7 █ █         7 █ 9 9 █ 8 8 █ 5 █         █ 6 █ 4 4 █ █ █ 5 █
5 █ █ 8 8 8 8 █ █ █         █ █ 9 █ █ █ █ 7 7 █         7 █ █ 9 █ █ 8 █ 5 █         █ 6 █ 4 █ █ 5 5 5 █
5 5 █ 8 █ █ █ 2 2 █         3 █ █ 4 4 4 4 █ █ █         7 7 █ █ 8 8 8 8 █ █         █ 6 █ 4 █ 3 █ █ 5 █
5 5 █ █ █ 1 █ █ █ █         3 3 █ █ █ █ █ █ 2 2         7 7 7 █ █ █ █ █ █ 1         6 6 █ █ █ 3 3 █ █ █



   17) Rabbit                   18) Kissing               19) Hang Glider

1 █ █ █ █ █ 7 7 █ █         3 █ █ █ █ 1 █ █ █ █         5 5 5 █ █ █ █ █ █ █
█ █ 3 3 3 █ █ 7 7 █         3 █ 7 7 7 █ █ 9 9 █         5 5 █ █ 9 9 9 9 9 █
█ 8 █ █ █ 4 █ █ 7 █         3 █ 7 7 █ █ 9 9 9 █         █ █ █ 9 9 █ █ █ █ █
█ 8 █ 2 █ 4 4 █ 7 █         █ █ 7 7 █ 2 █ █ 9 █         █ 6 6 █ 9 █ 8 8 8 8
█ 8 █ 2 █ 4 █ █ 7 █         █ 5 █ █ █ 2 █ 9 9 █         █ █ 6 █ 9 █ █ 8 8 8
█ 8 █ █ 9 █ █ 5 █ █         █ 5 █ 6 6 █ █ 9 █ █         3 █ 6 █ █ 1 █ █ █ 8
█ 8 8 █ 9 █ 5 5 █ 6         █ 5 █ 6 █ █ 4 █ █ 8         3 █ 6 6 █ █ 7 7 █ █
█ 8 8 █ 9 █ 5 █ █ 6         █ 5 █ 6 █ 4 4 █ 8 8         3 █ █ █ 4 █ 7 7 7 █
█ █ █ █ 9 █ 5 █ 6 6         █ 5 █ 6 █ 4 █ █ 8 8         █ 2 2 █ 4 █ █ 7 7 █
9 9 9 9 9 █ █ █ 6 6         █ █ █ 6 █ █ █ 8 8 8         █ █ █ █ 4 4 █ █ █ █

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK