Visualizing Search

Part of the appeal of building a solver for the fourth time (?!) for me is that it’s fun to watch how it solves the problem. While it’s possible and quick to hack something up on command line, the results aren’t that pretty and can’t be easily shared. In this post I’ll talk about building a frontend that talks to the backend via websockets and produces an animated visualization of how the search is solving the problem.

The scope of this post, and my initial frontend, is generalized NxN sudokus, and this first iteration of the frontend focused on largely non-interactive visualization. You can try it out for yourself online. I’ll talk about building up more interactive solvers for regular sudoku and crosswords separately.

A little background

I rewrote the solver a few times, for various reasons, but before this latest rewrite only my very first solver had any kind of visualization. It was built during my grad studies and, largely due to my familiarity with Java at the time, was built with a crude, but useful Java UX. So when I felt the itch to write some code, building up a UX this time around was high on the list of things to do. This time my language of choice for the solver was Go, and with Go being an awesome language for servers (web and otherwise), and my very dated front-end web dev experience, it felt like building up the solver in Go as a backend and having a JS web frontend would be the way to go.

Basic flow

The basic flow between the user, browser and the backend is this:

sequenceDiagram
    participant User
    participant Browser
    participant Backend
    User->>Browser: Presses "Next solution" button
    Browser->>Backend: Start solving
    loop Solving
      Backend->>Browser: State updates every 30ms until solved
    end

This doesn’t allow user to do much beyond hitting the button and watching the solver do its thing, but this is sufficient for trying out things like different heuristics, constraint propagation algorithms, and so on, and seeing how they impact search. You can check these out online, just be sure to open the configuration to adjust solver behavior.

Backend and frontend

Backend’s primary job is to solve problems thrown at it, but, to keep things simple and not add another dependency, it also happens to be a basic web server and serves up the largely static web pages, such as the initial screen for the NxN sudoku that the user sees. More importantly though, the backend also allows the frontend to connect to it via websockets, which are used to send state updates and basic control messages between the frontend and the backend. The page served by the backend has two key elements: the canvas where we will draw the state, and the button that lets the user kick off the solving process.

The frontend is in JS and is quite basic. It does the following:

• Waits for the user to press the button, and once pressed connects via a websocket to the backend. The websocket is kept open until either the user leaves the page or no more solutions can be found.
• For each message from the backend it will interpret the message per the rudimentary protocol, described below, and handle it.
• Most messages are state updates, and so JS will update the state of the sudoku board, represented by the large canvas element. This is the “Solving” loop in the sequence diagram above.
• There are a couple of other messages that the backend can send - one when a solution has been found and the user can search for more by hitting the button again, and another when no more solutions exist.

By the way, while I’m still waffling as to whether open-source the backend, JS frontend code is effectively open-sourced in that it is unobfuscated and easily readable. If you’d like, you can check it out here.

Websockets and the protocol

Since the bulk of communication between the backend and the frontend will be state updates that is the most interesting bit of the protocol, while the rest is truly simple and borderline silly. Let’s do these basic control messages first to get them out of the way; there are two categories: frontend telling backend it wants the next solution, and backend telling the frontend something other than a state update. Since the frontend doesn’t do anything other than says “Give me next solution” the protocol is literally that any message from the frontend to the backend will make the solver look for the next solution. The backend to frontend messages are almost as simple, as there are only two mentioned above, and they’re sent as strings. Could I do something shorter/smarter? Yes. Was it worth the effort? YAGNI says “nah” … at least until something breaks horribly and I’ll be forced to fix this.

State updates are more interesting - let’s see what the solver knows about the current state and how that can be passed along as part of the protocol:

• The solver knows the state of each cell in the NxN sudoku (represented internally by a variable). Naturally, there are NxN cells.
• A given cell can either be assigned a value, from 1 to N, or it can be unassigned.
• In my initial implementation that was basically what was sent through the websocket - either 1 through N, or 0 for unassigned state… but the solver knows something else about unassigned cells, namely how many values are in that variable’s live domain (remember constraint propagation?), so it’d be cool if we could show that on the frontend, too. We can do that fairly easily - for each cell that is not assigned we can use values N+1 through 2*N to pass this info on to the frontend. And that’s exactly what the protocol does.

TL;DR state updates are just a message with N*N bytes, and each byte mapped to values / remaining-live-values as per above.

A couple of quick notes:

