An Arduino Sudoku Solver

I saw a link to Peter Norvig’s post on “Solving Every SudokuPuzzle” on Hacker News where he had constructed a Python program to do just that. His purpose was to cure the world of Sudoku but as Sudoku appears to be an ongoing although mild mental affliction I thought his solution might be worth exploring for the Arduino platform.

I had a look at the JavaScript versions linked from the page as my Python knowledge is less even than rudimentary. I also had a good look at the C++ solution posted by Pau Fernandez. My draft plan was to write a solver for the MKR WiFi 1010 platform and to interact with it via an HTML page hosted by that board.

Peter Norvig’s post explains how he applied constraint propagation to the task of searching for a solution that does not require waiting for the heat death of the universe to run to completion. Take a look, as he certainly explains it better than I can although I will have a stab at it.

A 9 by 9 Sudoku grid contains 81 cells. The rules of Sudoku are straightforward. A valid solution to any puzzle requires that each column, row and square should contain all of the digits 1 to 9. Here you can see a Sudoku puzzle and its solution (thanks to Wikipedia Creative Commons license)

The rules represent the key constraints and to implement them the code needs to know which of 9 rows, 9 columns and 9 squares contains a given cell. The arithmetic for calculating the relevant sets is straightforward.

  for(int i = 0; i < 9; i++) {
    int sb = (i / 3) * 27 + (i % 3) * 3;
    for(int j = 0; j< 9; j++) {
      cols[i][j] = j * 9 + i;
      rows[i][j] = i * 9 + j;
      squares[i][j] = sb + j + (j / 3) * 6;
    }
  }

Deciding which column or row contains a given cell is simpler:

uint8_t Sudoku::getRow(uint8_t cell) {
  return cell/9;
}
uint8_t Sudoku::getCol(uint8_t cell) {
  return cell % 9;
}

There may well be a way of calculating the relevant square for a given cell but my head started to hurt and so I wimped out and implemented a search through the arrays.

Having got my head more or less around the constraints I had a bash at producing a couple of C++ classes designed to solve a sample (rather simple) puzzle. One class type representing a Sudoku puzzle with 81 cells each containing another class holding the possible values for that cell.

The process starts with a puzzle presented as a string with a placeholder for unknown cells. The first 9 characters are for the first row with the next 9 representing row 2 etc..

".2.4.6..76..2.753...5.8.1.2.5..4.8.9.6159...34.28.3..1216...49.......31.9.8...2.."

You can imagine each cell starting with the full set of possible values (1 to 9). As we insert values from the puzzle string into the related cells we can then apply a function that eliminates the set value from all of the related cells in the same column, row and square. If that process results in one of the targeted cells then being reduced to a single value then the function can be called recursively to apply that constraint in turn. Sometimes that is all that is needed to solve a simple puzzle.

bool Sudoku::assign(uint8_t cell, uint8_t val) {
  for(int i = 1; i <= 9; i++) {
    if(i != val) {
      // unset the other values in cell Possible instance
      if(!eliminate(cell, i)) { return false;}
    }
  }
  return true;
}

Thing to remember when reading the code is that in the final version a cell’s possible values are represented by a bit that is one index place lower in the notional array than the value. The array is notional because we are dealing with the lower 9 bits in a 16 bit integer but it is OK to picture that arrangement as an array of bool values. The C if statement will happily accept a single bit and treat a bit set on as true and a bit set off as false. I could have used bits 1 to 9 of course but that would probably have given me an opportunity to introduce a new bug or two – so I kept the original logic from when the possible values were represented by an array of Booleans (see later).

bool Sudoku::eliminate(uint8_t cell, uint8_t val) {
  if(!cells[cell].isSet(val)) {return true;}
  cells[cell].eliminate(val); // unset
  uint8_t vCount = cells[cell].count(); // how many possibles left?
  if(vCount == 0) {
    return false; // indicates an invalid puzzle
  }
  if(vCount == 1) {
    // now a single value so eliminate that from row, column and square
    uint8_t rv = cells[cell].value();
    uint8_t group = getRow(cell);
    for(int i = 0; i < 9; i++) {
      if(rows[group][i] != cell) {
        if(!eliminate(rows[group][i], rv)) { return false;}
      }
    }
    group = getCol(cell);
    for(int i = 0; i < 9; i++) {
      if(cols[group][i] != cell) {
        if(!eliminate(cols[group][i], rv)) { return false;}
      }
    }
    group = getSquare(cell);
    for(int i = 0; i < 9; i++) {
      if(squares[group][i] != cell) {
        if(!eliminate(squares[group][i], rv)) { return false;}
      }
    }
    return true;
  }
}

Most times, that process still leaves a lot of possible values in most of the cells. So, the next task is to run through each of the cells with more than one possible value counting the number in order to identify a cell with the least number of possibles. We can then create a new instance of the Sudoku class that copies all of the cell values from our first class. We can then use the same assign() method to set the equivalent cell in the new class to one of the possible values from our chosen cell. That will trigger the eliminate() method in turn. If that does not solve the puzzle then the process can be repeated until it is solved or the process runs afoul of the rules (constraints). If the process does not find a solution then it can revert to one of the other options in the list of possible values in the first Sudoku class instance cell as one of them must be correct.

