Sudoku solver in C++11

Posted by & filed under c++11, programming, python.

TL;DR Show me the code : Gist
Tell me how fast it runs : Follows the same trend reported in the original post. For instance, the difficult problem that was solved in 72.27 seconds by the Python code took 45.34 seconds.

EDIT :
After being chastised by many insightful comments on Reddit, I changed the code to use auto const& in places that matter, compiled with -O3, and re-ran both Python and C++ versions, and changed the times above to reflect those experiments. I had reported the time from Norvig’s webpage for the Python version which is not at all fair as that was probably on years old machine.

This post chronicles my effort to translate this Sudoku solver written in Python to C++11. (Yes, I know, I should call it C++, since the standard has been ratified, but C++11 feels like a completely new language, so I mentally separate C++03 and C++11). The first part sets up some lists to hold a grid configuration. Please refer to the original post to find out what each data structure means. I will show the Python code followed by the C++ with some explanation.

The above code is doing a cartesian product of two lists. I am going to use std::vector<> for representing lists. So here is the corresponding C++11 code for doing the cartesian product.

Note that the Python code is generic with respect to the type of the output list. The type of the output list is determined by the type of the expression a+b . We can emulate the same in C++ using decltype and late-specified return type as shown.

These are pretty straightforward :

unitlist is a list of lists of strings in Python. I chose vector<vector<string>> to represent it.

The code populates unitlist with 3 lists. Let’s look at the last list first.

It’s hard to get this concise in C++, but we can try. Python uniformly treats a string as a list of characters. However C++ doesn’t. So the first order of business is to write something that can convert a string literal like "123" to a vector<string>. To make it look more natural, I am going to use the C++11 user-defined literal facility. I am going to convert something like "123"_vec{/vec} to a {cpp}vector<string>. Here is the code to do it :

Now, here is the translation for the last of the three lists that make up unitlist :

Almost as concise, eh? The translations for the other two lists are easier.

Let’s look at the next two data structures :

A map is the straightforward translation for a Python dictionary.

units is easy to translate:

However, the way peers is populated is a bit tricky. Python sum function converts a list of lists into a list by simply appending the lists together. The equivalent can be achieved with std::accumulate. That is not the most efficient way to achieve the flattening of the nested list in C++, but I am just going to use this as it is not in any inner loop. Once I get the flattened vector, I am going to conditionally copy it to the output set, instead of doing a set difference.

Next, let’s tackle the assign, eliminate, parse_grid, and grid_values functions. All of either return the grid representation, which is a dictionary mapping strings to strings ( map<string, string>), or False, if the grid was inconsistent. Since C++ functions can have only one return type, I chose to represent the return type as follows :

The maybe<T> type will either contain a pointer to a data item of type T, in which case valid will be true, or it will be empty. That way, the C++ functions can return maybe<value_t>.
assign :

eliminate :

The only notable thing is returning maybe<value_t>() in place of Python’s False. Otherwise, the C++ code has almost one-to-one correspondence with the Python code. The final piece of the puzzle is searching for a solution.

The C++ code is here :

The code slightly deviates from the Python implementation, but remains similar in spirit. First, I copy the elements of the grid that have more than one valid entry in them to a temporary vector. If the temporary vector is empty, then we are done. If not, I pick the entry with smallest number of valid elements. That is what the min_element is doing. Then I recurse by setting that grid cell to each possible valid entry. The gist has a complete runnable program that takes the input grid as a command line argument. An example run :

Time wise, I found that the C++ implementation followed the same trend as the Python implementation. That is, most problems were solved in less than few milliseconds. The hard one that took 72.27 seconds by Python was solved in 45.34 seconds by the C++ code.

6 Responses to “Sudoku solver in C++11”

  1. Arjun Nayini

    Thanks for this. I had hoped to actually write my own in C++ and its nice that you have written this in the latest standard.

  2. Eric

    Did you mean to copy elements in all your for loops? ISTR for(auto& elem : container) is needed to avoid a copy. This might be part of the source of the slowly execution time. I’d expect far better results relative to python.

  3. David Grant

    Your time units are a bit messed up. I think for microseconds you should put “us”. And then you say “most problems were solved in less than a few microseconds” where I think you meant to say “milliseconds”. And when you say the hard problem took 160 seconds in C++ did you mean to say millseconds?

  4. Manjunath

    Yep, I was wrong. I meant milli when I wrote micro. But the 160 seconds is really in seconds, not milliseconds.

  5. David Grant

    “Time wise, I found that the C++ implementation followed the same trend as the Python implementation. That is, most problems were solved in less than few milliseconds”

    I found that your C++ implementation (with -O2) takes about 4ms for the example problem you gave and about 40ms using the Python solver.

  6. Thomas Petit

    What a funny coincidence ! I did the very same exercise (porting norvig sudoku solver to C++11) a few days ago.

    Here is where I deviated a bit from your solution :

    1) The “operator”" _vec” part. That’s quite fancy :)
    Here is a more common solution: First, overload cross() to take two std::string

    std::vector cross(const std::string& s1, const std::string& s2)
    {
    std::vector output;
    for(char c1 : s1){
    for(char c2 : s2){
    std::string s;
    s += c1;
    s += c2;
    output.push_back(s);
    }
    }
    }

    Then, you can fill unitlist this way :

    for(const std::string& r : {“ABC”, “DEF”, “GHI”})
    for(const std::string& c : {“123″, “456″, “789″}
    unitlist.push_back(cross(r, c));

    2) When initializing peers, you don’t need to accumulate everything into a std::vector then copy it to the set of peers. You can actually directly accumulate into a std::set this way :

    for(const std::string& s : squares){
    peers[s] = std::accumulate(units[s].begin(), units[s].end(), std::set(),
    [&](std::set& peer, const std::vector& v){
    for(const std::string& square : v)
    if(square != s)
    peer.insert(square );
    return peer;
    });
    }

Leave a Reply

  • (will not be published)

XHTML: You can use these tags: <a href="" title="" rel=""> <abbr title=""> <acronym title=""> <b> <blockquote cite=""> <cite> <code class="" title="" data-url=""> <del datetime=""> <em> <i> <q cite=""> <strike> <strong> <pre class="" title="" data-url=""> <span class="" title="" data-url="">

*