• Could the state updates be compressed? Yes, definitely. For now though, I am looking for ways to shed CPU cycles where possible, and between that and YAGNI it seemed unnecessary to apply compression on the server followed by decompression on the client. I may change my mind as this lack of compression is in part why the online version of NxN sudoku solver is limited to 36x36 sudokus, while in practice my E2 GCE instance could likely handle at least 64x64 without blowing up.
• Won’t this protocol break for N > 121? Yup… but with the current implementation 100x100 already takes close to an hour on my rather dated machine, so redesigning the protocol for grids 144x144 and larger isn’t a priority now.

Example message

Let’s take a quick look at the classic 9x9 sudoku. If you want to follow along you can open this link, set the size to 9x9, open DevTools and head over to the network tab, assuming that you’re in Chrome. After you hit “Next solution”, you’ll see the grid get populated. On the DevTools network tab you’ll also note a bunch of messages sent over the websocket, as shown below. We’ll examine one of them.

Here you can see how the first message to the server was just an empty string - as I mentioned above any message will trigger a solve, and I just happen to be sending an empty string to do so. That’s not too interesting though, so we’ll grab the 4th binary message from the server. Let’s copy it as hex. You should get this:

1

0102030f0f0f0f0f0f0f0f0f1212121212120f0f0f121212121212111111121212121212111111121212121212111111121212121212111111121212121212111111121212121212111111121212121212

As this is hex each two characters represent a value of a cell. Let’s look at the first few cells:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

0x01
0x02
0x03
0x0f
0x0f
0x0f
0x0f
0x0f
0x0f
0x0f
0x0f
0x0f
0x12

So what are we looking at? The backend assigns variables to values in lexicographic order, as we asked it to. The first message will be just the initial, empty grid, so after 4 messages we should get variables for cells (0, 0), (0, 1) and (0, 2) assigned; in other words, the first three squares in the top row. And that’s exactly what we see above, they are assigned to 1, 2 and 3, respectively.

The next few columns are a bit more interesting - we see a whole bunch of 0x0f values. Remember how the protocol uses values beyond N to represent that variables are unassigned and have some number of live values left? This is telling us that we have 0x0f - 9 = 6 live values left in the domain of these variables. There are 9 of these:

• The first 6 cover the remainder of the row; i.e., cells (0, 3) through (0, 8).
• The next three values will cover the cells on row 1 (zero index based) of the 3x3 box that the solver has just populated; i.e., cells (1, 0), (1, 1) and (1, 2), and they too, only have 6 live values.

Finally, we get to cell (1, 3) which is not affected by current assignments and has all 9 live values (0x12 - 9 = 9).

The rest of the message follows the same pattern as the above, as do all the other messages that the backend sends our way. Finally, the very last message also has the somewhat lazy plain-text string stating that more solutions are available, which I’ve also mentioned above.

Search state visualization

With the protocol defined and telling us what is being sent over the websocket, all that’s left is to render the sudoku. It’s easiest to describe this by walking through some code, so here’s the key bit:

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14

// Variable "edge" refers to the size of the sudoku;
// i.e. the "N" in NxN.
for (var y = 0; y < edge; y++) {
  for (var x = 0; x < edge; x++) {
    var idx = x + y * edge;
    var value = view.getUint8(idx);
    if (value > edge) {
      ctx.fillStyle = unassignedColors[value - edge - 1];
    } else {
      ctx.fillStyle = valueColors[value - 1];
    }
    ctx.fillRect(x*edgeLen, y*edgeLen, edgeLen, edgeLen);
  }
}

The two for-loops just go through the grid and give us an index into the view, which is just a JS DataView. That’s the value of that particular cell, and its meaning it mentioned in the protocol section above. Now that we have it, we know whether to render that as a set cell, or one that still hasn’t been set and has live values in its domain - that’s the if statement. We look up the color, and set that cell to that color.

With regards to the colors for assigned and unassigned variables (i.e., valueColors and unassignedColors in the code above, respectively), if you look at the source code a bit higher, you’ll see this bit:

1
2

var valueColors = generateHslaColors(70, 60, edge);
var unassignedColors = generateGrayscaleColors(30, edge);

That basically creates a slew of “rainbow” colors mapping red to low values and violet to high values for variables / cells that are set, and grayscale colors for unset variables, with white meaning all live values are possible and dark gray meaning very few live values remain. So what we’ll see is that any given row, horizontal or block in the NxN sudoku has unique “rainbow” colors, and as search gets deeper and deeper down the search tree the unassigned variables turn darker and darker as constraint propagation eliminates impossible values from live domains of unassigned variables.

And that’s it! Hopefully this helps you understand how visualization works, what the image at the top of this post is about, and gives you some ideas how you might go about visualizing interesting algos.