I'm currently in the process of salvaging keyboard from my wife's old, broken laptop. Keyboards are usually built in such way, that each key is placed on top of two wires: row and column. When you press the button, it shorts row with column, so that if you apply current to row (or column), you can determine from the second one, which button was pressed.
Keyboard connects with the motherboard with a 24-pin ribbon, so we have pins 1, 2, 3, ..., 23, 24. Some of them represent rows and some - columns. However, there is no specific rule regarding which ones are which, for instance in my case columns are 1, 2, 3, 4, 5, 14, 15, 16, 17, 18, 19, 20, 21, 22, 23, 24 and rows - 6, 7, 8, 9, 10, 11, 12, 13 (this is keyboard from Asus F3 - if anyone is interested)
It is relatively easy to write an Arduino program, which gives you a pair of pins which are shorted when you press a button. However, without keyboard schematics, you are unable to determine, which one represents row and which - column.
So the problem is: given a set of pairs (a, b), which represents coordinates in the table (but the order is unknown - row and column or the other way around), determine numbers representing rows and columns in that table. Numbers are unique, so a number may either represent a row or a column, never both.
For example:
(1, 3), (4, 2), (2, 3), (4, 1)
represents a table
1 2
3
4
Sorted coordinates would be then (1, 3), (2, 4), (2, 3), (1, 4).
There are at least two solutions to every problem (you can transpose the table).
What algorithm would you propose to determine, which numbers represents columns and rows? Is it NP-hard or is there some simpler solution?