The classic approach

Solving a sudoku puzzle is not very hard. Representing the puzzle as a thin wrapper around some kind of container (a std::array in this case), it could look like this:

template<typename T, size_t N>
class SudokuT
{
private:
  std::array<T,N*N> data;
public:
  SudokuT(const std::array<T,N*N>& a) : data(a) {}
  unsigned operator()(size_t row, size_t col) const { return data[row*N+col]; }
  SudokuT<T,N> replace(size_t row, size_t col, T val) {
    SudokuT<T,N> s(*this);
    s.data[row*N+col] = val;
    return s;
  }
  size_t dimension() const { return N; }
};
// the classic 9x9 sudoku
using Sudoku = SudokuT<unsigned, 9ul>;
using Cell = std::pair<size_t, size_t>;

The Sudoku class does not much more than simulating a two-dimensional matrix
over a one dimensional container. It is just for our convenience. It is a read-only class: there is no way to modify an instance, the only way to change fields (or cells) is calling Sudoku::replace to create a new instance containing the change. This allows a clean functional style which is easier to understand (at least for me) and will make it easier to transform the “classic approach” into the compile time solution later on.
We will use the value 0 (zero) to represent the unknown value, these are the cells which should be filled by the solver.

The solving function is just a simple backtracking algorithm:

constexpr Sudoku solve(const Sudoku& s)
{
  if (!valid(s)) return s;
  else {
    Cell n{next(s)};
    if (n.first == std::numeric_limits<Cell::first_type>::max()) return s;
    for(unsigned i=1;i<=s.dimension();++i) {
      auto ns = s.replace(n.first,n.second,i);
      Sudoku res = solve(ns);
      if (finished(res) && valid(res)) return res;
    }
    return s;
  }
}

valid() is a function which checks the validity (soundness) of a given sudoku (which may still contain 0 values), finish() checks the completeness of a given puzzle. The function next() returns a Cell with the coordinates of a Cell containing 0. If next() cannot find a free cell, it will return a cell with invalid coordinates. There are other (and maybe better) ways to check this, for instance calling finished() before ensuring next() can find a result or by throwing an exception in next().
I would not say this is a good solution, but it works (in a sense that valid input produces valid output, as usual all the error checking stuff was ignored). So lets go to the interesting part:

The compile time approach

C++ offers since C++11 the constexpr keyword. It is usable since C++11 and convenient since C++14. The latter added if-statements, and loops to the list of expressions allowed in a constexpr function. This allows us to just add the constexpr keyword to our solve() function:

constexpr Sudoku solve(const Sudoku& s)
{
  if (!valid(s)) return s;
  else {
    const Cell n{next(s)};
    if (n.first == std::numeric_limits<Cell::first_type>::max()) return s;
    for(unsigned i=1;i<=s.dimension();++i) {
      const auto ns = s.replace(n.first,n.second,i);
      const Sudoku res = solve(ns);
      if (finished(res) && valid(res)) return res;
    }
    return s;
  }
}

to turn it into a constexpr-function. As we are creating (modified) copies of our Sudoku class, it has to be constexpr too:

template<typename T, size_t N>
class SudokuT
{
  std::array<T,N*N> data;
public:
  constexpr SudokuT(const std::array<T,N*N>& a) : data(a) {}
  constexpr unsigned operator()(size_t row, size_t col) const {
    return row*N+col >= N*N ? 0
                            : data[row*N+col];
  }
  constexpr SudokuT<T,N> replace(size_t row, size_t col, T val) const;
  constexpr size_t dimension() const { return N; }
};

Fortunately std::array can be constexpr-constructed and has a constexpr-[]-operator. Our access function got an additional out-of-range check, and that is it. With one exception: the replace method becomes a small problem. We have to create the modified Sudoku in one step. As our Sudoku is just a thin wrapper around std::array, the question boils down to: how do we create a copy of an existing array with a value change at one position? What we are looking for is a function like this:

template<typename T, size_t N>
constexpr std::array<T,N> replace(const std::array<T,N>&a, const size_t offset, const T val);

This function should create a copy of a, change a[offset] to val, and return the resulting array. And it should be a constexpr function. It turns out to be a non-trivial problem.

Playing with std::array

std::array is just a wrapper over the old c-style-arrays. It provides not much functionality by itself. But it turns out the be a source of much fun in conjunction with variadic templates. Consider, for instance, a function make_unique_array, which creates an array were all elements have the same value:

template<typename T, size_t N>
constexpr std::array<T,N> make_unique_array(const T val);
auto a = make_unique_array<unsigned,40ul>(42);

