Slant is an awesome but underrated game that you can play here if you're interested. Made by the same puzzle company as sudoku, the rules for slant are as follows:
Fill in a diagonal line (a slant) in every grid tile so that there are no loops in the grid, and so that every numbered point has that many lines meeting at it.
Clearly, slant is a superior puzzle when compared against
something like sudoku, as it's easy to get into and revolves around taking a large number of actions, each with satisfying feedback.
But how hard is slant really? Honestly, I'm not sure yet. Slant might be as hard as sudoku (NP complete),
or it might be much easier (polynomial time).
This is the first post in a blog series about slant, where our goal will be to analyze the game, figure out how challenging it is, and learn how
to solve these puzzles efficiently.
A. Intro to Rules
As you start playing slant, you'll notice simple rules you can take advantage of. Often, it's possible to prove a tile must contain either a left or right slant. One common example is the following 3x3 grid, where two (1) numbered points are orthogonally adjacent. If any of the lines shown were flipped to be touching a (1), it would result in a inconsistent state, where the two lines must be touching the other (1).
B. Brute Forcing Slant
Our first goal is to solve slant at all, which we'll do by applying rules. Each rules help us fill in tiles, so let's figure out as many rules as possible!
One way to figure out some new rules is to check every configuration of slants around a set of numbered points. If every valid configuration
has the same slant in a grid tile, then that slant can be inferred. In our example above, all the green slants have to be there, otherwise one
of the puzzle rules will be broken.
A 3x3 grid can contain 4 numbered points in the middle 2x2 locations. In addition, there are only 4 non-trivial kinds of numbered points:
(1), (2), (3), and empty (or no-constraint). This means there are 256 unique permutations of numbered points. However, since all
slant rules are actually the same rule if rotated and/or flipped, there are actually only 55 unique combinations, and that's not event taking
into account the underlying rule.
We start by checking every possible permutation of slants that files the 3x3 grid for a combination of 4 numbered points. Each permutation
of slants will either solve the puzzle or break one of the rules, leaving it inconsistent. If there are no valid solutions for a set of numbered
points, then that puzzle is unsolvable. Going through all combinations, and taking into account rotational
symmetry, we find only 4 2x2 patterns which are not solvable.
If you're playing a valid slant puzzle, you'll never see the following combinations.
Next, if a combination of 4 numbered points has multiple solutions, we can look through them all and see if there are any diagonals which stay
the same the same throughout every pattern.
The following 22 patterns are those which have at least one solution & imply a slant can be placed.
Most of these patterns are ones which are easy to figure out yourself, most notably the ones involving orthogonal (1)s or (3)s.
However, there were two rules I didn't know about before! These rules didn't exist in any of the few sites in which I
could find slant strategies or deductions.
So they're probably brand new!
These rules appear to be different from all the others, being the result of unique interactions caused by the (2)s propagating changes of the (1)s and (3)s.
Placing the opposite slant in any of the corner tiles would result in a contradiction. In addition, like most rules we see a form of inverse symmetry
between the (1)s and (3)s.
However, the diagonals touching the (2)s are an interesting case. The only way to learn these rules naturally is to place a multiple slants and observe
that all cases, would result in a contradiction contradiction. The other rules we've figured out before now only require placing one slant and immediately
noticing a contradiction follows.
This realization begs a few questions
Are there more rules that require more slants to be placed down?
Could we logically derive this rule without brute forcing?
Are there rules that we can't find efficiently without brute forcing?Or even
What's the most efficient way to solve slant puzzles?
C. Next Time
Next time, we'll extend our simple pattern finder from before and construct a pattern database for automated solving of puzzles. Using this
automated solver, we can begin to dive into the complexity of slant and answer some of these questions.
In the future, I want to spend some time figuring out if slant is really NP complete, how to design the hardest puzzles, and
how to use deduction to learn slant rules instead of brute force.
Slant is mathematically interesting, and it'll work as a great punching bag to learn when to apply techniques from different fields or not!
The next article in this series is not out yet! back to home