Beware of bugs in the above code; I have only proved it correct, not tried it. — Donald Knuth
Important ⚠️
-
This post includes Wang Tiles 😲
-
Disclaimer, all code provided here is under GPLv3, use it at your own risk.
Introduction
is a simple but powerful language for writing documents developed by Donald Knuth in 1978. Six years later, in 1984, Leslie Lamport released , a complete set of easy-to-use macros that extends TeX. Nowadays, LaTeX is considered a high-level language on its own. Due to the number and completeness of macros, it is unusual to use TeX commands in standard documents. However, LaTeX is less powerfull than raw TeX and most packages only use low-level TeX commands that have access to all features.
On this post, I want to explore TeX commands to perform unusual things, like reading files and defining macros that define other macros. I will describe a format to store Wang Tiles instances, and how to use LaTeX and Tikz to plot them. As a bonus, at the end of this post there is a solver, that is able to generate solutions to any particular instance.
The final solution works, but there are much easier ways to archieve a similar result, for instance, if you take a look at the source code of this page, you will find a CSS definition that is more appropiate for the purpose of drawing tiles. There is also `luatex’ and other TeX processors that let you use other friendlier languages, but I want to learn the fundamentals. Also, this is my first time doing this kind of thing in TeX, if you know a better way to do it, I would appreciate your feedback.
Wang Tiles Format
The format should be simple and contain the minimum information. For convenience we isolate the input of the problem (Tileset) from the output (Placement of tiles), which means that in order to represent the solution we need both files. The advantage of using different files is that we can easily integrate a solver that takes the input and generates a valid solution, see Bonus.
Tileset format
By definition, each tile has 4 colors, for convenience we assign an integer to each color. We store each tile in a line and their colors in this order {left, top, right, bottom}. The numbers assigned to each color are not important, just be consistent and use the same mapping for all tiles.
tiles.txt
3 1 1 1 3 2 1 2 3 1 3 3 2 4 2 1 2 2 2 0 0 0 0 1 0 1 3 2 1 2 0 2 1 2 1 4 1 3 3 2 3 1 0 1
Solution format
Assuming we already have the tileset, the solution can be represented using an N x M matrix where each element a_i,j is the tile at position i,j. Tiles are represented as their respective index in the tileset file described above.
solution.txt
3 4 3 3 3 3 3 4 4 3 3 3 3 3 4 3 3 4 4 3 3 3 3 3 3 3 3 4 4 3 10 5 6 10 6 2 10 5 5 6 2 10 6 10 5 6 10 5 5 6 2 10 6 2 10 6 10 5 5 6 6 0 7 6 1 9 10 6 2 1 9 0 7 6 0 7 6 10 6 1 9 2 1 9 0 7 6 10 6 1 7 6 1 8 8 7 6 1 9 1 7 6 1 7 6 1 7 6 1 8 8 9 1 7 6 1 7 6 1 7 4 4 4 3 3 4 4 4 4 4 4 4 4 4 4 4 4 4 4 3 3 4 4 4 4 4 4 4 4 4 5 5 5 6 10 5 5 5 5 5 5 5 5 5 5 5 5 5 5 6 10 5 5 5 5 5 5 5 5 5 6 2 0 7 6 10 6 2 10 6 2 10 6 10 6 2 10 6 0 7 6 10 6 2 10 6 2 10 6 10 1 9 2 1 7 6 1 9 2 1 9 0 7 6 1 9 0 7 6 1 7 6 1 9 2 1 9 0 7 6 8 8 9 1 8 8 8 8 9 1 7 6 1 8 8 7 6 1 8 8 8 8 8 8 9 1 7 6 1 7 3 3 4 4 3 3 3 3 4 4 4 4 4 3 3 4 4 4 3 3 3 3 3 3 4 4 4 4 4 4 2 10 5 5 6 2 2 10 5 5 5 5 5 6 10 5 5 5 6 10 6 10 6 10 5 5 5 5 5 5
Latex I: Drawing Tiles
The building blocks of the picture are Wang Tiles, in this section we define a TiKZ macro that plots a 1x1cm tile. It can be used in a tikzpicture environment as \tile{red, green, blue, yellow}. I use polar coordinates, because it is possible to loop through the points changing only the angle. All tiles created with this method are centered on (0, 0), it is possible to reposition them with a scope and shifting the position, this is how we will do it.
\def\tile#1{
\def\sqwidth{0.7071cm} % 1cm width <-> sqrt(2) diagonal
\def\startangle{225} % Left triangle first
\newcount\itc;
\itc=0;
\foreach \x in {#1} {
\draw[draw=none,fill=\x]
(0:0cm) -- (-\the\itc*90+\startangle:\sqwidth) -- (-\the\itc*90+\startangle-90:\sqwidth);
\global\advance\itc by1
}
\draw[line width=1pt] (45:\sqwidth) -- (135:\sqwidth)
-- (225:\sqwidth) -- (315:\sqwidth) -- cycle;
\draw[line width=0.7pt] (45:\sqwidth) -- (225:\sqwidth)
(135:\sqwidth) -- (315:\sqwidth);
}
Latex II: Color Palette
In order to plot the tiles, we need a mapping from integers to colors, for instance, 0 → red, 1 → blue. This is not defined in any file, because it is just a visual representation and has nothing to do with the problem, the only thing we should care about is that no two integers represent the same color.
To accomplish this, we could manually set variables wang0 → red, wang1 → blue. However, this doesn’t scale well and contains too much complexity, instead it would be much nicer to define them with one vector. To do so, we create a new macro WangColors. This method is based on section 11.9.1 of TEX by Topic: A TEXnician’s Reference and takes a list of parameters and creates and initializates the variables.
\def\WangColors(#1){\xColors#1,xxx,}
\def\endcolors{xxx}
\def\xColors#1,{\def\temp{#1}
\ifx\temp\endcolors
\else\addwangcolor#1Y
\expandafter\xColors
\fi}
\newcount\wangcnum
\def\addwangcolor#1Y{
\expandafter\gdef\csname wangcol\the\wangcnum\endcsname{#1}
\global\advance\wangcnum by1
}
Usage:
\WangColors(red,blue,green,yellow,orange) % Define palette
% Using the palette to draw a tile
\tile{
\csname wangcol0\endcsname % wangcol0 -> red
\csname wangcol2\endcsname % wangcol2 -> green
\csname wangcol1\endcsname % wangcol1 -> blue
\csname wangcol1\endcsname % wangcol1 -> blue
}
Latex III: Reading the tileset file
Reading files with LaTeX is not much different than any other languages, we use the typical loop that reads the file line by line until EOF. The interesting part is that the TeX processor performs some sort of unification, when the macro is expanded it automatically matches the arguments, this is really helpful to parse custom formats. In this case, we can match the four numbers to their respective four “variables” #1. As you can see on \addtile.
% Input tile set [tiles.txt]
\newread\tilesfile
\openin\tilesfile=tiles.txt
{\endlinechar=-1 \global\read\tilesfile to\tilesline}
\loop\ifeof\tilesfile
\else
\expandafter\addtile\tilesline%
{\endlinechar=-1 \global\read\tilesfile to\tilesline}
\repeat
\closein\tilesfile
% Define tiles using the palette colours
\newcount\tilecount
\def\addtile#1 #2 #3 #4{
\expandafter\gdef\csname cstile\the\tilecount\endcsname{
\tile{
\csname wangcol#1\endcsname,
\csname wangcol#2\endcsname,
\csname wangcol#3\endcsname,
\csname wangcol#4\endcsname
}
}
\global\advance\tilecount by1
}
Example:
\csname cstile0\endcstile % Draws the first tile of the palette with the colors defined in WangColors
Latex IV : Reading the solution file
This time we can’t use the matching, because we don’t know beforehand how many numbers are in each line, we could fix this by defining the N and M in the first line, but I prefer to automatically infer the dimensions. Using a similar approach to the WangColor macro, we process the numbers, one by one, defining at each step the tile-position.
We can derive N by counting the number of lines and M by counting the total number of tiles divided by N.
% Define grid
\newcount\gridnum
\def\addwtile(#1){\expandafter\xWtile#1 xxx }
\def\xWtile#1 {\def\temp{#1}
\ifx\temp\endcolors
\else\addgrid#1Y
\expandafter\xWtile
\fi}
\def\addgrid#1Y{
\expandafter\def\csname wt\the\gridnum\endcsname{\csname cstile#1\endcsname}
\global\advance\gridnum by1
}
\newcount\linenum
\newread\solutionfile
\openin\solutionfile=solution.txt
{\endlinechar=-1 \global\read\solutionfile to\tilesline}
\loop\ifeof\solutionfile
\else
\expandafter\addwtile(\tilesline)%
\global\advance\linenum by1
{\endlinechar=-1 \global\read\solutionfile to\tilesline}
\repeat
\closein\solutionfile
Example:
\csname wt0\endcstile % Draws the first tile of the solution with the corresponding cstile
Latex V: Final plot
This is the final result displayed on the beginning of this post. The idea is to iterate all the positions on the grid and each time draw the corresponding tile. You can see that the \begin{scope} is reponsible for placing the tile at its position.
\def\plottile#1{\csname cstile#1\endcsname}
\def\gridtile#1{\csname wt#1\endcsname}
\begin{tikzpicture}
\pgfmathsetmacro\gridheight{int(\the\linenum - 1)}
\pgfmathsetmacro\gridwidth{int(\the\gridnum/\the\linenum - 1)}
\foreach \i in {0,...,\gridheight} {
\foreach \j in {0,...,\gridwidth} {
\begin{scope}[xshift=\j cm, yshift=-\i cm]
\pgfmathsetmacro\wid{int(\i*(\gridwidth+1) + \j)}
\gridtile\wid
\end{scope}
}
}
\begin{scope}[yshift=2cm]
\pgfmathsetmacro\tilecountm{int(\the\tilecount-1)}
\foreach \i in {0,...,\tilecountm} {
\begin{scope}[xshift=\i cm]
\plottile\i
\end{scope}
}
\end{scope}
\end{tikzpicture}
Bonus: Wang Tiles Solver using PySAT
Initially this section was just solver for the Wang Tiles problem, so you could generate custom
solutions.txtfromtiles.txt, but I received your feedback and I want to provide you a detailed explanation of the underlying idea.
This solver is based on SAT and should outperform any naïve implementation. The idea is to convert the tiles to a set of Boolean variables, add the problem constraints and find a feasible assignment using a SAT solver, finally retrieve the tiles from the Boolean variables. Finding an assignment is out of the scope of this post, I will focus on modeling the problem.
Why SAT
Why not a simple backtracking algorithm? First, this problem easily translates to SAT and it is straighforward to implement in Python. Second, it is not trivial to do it faster, SAT solvers use good heuristics and low-level CPU tricks.
Why not Mixed-Integer Programming? This problem does not use arithmetic and is highly combinatorial, for this reason I believe a MIP would be much slower than SAT. Let me know if you try it, so I can include it here 😀 .
The Model
We are given a set of tiles and two dimensions N and M. On the following figure, we observe the complete search space where each position can contain any tile. Let be a Boolean variable that is 1 when tile k is at position i,j and zero otherwise. Our goal is to find an assignment to each variable under some constraints.
Constraints
You have probably already guessed the first constraint, there has to be exactly one tile in each position. Then we need two more constraints, horizontally adjacent tiles must have the same color on the same edge, and the same but vertically. These constraints are generated from the tileset and applied to each position of the grid. In the following figure we see an example, setting the first tile to 1 restricts the set of tiles we can place on the second tile.
The complete set of constraints is the following:
The first constraint contains an arithmetic operation, but it is not a problem since it can be implemented using Boolean constraints. In fact, it is known as Exactly-K, and exploring how different encondings affect the speed and size of the model is an active area of research.
Source Code
Boolean variables are defined as literals, . With this encoding we can recover the tiles at each position by filtering the positive literals (mod T). The +1 is there because the literal zero can’t be used.
I used the sequential counter for the cardinality constraint (1), this needs extra Boolean variables that are provided with IDPool.
from pysat.solvers import MinisatGH
from pysat.formula import IDPool
from pysat.card import *
import sys, getopt
class Tiles():
def __init__(self, infile, width, height):
fopen = open(infile, "r")
lines = fopen.readlines()
fopen.close()
self.tileset = [x.split() for x in lines]
T = len(self.tileset)
self.cons2 = [(x, [y for y in range(T) if self.tileset[x][3] == self.tileset[y][1]]) for x in range(T)]
self.cons3 = [(x, [y for y in range(T) if self.tileset[x][2] == self.tileset[y][0]]) for x in range(T)]
self.width = width
self.height = height
self.pool = IDPool(start_from=self.a(self.width-1, self.height-1, len(self.tileset)-1) + 1)
def tile_idx(self, i, j):
return i*self.width+j+1
def a(self, i, j, k):
return self.tile_idx(i, j)*len(self.tileset) + k
def constraint_1(self, i, j):
lits = [self.a(i, j, x) for x in range(len(self.tileset))]
return CardEnc.equals(lits=lits, encoding=EncType.seqcounter, bound=1, vpool=self.pool).clauses
def constraint_2(self, i, j):
res = []
for x, y in self.cons2:
res += [[-self.a(i, j, x)] + list(map(lambda m: self.a(i+1, j, m), y))]
return res
def constraint_3(self, i, j):
res = []
for x, y in self.cons3:
res += [[-self.a(i, j, x)] + list(map(lambda m: self.a(i, j+1, m), y))]
return res
def get_formula(self):
formula = CNF()
for i in range(self.height):
for j in range(self.width):
for c in self.constraint_1(i, j):
formula.append(c)
if i < self.height - 1:
for c in self.constraint_2(i, j):
formula.append(c)
if j < self.width - 1:
for c in self.constraint_3(i, j):
formula.append(c)
return formula
def solve(self):
formula = self.get_formula()
g = MinisatGH()
for c in formula.clauses:
g.add_clause(c)
feasible = g.solve()
if feasible:
self.solution = [
y % len(self.tileset)
for y in sorted([x for x in g.get_model()
if x > 0 and x <= self.a(self.width-1,self.height-1,len(self.tileset)-1)])
]
return feasible
def output(self):
if not self.solution:
raise "UNKNOWN"
for i, tilecol in enumerate(self.solution):
print(tilecol, end=" ")
if (i+1) % self.width == 0:
print()
def main(argv):
inputfile = ''
width = 10
height = 10
try:
opts, args = getopt.getopt(argv,"i:w:h:",["ifile="])
except getopt.GetoptError:
print('[error]: solver.py -i <inputfile>')
sys.exit(2)
for opt, arg in opts:
if opt in ("-i", "--ifile"):
inputfile = arg
elif opt in ("-w", "--width"):
width = int(arg)
elif opt in ("-h", "--height"):
height = int(arg)
model = Tiles(inputfile, width, height)
if model.solve():
model.output()
if __name__ == "__main__":
main(sys.argv[1:])
Usage:
$ ./solver.py -i <inputfile> -w <width> -h <height> > solution.txt
Future steps
Learn how shapes.geometric shapes are defined and how to create anchor points.