Fast Sudoku Solver in Haskell #1: A Simple Solution

Sudoku is a number placement puzzle. It consists of a 9x9 grid which is to be filled with digits from 1 to 9. Some of the cells of the grid come pre-filled and the player has to fill the rest.

Haskell is a purely functional programming language. It is a good choice to solve Sudoku given the problem’s combinatorial nature. The aim of this series of posts is to write a fast Sudoku solver in Haskell. We’ll focus on both implementing the solution and making it efficient, step-by-step, starting with a slow but simple solution in this post¹.

This is the first post in a series of posts:

Discuss this post on r/haskell.

Constraint Satisfaction Problem

Solving Sudoku is a constraint satisfaction problem. We are given a partially filled grid which we have to fill completely such that each of the following constraints are satisfied:

Each of the nine rows must have all the digits, from 1 to 9.
Each of the nine columns must have all the digits, from 1 to 9.
Each of the nine 3x3 sub-grids must have all the digits, from 1 to 9.

+-------+-------+-------+
| . . . | . . . | . 1 . |
| 4 . . | . . . | . . . |
| . 2 . | . . . | . . . |
+-------+-------+-------+
| . . . | . 5 . | 4 . 7 |
| . . 8 | . . . | 3 . . |
| . . 1 | . 9 . | . . . |
+-------+-------+-------+
| 3 . . | 4 . . | 2 . . |
| . 5 . | 1 . . | . . . |
| . . . | 8 . 6 | . . . |
+-------+-------+-------+
    A sample puzzle

+-------+-------+-------+
| 6 9 3 | 7 8 4 | 5 1 2 |
| 4 8 7 | 5 1 2 | 9 3 6 |
| 1 2 5 | 9 6 3 | 8 7 4 |
+-------+-------+-------+
| 9 3 2 | 6 5 1 | 4 8 7 |
| 5 6 8 | 2 4 7 | 3 9 1 |
| 7 4 1 | 3 9 8 | 6 2 5 |
+-------+-------+-------+
| 3 1 9 | 4 7 5 | 2 6 8 |
| 8 5 6 | 1 2 9 | 7 4 3 |
| 2 7 4 | 8 3 6 | 1 5 9 |
+-------+-------+-------+
    and its solution

Each cell in the grid is member of one row, one column and one sub-grid (called block in general). Digits in the pre-filled cells impose constraints on the rows, columns, and sub-grids they are part of. For example, if a cell contains 1 then no other cell in that cell’s row, column or sub-grid can contain 1. Given these constraints, we can devise a simple algorithm to solve Sudoku:

Each cell contains either a single digit or has a set of possible digits. For example, a grid showing the possibilities of all non-filled cells for the sample puzzle above:

+-------------------------------------+-------------------------------------+-------------------------------------+
| [123456789] [123456789] [123456789] | [123456789] [123456789] [123456789] | [123456789] 1           [123456789] |
| 4           [123456789] [123456789] | [123456789] [123456789] [123456789] | [123456789] [123456789] [123456789] |
| [123456789] 2           [123456789] | [123456789] [123456789] [123456789] | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| [123456789] [123456789] [123456789] | [123456789] 5           [123456789] | 4           [123456789] 7           |
| [123456789] [123456789] 8           | [123456789] [123456789] [123456789] | 3           [123456789] [123456789] |
| [123456789] [123456789] 1           | [123456789] 9           [123456789] | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| 3           [123456789] [123456789] | 4           [123456789] [123456789] | 2           [123456789] [123456789] |
| [123456789] 5           [123456789] | 1           [123456789] [123456789] | [123456789] [123456789] [123456789] |
| [123456789] [123456789] [123456789] | 8           [123456789] 6           | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+

If a cell contains a digit, remove that digit from the list of the possible digits from all its neighboring cells. Neighboring cells are the other cells in the given cell’s row, column and sub-grid. For example, the grid after removing the fixed value 4 of the row-2-column-1 cell from its neighboring cells:

+-------------------------------------+-------------------------------------+-------------------------------------+
| [123 56789] [123 56789] [123 56789] | [123456789] [123456789] [123456789] | [123456789] 1           [123456789] |
| 4           [123 56789] [123 56789] | [123 56789] [123 56789] [123 56789] | [123 56789] [123 56789] [123 56789] |
| [123 56789] 2           [123 56789] | [123456789] [123456789] [123456789] | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| [123 56789] [123456789] [123456789] | [123456789] 5           [123456789] | 4           [123456789] 7           |
| [123 56789] [123456789] 8           | [123456789] [123456789] [123456789] | 3           [123456789] [123456789] |
| [123 56789] [123456789] 1           | [123456789] 9           [123456789] | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| 3           [123456789] [123456789] | 4           [123456789] [123456789] | 2           [123456789] [123456789] |
| [123 56789] 5           [123456789] | 1           [123456789] [123456789] | [123456789] [123456789] [123456789] |
| [123 56789] [123456789] [123456789] | 8           [123456789] 6           | [123456789] [123456789] [123456789] |
+-------------------------------------+-------------------------------------+-------------------------------------+

Repeat the previous step for all the cells that are have been solved (or fixed), either pre-filled or filled in the previous iteration of the solution. For example, the grid after removing all fixed values from all non-fixed cells:

+-------------------------------------+-------------------------------------+-------------------------------------+
| [    56789] [  3  6789] [  3 567 9] | [ 23 567 9] [ 234 678 ] [ 2345 789] | [    56789] 1           [ 23456 89] |
| 4           [1 3  6789] [  3 567 9] | [ 23 567 9] [123  678 ] [123 5 789] | [    56789] [ 23 56789] [ 23 56 89] |
| [1   56789] 2           [  3 567 9] | [  3 567 9] [1 34 678 ] [1 345 789] | [    56789] [  3456789] [  3456 89] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| [ 2   6  9] [  3  6  9] [ 23  6  9] | [ 23  6   ] 5           [123    8 ] | 4           [ 2   6 89] 7           |
| [ 2  567 9] [   4 67 9] 8           | [ 2   67  ] [12 4 67  ] [12 4  7  ] | 3           [ 2  56  9] [12  56  9] |
| [ 2  567  ] [  34 67  ] 1           | [ 23  67  ] 9           [ 234  78 ] | [    56 8 ] [ 2  56 8 ] [ 2  56 8 ] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| 3           [1    6789] [     67 9] | 4           7           [    5 7 9] | 2           [    56789] [1   56 89] |
| [ 2   6789] 5           [ 2 4 67 9] | 1           [ 23   7  ] [ 23   7 9] | [     6789] [  34 6789] [  34 6 89] |
| [12    7 9] [1  4  7 9] [ 2 4  7 9] | 8           [ 23   7  ] 6           | [1   5 7 9] [  345 7 9] [1 345   9] |
+-------------------------------------+-------------------------------------+-------------------------------------+

Continue till the grid settles, that is, there are no more changes in the possibilities of any cells. For example, the settled grid for the current iteration:

