適当に書いた数独

sudoku.cpp

// compile: g++ -std=c++11 sudoku.cpp

#include <iostream>
#include <tuple>
#include <string>
#include <vector>
#include <array>
#include <cmath>

using namespace std;

const int N = 9;
const int ROOM = (int) sqrt(N);

struct Coord {
  tuple<int, int> coord;
  Coord(const tuple<int, int> &coord) : coord(coord) {}
  inline int i() { return get<0>(coord); }
  inline int j() { return get<1>(coord); }
  Coord next();
};

Coord Coord::next() {
  if (j() == N-1) {
    if (i() == N-1) return Coord(make_tuple(0, 0));
    return Coord(make_tuple(i()+1, 0));
  }
  return Coord(make_tuple(i(), j()+1));
}

struct Field {
  array<string, N> field;
  Field(const array<string, N> &field) : field(field) {}
  inline int get(Coord &c);
  inline int get(int i, int j);
  inline void put(Coord &c, int k);
  inline bool can_put(Coord &c, int k);
  bool all_filled();
  void dump();
};

inline int Field::get(int i, int j) {
  return field[i][j] - '0';
}

inline int Field::get(Coord &c) {
  return get(c.i(), c.j());
}

inline void Field::put(Coord &c, int k) {
  if (k == 0 || can_put(c, k)) {
    field[c.i()][c.j()] = k + '0';
  }
}

inline bool Field::can_put(Coord &c, int k) {
  for (int x = 0; x < N; ++x) {
    if (get(c.i(), x) == k) return false;
    if (get(x, c.j()) == k) return false;
  }
  for (int x = 0; x < ROOM; ++x) {
    for (int y = 0; y < ROOM; ++y) {
      if (get((c.i()/ROOM)*ROOM+x, (c.j()/ROOM)*ROOM+y) == k) return false;
    }
  }
  return true;
}

bool Field::all_filled() {
  for (int i = 0; i < N; ++i) {
    for (int j = 0; j < N; ++j) {
      if (get(i, j) == 0)
        return false;
    }
  }
  return true;
}

void Field::dump() {
  for (auto row : field)
    cout << row << endl;
}

class Problem {
  Field original;
  vector<Field> answers;
  void inner_solve(Coord c, Field &current);
public:
  Problem(const array<string, N> &field) : original(field) {}
  vector<Field> solve();
};

vector<Field> Problem::solve() {
  answers.clear();
  auto current = original;
  auto c = Coord(make_tuple(0, 0));
  inner_solve(c, current);
  return answers;
}

void Problem::inner_solve(Coord c, Field &current) {
  if (current.all_filled()) {
    answers.push_back(current);
    cout << "found!" << endl;
    return;
  }
  if (current.get(c.i(), c.j()) != 0) {
    inner_solve(c.next(), current);
  } else {
    //current.dump();
    //cout << "fill: " << c.i() << ", " << c.j() << endl;
    for (int k = 1; k <= N; ++k) {
      if (current.can_put(c, k)) {
        current.put(c, k);
        inner_solve(c.next(), current);
        current.put(c, 0);
      }
    }
  }
}

int main() {
  array<string, N> field;
  for (int i = 0; i < N; ++i)
    cin >> field[i];
  Problem p(field);
  auto solved = p.solve();
  cout << solved.size() << " answers found" << endl;
  for (auto ans : solved) {
    ans.dump();
  }
}