You will need three sensors: front, left, and right.
Then, build a representation of where the walls are as you navigate.
Build a map from the data you acquire as you navigate.
Once you have the map, you can identify areas that you haven't yet "seen" and navigate to there using basic graph search theory (breadth-first, A-star, Dijkstra, or whatever.)
In general, this class of algorithm is known as "SLAM" although this special case can be solved more simply than the general case.
I'd use a grid-based map representation with cells being about 1/4 the side length of the robot size. I'd classify a cell as "blocked" or "open," perhaps with a few levels of intermediate passability for uncertainty handling. (Might as well use a byte per cell)
Also, it's important the robot can navigate straight, to avoid skew! IMU sensors, GPS (assuming you are in a place where GPS can get a lock,) and encoders on wheels/motors to drive straight could all be very helpful.
It's unlikely that a microcontroller with limited RAM, like the Atmegas and PICs of the world, would have enough RAM to do a decent job of this; I'd recommend a small SBC like the Raspberry Pi or the BeagleBone/Black. (The RPi is available, well documented, and cheap -- that'd be my first option for this.)