emp_viz_full.ps

% Edge-matching puzzle solver for 3x3 grid
% Usage: gs emp_viz_full.ps

% Define 9 puzzle pieces with their edge colors
% Format: ID + rotation + 4 edge colors (top, right, bottom, left)
% Colors: lowercase/uppercase pairs must match (g matches G, p matches P, etc.)

/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

/W   100      def
/W2  W  2 div def
/W4  W  4 div def
/W8  W  8 div def

/Helvetica findfont 16 scalefont setfont

/colors <<
    /R [0.9 0.3 0.3]
    /G [0.3 0.9 0.3]
    /B [0.3 0.3 0.8]
    /P [0.8 0.3 0.8] 
>> def

/rectPath { 0 0 W4 W4 neg } def

/trianglePath { 0 0 moveto W8 W4 neg lineto W4 0 lineto closepath } def

/_c_drawShape {
    
    dup

    colors exch toUpper get aload pop setrgbcolor    

    W8 neg W2 translate

    97 ge {
        rectPath rectfill
        0 setgray
        rectPath rectstroke
    } {
        trianglePath fill
        0 setgray
        trianglePath stroke
    } ifelse
    
} def

/toUpper {
    dup 97 ge { 32 sub } if
    ( ) dup 0 4 -1 roll put
} def

/_p_drawPiece {
 
    /p exch def
    
    % tile background
        
    gsave
    1 1 0.8 setrgbcolor
    0 0 W W rectfill
    0 0 0 setrgbcolor
    0 0 W W rectstroke
    grestore
    
    % name

    W2 10 sub W2 6 sub moveto
    p 0 2 getinterval show
    
    % symbol
    
    /rot { p 1 get 48 sub } def
        
    0 1 3 {
        /i exch def
        
        gsave
        W2 W2 translate
        rot i sub 90 mul rotate
        p 3 i add get _c_drawShape
        grestore
        
    } for
        
} def

/_b_showBoard {
    
    /b exch def
    
    0 1 8 {
        /pos exch def
        
        gsave
        pos 3 mod W mul pos 3 idiv W neg mul translate 
        b pos get _p_drawPiece
        grestore        

    } for
    
} def

% ----------

% Game state
/board  [ 9 { null } repeat ] def  % 3x3 board (9 positions), initially empty
/used   [ 9 { false } repeat ] def % Track which pieces have been placed

% Convert lowercase to uppercase and vice versa
% Matching edges must have opposite cases (g matches G)
/swapCase {
    dup 97 ge { 32 sub } { 32 add } ifelse  % if >= 'a' subtract 32, else add 32
} bind def

% Extract the color of a specific edge from a piece, accounting for rotation
% Usage: side piece getSide -> color_character
% side: 0=top, 1=right, 2=bottom, 3=left
/getSide { 
    exch dup 1 get 48 sub           % Get rotation value (convert ASCII digit to number)
    3 -1 roll add 4 mod 3 add get   % Calculate rotated side position and get color
} def

% Main recursive solving function using backtracking
% Usage: position solve
/solve {
    0 dict begin
    /pos exch def % Store current board position (0-8)
    
    % Base case: if we've filled all 9 positions, we found a solution!
    pos 9 eq {
        (* SOLUTION: ) =only
        board { 0 2 getinterval =only (,) =only } forall  % Print piece IDs
        board _b_showBoard
        () = showpage stop
    } {
        
        % Try placing each unused piece at current position
        0 1 8 {
            /i exch def
            used i get not {  % Only try unused pieces
                
                % Try all 4 possible rotations (0°, 90°, 180°, 270°)
                0 1 3 {
                    /r exch def  % Current rotation (0-3)
                    
                    % Create a copy of the piece with the specified rotation
                    /rp pieces i get def
                    rp 1 r 48 add put  % Update rotation digit in piece string
                    
                    % Check if this rotated piece fits at current position
                    /fits true def  % Assume it fits until proven otherwise
                    
                    % Check left neighbor compatibility (if not in leftmost column)
                    pos 3 mod 0 gt {
                        % Compare right edge of left neighbor with left edge of current piece
                        rp 3 getSide swapCase board pos 1 sub get 1 getSide ne { 
                            /fits false def 
                        } if
                    } if
                    
                    % Check top neighbor compatibility (if not in top row)
                    pos 3 ge {
                        % Compare bottom edge of top neighbor with top edge of current piece  
                        rp 0 getSide swapCase board pos 3 sub get 2 getSide ne { 
                            /fits false def 
                        } if
                    } if
                    
                    % If piece fits, place it and continue solving
                    fits {
                        % Place the rotated piece on the board
                        board pos rp put
                        used i true put  % Mark piece as used
                        
                        % Recursively solve the next position
                        pos 1 add solve
                        
                        % Backtrack: remove piece and mark as unused for other attempts
                        board pos null put
                        used i false put
                    } if
                    
                } for
            } if
        } for
    } ifelse
    
    end
} def

gsave W W 6   mul translate pieces _b_showBoard grestore
gsave W W 2.5 mul translate 0 solve             grestore

% Example solution output:
% (* FOUND SOLUTION *)
% A0,H0,B2,G3,E1,F3,C1,D0,I2