数独を解いてくれるやつを作った経緯

数独、難しいですよね。私も苦手です。
先日、バイト先で先輩が数独の問題に頭を抱えていたんですよ。それを見てもう、人類、数独やんなくてよくね、と。お正月だし。時間があったらもう少し有意義なことに活用しましょうよねぇ？

さあ、文明の利器を駆使して人類を苦悩から解放しましょう。

アルゴリズム

退勤時の武蔵野線に揺られながら、貪欲法と枝切り法を組み合わせたような以下のアルゴリズムを考案しました。

そろえるべき組(以下、組。1から9までの数字が入らなければいけない行や列やグループ。)のうち、一番そろっているものを選択する(以下、特殊組。)。
特殊組の中に入りうる数字の中で、一番小さなものを選択する(以下、最小数。)。
最小数を特殊組の空白に対して順に入れていく(これを試行とよぶ。)。
それぞれの試行に対して、それが正答でない限り1～4を再帰的に行う。

結構下手な説明なので、伝わらなかった方はソースコードを見てください。

#include <array>
#include <cstdlib>
#include <iostream>
#include <string>
#include "unistd.h"  //Windowsが好きな人はこの辺を書き換えてね

class Board {
 public:
  Board(Board *b) {
    //コピーコンストラクタ
  }
  Board() {
    //ゼロで初期化するコンストラクタ
  }
  int &at(int x, int y) {
    if (x >= 9 || x < 0 || y >= 9 || y < 0) {
      printf("out of range%d, %d\n", x, y);
      exit(1);
    } else {
      return data.at(x).at(y);
    }
  }
  void print() {
    //省略。盤面を標準出力で出力する関数。
  }

  bool isvalid() {
    //省略。盤面が誤りでないか確かめる関数。
  }

  bool isanswer() {  //正答かどうか確認する関数。
    if (!zerois() && isvalid()) return true;
    return false;
  }

  Board solve() {  //この関数を再帰する。
    print();
    if (isvalid() && zerois()) {  //盤面が誤りでなく、空白が存在しているときのみ再帰する。
      int zeromin = 0;
      int min = 9;
      for (int i = 0; i < 27; i++) {
        int count = 0;
        for (int j = 0; j < 9; j++) {
          if (atindex(i, j) == 0) count += 1;
        }
        if (count < min && count != 0) {
          min = count;
          zeromin = i;
        }
      }
      bool num[9];
      for (int i = 0; i < 9; i++) num[i] = false;
      for (int i = 0; i < 9; i++) num[atindex(zeromin, i)] = true;
      int minnum = 9;
      for (int i = 0; i < 9; i++) {
        if (!num[i]) {
          minnum = i;
          break;
        }
      }
      for (int i = 0; i < 9; i++) {
        if (atindex(zeromin, i) == 0) {
          Board b(this);
          b.atindex(zeromin, i) = minnum;
          Board c = b.solve();
          if (c.isanswer()) return c;
        }
      }
    } else {
      return this;  //誤答になった時点でその枝は切る。
    }
  }
  int &atindex(int i, int t) {  //特殊組のt番目のポインタを返す関数
    if (i < 9) {
      return at(t, i);
    } else if (i >= 9 && i < 18) {
      return at(i % 9, t);
    } else {
      int x0 = ((i % 9) % 3) * 3;
      int y0 = ((i % 9) / 3) * 3;
      return at(x0 + t % 3, y0 + t / 3);
    }
  }

 protected:
  std::array<std::array<int, 9>, 9> data;  //盤面のデータ

 private:
  bool zerois() {
    //省略。盤面に空白が存在しているかどうかを確かめる関数。
  }
};

int main() {
  Board b;
  for (int i = 0; i < 9; i++) {  //標準入力から盤面データを読み込む。
    std::string s;
    std::cin >> s;
    for (int j = 0; j < 9; j++) {
      b.at(j, i) = s.at(j) - '0';
    }
  }
  b.print();
  b.solve();  //解く。
  return 0;
}

実際に解いてみる

Google画像検索の窓に以下のような文字列を入力します。

数独難問

すると、以下のように難問が表示されます。

これを筑波大学情報科学群情報科学類の計算用サーバーであるviola12に計算してもらいました(三が日でも動いてるのは偉いですね、さすがは大学です。)。スペックは以下の通りです。
CPU: Intel(R) Xeon(R) Gold 6130 CPU @ 2.10GHz RAM: 8GB

大体30秒足らずで計算できました。
今回作成したプログラムでは、解に至るまでのすべての過程を出力するので、その分でかなり無駄があるかと思われます。
めんどくさいので出力なしの時間はあとで追記します。

まとめ

これで人類は数独をやらなくてよくなりましたね！！やったぜ！！！！！！！！