There needs to be some representation of the state of the puzzle such as the cells having symbols in them (or being blank) and what is known about cell content but is not ready to commit to writing in the cell. There is unchanging geometry about which cells are sharing a set of symbols with which others. I coined the term "clot" for 9 related cells whether that's a row, a column or a block. The solver's treatment of them doesn't care very much which it is. This led me to classes "board, "clot","cell".
An argument "-a" is read if present. Either a file named on the command line or STDIN is read for the initial puzzle state. The size of the square (9x9 to 36x36) is discovered from that input.
As the OO part starts board->new() is called. Setup of the board includes defining the character set allowed in cells because that depends on the puzzle size. Other parts of the code need to be aware of this. set_cell($dig, "input provided") is used to write the initial state into the relevant cells.
The main program file enters a loop where it calls board methods "infer" (for logic) and "guess" and "unguess" until the termination conditions are met.
board->infer() calls clot->infer() on all clots not yet solved. clot->infer() has 3 logical ways of progressing the puzzle.
notdig() is the way of propagating negative knowledge around the puzzle - for instance if the first cell is 1 then all the other cells in the same 3 clots cannot be 1. clot->notdig() is called every time set_cell() sets a cell value not known before.
Guessing is done by making a whole new copy of the board and adjusting that (while keeping a path back to the earlier board for unguessing). This is where the languange with its attitude to objects and memory management affects what programming styles make sense.I'd write something about profiling it but it's been written already. 
perl -d:NYTProf ./solve.plx in nytprofhtml --open