Edge-matching puzzle solver for 3x3 grid

emp_full.ps

% Edge-matching puzzle solver for 3x3 grid
% Usage: gs -q -dNODISPLAY emp.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

% Initialize the 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  % Create local variable scope
    /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
        () = stop
    } {
        
        % Try placing each unused piece at current position
        0 1 8 {
            /i exch def  % Current piece index
            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  % End rotation loop
            } if
        } for  % End piece loop
    } ifelse
    
    end  % End local variable scope
} def

% Start solving from position 0 (top-left corner)
0 solve

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