This is the final solution for my experiment to find the most optimal keyboard layout for use by one-finger or cursor+click movement:

  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z

The vowels in the second row would be enlarged to cover the width of the entire row.

The primary goal of the KType project is to improve communication for people with disabilities. I am developing an iPad app that presents the users with an on-screen keyboard with large keys that can be re-arranged easily for comfort and efficiency. The application makes communication easier by predicting what the user will type next. I analyzed how people talk on Twitter to create KType's prediction engine. Improving prediction is just one way to reduce the effort needed to communicate. Another way is to minimize the amount of movement required to type.

The computer keyboard layout we are all familiar with is called QWERTY based on the first six letters in the top row. It was designed by C. L. Sholes in 1878 for using a typewriter with two hands and the letters were arranged in a special, non-alphabetical order to improve the speed of typing by minimizing jamming of the typewriter. Since computer keyboards don't jam, many people have tried to re-arrange the keyboard layout to improve typing efficiency; a layout popular among computer programmers is called Dvorak. But all of these layouts are optimized for users with two hands, ten fingers.

Potential users of KType might use head-tracking and blink-action to type. Existing keyboard layouts are inefficient for typing with a single finger or cursor+click movement. KType users could certainly benefit from a keyboard layout that requires the least amount of movement when typing with just one finger. With that goal in mind, I sought to design such a layout - the Optimus Keyboard Layout.

In addition to Optimus, KType will also provide QWERTY, DVORAK, ABCDEF keyboard layouts to users who are already accustomed to a particular layout and do not wish to switch.

The 26 letters of the English alphabet can be rearranged into infinite ways on a flat surface. You can put all the keys in a straight line, arrange the consonants in a circle with the vowels in the middle, or break them into rows like regular computer keyboards. How can we measure if one keyboard layout is better than any other? To answer that question, I used a simple formula to calculate the score for each keyboard layout:

Keyboard Score = (Distance between a key and every other key) * (Frequency of that key-pair being used in regular typing)

The distance is relatively easy to calculate. Keys next to each other and above/below each other have a distance of one. Keys diagonal to each other have a distance of square-root of 2. If the keys are in a grid, it is trivial to compute the distances using the Pythagoras Theorem. Python even has a math.hypot function to make this easy.

The frequency for each combination of letters comes from my recent analysis of Twitter data that resulted in this letter-pair frequency table. I analyzed 9 million Tweets and obtained a list of the most common words and phrases used by over a hundred thousand users. Based on the frequency of use of each word and phrase, it was straightforward to calculate how often do two letters follow each other in common usage. Not surprisingly, the letters 'T' and 'H' are typed in a row most often, followed by 'I' and 'N', then 'E' and 'R'.

Imagine just three keys 'A', 'C', and 'T' arranged next to each other like [A][C][T]:

Distance between A and C                            1
Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Distance between A and T                            2
Frequency of typing 'AT' or 'TA'               x  500  = 1000 (for A, T)
Distance between C and T                            1
Frequency of typing 'CT' or 'TC'               x  100  =  100 (for C, T)
---------------------------------------------------------------------------
Total Keyboard Score                                   = 1300 (for A, C, T)

Lower keyboard scores mean the finger has to travel a shorter distance to type the most common words and phrases. To improve a keyboard layout, we just need to rearrange the letters such that letters most commonly typed in a row (like 'T' and 'H' or 'I' and 'N') are next to each other. In the above example, 'A' and 'T' are furthest apart at a distance of 2 and also typed the most often i.e. frequency of 500. We could easily re-arrange this keyboard to reduce the score as follows:

Re-arrange the three keys 'A', 'C', and 'T' to [C][A][T]:

Distance between A and C                            1
Frequency of typing 'AC' or 'CA'               x  200  =  200 (for A, C)
Distance between A and T                            1
Frequency of typing 'AT' or 'TA'               x  500  =  500 (for A, T)
Distance between C and T                            2
Frequency of typing 'CT' or 'TC'               x  100  =  200 (for C, T)
---------------------------------------------------------------------------
Total Keyboard Score                                   =  900 (for C, A, T)