The recursive creation and search of Sudoku classes can become quite deep and broad as multiple options are tested and eliminated. This simple process running within tight constraints can quickly run through thousands of options to arrive at a solution.

Sudoku* solve(Sudoku* S) {
  if(S->isSolved()) {return S;}
  uint8_t cell = S->leastCount(); // get cell with least possibles
  Possible p = S->possible(cell);
  for(int i = 1; i <= 9; i++) {
    if(p.isSet(i)) {
      // we need to create a copy of the Sudoku instance
      Sudoku n(S);
      // assign the selected value in that instance
      if(n.assign(cell,i)){
        // and call solve on that
        if(auto S2 = solve(&n)) {
          return S2;
        }
      }
      // if not solved then try the next possible cell value
    }
  }
  return NULL;
}

I uploaded my stab at the code to my MKR WiFi 1010 Arduino board which promptly crashed. There was a good reason for this - several bugs and (as it turned out later) a large memory leak. Boy, did that board crash – it subsequently refused to accept any updated program as it crashed so quickly when powered back up the USB port had no time to take control.

So, I learned how to reset a MKR 1010. If you ever get in a similar jam, just double click the re-set button. You will know that you have got the slightly fiddly double click right when one of the on-board LEDs starts to slowly fade. This is very distinctive. The COM port associated with the board will also have changed temporarily. Once a new program has been uploaded (even Blink) then the COM port will revert and the board will be back in service.

I copy pasted the bulk of my buggy code to an MS Visual Studio C++ project and used the debugger there to get things running. OK, it needed some minor code changes to manage output and the addition of a few #include statements. This is a good reminder of just how supportive the regular Arduino IDE is. Once I had stepped through the code a few times and the obvious bugs had been flushed I was able to port the code back again to the Arduino IDE (I could maybe have carried on using Visual Studio).

I dug out an Arduino Due as that board has 96K bytes of SRAM for the next attempt which proved to be a wise choice. The code found a solution to an easy puzzle and then one rated as medium. When faced with a harder puzzle with more unknowns, it looked like the Due had run out of memory. Time to see what could be done to reduce the memory footprint of each instance of the Sudoku solving class. The possible values for each cell were stored as an array of 9 bool values. This added up to 81 x 9 = 729 bytes per instance. I switched the code to using 9 bits from a 16 bit integer which reduced that component of the memory footprint to 162 bytes per instance which is roughly a 78% reduction.** Now a harder puzzle ran nicely on the Due but when I measured the before and after free SRAM I found that there was a memory leak associated with the nearly 500 class instances needed to solve that puzzle. Those recursive functions are out to get you (as is an improperly used new statement if you have trouble with delete).

The memory issue derived from the way I was instancing the classes and once I was a bit more dogmatic the memory overhead went away. Indeed (on the Due) the SRAM was all free once the code had completed. This is because the Due (and other ARM processor based boards) keeps any string constants (such as my test puzzles) in the program space and does not copy them to SRAM. No PROGMEM or F macro needed on that board.

Now I had a code base that could be used repeatedly, I was able to feed it with a sequence of test puzzles. I ran a test suite of 96 (mostly challenging and all stolen) puzzles and these were all solved correctly. Most completed in a tiny fraction of a second and a couple took as much as 10 seconds. I then uploaded the same program to the MKR 1010 and ran the tests again. All went well within the tighter 32K of memory although the slower processor meant that run times just about doubled. We clearly need even newer MKR WiFi boards with more capacity and more oomph but this one now looked OK to proceed with phase 2.

This is turning into a long story but there will be code links.

I wrote the HTML and the JavaScript for the interactive user interface up front using Visual Studio Code so I could test the layout and main JavaScript functions easily in the Chrome browser.  I also decided to go with Ajax to send requests for Sudoku solving sessions to the Arduino server. That made the option to include jQuery a no brainer for me. I know that jQuery is now considered rather old hat but I am still a big fan. Using Ajax also made it sensible to get the Arduino to respond with JSON so that it was straightforward to return additional information along with a completed puzzle.
Of course, after writing and testing the page I was faced with porting the mark-up and code from Visual Studio Code into C strings for the Arduino IDE where all those embedded quote marks and the odd backslash were going to need to be escaped. That sounded like a long and tedious editing session even with find/replace. The quick answer to that was a 6 line (Windows Forms) C# program to automatically edit text pasted from VS Code into a multi-line textbox, placing the result in another text box ready to be copy pasted to the Arduino IDE. Another tool now sitting in my toolbox.

The above image shows my final result via the web browser interface. Yes, over 60 thousand instances of the Sudoku class were needed to solve this puzzle although most are a lot less taxing. A more typical result would have seen the puzzle solved in a couple of tenths of a second.

The version using the Serial Monitor (see below) has a simpler but acceptable presentation although setting a new puzzle might prove a tad clumsy. (It does have a lot of puzzles built in ready to play with).

