Edge Matching Puzzles

September 2025

Hard to solve but easy to verify, edge matching puzzles are NP-complete problems.

Python Solver and Visualizer

https://github.com/nst/EdgeMatchingPuzzles

PostScript Solver

/pieces
[(A0-grBP)  % Piece A: green(top), red(right), Blue(bottom), Purple(left)
 (B0-pBPg)  % Piece B: purple, Blue, Purple, green
 (C0-bgBR)  % Piece C: blue, green, Blue, Red
 (D0-pGRb)  % Piece D: purple, Green, Red, blue
 (E0-RpgP)  % Piece E: Red, purple, green, Purple
 (F0-brGP)  % Piece F: blue, red, Green, Purple
 (G0-rGRb)  % Piece G: red, Green, Red, blue
 (H0-gbPR)  % Piece H: green, blue, Purple, Red
 (I0-pgRP)  % Piece I: purple, green, Red, Purple
] def

* SOLUTION: A0,H0,B2,G3,E1,F3,C1,D0,I2,

Minified, 10 lines version: emp_mini.ps

PostScript Solver and Visualizer

emp_viz_full.ps

Define your puzzle, and let your printer solve it!

PostPostScript Solver and Visualizer, minified

Minified in 1127 bytes, using similar techniques from PostScript Tiny Ray Tracer.

emp_viz_1127.ps

Hard-wrapped:

/!{def}def/?[(A0grBP)(B0pBPg)(C0bgBR)(D0pGRb)(E0RpgP)(F0brGP)(G0rGRb)(H0gbPR)(I0
pgRP)]!/`{11}!/Courier findfont 16 scalefont setfont/O{( )}!/'{O " 0 4 3 d h}!/:
<</R[1 0 0]/G[0 1 0]/B[0 0 1]/P[1 0 1]>>!/P{/D}!/Q{/C}!/R{/G}!/S{/B}!/T{/A}!/V{/
F}!/X{/E}!/Z{aload}!/@{repeat}!/&{dict begin}!/${count}!/+{add}!/-{sub}!/#{rects
troke}!/"{dup}!/;{div}!/*{mul}!/~{neg}!/^{gt}!/={eq}!/_{not}!/,{end}!/.{showpage
stop}!/|{32 xor}!/ifelse/moveto/lineto/roll/idiv/stroke/get/put/false/exp/for/if
/translate/fill/mod/setgray/exch/rectfill/setrgbcolor/grestore/gsave/closepath/g
etinterval/show/rotate/pop ${O " 0 $ 93 + put exch cvx !}@/H{putinterval}!/W[128
{{' cvn}}@]! W 48[10{{' cvi}}@]H W 123{z[}h W 125{z]}h/Y[9{0}@]!/U[9{i}@]!({0"`2
*`2*~}{0"b``2*~c`2*0cv}{q"1g68*-32d+4o2+g}{J=_{Vi!}l}{Pq!018{Qq!uC3o`8**C3e`8*~*
mDCgRq!0"`8*`8*#`4*`-`4*6-bG02wx013{Sq!u`4*`4*mG1g68*-B-9""*+*yG2B+g":q"9""*+^{8
4*-}lO"043dhgZzs`~`4*m9""*+^{Hr0pH#}{In0pIf}at}kt}k}{0&Pq!D9={YL.}{018{Sq!UBg_{0
13{Tq!X?Bg!E1A68*+hVi_!D3o0^{E3J|YD1-g1K}lD2^{E0J|YD3-g2K}lF{YDEhUBi_hD1+MYD0hUB
ih}l}k}l}k}a,}{u`8*`87**m?Ltu`8*`83**m0Mu}){" W q g exec cvx}forall ${$ 71 + ' q
!}@ N

C minimal solver

https://gist.github.com/nst/1877490070be99d2dc16c7ee8df5c35d