std::array a should now contain 40 elements and each of it with value 42. This can be easily implemented using variadic templates and a little helper function:

template<typename T, size_t... Ids>
constexpr std::array<T,sizeof...(Ids)> make_unique_array_impl(const T val, const std::index_sequence<Ids...>)
{
  return { {(static_cast<void>(Ids), val)...} };
}
template<typename T, size_t N>
constexpr std::array<T,N> make_unique_array(const T val)
{
  return make_unique_array_impl(val, std::make_index_sequence<N>());
}

std::make_index_sequence was added in C++14. It creates a variadic template (with N elements), which we use to instantiate the right version of the make_unique_array_impl function. In this function we finally use a parameter pack to create our new array: “(static_cast(Ids), val)…” will be expanded during compilation to (note that Ids in our case is the list 0, 1, 2, …, N): (static_cast(0), val), (static_cast(1), val), …, (static_cast(N), val). The cast is used to just avoid a compiler warning(unused value). The comma operator returns always the last argument, which is “val” in our case. With this little trick we get a list of N elements each with value “val”, which we use to create our array.
The same idea can be used to merge two arrays depending on the result of select-function:

template<typename T, size_t N, typename Sel, size_t... Idx>
constexpr std::array<T,N> merge(const std::array<T,N>&a, const std::array<T,N>&b, Sel sel, std::index_sequence<Idx...>)
{
  return { {sel.select(a[Idx],b[Idx],Idx)...} };
}
template<typename T, size_t N, typename Sel>
constexpr std::array<T,N> merge(const std::array<T,N>&a, const std::array<T,N>&b, Sel sel)
{
  return merge(a,b,sel,std::make_index_sequence<N>());
}

Given two arrays a and b of the same size (N) and type (T), the merge function creates a merge array c of size N and type T where each element c[i] == sel.select(a[i],b[i]).
Note that all functions above are marked as constexpr, thus it can be evaluated at compile time.

The replace

Given the functions above it is finally easy to implement the replace function:

template<typename T>
struct Sel {
  size_t idx;
  constexpr Sel(size_t i) : idx{i} {}
  constexpr T select(T a, T b, size_t index) {
    return index==idx?b:a;
  }
};
template<typename T, size_t N>
constexpr std::array<T,N> replace(const std::array<T,N>&a, const size_t offset, const T val)
{
  return merge(a, make_unique_array<T,N>(val), Sel<T>{offset});
}

Note that Sel is a constexpr class too.
Obviously replace can be simplified further:

template<typename T, size_t N, typename Sel, size_t... Idx>
constexpr std::array<T,N> replace_impl(const std::array<T,N>&a, Sel sel, std::index_sequence<Idx...>)
{
  return { {sel.select(a[Idx],Idx)...} };
}
template<typename T, size_t N, typename Sel>
constexpr std::array<T,N> replace(const std::array<T,N>&a, Sel sel)
{
  return replace_impl(a, sel, std::make_index_sequence<N>());
}
template<typename T, typename S>
struct Selector
{
  T val;
  S offset;
  constexpr Selector(const T& v, const S& o) : val(v), offset(o) {}
  constexpr T select(T a, S index) const {
    return index==offset?val:a;
  }
};

Now we can write our Sudoku-replace:

template<typename T, size_t N>
class SudokuT
{
  ...
  constexpr SudokuT<T,N> replace(size_t row, size_t col, T val) const {
    return {::replace(data,Selector<T,size_t>(val,row*N+col))};};
  }
  ...
};

The complete code is available at github.

Performance

Obviously the constexpr version runs faster, but we have to pay a price at compile time:

Version	Compile time (sec)	Run time (sec)
Dynamic classic	0.66	2.1
Compile time	720	0.005
Empty		0.005

The Empty version just returns immediately from solve(). This is just to show, that the runtime of the constexpr version is mainly caused by the output of the result.

Conclusion

There are two important (at least for me) results. The first one is: compile time calculation is very funny. The second one: one should think very careful if and where it is useful. It increases compile time dramatically. And there is (at least at the moment) no possibility to debug this code. Please do not forget the alternatives just because constexpr are so funny: “Write programs which write programs” (I do not remember the author). If you need some special values in your program, just write a program which calculates these values and generates an include file. Place this program in your build toolchain. Or run some initialization code at startup which fills lookup tables. All these techniques are well established, easy to maintain. Use constexpr only if you can prove, it makes sense (or if it is trivial to implement). Or if you have enough time and need some fun.