Re-arranging the keys reduced the total keyboard score without any change in the frequency of typing different letter combinations. This 30% improvement in score means the same text can be typed faster and require less movement. For users who find it difficult to move their hands, this could be a remarkable improvement.

By this metric, the new Optimus keyboard should be significantly better than QWERTY, DVORAK, and alternatives.

To make it even possible to design an optimal keyboard, I had to place some restrictions on the layout:

• It must be a grid of keys (10×3, 9×3, 7×4, 6×5)
• The keys must be directly next to or above/below each other, unlike the QWERTY layout where 'A' is not directly under 'Q'
• Blank key slots are allowed because the only grid layout with exactly 26 slots are 1×26 and 2×13
• All keys must be the same size (keyboard-score calculations get complex otherwise; would also have to worry about overlap/collisions)

These restrictions mean that I could be ignoring a more efficient keyboard layout (possibly circular) but given the fact that almost every keyboard in existence is close to a grid (3 rows of 10 keys) and the iPad has a rectangular screen, a grid-like layout will work for my users. The closer the grid is to a square, the lower the score is. I prefer 7×4 (28 key slots) grid because it is closer to square than 9×3 (27 key slots) and only has two blanks as compared to 6×5 (30 key slots) grid with 4 blanks. Additionally, the KType interface is suited quite well for 4 rows of letters.

The 26 alphabets could be arranged into a grid of 7×4 in over 10^29 ways, into a grid of 6×5 in over 10^32 ways. Planet Earth has only 10^50 atoms so given the current state of technology and my dwindling savings account, it is impossible to simulate every possible keyboard layout and calculate its score to find Optimus. In computer science terms, this is problem is in NP.

After realizing that I was trying to find a perfect solution to an uncomputable problem, I decided to put my four years of college to use. I dug into complexity theory articles and papers to see if someone has solved this exact problem but that effort was fruitless. I turned to reddit/r/compsci subreddit and rephrased my problem into more understandable terms: How would you seat 26 people in a big room of cubicles such that people who like each other a lot end up sitting close to each other? While I did not get an exact answer (and neither did I expect one), I got a lot of leads: genetic optimization, dynamic programming, distance preserving embedding graphs, facilities problem, k-means clustering, and simulated annealing.

I was very interested in using genetic algorithms to evolve a better keyboard from two or more good keyboards but found it impossible to combine two keyboard layouts into a new one. How would one combine the QWERTY and DVORAK layouts to create a new generation in one-pass anyway? I had similar issues in applying k-means clustering, graph layouts etc. to my problem. I don't mean it is impossible to use these methods, I just couldn't find a logical, simple way to apply these solutions to my problem. After fiddling with tons of algorithms, I found that simulated annealing works pretty nicely for this particular problem.

Update 2011-02-28, 1:25pm: Redditor deong mentioned that this problem is called Quadratic assignment problem, which is one of the fundamental combinatorial optimization problems in the branch of optimization or operations research in mathematics, from the category of the facilities location problems.

I tried three different methods to find the most optimal keyboard. I started with the simplest algorithm I could think of:

Step 1: Select a grid size: 7x4 (or 10x3, 9x3, 6x5)
Step 2: Randomly put all the alphabets into the grid
Step 3: Calculate the score
Step 4: Swap two or more keys and recalculate score
Step 5: If score in Step 4 is 'progressively better' than Step 3, keep the new layout
Step 6: Repeat Step 4 about 100,000 times

Each time the above program was run, I would get a new keyboard layout with the lowest possible score that random swapping could achieve. I ran the script 10,000 times for 7×4 grid and here are the three best layouts:

Rank #1, Score: 130575410797

  _ J Y M L D Z
  Q B U O A N G
  X P R E T I C
  _ V F S H W K

Rank #2, Score: 130676148330

  _ K W H S F V
  X C I T E R P
  Q G N A O U B
  _ Z D L M Y J