What did I leave out of the web browser version? I could have added JavaScript code to ensure that the user only entered numeric values between 1 and 9 but I sort of dealt with that issue by treating all cell values that were not valid digits as a blank cell. I could also have tested that the puzzle had a minimum of 17 valid cells using at least 8 of the values 1 to 9. At the end of the day though, this was an Arduino project to explore the use of a board providing a web service while also entertaining me.

You might well think that this little project got a bit out of hand. Using Microsoft’s Visual Studio, VS Code, a custom Windows program and the Arduino IDE. Notepad++ came in handy at one point and the Chrome browser developer tools were invaluable. Plus writing code using C++, C#, JavaScript and HTML all with the intention of further making Sudoku puzzles even more pointless. It begs the question. And the answer to that question is: building the tools to solve Sudoku on an Arduino proved way more enthralling than doing the puzzles.

All of the code can be found on GitHub https://github.com/MikeGWem/ArduinoSudoku

You will find three versions there. Two use the Serial Monitor to display a complete puzzle and the third has the full HTML user interface. Both approaches use more or less the same Sudoku class although the WiFi one has a small mod to indicate an error in the set puzzle to the calling web page.

If you just fancy taking a look at the Sudoku solver then the Serial Monitor versions are probably for you. If you are interested in using an Arduino to provide web services then the other option would prove more attractive of course.

Some notes on the support code in the WiFi version.

After the board connects to WiFi the server is started on port 80 (standard HTTP). The server is monitored in the standard loop() function waiting for client connections. If a connection is made then characters sent by the client are stored in a buffer waiting for an end of line character (this works fine with GET requests). When the end of a line is detected then the buffer is checked to see what the request is. If the request is for “/ “ then the page containing the user interface is served to the client. If the request contains the (arbitrary) string “ajax/” then this is treated as a request for puzzle solving. The puzzle string should follow a ‘?’ character indicating the start of the request data coming from the client. 

The serveAjax() function captures the puzzle string and passes it to a new instance of the Sudoku class and passes that to the solve() function. If all goes well then the puzzle is returned as part of a JSON string along with some statistics. If an error is detected then a simple error message replaces the puzzle solution in the JSON which also includes an error flag.

As C++ does not support reflection, the function used to create the JSON string is specific to this task – it would be nice to write something generic. The function here uses the Arduino String object that in general I avoid. It does have some utility when you have to collect a number of components into a string and its use is just about acceptable when confined in a minor function so that the memory footprint will quickly be recovered. One day, I really must sit and code a better String class – one day.

The three functions that (combined) pass the web page content to an attached client when requested are on separate tabs named ManageUI and ManageJS. This arrangement was simply to keep the main code tab clean. All they do is output (as strings) the content of the web page which should be identical to the index.html file included in the GitHub repository (as it is way easier to read). The code uses the << operator defined for any Print object (used by Serial as well as the WiFiClient instance) at the top of the Sudoku.h tab.

Some notes on the web page

If you look at the index.html page representation of the page that is served by this Arduino project you will notice that two files are downloaded from CDNs. This means that on at least the first occasion that the project is run, it needs to be on a WiFi network with an Internet connection (which is the expected state in most instances). After that, the files will probably have been cached by the browser. One of the files is the jQuery library and the other is a little frippery that is used by the code to do some colour easing and makes no meaningful contribution to the task – but I like it.

When the Arduino boots and has joined a WiFi network it displays the IP code in the Serial Monitor window ready to be entered to a browser – the address of the server will often be something like http://192.168.0.52/.

The HTML provides a simple framework with a page heading, a <div> for the Sudoku “table” and three buttons. The JavaScript includes a function drawTable() that builds a table of tables with each inner table cell containing an <input> element. I could have created the whole thing in mark-up but hey I am a programmer and thanks to Pankaj Kumar for the tables within a table idea for a simple but attractive visual effect.

The advantages that flow from using jQuery are obvious when you look at the clearTable() function that has only one line.

The solveGrid() function assembles the puzzle string and sends it via a GET request to the Arduino server using the jQuery $.ajax() built in function that takes a url (must be part of the same domain as the page was fetched from), any data (our puzzle) and a call back function for any response from the server.

The call-back function is readResult() and this uses the jQuery.parseJSON() function to create a JavaScript object from the JSON string when it arrives. Modern versions of JavaScript (read modern browsers) have a similar function JSON.parse() – just never be tempted to use eval() in this context (although I can remember having to, in ancient times). The members of the resulting object are then used to update the UI appropriately. 

As a reminder, all of the code can be found, reviewed and downloaded from GitHub 

Running on older Arduino boards

I edited a final (non WiFi) version with judicious use of PROGMEM to see how it might run on older 8 bit Arduinos. This version ran fine on a MEGA 2560 although the slower processor meant extended run times for those puzzles that needed an extended search to resolve. I even gave that version a run on an Arduino UNO where the first two trial puzzles were solved but the board lost contact after those relatively simple ones were completed.

** Worth pointing out that if I had been coding on a platform that used the standard C++ Vector and used that to hold the bool values this would have been done automatically by the Vector class. However an array is faster than a vector and thus always preferable when you know just how many elements you need to store.