+-------------------------------------+-------------------------------------+-------------------------------------+
| [    56789] [  3  6789] [  3 567 9] | [ 23 567 9] [ 234 6 8 ] [ 2345 789] | [    56789] 1           [ 23456 89] |
| 4           [1 3  6789] [  3 567 9] | [ 23 567 9] [123  6 8 ] [123 5 789] | [    56789] [ 23 56789] [ 23 56 89] |
| [1   56789] 2           [  3 567 9] | [  3 567 9] [1 34 6 8 ] [1 345 789] | [    56789] [  3456789] [  3456 89] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| [ 2   6  9] [  3  6  9] [ 23  6  9] | [ 23  6   ] 5           [123    8 ] | 4           [ 2   6 89] 7           |
| [ 2  567 9] [   4 67 9] 8           | [ 2   67  ] [12 4 6   ] [12 4  7  ] | 3           [ 2  56  9] [12  56  9] |
| [ 2  567  ] [  34 67  ] 1           | [ 23  67  ] 9           [ 234  78 ] | [    56 8 ] [ 2  56 8 ] [ 2  56 8 ] |
+-------------------------------------+-------------------------------------+-------------------------------------+
| 3           [1    6 89] [     6  9] | 4           7           [    5   9] | 2           [    56 89] [1   56 89] |
| [ 2   6789] 5           [ 2 4 67 9] | 1           [ 23      ] [ 23     9] | [     6789] [  34 6789] [  34 6 89] |
| [12    7 9] [1  4  7 9] [ 2 4  7 9] | 8           [ 23      ] 6           | [1   5 7 9] [  345 7 9] [1 345   9] |
+-------------------------------------+-------------------------------------+-------------------------------------+

Once the grid settles, choose one of the non-fixed cells following some strategy. Select one of the digits from all the possibilities of the cell, and fix (assume) the cell to have that digit. Go back to step 1 and repeat.
The elimination of possibilities may result in inconsistencies. For example, you may end up with a cell with no possibilities. In such a case, discard that branch of solution, and backtrack to last point where you fixed a cell. Choose a different possibility to fix and repeat.
If at any point the grid is completely filled, you’ve found the solution!
If you exhaust all branches of the solution then the puzzle is unsolvable. This can happen if it starts with cells pre-filled wrongly.

This algorithm is actually a Depth-First Search on the state space of the grid configurations. It guarantees to either find a solution or prove a puzzle to be unsolvable.

Setting up

We start with writing types to represent the cells and the grid:

data Cell = Fixed Int | Possible [Int] deriving (Show, Eq)
type Row  = [Cell]
type Grid = [Row]

A cell is either fixed with a particular digit or has a set of digits as possibilities. So it is natural to represent it as a sum type with Fixed and Possible constructors. A row is a list of cells and a grid is a list of rows.

We’ll take the input puzzle as a string of 81 characters representing the cells, left-to-right and top-to-bottom. An example is:

.......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6...

Here, . represents an non-filled cell. Let’s write a function to read this input and parse it to our Grid data structure:

readGrid :: String -> Maybe Grid
readGrid s
  | length s == 81 = traverse (traverse readCell) . Data.List.Split.chunksOf 9 $ s
  | otherwise      = Nothing
  where
    readCell '.' = Just $ Possible [1..9]
    readCell c
      | Data.Char.isDigit c && c > '0' = Just . Fixed . Data.Char.digitToInt $ c
      | otherwise = Nothing

readGrid return a Just grid if the input is correct, else it returns a Nothing. It parses a . to a Possible cell with all digits as possibilities, and a digit char to a Fixed cell with that digit. Let’s try it out in the REPL:

*Main> Just grid = readGrid ".......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> mapM_ print grid
[Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 1,Possible [1,2,3,4,5,6,7,8,9]]
[Fixed 4,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Possible [1,2,3,4,5,6,7,8,9],Fixed 2,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 5,Possible [1,2,3,4,5,6,7,8,9],Fixed 4,Possible [1,2,3,4,5,6,7,8,9],Fixed 7]
[Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 8,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 3,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 1,Possible [1,2,3,4,5,6,7,8,9],Fixed 9,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Fixed 3,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 4,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 2,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Possible [1,2,3,4,5,6,7,8,9],Fixed 5,Possible [1,2,3,4,5,6,7,8,9],Fixed 1,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]
[Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Fixed 8,Possible [1,2,3,4,5,6,7,8,9],Fixed 6,Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9],Possible [1,2,3,4,5,6,7,8,9]]

The output is a bit unreadable but correct. We can write a few functions to clean it up:

showGrid :: Grid -> String
showGrid = unlines . map (unwords . map showCell)
  where
    showCell (Fixed x) = show x
    showCell _ = "."

showGridWithPossibilities :: Grid -> String
showGridWithPossibilities = unlines . map (unwords . map showCell)
  where
    showCell (Fixed x)     = show x ++ "          "
    showCell (Possible xs) =
      (++ "]")
      . Data.List.foldl' (\acc x -> acc ++ if x `elem` xs then show x else " ") "["
      $ [1..9]

Back to the REPL again:

*Main> Just grid = readGrid ".......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> putStrLn $ showGrid grid
. . . . . . . 1 .
4 . . . . . . . .
. 2 . . . . . . .
. . . . 5 . 4 . 7
. . 8 . . . 3 . .
. . 1 . 9 . . . .
3 . . 4 . . 2 . .
. 5 . 1 . . . . .
. . . 8 . 6 . . .

*Main> putStrLn $ showGridWithPossibilities grid
[123456789] [123456789] [123456789] [123456789] [123456789] [123456789] [123456789] 1           [123456789]
4           [123456789] [123456789] [123456789] [123456789] [123456789] [123456789] [123456789] [123456789]
[123456789] 2           [123456789] [123456789] [123456789] [123456789] [123456789] [123456789] [123456789]
[123456789] [123456789] [123456789] [123456789] 5           [123456789] 4           [123456789] 7
[123456789] [123456789] 8           [123456789] [123456789] [123456789] 3           [123456789] [123456789]
[123456789] [123456789] 1           [123456789] 9           [123456789] [123456789] [123456789] [123456789]
3           [123456789] [123456789] 4           [123456789] [123456789] 2           [123456789] [123456789]
[123456789] 5           [123456789] 1           [123456789] [123456789] [123456789] [123456789] [123456789]
[123456789] [123456789] [123456789] 8           [123456789] 6           [123456789] [123456789] [123456789]

The output is more readable now. We see that, at the start, all the non-filled cells have all the digits as possible values. We’ll use these functions for debugging as we go forward. We can now start solving the puzzle.

Pruning the Cells

We can remove the digits of fixed cells from their neighboring cells, one cell as a time. But, it is faster to find all the fixed digits in a row of cells and remove them from the possibilities of all the non-fixed cells of the row, at once. Then we can repeat this pruning step for all the rows of the grid (and columns and sub-grids too! We’ll see how).

pruneCells :: [Cell] -> Maybe [Cell]
pruneCells cells = traverse pruneCell cells
  where
    fixeds = [x | Fixed x <- cells]

    pruneCell (Possible xs) = case xs Data.List.\\ fixeds of
      []  -> Nothing
      [y] -> Just $ Fixed y
      ys  -> Just $ Possible ys
    pruneCell x = Just x

pruneCells prunes a list of cells as described before. We start with finding the fixed digits in the list of cells. Then we go over each non-fixed cells, removing the fixed digits we found, from their possible values. Two special cases arise:

If pruning results in a cell with no possible digits, it is a sign that this branch of search has no solution and hence, we return a Nothing in that case.
If only one possible digit remains after pruning, then we turn that cell into a fixed cell with that digit.

