ナンプレを解くプログラムを方法ごとに３つ作成した。今回はその中で全探索による解法を紹介する。
全探索という名前の通り，すべての組み合わせを試し，ナンプレのルールに矛盾しないものを見つけ出す方法である。アルゴリズムは次のようになる。

—– アルゴリズム —–

1. 数値が確定していないマスに，矛盾しない数値を入れる。2.へ
2. 次の空いているマスについても同様に，矛盾しない数値を入れる。3.へ
3. 矛盾しない数値が存在する場合は2.へ，存在しない場合は4.へ
4. 一つ前のマスに戻り，別の矛盾しない数値を入れる。3.へ

このアルゴリズムをC言語で実装した
ソースファイル             →nan_solve_全探索.c
サンプルの問題データ → sample.txt

——— 2018/05/13 追記 ———-
ソースファイルとサンプルの問題データをGitLabに移動した。
https://gitlab.alprovs.com/alprovs/numberPlace-fullSearch

このコードをコンパイルして実行した結果を一応載せておきます

$ ./a.out ./sample.txt 
  /  2  /   /  /  /   /  7  / 
  9  /  /   1  /  2   /  /  8 
  /  /  /   /  8  /   /  /  / 

  /  5  /   /  /  /   /  1  / 
  /  /  7   /  9  /   5  /  / 
  /  6  /   /  /  /   /  2  / 

  /  /  /   /  4  /   /  /  / 
  5  /  /   8  /  3   /  /  9 
  /  1  /   /  /  /   /  6  / 



  8  2  1   4  5  9   6  7  3 
  9  3  6   1  7  2   4  5  8 
  7  4  5   3  8  6   2  9  1 

  2  5  4   6  3  8   9  1  7 
  1  8  7   2  9  4   5  3  6 
  3  6  9   7  1  5   8  2  4 

  6  9  3   5  4  1   7  8  2 
  5  7  2   8  6  3   1  4  9 
  4  1  8   9  2  7   3  6  5

以上。

この方法はプログラムで実装するには簡単なのですが，解けるまでの時間はかなり遅いです。
通常の９×９であれば遅くても数秒あれば解くことができますが，１６×１６となると数日かかります。
ということで，次回はもっと早く解くことのできるアルゴリズムを紹介しようと思います。

プログラムでオーバーフローするような大きな値を扱った際にnan（非数）やinf（無限）が出現した。このnanやinfが出現する法則がよくわからないので（マニュアル等を見れば書いてあるのだろうが…）自分が所持している環境で検証を行った。ソースは次のとおり

#include 
#include 

int main(void)
{
  printf("1/0  = %f\n", 1./0.);
  printf("exp(710) = %e\n", exp(710.));
  printf("log(0) = %f\n\n", log(0.));
  //infの有限値との加減乗除
  printf("1 + inf = %f\n", 1.+exp(710.));
  printf("1 - inf = %f\n", 1.-exp(710.));
  printf("1 * inf = %f\n", 1.*exp(710.));
  printf("1 / inf = %f\n\n", 1./exp(710.));
  //inf同士の加減乗除
  printf("inf + inf = %f\n", exp(710.)+exp(710.));
  printf("inf - inf = %f\n", exp(710.)-exp(710.));
  printf("inf * inf = %f\n", exp(710.)*exp(710.));
  printf("inf / inf = %f\n\n", exp(710.)/exp(710.));
  //nanと有限値の加減乗除
  printf("1 + nan = %f\n", 1.+(exp(710.)/exp(710.)));
  printf("1 - nan = %f\n", 1.-(exp(710.)/exp(710.)));
  printf("1 * nan = %f\n", 1.*(exp(710.)/exp(710.)));
  printf("1 / nan = %f\n\n", 1./(exp(710.)/exp(710.)));
  return 0;
}

最初の3つの式がパッと思いついたnan,infになると思われるもので、
1/0 = nan, exp(710) = inf, log(0) = -infになると予想する。
指数関数の710という値はdouble型の上限1.797693e+308から
exp(x) = 1.797693e+308 -> x = log(1.797693)+308*log(10) = 709.78
より上限を越える値を選択した。

• 結果1
  コンパイラ：gcc(version 4.4.7)
  実行結果

  1/0  = inf
  exp(710) = inf
  log(0) = -inf
  
  1 + inf = inf
  1 - inf = -inf
  1 * inf = inf
  1 / inf = 0.000000
  
  inf + inf = inf
  inf - inf = -nan
  inf * inf = inf
  inf / inf = -nan
  
  1 + nan = -nan
  1 - nan = -nan
  1 * nan = -nan
  1 / nan = -nan

• 結果2
  コンパイラ：Microsoft(R) 32-bit C/C++ Optimizing Compiler Version 15.00.21022.08(Visual Studio 2008)
  このコンパイラでは1/0は
  「error C2124: 除算、剰余演算が 0 で行われています。」
  とエラーで弾かれてしまった為、変数に0を格納して実行した。
  実行結果

  1/0  = 1.#INF00
  exp(710) = 1.#INF00
  log(0) = -1.#INF00
  
  1 + inf = 1.#INF00
  1 - inf = -1.#INF00
  1 * inf = 1.#INF00
  1 / inf = 0.000000
  
  inf + inf = 1.#INF00
  inf - inf = -1.#IND00
  inf * inf = 1.#INF00
  inf / inf = -1.#IND00
  
  1 + nan = -1.#IND00
  1 - nan = -1.#IND00
  1 * nan = -1.#IND00
  1 / nan = -1.#IND00

  結果の表現は違うが1.#INF00はinf、-1.#IND00はnanを表している

今回2つの環境でテストを行ったが、両方共に同じ結果となった。ちなみに変数がinfかnanかを判定するには”==”でなく”isinf()”と”isnan()”というマクロを使用する。（詳細は他のサイトを参考にしてください）