Rank #3, Score: 130683308691

  V F S H W K _
  P R E T I C Z
  B U O A N G Q
  J Y M L D X _

Notice that the keys 'E', 'T', 'H', are always adjacent to each other and generally towards the center. Similarly 'I', 'N', 'A' are adjacent and close to the center. In practical terms, all three of these keyboards are equally good but the problem with them is that I cannot definitively tell if they are optimal or not. They just look so random!

Step 1: Get an optimized keyboard using Random Grid method
Step 2: For each key in the keyboard, store its position in the grid and the keyboard score
Step 3: Repeat Step 1 about 10,000 times
Step 4: Find the key with the best position among all layouts and place it in that position
Step 5: Repeat Step 4 for all keys i.e. find best open position for each key
Step 6: Print the keyboard with best position for each key

I wrote this algorithm with the idea that if keyboards with letter 'E' in the second row, middle column most often get low scores then there is a good chance that 'E' belongs in the second row, middle column in the Optimus keyboard. It is also possible that keyboards with the letter 'T' in second row, middle column also get very low scores but not as low as 'E' in the same position. In that case we pick the next open position that 'T' has low scores in, and so on for each letter. I ran the script hundreds of times but not one keyboard scored better than any of the Random Grid keyboards, even though we combined optimized keyboard generated via the Random Grid algorithm. Applying 100,000 generations of randomized swapping to the final heat-map keyboard helped, but it was no different than starting with a completely random grid. So in the end, I abandoned this approach.

Step 1: Set grid size to: 7x4
Step 2: Put '_AEIOU_' in the second row, randomly put consonants into rows 1, 3, and 4
Step 3: Calculate the score
Step 4: Swap two or more keys in rows 1, 3, or 4 and recalculate score
Step 5: If score in Step 4 is 'progressively better' than Step 3, keep the new layout
Step 6: Repeat Step 4 about 100,000 times

This method is almost identical to Random Grid with the exception that vowels are fixed in the second row. The idea behind this is three-fold:

• With just 5 letters in second row, I can make the vowels larger and easier to click
• Having a fixed row of vowels will make the keyboard easier to remember and provide a stable home row
• Putting all the vowels in second row means no consonant will be more than 2 vertical units away from the vowels

I ran the above algorithm 100,000 times and was pleasantly surprised at the result. Every single time the best keyboard was the following:

Rank #1, Score: 135242359724

  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z

I also saw the following two layouts popup many times, notice how similar they are to the above layout:

Rank #2, Score: 135298507794
  V D R N G F Q
  _ A E I O U _
  C H T S L P J
  X K W M Y B Z

Rank #3, Score: 135428576171
  V D R N G F Q
  _ A E I O U _
  K C H T S M J
  X B W L Y P Z

I verified my code to ensure that I was indeed going through thousands of random keyboards and not the same random layout over and over again. Yet the exact same layout out of a possible combination of 10^19 (21-factorial permutations) kept showing up as the best result over and over again. Either I was constantly hitting the local minima or I had found Optimus. I wasn't sure. Time to graph it up.

If you look at Step 5 of Random Grid and Fixed Vowel Row algorithms, you'll see I only keep a keyboard generated from swapping two or more keys if the new score is 'progressively better' than the previous score. Whether a new keyboard is considered progressively better or not directly affects how a random keyboard mutates over generations to achieve a lower score. The problem with iteratively generating improved keyboards from an initial random layout is getting stuck in local minima. Local minima is the state where after a number of generations, randomly swapping 2-6 keys over and over will not help lower the score of the keyboard. This doesn't mean we have achieved the best keyboard layout possible, but rather an entirely different layout would be required if we were to get any lower. This is similar to playing Sudoku where after getting the first 2-3 numbers fit, we find it impossible to solve the rest of the puzzle, because even though these 2-3 numbers fit a small section of the puzzle, they are not the correct values and thus do not align with the final solution.