We use the traverse function for pruning the cells so that a Nothing resulting from pruning one cell propagates to the entire list.

Let’s take it for a spin in the REPL:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> putStr $ showGridWithPossibilities $ [head grid] -- first row of the grid
6           [123456789] [123456789] [123456789] [123456789] [123456789] [123456789] 1           [123456789]
*Main> putStr $ showGridWithPossibilities [fromJust $ pruneCells $ head grid] -- same row after pruning
6           [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] 1           [ 2345 789]

It works! 6 and 1 are removed from the possibilities of the other cells. Now we are ready for …

Pruning the Grid

Pruning a grid requires us to prune each row, each column and each sub-grid. Let’s try to solve it in the REPL first:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = traverse pruneCells grid
*Main> putStr $ showGridWithPossibilities grid'
6           [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] [ 2345 789] 1           [ 2345 789]
4           [123 56789] [123 56789] [123 56789] [123 56789] [123 56789] [123 56789] [123 56789] [123 56789]
[1 3456789] 2           [1 3456789] [1 3456789] [1 3456789] [1 3456789] [1 3456789] [1 3456789] [1 3456789]
[123  6 89] [123  6 89] [123  6 89] [123  6 89] 5           [123  6 89] 4           [123  6 89] 7
[12 4567 9] [12 4567 9] 8           [12 4567 9] [12 4567 9] [12 4567 9] 3           [12 4567 9] [12 4567 9]
[ 2345678 ] [ 2345678 ] 1           [ 2345678 ] 9           [ 2345678 ] [ 2345678 ] [ 2345678 ] [ 2345678 ]
3           [1   56789] [1   56789] 4           [1   56789] [1   56789] 2           [1   56789] [1   56789]
[ 234 6789] 5           [ 234 6789] 1           [ 234 6789] [ 234 6789] [ 234 6789] [ 234 6789] [ 234 6789]
[12345 7 9] [12345 7 9] [12345 7 9] 8           [12345 7 9] 6           [12345 7 9] [12345 7 9] [12345 7 9]

By traverse-ing the grid with pruneCells, we are able to prune each row, one-by-one. Since pruning a row doesn’t affect another row, we don’t have to pass the resulting rows between each pruning step. That is to say, traverse is enough for us, we don’t need foldl here.

How do we do the same thing for columns now? Since our representation for the grid is rows-first, we first need to convert it to a columns-first representation. Luckily, that’s what Data.List.transpose function does:

*Main> Just grid = readGrid "693784512487512936125963874932651487568247391741398625319475268856129743274836159"
*Main> putStr $ showGrid grid
6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9
*Main> putStr $ showGrid $ Data.List.transpose grid
6 4 1 9 5 7 3 8 2
9 8 2 3 6 4 1 5 7
3 7 5 2 8 1 9 6 4
7 5 9 6 2 3 4 1 8
8 1 6 5 4 9 7 2 3
4 2 3 1 7 8 5 9 6
5 9 8 4 3 6 2 7 1
1 3 7 8 9 2 6 4 5
2 6 4 7 1 5 8 3 9

Pruning columns is easy now:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = fmap Data.List.transpose . traverse pruneCells . Data.List.transpose $ grid
*Main> putStr $ showGridWithPossibilities grid'
6           [1 34 6789] [ 234567 9] [ 23 567 9] [1234 678 ] [12345 789] [1   56789] 1           [123456 89]
4           [1 34 6789] [ 234567 9] [ 23 567 9] [1234 678 ] [12345 789] [1   56789] [ 23456789] [123456 89]
[12  5 789] 2           [ 234567 9] [ 23 567 9] [1234 678 ] [12345 789] [1   56789] [ 23456789] [123456 89]
[12  5 789] [1 34 6789] [ 234567 9] [ 23 567 9] 5           [12345 789] 4           [ 23456789] 7
[12  5 789] [1 34 6789] 8           [ 23 567 9] [1234 678 ] [12345 789] 3           [ 23456789] [123456 89]
[12  5 789] [1 34 6789] 1           [ 23 567 9] 9           [12345 789] [1   56789] [ 23456789] [123456 89]
3           [1 34 6789] [ 234567 9] 4           [1234 678 ] [12345 789] 2           [ 23456789] [123456 89]
[12  5 789] 5           [ 234567 9] 1           [1234 678 ] [12345 789] [1   56789] [ 23456789] [123456 89]
[12  5 789] [1 34 6789] [ 234567 9] 8           [1234 678 ] 6           [1   56789] [ 23456789] [123456 89]

First, we transpose the grid to convert the columns into rows. Then, we prune the rows by traverse-ing pruneCells over them. And finally, we turn the rows back into columns by transpose-ing the grid back again. The last transpose needs to be fmap-ped because traverse pruneCells returns a Maybe.

Pruning sub-grids is a bit trickier. Following the same idea as pruning columns, we need two functions to transform the sub-grids into rows and back. Let’s write the first one:

subGridsToRows :: Grid -> Grid
subGridsToRows =
  concatMap (\rows -> let [r1, r2, r3] = map (Data.List.Split.chunksOf 3) rows
                      in zipWith3 (\a b c -> a ++ b ++ c) r1 r2 r3)
  . Data.List.Split.chunksOf 3

And try it out:

*Main> Just grid = readGrid "693784512487512936125963874932651487568247391741398625319475268856129743274836159"
*Main> putStr $ showGrid grid
6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9
*Main> putStr $ showGrid $ subGridsToRows grid
6 9 3 4 8 7 1 2 5
7 8 4 5 1 2 9 6 3
5 1 2 9 3 6 8 7 4
9 3 2 5 6 8 7 4 1
6 5 1 2 4 7 3 9 8
4 8 7 3 9 1 6 2 5
3 1 9 8 5 6 2 7 4
4 7 5 1 2 9 8 3 6
2 6 8 7 4 3 1 5 9

You can go over the code and the output and make yourself sure that it works. Also, it turns out that we don’t need to write the back-transform function. subGridsToRows is its own back-transform:

*Main> putStr $ showGrid grid
6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9
*Main> putStr $ showGrid $ subGridsToRows $ subGridsToRows $ grid
6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9

Nice! Now writing the sub-grid pruning function is easy:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = fmap subGridsToRows . traverse pruneCells . subGridsToRows $ grid
*Main> putStr $ showGridWithPossibilities grid'
6           [1 3 5 789] [1 3 5 789] [123456789] [123456789] [123456789] [ 23456789] 1           [ 23456789]
4           [1 3 5 789] [1 3 5 789] [123456789] [123456789] [123456789] [ 23456789] [ 23456789] [ 23456789]
[1 3 5 789] 2           [1 3 5 789] [123456789] [123456789] [123456789] [ 23456789] [ 23456789] [ 23456789]
[ 234567 9] [ 234567 9] [ 234567 9] [1234 678 ] 5           [1234 678 ] 4           [12  56 89] 7
[ 234567 9] [ 234567 9] 8           [1234 678 ] [1234 678 ] [1234 678 ] 3           [12  56 89] [12  56 89]
[ 234567 9] [ 234567 9] 1           [1234 678 ] 9           [1234 678 ] [12  56 89] [12  56 89] [12  56 89]
3           [12 4 6789] [12 4 6789] 4           [ 23 5 7 9] [ 23 5 7 9] 2           [1 3456789] [1 3456789]
[12 4 6789] 5           [12 4 6789] 1           [ 23 5 7 9] [ 23 5 7 9] [1 3456789] [1 3456789] [1 3456789]
[12 4 6789] [12 4 6789] [12 4 6789] 8           [ 23 5 7 9] 6           [1 3456789] [1 3456789] [1 3456789]

