Suduku Solver

sudoku.cpp

#include <array>
#include <assert.h>
#include <functional>
#include <iostream>
#include <set>
#include <stack>

class SudokuSolver {
private:
  std::array<int, 81> &sudoku_;
  std::array<std::set<int>, 81> allows_;

public:
  SudokuSolver(std::array<int, 81> &sudoku) : sudoku_(sudoku) { parse(); }

  bool solve(int pos = 0) {
    while (pos < 81 && allows_[pos].size() == 1) {
      ++pos;
    }
    if (pos == 81)
      return true;
    if (allows_[pos].size() == 0)
      return false;

    std::array<std::set<int>, 81> backup = allows_;

    auto possibles = allows_[pos];

    for (int possible : possibles) {
      set(pos, possible);
      allows_[pos] = {possible};
      if (solve(pos + 1)) {
        return true;
      }
      allows_ = backup;
    }

    return false;
  }

  void print() {
    for (int i = 0; i < 81; i++) {
      for (auto j : allows_[i]) {
        std::cout << j;
      }
      std::cout << ' ';
      if (i % 9 == 8)
        std::cout << "\n";
    }
  }

private:
  bool parse() {
    allows_.fill(std::set<int>{1, 2, 3, 4, 5, 6, 7, 8, 9});
    for (int i = 0; i < 81; i++) {
      if (sudoku_[i] > 0) {
        allows_[i] = {sudoku_[i]};
        set(i, sudoku_[i]);
      }
    }
    return true;
  }

  void visit(int i, const std::function<void(int)> &action) {
    int line = i / 9;
    int col = i % 9;
    int cubline = line / 3;
    int cubcol = col / 3;
    // line
    for (int j = 0; j < 9; ++j) {
      int index = line * 9 + j;
      if (index != i) {
        action(index);
      };
    }
    // row
    for (int j = 0; j < 9; ++j) {
      int index = j * 9 + col;
      if (index != i) {
        action(index);
      };
    }
    // cube
    for (int j = 0; j < 3; ++j) {
      for (int k = 0; k < 3; ++k) {
        int index = (cubline * 3 + j) * 9 + cubcol * 3 + k;
        if (index != i) {
          action(index);
        };
      }
    }
  }


  void set(int pos, int val) {
    visit(pos, [&](int i) {
      if (allows_[i].count(val) > 0) {
        allows_[i].erase(val);
        if (allows_[i].size() == 0) {
          return;
        }
        if (allows_[i].size() == 1) {
          set(i, *(allows_[i].begin()));
        }
      }
    });
  }
};

int main() {
  std::array<int, 81> sudoku = {
      0, 0, 3, 0, 2, 0, 6, 0, 0,
      9, 0, 0, 3, 0, 5, 0, 0, 1,
      0, 0, 1, 8, 0, 6, 4, 0, 0,
      0, 0, 8, 1, 0, 2, 9, 0, 0,
      7, 0, 0, 0, 0, 0, 0, 0, 8,
      0, 0, 6, 7, 0, 8, 2, 0, 0,
      0, 0, 2, 6, 0, 9, 5, 0, 0,
      8, 0, 0, 2, 0, 3, 0, 0, 9,
      0, 0, 5, 0, 1, 0, 3, 0, 0};
  SudokuSolver ss(sudoku);
  bool result = ss.solve();
  if (result) {
    std::cout << "solved!\n";
    ss.print();
  }
}