One sure way of getting stuck in the local minima is to set the definition of 'progressively better' to mean strictly better: Only accept a new keyboard if its score is lower than the previous score. A good way to avoid getting stuck in local minima is to accept scores slightly worse than the previous score, in the hope that future generations will lower the scores fast enough to achieve global minima eventually. For us, global minima is the lowest possible score achievable by a keyboard, which by definition is the Optimus Keyboard Layout that we seek.

I ran the Fixed-Vowel Row script with different values for 'progressively better':

• SA=1.05: Accept keyboard if new score is less than 105% of previous score
• SA=1.025: Accept keyboard if new score is less than 102.5% of previous score
• SA=1.01: Accept keyboard if new score is less than 101% of previous score
• SA=1.001: Accept keyboard if new score is less than 100.1% of previous score
• SA=1: Accept keyboard if new score is less than previous score

The following graph shows the keyboard score over 1000 generations for each value of SA. Each of the five curves was generated by taking the lowest score for each generation from 1000 independent runs of the Fixed Vowel Row algorithm.

The horizontal axis is time i.e. the generation of each keyboard layout and vertical axis is the scaled-down keyboard score (100 = worst, 0 = best). Notice that the values for SA=1.001 are lower than those of SA=1 between generations 244 and 460. Both the lines approach 0 as time goes on. The graph for SA=1 gradually goes down to 0, without ever rising. The graph for SA=1.001 rises a few times and then falls down further towards zero. This is a visualization of the algorithm escaping the local minima. In the download section, you will find two Excel files in the zip file with more data showing the effect of the various SA values.

After examining these graphs I realized that if there is a completely different global minima, I'm not seeing any evidence for it. It appears to me that indeed the Fixed Vowel Row layout with score of 135242359724 is the most optimal layout I could come up with. I feel comfortable in saying that I have found Optimus.

Optimus is only useful if it is significantly better than the existing keyboard layouts. In designing Optimus, I made two types of changes:

• Change the grid size to 7×4
• Re-arrange the keys for optimal usage

As I mentioned above, the closer a grid is to a square, the lower the score will be. Consequently, a random 7×4 keyboard should have a lower score than a random 10×3 or 9×3 keyboard layout. In an example above I showed that re-arranging keys without changing grid size can significantly lower scores too.

To make direct comparisons with QWERTY/DVORAK possible, I also designed a 10×3 Random Grid keyboard:

Score: 234828339277 - QWERTY

  Q W E R T Y U I O P
  A S D F G H J K L _
  _ Z X C V B N M _ _

Score: 285170559534 - DVORAK

  _ _ P Y F G C R L _
  A O E U I D H T N S
  _ Q J K X B M W V Z

Score: 228186373801 - ABCDEF

  A B C D E F G H I _
  J K L M N O P Q R _
  _ S T U V W X Y Z _

Score: 142812598543 - Random Grid 10x3

  X V W H E R M B J _
  Z C D A T O U Y P _
  _ K G N I S L F Q _

Score: 130575410797 - Random Grid 7x4

  _ J Y M L D Z
  Q B U O A N G
  X P R E T I C
  _ V F S H W K

Score: 135242359724 - Fixed Vowel Row - Optimus

  V D R N G F Q
  _ A E I O U _
  K H T S L B J
  X C W M Y P Z

The Random Grid 10×3 layout is 40% better than QWERTY and 50% better than DVORAK. Surprisingly, the simple ABCDEF is better than both QWERTY and DVORAK when it comes to typing regular English words with one-finger but it is still no match for Random Grid 10×3. The absolute best layout is indeed Random Grid 7×4 but it is only marginally better than the best Fixed Vowel Row layout - Optimus.

I will be using this Optimus layout in the KType iPad application. The Optimus Keyboard Layout and all the other layouts I designed as part of KType are released under Creative Commons Attribution 3.0 Unported license. You are free to use these layouts in your products and projects freely. Feel free to contact me if you wish to discuss customizing these layouts to better suit your application.

Download: ktype-design-optimus.zip (480 kb).

The file contains the following letter-pair frequency table, Python source code to generate the keyboard layouts using various algorithms, resulting keyboard layouts, and analysis of simulated annealing effects.