It works well. Now we can string together these three steps to prune the entire grid. We also have to make sure that result of pruning each step is fed into the next step. This is so that the fixed cells created into one step cause more pruning in the further steps. We use monadic bind (>>=) for that. Here’s the final code:

pruneGrid' :: Grid -> Maybe Grid
pruneGrid' grid =
  traverse pruneCells grid
  >>= fmap Data.List.transpose . traverse pruneCells . Data.List.transpose
  >>= fmap subGridsToRows . traverse pruneCells . subGridsToRows

And the test:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = pruneGrid' grid
*Main> putStr $ showGridWithPossibilities grid'
6           [  3   789] [  3 5 7 9] [ 23 5 7 9] [ 234  78 ] [ 2345 789] [    5 789] 1           [ 2345  89]
4           [1 3   789] [  3 5 7 9] [ 23 567 9] [123  678 ] [123 5 789] [    56789] [ 23 56789] [ 23 56 89]
[1   5 789] 2           [  3 5 7 9] [  3 567 9] [1 34 678 ] [1 345 789] [    56789] [  3456789] [  3456 89]
[ 2      9] [  3  6  9] [ 23  6  9] [ 23  6   ] 5           [123    8 ] 4           [ 2   6 89] 7
[ 2  5 7 9] [   4 67 9] 8           [ 2   67  ] [12 4 67  ] [12 4  7  ] 3           [ 2  56  9] [12  56  9]
[ 2  5 7  ] [  34 67  ] 1           [ 23  67  ] 9           [ 234  78 ] [    56 8 ] [ 2  56 8 ] [ 2  56 8 ]
3           [1    6789] [     67 9] 4           7           [    5 7 9] 2           [    56789] [1   56 89]
[ 2    789] 5           [ 2 4 67 9] 1           [ 23   7  ] [ 23   7 9] [     6789] [  34 6789] [  34 6 89]
[12    7 9] [1  4  7 9] [ 2 4  7 9] 8           [ 23   7  ] 6           [1   5 7 9] [  345 7 9] [1 345   9]
*Main> putStr $ showGrid grid
6 . . . . . . 1 .
4 . . . . . . . .
. 2 . . . . . . .
. . . . 5 . 4 . 7
. . 8 . . . 3 . .
. . 1 . 9 . . . .
3 . . 4 . . 2 . .
. 5 . 1 . . . . .
. . . 8 . 6 . . .
*Main> putStr $ showGrid grid'
6 . . . . . . 1 .
4 . . . . . . . .
. 2 . . . . . . .
. . . . 5 . 4 . 7
. . 8 . . . 3 . .
. . 1 . 9 . . . .
3 . . 4 7 . 2 . .
. 5 . 1 . . . . .
. . . 8 . 6 . . .

We can clearly see the massive pruning of possibilities all around the grid. We also see a 7 pop up in the row-7-column-5 cell. This means that we can prune the grid further, until it settles. If you are familiar with Haskell, you may recognize this as trying to find a fixed point for the pruneGrid' function, except in a monadic context. It is simple to implement:

pruneGrid :: Grid -> Maybe Grid
pruneGrid = fixM pruneGrid'
  where
    fixM f x = f x >>= \x' -> if x' == x then return x else fixM f x'

The crux of this code is the fixM function. It takes a monadic function f and an initial value, and recursively calls itself till the return value settles. Let’s do another round in the REPL:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = pruneGrid grid
*Main> putStr $ showGridWithPossibilities grid'
6           [  3   789] [  3 5 7 9] [ 23 5 7 9] [ 234   8 ] [ 2345 789] [    5 789] 1           [ 2345  89]
4           [1 3   789] [  3 5 7 9] [ 23 567 9] [123  6 8 ] [123 5 789] [    56789] [ 23 56789] [ 23 56 89]
[1   5 789] 2           [  3 5 7 9] [  3 567 9] [1 34 6 8 ] [1 345 789] [    56789] [  3456789] [  3456 89]
[ 2      9] [  3  6  9] [ 23  6  9] [ 23  6   ] 5           [123    8 ] 4           [ 2   6 89] 7
[ 2  5 7 9] [   4 67 9] 8           [ 2   67  ] [12 4 6   ] [12 4  7  ] 3           [ 2  56  9] [12  56  9]
[ 2  5 7  ] [  34 67  ] 1           [ 23  67  ] 9           [ 234  78 ] [    56 8 ] [ 2  56 8 ] [ 2  56 8 ]
3           [1    6 89] [     6  9] 4           7           [    5   9] 2           [    56 89] [1   56 89]
[ 2    789] 5           [ 2 4 67 9] 1           [ 23      ] [ 23     9] [     6789] [  34 6789] [  34 6 89]
[12    7 9] [1  4  7 9] [ 2 4  7 9] 8           [ 23      ] 6           [1   5 7 9] [  345 7 9] [1 345   9]

We see that 7 in the row-7-column-5 cell is eliminated from all its neighboring cells. We can’t prune the grid anymore. Now it is time to make the choice.

Making the Choice

One the grid is settled, we need to choose a non-fixed cell and make it fixed by assuming one of its possible values. This gives us two grids, next in the state-space of the solution search:

one which has this chosen cell fixed to this chosen digit, and,
the other in which the chosen cell has all the other possibilities except the one we chose to fix.

We call this function, nextGrids:

nextGrids :: Grid -> (Grid, Grid)
nextGrids grid =
  let (i, first@(Fixed _), rest) =
        fixCell
        . Data.List.minimumBy (compare `Data.Function.on` (possibilityCount . snd))
        . filter (isPossible . snd)
        . zip [0..]
        . concat
        $ grid
  in (replace2D i first grid, replace2D i rest grid)
  where
    isPossible (Possible _) = True
    isPossible _            = False

    possibilityCount (Possible xs) = length xs
    possibilityCount (Fixed _)     = 1

    fixCell (i, Possible [x, y]) = (i, Fixed x, Fixed y)
    fixCell (i, Possible (x:xs)) = (i, Fixed x, Possible xs)
    fixCell _                    = error "Impossible case"

    replace2D :: Int -> a -> [[a]] -> [[a]]
    replace2D i v =
      let (x, y) = (i `quot` 9, i `mod` 9) in replace x (replace y (const v))
    replace p f xs = [if i == p then f x else x | (x, i) <- zip xs [0..]]

We choose the non-fixed cell with least count of possibilities as the pivot. This strategy make sense intuitively, as with a cell with fewest possibilities, we have the most chance of being right when assuming one. Fixing a non-fixed cell leads to one of the two cases:

the cell has only two possible values, resulting in two fixed cells, or,
the cell has more than two possible values, resulting in one fixed and one non-fixed cell.

Then all we are left with is replacing the non-fixed cell with its fixed and fixed/non-fixed choices, which we do with some math and some list traversal. A quick check on the REPL:

*Main> Just grid = readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> Just grid' = pruneGrid grid
*Main> putStr $ showGridWithPossibilities grid'
6           [  3   789] [  3 5 7 9] [ 23 5 7 9] [ 234   8 ] [ 2345 789] [    5 789] 1           [ 2345  89]
4           [1 3   789] [  3 5 7 9] [ 23 567 9] [123  6 8 ] [123 5 789] [    56789] [ 23 56789] [ 23 56 89]
[1   5 789] 2           [  3 5 7 9] [  3 567 9] [1 34 6 8 ] [1 345 789] [    56789] [  3456789] [  3456 89]
[ 2      9] [  3  6  9] [ 23  6  9] [ 23  6   ] 5           [123    8 ] 4           [ 2   6 89] 7
[ 2  5 7 9] [   4 67 9] 8           [ 2   67  ] [12 4 6   ] [12 4  7  ] 3           [ 2  56  9] [12  56  9]
[ 2  5 7  ] [  34 67  ] 1           [ 23  67  ] 9           [ 234  78 ] [    56 8 ] [ 2  56 8 ] [ 2  56 8 ]
3           [1    6 89] [     6  9] 4           7           [    5   9] 2           [    56 89] [1   56 89]
[ 2    789] 5           [ 2 4 67 9] 1           [ 23      ] [ 23     9] [     6789] [  34 6789] [  34 6 89]
[12    7 9] [1  4  7 9] [ 2 4  7 9] 8           [ 23      ] 6           [1   5 7 9] [  345 7 9] [1 345   9]
*Main> -- the row-4-column-1 cell is the first cell with only two possibilities, [2, 9].
*Main> -- it is chosen as the pivot cell to find the next grids.
*Main> (grid1, grid2) = nextGrids grid'
*Main> putStr $ showGridWithPossibilities grid1
6           [  3   789] [  3 5 7 9] [ 23 5 7 9] [ 234   8 ] [ 2345 789] [    5 789] 1           [ 2345  89]
4           [1 3   789] [  3 5 7 9] [ 23 567 9] [123  6 8 ] [123 5 789] [    56789] [ 23 56789] [ 23 56 89]
[1   5 789] 2           [  3 5 7 9] [  3 567 9] [1 34 6 8 ] [1 345 789] [    56789] [  3456789] [  3456 89]
2           [  3  6  9] [ 23  6  9] [ 23  6   ] 5           [123    8 ] 4           [ 2   6 89] 7
[ 2  5 7 9] [   4 67 9] 8           [ 2   67  ] [12 4 6   ] [12 4  7  ] 3           [ 2  56  9] [12  56  9]
[ 2  5 7  ] [  34 67  ] 1           [ 23  67  ] 9           [ 234  78 ] [    56 8 ] [ 2  56 8 ] [ 2  56 8 ]
3           [1    6 89] [     6  9] 4           7           [    5   9] 2           [    56 89] [1   56 89]
[ 2    789] 5           [ 2 4 67 9] 1           [ 23      ] [ 23     9] [     6789] [  34 6789] [  34 6 89]
[12    7 9] [1  4  7 9] [ 2 4  7 9] 8           [ 23      ] 6           [1   5 7 9] [  345 7 9] [1 345   9]
*Main> putStr $ showGridWithPossibilities grid2
6           [  3   789] [  3 5 7 9] [ 23 5 7 9] [ 234   8 ] [ 2345 789] [    5 789] 1           [ 2345  89]
4           [1 3   789] [  3 5 7 9] [ 23 567 9] [123  6 8 ] [123 5 789] [    56789] [ 23 56789] [ 23 56 89]
[1   5 789] 2           [  3 5 7 9] [  3 567 9] [1 34 6 8 ] [1 345 789] [    56789] [  3456789] [  3456 89]
9           [  3  6  9] [ 23  6  9] [ 23  6   ] 5           [123    8 ] 4           [ 2   6 89] 7
[ 2  5 7 9] [   4 67 9] 8           [ 2   67  ] [12 4 6   ] [12 4  7  ] 3           [ 2  56  9] [12  56  9]
[ 2  5 7  ] [  34 67  ] 1           [ 23  67  ] 9           [ 234  78 ] [    56 8 ] [ 2  56 8 ] [ 2  56 8 ]
3           [1    6 89] [     6  9] 4           7           [    5   9] 2           [    56 89] [1   56 89]
[ 2    789] 5           [ 2 4 67 9] 1           [ 23      ] [ 23     9] [     6789] [  34 6789] [  34 6 89]
[12    7 9] [1  4  7 9] [ 2 4  7 9] 8           [ 23      ] 6           [1   5 7 9] [  345 7 9] [1 345   9]

Solving the Puzzle

We have implemented parts of our algorithm till now. Now we’ll put everything together to solve the puzzle. First, we need to know if we are done or have messed up:

isGridFilled :: Grid -> Bool
isGridFilled grid = null [ () | Possible _ <- concat grid ]

isGridInvalid :: Grid -> Bool
isGridInvalid grid =
  any isInvalidRow grid
  || any isInvalidRow (Data.List.transpose grid)
  || any isInvalidRow (subGridsToRows grid)
  where
    isInvalidRow row =
      let fixeds         = [x | Fixed x <- row]
          emptyPossibles = [x | Possible x <- row, null x]
      in hasDups fixeds || not (null emptyPossibles)

    hasDups l = hasDups' l []

    hasDups' [] _ = False
    hasDups' (y:ys) xs
      | y `elem` xs = True
      | otherwise   = hasDups' ys (y:xs)

isGridFilled returns whether a grid is filled completely by checking it for any Possible cells. isGridInvalid checks if a grid is invalid because it either has duplicate fixed cells in any block or has any non-fixed cell with no possibilities.

Writing the solve function is almost trivial now:

solve :: Grid -> Maybe Grid
solve grid = pruneGrid grid >>= solve'
  where
    solve' g
      | isGridInvalid g = Nothing
      | isGridFilled g  = Just g
      | otherwise       =
          let (grid1, grid2) = nextGrids g
          in solve grid1 <|> solve grid2

We prune the grid as before and pipe it to the helper function solve'. solve' bails with a Nothing if the grid is invalid, or returns the solved grid if it is filled completely. Otherwise, it finds the next two grids in the search tree and solves them recursively with backtracking by calling the solve function. Backtracking here is implemented by the using the Alternative (<|>) implementation of the Maybe type². It takes the second branch in the computation if the first branch returns a Nothing.

Whew! That took us long. Let’s put it to the final test now:

*Main> Just grid =
  readGrid "6......1.4.........2...........5.4.7..8...3....1.9....3..4..2...5.1........8.6..."
*Main> putStr $ showGrid grid
6 . . . . . . 1 .
4 . . . . . . . .
. 2 . . . . . . .
. . . . 5 . 4 . 7
. . 8 . . . 3 . .
. . 1 . 9 . . . .
3 . . 4 . . 2 . .
. 5 . 1 . . . . .
. . . 8 . 6 . . .
*Main> Just grid' = solve grid
*Main> putStr $ showGrid grid'
6 9 3 7 8 4 5 1 2
4 8 7 5 1 2 9 3 6
1 2 5 9 6 3 8 7 4
9 3 2 6 5 1 4 8 7
5 6 8 2 4 7 3 9 1
7 4 1 3 9 8 6 2 5
3 1 9 4 7 5 2 6 8
8 5 6 1 2 9 7 4 3
2 7 4 8 3 6 1 5 9

It works! Let’s put a quick main wrapper around solve to call it from the command line:

main :: IO ()
main = do
  inputs <- lines <$> getContents
  Control.Monad.forM_ inputs $ \input ->
    case readGrid input of
      Nothing   -> putStrLn "Invalid input"
      Just grid -> case solve grid of
        Nothing    -> putStrLn "No solution found"
        Just grid' -> putStrLn $ showGrid grid'

And now, we can invoke it from the command line:

$ echo ".......12.5.4............3.7..6..4....1..........8....92....8.....51.7.......3..." | stack exec sudoku
3 6 4 9 7 8 5 1 2
1 5 2 4 3 6 9 7 8
8 7 9 1 2 5 6 3 4
7 3 8 6 5 1 4 2 9
6 9 1 2 4 7 3 8 5
2 4 5 3 8 9 1 6 7
9 2 3 7 6 4 8 5 1
4 8 6 5 1 2 7 9 3
5 1 7 8 9 3 2 4 6

And, we are done.

If you want to play with different puzzles, the file here lists some of the toughest ones. Let’s run³ some of them through our program to see how fast it is:

$ head -n100 sudoku17.txt | time stack exec sudoku
... output omitted ...
      116.70 real       198.09 user        94.46 sys

It took about 117 seconds to solve a hundred puzzles, so, about 1.2 seconds per puzzle. This is pretty slow but we’ll get around to making it faster in the subsequent posts.

Conclusion

In this rather verbose article, we learned how to write a simple Sudoku solver in Haskell step-by-step. In the later parts of this series, we’ll delve into profiling the solution and figuring out better algorithms and data structures to solve Sudoku more efficiently. The code till now is available here. Discuss this post on r/haskell or leave a comment.

This exercise was originally done as a part of the Haskell classes I taught at nilenso.↩︎

Alternative implementation of Maybe:

instance Alternative Maybe where
  empty = Nothing
  Nothing <|> r = r
  l       <|> _ = l

↩︎

All the runs were done on my MacBook Pro from 2014 with 2.2 GHz Intel Core i7 CPU and 16 GB memory.↩︎

If you liked this post, please leave a comment.

Original post by Abhinav Sarkar - check out All posts on abhinavsarkar.net

Finances in an Employee-Owned Technology Co-operative

If you are not already familiar with nilenso, I apologize. This article may not make any sense to you. Requested as an opinion piece in reply to an internal email on salaries, it hinges on a lot of context.

You may find that context interesting.

YourStory: India’s first software co-operative
Huh? A Software Cooperative? — an introduction
How to Co-op: Salaries and Reviews
“I have cramps.” — introducing our menstrual leave policy
nilenso policies — democratic corporate benefits
nilenso reviews — how do we evaluate one another?
blog archive — the rest of the articles we’ve written

The email which spawned this discussion was from a new employee, suggesting that we raise salaries. We discuss such organizational and infrastructural changes on occasion (not often) and an open conversation is welcome.

However, as I’m leaving nilenso in July, it felt worthwhile to capture what would otherwise be a one-time, long-winded email to nilenso’s existing staff and transform that into an article which could capture one founding member’s opinion of what nilenso is, for all future staff — and other fans of Employee-owned Co-operatives—who would care to read it.

On Salaries

The original email had a fairly simple 3-part structure.

First: How much can we pay? …without compromising on organizational goals like maintaining a rainy-day cash buffer and financing experimental new ventures?

Second, a declaration of our rates & salaries. Highlighted is the delta between the two. Our rates vary a lot from project to project, but for the sake of example, imagine our rates average to $100/hour. (100 is a nice round number.) At $100/hour, our rates were high for Indian software consultancies, but not astronomical. A napkin calculation roughs $100/hour to over $100,000/year in revenue. Historically, very senior people at nilenso made about half this revenue figure as salary.

[F]or people with more experience and established reputation, there is an incentive to break away and start their own business so that they can pocket the difference.

(All quotes are from the aforementioned email.)

Third and last, a spectrum of starting salaries. These were listed for college grads of reputable Indian universities, such as NIT and IIT. Paymasters near the top included Uber and Goldman Sachs. Near the bottom were Samsung and American Express.

Some of the people I know from college are very good programmers and I’ll have a very hard [time] convincing them to join Nilenso [sic], because the difference between our salaries and the industry “standard” is too large.

….

[M]ost of our clients can pay pretty high salaries. From their perspective it isn’t an unreasonable strategy to hire a bunch of folks from nilenso instead of negotiating our high rates

It is possible this argument doesn’t seem irrational in isolation, so let’s break it down part by part. From hereon out, please automatically prefix any declaration I make with “as of this writing.”

Part 3: A unicorn pissing contest

Let’s start from the end, since—tellingly—the actionable question was actually posed first.

There are a number of reasons our clients have not frequently hired our staff away. First, and most strictly, some contracts we sign have a two-way no-hire clause. In these cases, our clients cannot hire our employees and we cannot hire theirs. However, just because the contract does not forbid poaching does not make it a good idea. Our preferred engagement model is a long-term, cooperative and collaborative relationship; if either side starts yanking the other entity’s employees, that’s a great way to either poison the engagement.

In addition to all of this, however, there is sustainability at stake. As global consultancies go, nilenso is very small and very good. The author of the email is our 20th co-op member. Unless a client is very comfortable burning bridges, hiring two of our staff today trims our numbers by a non-trivial 10%. We don’t work with cannibal business owners.

That isn’t to say no one has ever left nilenso this way. If it happens, we simply hope that person takes their decision very seriously. Some of our alumni left to join past clients — and we wished them well.

People do not work at nilenso to get rich.

People work here because they believe in something. As we’ll see, “something” isn’t defined by some manifesto or mission statement. The “something” isn’t likely to be found elsewhere and it’s even less likely to be the same for two different people at nilenso. “Something” probably isn’t a single thing within the mind of a single person. “Something” is fractured and ever-changing. Each fractured shard is at any given time either a hallucination manifesting in action or a miscalculation fading to black.

As complex as The Somethings are, there has thus far been a few consistent threads. One? Technical excellence. A potential client from Vietnam recently asked “what is the ratio of fresh grads you hire to senior developers?” Though it may not appear so on the surface, the idea that “I’ll have a very hard [time] convincing [people I know from college] to join” stems from the very same misconception.

nilenso is not a leveraged consultancy.

The misconception is that nilenso desires to behave as other consultancies by “leveraging”** their weakest employees (read: fresh grads) and charging the highest possible rate by inflating them with as few “senior”** developers as possible. The misconception is not unfounded. Most consultancies operate this way. We do not.

** industry terminology, not mine

Convincing college grads to apply to nilenso is not a problem we’d like to solve. We have college grads begging us for internships and offering to work for free.

We do not want to hire college grads.

When our clients hire nilenso, we don’t want them satisfied. We want them elated. With one or two exceptions, our most junior developers always have multiple years of experience. They joined us because they couldn’t find their Something anywhere else in the industry. Not only has a college grad not, by definition, owned her own software in production — she hasn’t had an opportunity to go look for Something yet. Go searching first—and learn to build and deploy software while you’re at it. Maybe she’ll find her Something. If she doesn’t, she can join a company like ours.

We are not Uber or Goldman Sachs. We don’t treat our female colleagues like shit, we don’t have an “asshole culture”, we haven’t received a failing grade from the Better Business Bureau, nor do we have a list of “controversies and legal issues” as long as your arm.

