Replacing tactile membrane with Arduino/relay - 3 terminal (3P1T) relays

Hello, 

This is my first post. I've been searching for days on how to resolve this challenge without much luck.

I'm trying to replace a tactile membrane with a set of relays controlled by an arduino. I've map the membrane and the design is such that every one of the 18 buttons is triggered by 2 terminals and 1 common "exciting" terminal, meaning every action requires shorting 3 terminals. 

I could easily do this with 2 relays per button but you can imagine 36 relays and 2 arduinos to control is a bit too much. I assume this is the brute-force approach result of my lack of experience in electronic design.

I'm open to even forego the idea of the Arduino to control and go to micro switchs, but I can't find what I look for. 3P1T doesn't seem to be fit/size for my application..

Can somebody propose an approach for this?

Any help will be very much appreciated