Some of us have worked for companies like these and we have done everything in our power to prevent nilenso from becoming such a company. We don’t need revenue in the billions to behave this way but racing to compete salaries with such companies does us zero favours in that arena.

There is perhaps no better way for a college kid to learn the value of a company like nilenso than to experience a cesspool like Uber firsthand for a couple years. Not that I recommend the grads start their search there, mind you.

Part 2: Where is all this magical money coming from?

In “Part 3”, when I say that nilenso is “very small and very good” I mean that from the bottom of my heart. We are very good. We don’t fantasize about our clients paying us $100/hour — our current clients pay us this because we are worth it. Our first month with every new client is always evaluatory (we even did a 3-month evaluation period once). This is an opportunity for our clients to fire us if they find us too expensive and for us to fire them if we find the relationship isn’t productive.

Why are our developers worth well over $10,000 USD per month?

There is a watermark here. One can calculate the watermark in a number of ways. The first and most obvious is: How many people at nilenso have ever been paid $120,000/year or higher in any country? Two. So that probably puts the watermark too high. How many people at nilenso could be paid $120,000/year (roughly 77 lakh rupees) today — specifically in Bangalore? Three.

These numbers are clearly too low. The entire value of our company does not hinge on two or three people. But these are the only objective numbers we have on this axis. If we wanted to reach for a subjective number, we could say the watermark exists beneath anyone to whom our rates can be actively attributed. I would say these people number seven.

Seven of twenty active knowledge workers does not mean we “leverage” (ugh, that word) the other thirteen. Other folks are very close or arguably cross this watermark. But every team has a natural pecking order (a hierarchy drawn in a straight line, whether you draw it with a pen or with your mind) and wherever we assume this watermark to be, our value to our customers is more than the sum of the parts.

The flaw in the “wow, we make so much money!” argument is that no matter where you place this watermark, you must actively acknowledge from where this value is generated: above the watermark. If there is an argument to be made for altering the salary curve to reflect this, that alteration always implies an inflection point at the watermark. People above the watermark should be paid more. People below the watermark should be paid less. Your financial goals as an employee of such a company are dictated by your ability to cross the watermark and stay above it.

That doesn’t sound like a place I’d like to work.

I’m guessing the author of the original email feels the same way. Being our most junior staff member means starting at the very bottom of this curve and a search for the source of a consultancy’s value is always upward-facing. That’s a big hill to climb and it’s a lot more likely that crossing the watermark will involve nilenso growing from 20 to 40 rather than the most junior employee leapfrogging over 10 other people. We grow slowly on purpose — and it’s not to keep junior people at the bottom of the pay scale.

We would rather grow inside. We want our most junior staff to become more senior not by stacking themselves on top of new junior people but by perfecting their execution.

[F]or people with more experience and established reputation, there is an incentive to break away and start their own business so that they can pocket the difference.

No one at nilenso has ever done this. Why not?

Part 1: Where does all this money go?

Now we get to the juicy bits. The interesting question is not “how much can we pay?” at all. If someone wants to double her salary she can very easily do so today and nilenso is entirely unequipped to deal with that except to wish her the best with her new job.

People do not work at nilenso to get rich.

People work at nilenso to find… something. Something. What is that Something? To answer this, we must ask: What is nilenso? This is the interesting question.

Nilenso Software LLP is, today, a co-op; nilenso is self-hosted. It is written in a homoiconic language. It is self-referential. It is self-describing. The specification is the paper the specification is written on. And while none of these qualities are the Something we were all after, they are the qualities which equip us to do anything we want with the company. We are uninhibited in finding our Somethings if we never need to beg for VC money, never need to give up control, and never need to grow before we’re ready.

“Anything we want” can include bumping our salaries by 10% or 50%. It can include handing out bonuses. It can include democratically deciding we want to execute across-the-board pay cuts. But these are all pretty boring axes to manipulate the business. You don’t have to work at a co-op (and therefore run it) for very long to realize the the classic definitions of success are mind-numbingly boring… albeit always tempting.

Anything we want? Here is a far more interesting list:

helping parents raise children in the modern world
protect privacy as a fundamental right
fuel our office with solar panels
make the activity of building free software a work of pride, again
liberate the data sciences with truly open data
globally redefine what constitutes a “normal workplace”
what do you want to do? does it take money to do it? (hint: yes)

Every rupee we keep inside nilenso, invest as nilenso, or spend as nilenso pushes us further toward a collective activity, a collective vision. Every rupee we divide and distribute, 5 paise per co-op member, is a step away from a collective vision. The farthest we can go in this direction is to distribute everything: nilenso saves nothing, invests nothing, and builds nothing. Well before that stage, nilenso becomes an Umbrella Consultancy and we are nilenso in name only… another army of contractors with a brand attached and a few rupees saved every month to pay the water bill.

It is entirely valid for the collective vision of nilenso to be “we don’t want to have a collective vision” but once that is decided, there is no going back. If you want to become a software product company (as we attempted with Relay and previously attempted with Kulu), an electric rickshaw taxi service (a business model we have seriously considered), or a cafe (a business model we have jokingly considered)… you can’t. You get to go back to Square One, where we were when we incorporated nilenso in 2013. But you get to go back with no money and no way to compete on salaries but to rebuild a vision from scratch.

Good luck. It wasn’t easy the first time.

Epilogue

There is no easy way to think about the future regarding corporate or personal finances and arrive at novel conclusions. Follow Steve Jobs’ advice, drop enough acid, and you may. But you are still unlikely to execute based on these conclusions when you are sober on Monday. Such contemplations demand an entire suite of thought exercises. This is my favourite:

Flip the Five Whys exercise around and you have the And Then What? exercise.

Once you are rich, then what? Once you have solved the original problem, then what? Once you have solved an entire category of problems, then what? Once you have taught others to do it, then what?

And then what?

Original post by Steven Deobald - check out Stories by Steven Deobald on Medium

Designing for Open Source Software

Mattermost → Relay

When you hear the words “open source” attached to a product, what image comes to mind? Do you imagine an office full of designers obsessing over every little pixel? Or do you imagine an army of alpha-nerds piecing together a slap-dash knockoff of some proprietary software?

We all believe open source software is badly designed because, historically, it was. (#NotAllOpenSourceSoftware)

Thirty years ago, in 1988, the very concept of a license or design language for software was far beyond the average person. A decade later, everything was still awful. Software barely worked. Your PC definitely had a virus on it. HTML had a <blink> tag. Installing Linux required weeks of patience and belief in oneself — the kind of conviction I would need to train for a marathon. If there is one canonical failure we can promote as the poster child of this dark era, it is OpenOffice. Or StarOffice or LibreOffice or Apache OpenOffice or OOo or AOO or whatever name you might know it by. When the very name of the product is this broken it’s unlikely to succeed as a brand.

Fast forward ten more years. As of 2008, Firefox was eating Microsoft’s lunch. Firefox was open source, fast, and standards-compliant. It was easy to like Firefox. But we didn’t like Firefox. We loved Firefox. Firefox had a brand before it was Firefox. A brand isn’t a snappy name and a cute logo. Your product is your brand and your product is dictated by its design.

In 2018, user expectations demand that design asymptotically approach perfection: your product better be open, compatible, clean, fast, and powerful. When nilenso first made the move from Slack to Mattermost, we kept all of this in mind. From our very first deployment of Mattermost it felt whole. We chose Mattermost because it was so very close to the design we wanted, we knew we could help bring it the rest of the way.

The beginning

The design problems that currently exist with Mattermost aren’t just visual but interaction and experience related. One of the first issues we took up was adding infinite scroll to the channel history. We couldn’t fathom why users should manually click to load every page of history. So we fixed it!

In the not-too-distant future we will add all the little nuanced details which transform Relay into software you absolutely love. At the moment, however, our aim is to solve the obvious problems our users have with the Mattermost/Relay experience. Like infinite scroll, these are the problems that left our early users shouting at us “ugh… how have you not fixed this yet?!”

Such problems stem from the pains caused by inconsistencies and visual discrepancies which hamper usability. It is surprising to many how quickly these seemingly small issues amount to death by a thousand papercuts. It is equally surprising how quickly software becomes a joy to use once you get the basics right.

We’ll start with the basics — icons and fonts — and then move on to the specifics of how we redesigned Mattermost as Relay, piece by piece.

Icons

When we moved from Slack to Mattermost the difference in icons used was stark. All icons used in Mattermost were inconsistent with respect to weights. They were standing out of the interface rather than blending in.

After further digging, we realised that Mattermost uses the free version of Font Awesome. Don’t get me wrong, I love the guys at Font Awesome; I even backed their kickstarter. But not all icons being available in the free weights (regular & solid) is quite a bummer.

We had three rules for selecting an icon set:

Icons must be open source
Icons need to be extensive
Icons need to be available in different styles (line and solid)

Allow me to interrupt with an aside. Technically, it is possible for us to build commercial artefacts into the Relay client by keeping them out of the source tree, even though Relay is AGPL3-licensed (as a derivative of the mattermost-webapp). Why, then, do we feel it is essential that the icons be open source? Relay lives at the intersection of the principles of Free Software and the license which governs it. Relay stands on the shoulders of giants — not only the Mattermost source code but Linux, GoLang, React, and hundreds of other projects. Here, between the spirit and the letter of Open Philosophies, exists a great deal of nuance. Cutting through this nuance is a root concept, however: “share alike.” If we take something from the free/open software community, what we return to that community should afford the next recipient the same freedoms we had. If we tweak Relay’s design until it is absolutely perfect but that involves changes which Mattermost cannot absorb upstream, we have failed them and every other project we have built ourselves upon. Thus, our icons must have an open license. — Steven Deobald

Thanks Steve. Keeping the above mentioned points in mind, there were three icon sets that made the final round of discussion:

We chose the Clarity icon set because of styles, consistency, and the icons being part of a design language system. Clarity is an open source design system created and maintained by the good folks at VMware. Since VMware has a dedicated team pushing continuous updates there is little fear the icon set will be abandoned or go stale.

Font

Our font selection followed the same rules:

Fonts must be open source
Fonts should be available in multiple weights

…along with these additions:

Fonts with large x-height for easy readability
Fonts with thick Regular weight so fonts will be crisp

We stress so much on font weights because Relay is, first and foremost, a messaging tool. In Relay, you spend most of your time reading and we want this experience to be as enjoyable as possible. Relay also has complete Markdown support and weights help establish hierarchy both within the app and within the messages themselves.

We had a few contenders which satisfied these requirements. PT Sans, Lato, and Noto Sans all have an enjoyable reading experience but after a lot of trial and error we chose Fira Sans.

Fira Sans is an incredible font. It has a healthy variety of weights and the compressed nature of the font holds the messaging interface together while keeping it crisp.

Did you know that Fira Sans was built on top of Erik Spiekermann’s commercial font FF Meta? And that Spiekermann was commissioned by the Mozilla Foundation! Read the whole story here

How Mattermost became Relay

Implementing the design basics improved the existing experience. But to make those changes truly delightful we need to fine-tune every aspect of the app. We have started with three major sections:

Left sidebar
Channel header
Main messaging interface

1. Left sidebar

The sidebar’s Team section allows users to switch between teams within organisations that they’re a part of. The current Mattermost implementation truncates the team name and adds a byline. The problem with this is that it does not add any value since hovering over the team opens a tooltip with the team name anyway. We removed the byline and the truncated text.

The sidebar’s Channel section felt mashed together. There is a clear hierarchy intended, which includes channel headers such as “Favorite Channels” and a distinction between active and inactive channels. We brought this hierarchy to the surface. Active channels have a heavy weight and inactive channels fade away with a lower opacity, despite the increased crispness of Fira Sans.

Grouped channels now have tighter spacing and groups themselves have larger spacing, allowing group titles to have a smaller font. All together, this makes the hierarchy obvious even at a glance.

2. Channel header

In the channel header we cleaned up the icons. Here are the issues we encountered with the icons:

Most icons weren’t of the same weight
Some icons were of a different size
Some icons had some positioning overrides to align them

The old icons for the channel header stood out, drawing attention away from the main chat area. We wanted them instead to blend into the design — unobtrusive but still obvious. To do this we removed the borders and switched the icon set to Clarity.

In addition to icons, we fixed the CSS for the header and right sidebar, getting rid of all funny margins and relative positioning. We also added consistent heights, paddings, and sizes for each of the icons. These fixes don’t just add polish to the UI; once merged, they will also ensure it is easier for anyone in the community, including us, to customise Mattermost.

3. Messaging interface

The messaging interface is where users spend the most time. The messaging interface is also where Mattermost has most of its design inconsistencies, which are most glaring in the basics: alignment, spacing between posts, font size, and other elements on the interface such as the reply box.

After we moved to Fira Sans we bumped up the font size, made sure the headings and names are bolded to establish hierarchy, and fixed alignment and spacing issues to deliver a crisper and more enjoyable reading experience.

Themes

Accessibility matters. We have light-sensitive coworkers and we’re sure you do, too. That’s why Relay comes with light and dark themes out of the box.

There are many Relay/Mattermost-compatible themes available already but we will pour all our energy into these two. They already make Relay beautiful and with every kaizen they will only get better.

Of course, we don’t restrict you to these two themes. Relay also comes with community themes and Relay’s entire colour scheme is fully customisable… not just the sidebar (*cough* Slack *cough*). We are working to make Relay 100% customisable through CSS so users have complete control over every aspect of the UI, if they want.

Putting it all together

By following a consistent design language for icons, font, and themes we ensure all our “pieces” are whole unto themselves. Putting them back together, the application itself becomes whole.

Mattermost has published a design challenge that encourages designers from all over the world to improve Mattermost (and, hence, Relay) readability and usability. Our redesign addresses this challenge.

Along with visual design changes, Relay also aims to significantly improve its user experience. Our public Trello board contains our plan for Relay’s future.

Future

“Design” is the 8th most popular tag on Medium. “Open Source” is ranked 290. Source code licenses will never be sexy for the same reason your city’s water utility company will never be. The water supply is inherently a part of your city’s design. Similarly, your freedom as a user is designed into software you buy. Your ownership of a product is but one more limb in the tree of design.

Open source software needs good design because good design respects you, the user.

❤

<hr><p>Designing for Open Source Software was originally published in The Relay on Medium, where people are continuing the conversation by highlighting and responding to this story.</p>

Original post by Varun Pai - check out Stories by Varun Pai on Medium

« Older Blog Archives Newer »