最新の数独解析プログラムで何問か難易度★5の問題を解いてみたのですが。
順調に問題解けてます。
ロジック周りはほぼ完成と言ったところでしょうか。
あとはもうちょっと使い勝手が良くなるようにカスタマイズしていこうと思います。
【C#】【数独】数独解析プログラム、良い感じです。
「#C#」タグアーカイブ
【C#】【数独】ログ出力を強化し不具合を探す
前回までの状況はこちら。
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
前回のソースでは、以下のような問題で解析が途中で失敗していました。
この原因を探るため、ログ出力を強化します。
まず、マスに値を入れるタイミングでログを出します。
次に、仮置きロジックを適用する時と、仮置き前に巻き戻しをする時に、それが分かるようにログを出します。
さらに、仮置きロジックを適用する場所をログに出力するようにします。
ここまでやって、 仮置きロジックを適用する場所を探す処理に不具合がある事が分かりました。
/**
* 仮置き対象のマスを抽出する
*
* squares マス
*/
private List<Square> searchKariokiSquare(Square[,] squares)
{
List<Square> ret = null;
for (int row = 0; row < 9; row += 3)
{
for (int col = 0; col < 9; col += 3)
{
List<Square> temp = new List<Square>();
for (int i = 0; i < 3; i++)
{
for (int j = 0; j < 3; j++)
{
if (squares[row + i, col + j].isConfirmed() == false)
{
temp.Add(_square[row + i, col + j]);
}
}
}
if (ret != null) //←★ここ
{
if (ret.Count > temp.Count && temp.Count != 0)
{
ret = temp;
}
}
else
{
ret = temp;
}
}
}
return ret;
}
★の箇所で、ret=nullで、temp.Count = 0の時に、仮置きロジックを適用する箇所がない(ret.Count=0)となり、解析が終了していることが分かりました。
なので、★の箇所を修正します。
if (ret != null)
{
if (ret.Count > temp.Count && temp.Count != 0)
{
ret = temp;
}
}
else if(temp.Count != 0)
{
ret = temp;
}
解けました。
難易度★5の問題も解けるようになったので、大抵の問題は解けるようになりました。
もう少し動かしてみます。
【C#】【数独】仮置きロジックを簡略化する。
前回までの状況はこちら。
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
前回、仮置きロジックを完成させたのですが、
このコード、結構無駄な処理をやっていることに気がついたんですよ。
private Square doKarioki(Square[,] squares)
{
Square ret = null;
List<Square> kariokiList = searchKariokiSquare(squares);
foreach (var s in kariokiList)
{
bool roop = true;
int kariValue = GetUnconfirmedValue(s.GetCandidate());
if (kariValue == 0)
{
return null;
}
Square[,] copySquare = makeClone(squares);
copySquare[s.Row, s.Col].SetValue(kariValue);
int now_count = 0;
int prev_coount = 0;
while (roop)
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
if (copySquare[row, col].isConfirmed() == false)
{
Candidate candidate = new Candidate();
searchRowLine(copySquare, row, candidate);
searchColLine(copySquare, col, candidate);
search9Area(copySquare, row, col, candidate);
copySquare[row, col].checkCandidate(candidate);
}
}
}
searchNumber(copySquare);
if (checkContradict(copySquare))
{
break;
}
prev_coount = now_count;
now_count = countInputedNumber(copySquare);
if (prev_coount == now_count)
{
Console.WriteLine("仮置きロジック");
Square s2 = doKarioki(copySquare);
if (s2 == null)
{
Console.WriteLine("失敗しました");
return null;
}
else
{
copySquare[s2.Row, s2.Col].SetValue(s2.GetValue());
}
}
if (checkEnd(copySquare) == true)
{
★
roop = false;
s.SetValue(kariValue);
Console.WriteLine("[{0},{1}] = {2}", s.Row, s.Col, s.GetValue());
ret = s;
}
FileAccess.Output(copySquare);
}
if(ret != null)
{
break;
}
}
return ret;
}今までは★に入ったタイミングで仮置きした値が確定して、という処理を行っていたんですが、
実はここに入った時点で解析結果が判明しているんですよね。
なので、この時点で解析結果を出力して終了、という処理にすれば、大幅に処理が短くなるはずです。
詳細はgitHubのソースコードを参照して頂ければ。
ついでに関数ヘッダにコメント入れました。
【C#】【数独】矛盾チェック処理と仮置きロジック再帰処理の実装
前回までの状況はこちら。
最新ソースはこちら(gitHub)
いやーロジック考えるのに時間かかりました。
まず、仮置きロジックを完成させるには、仮置きした結果、矛盾が発生した、ということを検出できる用にしなければならなくて。
これが、以外と難しい。
実際のコードは短くなっても、そこにたどり着くのが難しいのです。
オイラはこのように書きました。
private bool checkContradict(Square[,] squares)
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
if(squares[row,col].isConfirmed() == false)
{
Candidate candidate = new Candidate();
searchRowLine(_square, row, candidate);
searchColLine(_square, col, candidate);
search9Area(_square, row, col, candidate);
if(candidate.Count() == 9)
{
return true;
}
}
}
}
return false;
}
値は確定していない、しかし、縦、横、9マスを調べた結果、置ける数字が無い場合、という風に考えました。
これを使って仮置きロジックを作成します。
private Square doKarioki(Square[,] squares)
{
Square ret = null;
List<Square> kariokiList = searchKariokiSquare(squares);
foreach (var s in kariokiList)
{
bool roop = true;
int kariValue = GetUnconfirmedValue(s.GetCandidate());
if (kariValue == 0)
{
return null;
}
Square[,] copySquare = makeClone(squares);
copySquare[s.Row, s.Col].SetValue(kariValue);
int now_count = 0;
int prev_coount = 0;
while (roop)
{
for (int row = 0; row < 9; row++)
{
for (int col = 0; col < 9; col++)
{
if (copySquare[row, col].isConfirmed() == false)
{
Candidate candidate = new Candidate();
searchRowLine(copySquare, row, candidate);
searchColLine(copySquare, col, candidate);
search9Area(copySquare, row, col, candidate);
copySquare[row, col].checkCandidate(candidate);
}
}
}
searchNumber(copySquare);
if (checkContradict(copySquare))
{
break;
}
prev_coount = now_count;
now_count = countInputedNumber(copySquare);
if (prev_coount == now_count)
{
Console.WriteLine("仮置きロジック");
Square s2 = doKarioki(copySquare);
if (s2 == null)
{
Console.WriteLine("失敗しました");
return null;
}
else
{
copySquare[s2.Row, s2.Col].SetValue(s2.GetValue());
}
}
if (checkEnd(copySquare) == true)
{
roop = false;
s.SetValue(kariValue);
Console.WriteLine("[{0},{1}] = {2}", s.Row, s.Col, s.GetValue());
ret = s;
}
FileAccess.Output(copySquare);
}
if(ret != null)
{
break;
}
}
return ret;
}
難しかったのが、仮置きロジックの計算中に再び仮置きロジックが必要になった場合。
そう、このロジックを再帰的に実行する処理が必要なのです。
これを実装するために、これ以外の所もかなりの広範囲で書き換えています。
しかし、これでようやく解を得ることができました。
138964275
624715398
957283614
285637941
796841523
341529786
512476839
479358162
863192457
このロジックでいろいろな問題を解いてみようと思います。
【C#】【数独】仮置き対象を抽出する
かなり時間が空いてしまいましたが。
前回までの状況はこちら。
最新ソースはこちら(gitHub)。
https://github.com/takishita2nd/sudoku
さて、実際に仮置きロジックを実装していくのですが、
そのときに必要となる情報が、
仮置きロジックをどこに適用するか
ということです。
今回は、9マスのエリアの中で、一番空きマスの少ない箇所を選択するように実装してみようと思います。
private List<Square> searchKariokiSquare(Square[,] squares)
{
List<Square> ret = null;
for(int row = 0; row < 9; row += 3)
{
for(int col = 0; col < 9; col += 3)
{
List<Square> temp = new List<Square>();
for(int i = 0; i < 3; i++)
{
for(int j = 0; j < 3; j++)
{
if(squares[row + i, col + j].isConfirmed() == false)
{
temp.Add(_square[row + i, col + j]);
}
}
}
if(ret != null)
{
if(ret.Count > temp.Count && temp.Count != 0)
{
ret = temp;
}
}
else
{
ret = temp;
}
}
}
return ret;
}
コードはこんな感じに書いてみました。
9マスエリアに対して、まだ数字が入っていないマスの数を確認します。
数字が入っていないマスのオブジェクトをリストに登録し、それが他の9マスエリアの数より少ないか、を確認します。
調査結果は数字が入っていないマスのオブジェクトのリストを返します。
では、このメソッドを使用する処理を作成します。
private void doKarioki()
{
Square[,] copySquare = makeClone(_square);
List<Square> kariokiList = searchKariokiSquare(copySquare);
foreach(var s in kariokiList)
{
Console.WriteLine("[{0},{1}]", s.Row, s.Col);
}
}
仮置き処理を実行するので、処理前にマス配列のクローンを作成します。
そして、先ほどのメソッドを使用して仮置き対象のマスをリストで取得。
そして、それに対してforeachを使って仮置きロジックを適用していきます。
Windows TerminalPS E:\Source\Repos\takishita2nd\sudoku\sudoku\bin\Debug> .\sudoku.exe .\q026.txt
仮置きロジック
[0,6]
[2,6]こんな感じで、仮置き対象のマスの抽出ができました。
うん、完成が見えてきたぞ。
【C#】【数独】仮置きロジックを適用する条件を考える。
前回までの状況はこちら。
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
さて、いよいよ仮置きロジックの実装にとりかかります。
そのためには、仮置きロジックを行う条件を考えましょう。
現在まで実装しているロジックでのみで、ある程度はマスを埋めることができますので、そのロジックでも埋まらなかった場合、と考えるのが妥当でしょう。
その条件とは、周期処理の前と後で、確定しているマスの数が同じならば、と判断するのが一番簡単だと思います。
それでは実装します。
まずは、確定しているマスを数えるメソッドを作成します。
private int countInputedNumber()
{
int ret = 0;
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(_square[i, j].isConfirmed())
{
ret++;
}
}
}
return ret;
}
特に難しいところはありませんね。
これを、周期処理に組み込みます。
private int now_count = 0;
private int prev_coount = 0;
public void run()
{
bool roop = true;
while (roop)
{
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
{
if(_square[row,col].isConfirmed() == false)
{
Candidate candidate = new Candidate();
searchRowLine(row, candidate);
searchColLine(col, candidate);
search9Area(row, col, candidate);
_square[row, col].checkCandidate(candidate);
}
}
}
searchNumber();
prev_coount = now_count;
now_count = countInputedNumber();
if(prev_coount == now_count)
{
//debug
Console.WriteLine("ここで仮置きロジックを適用する {0} {1}", prev_coount, now_count);
return;
}
roop = !checkEnd();
FileAccess.Output(_square);
}
}
こんな感じでどうでしょうか。
prev_coountが周期前の確定したマス数、now_countが周期後の確定したマス数です。
確定したマス数を数える前に前回のマス数を保存し、それと、現周期でのマス数を比較します。
これが同じならば、仮置きロジックを適用する（debug出力を行っているところ）という動きになります。
次回は、このdebugの箇所を考えていきます。
【C#】【数独】オブジェクトを複製する
前回までの状況はこちら。
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
仮置きロジックに必要な処理を実装していきます。
まずは、解析状況のデータの複製を作るところです。
仮置き解析して、矛盾があれば、そのデータを破棄するようにします。
オブジェクトの複製に=演算子を使用してはいけません。
これはオブジェクトの移動です。
C言語的に言えば、ポインタを移しているだけです。
なので、オブジェクトをnewで作成して、同じデータを持たせるように設定しなければなりません。
まずは、Squareクラス。
class Square
{
// 確定した数字
private int _value;
// 確定したかどうか
private bool _confirmed;
public Square()
{
this._value = 0;
this._confirmed = false;
}
public Square(int val)
{
this._value = val;
if(val == 0)
{
this._confirmed = false;
}
else
{
this._confirmed = true;
}
}
中略
public Square Clone()
{
return new Square(_value);
}
}
Clone()で同じデータを持つオブジェクトを作成して返しています。
次に、Sudokuクラス。
class Sudoku
{
private Square[,] _square;
中略
private Square[,] makeClone(Square[,] _square)
{
Square[,] ret = new Square[9, 9];
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
ret[i, j] = _square[i, j].Clone();
}
}
return ret;
}
}
Square[]をnewで作成し、SquareのCloneを設定し、返しています。
これでこの関数の戻り値は、完全なSquare[,]の複製が作成されます。
次回は実際に仮置きをするロジックを考えます。
【C#】【数独】解析ロジック(仮置き矛盾チェック)を考える
前回までの状況はこちら
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
さて、以下のような問題が出題されたとき、解析が止まってしまう現象が発生しました。
例えば、数字の2に注目した場合、
オレンジの2箇所と青の2箇所が数字の2が入る可能性があるのですが、今までのロジックでは値が確定しないため、解析が進まない状態となってしまいます。
この場合、仮置きというやり方をします。
例えば、
オレンジのマスに数字2を置いた場合、今までの解析ロジックから青のマスに2が入りますが、同じライン上に2がすでに存在しますので、この置き方は誤りと言うことになります。
逆に、このように置けば、矛盾が発生しませんので、このマスに入る数字は2で確定する事になります。
これをプログラムでロジック化します。
やり方をまとめます。
解析ループ処理に変化が無かった場合、仮置きロジックを適用します。
解析途中のデータを複製し、空いている箇所に、仮の値を置き、通常の解析ロジックを実施します。
その結果、矛盾が発生していれば、その複製データを破棄します。
矛盾が発生していなければ、その値で確定します。
値が確定すれば、その状態で解析を継続します。
ざっくり言えばこんな感じですね。
次回以降、もう少し細かいところを詰めて、実装していこうと思います。
【C#】【数独】解析ロジック(ラインチェック)を追加する
前回までの状況はこちら。
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
さて、前回のアルゴリズムで、いくつか問題を解いてみたのですが、
こんな問題の時、解析が完了しませんでした。
この状態のまます、解析が進まなかったんですね。
この状態、手で解いた場合、
この2箇所に「3」が入ります。
この時の解析ロジックを組み込まなければなりません。
では、どうやって解析すればいいのか。
この場合、3という数字に注目すると、
この部分、および、すでに確定されているマスに「3」が入ることができません。
赤いところの9マスは一箇所しか空いていないため、そこの空いているマスには「3」が入ることが確定されます。
これをプログラミングで行います。
考え方は、9×9の二次元配列を用意し、各数字について、入れることができないマスを埋めていき、9エリアに一箇所だけ空きがあれば、その値が確定する、とします。
private void searchNumber()
{
for(int number = 1; number <= 9; number++)
{
bool[,] tempTable = new bool[9, 9];
// 初期化
for (int i = 0; i < 9; i++)
{
for (int j = 0; j < 9; j++)
{
tempTable[i, j] = false;
}
}
// 数字が入らないところをtrueにする
for (int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(tempTable[i,j] == false)
{
tempTable[i, j] = _square[i, j].isConfirmed();
if(_square[i,j].GetValue() == number)
{
for(int row = 0; row < 9; row++)
{
tempTable[row, j] = true;
}
for(int col = 0; col < 9; col++)
{
tempTable[i, col] = true;
}
int rowStart;
int colStart;
getRowCol9Area(i, j, out rowStart, out colStart);
for (int r = rowStart; r < rowStart + 3; r++)
{
for (int c = colStart; c < colStart + 3; c++)
{
tempTable[r, c] = true;
}
}
}
}
}
}
// debug
FileAccess.Output(tempTable);
// 結果を確認する
for(int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(tempTable[i,j] == false)
{
int rowStart;
int colStart;
getRowCol9Area(i, j, out rowStart, out colStart);
int count = 0;
for (int r = rowStart; r < rowStart + 3; r++)
{
for (int c = colStart; c < colStart + 3; c++)
{
if(tempTable[r,c] == false)
{
count++;
}
}
}
if(count == 1)
{
_square[i, j].SetValue(number);
}
}
}
}
}
}
private void getRowCol9Area(int row, int col, out int rowStart, out int colStart)
{
if (row >= 0 && row <= 2)
{
rowStart = 0;
}
else if (row >= 3 && row <= 5)
{
rowStart = 3;
}
else
{
rowStart = 6;
}
if (col >= 0 && col <= 2)
{
colStart = 0;
}
else if (col >= 3 && col <= 5)
{
colStart = 3;
}
else
{
colStart = 6;
}
}
一応、色塗りした処理結果もデバッグ用に出力させました。
３の時の色塗り結果を見てみると、９マスで一か所だけ空きがあることが分かります。
目論見通り、３が確定されました。
全部埋まりました。
ロジックがうまく働いたようです。
【C#】【数独】終了判定を実装する
前回までの状況はこちら
最新ソースはこちら(gitHub)
https://github.com/takishita2nd/sudoku
さて、最後に解析終了処理を実装していきます。
解析終了条件は、9×9＝81マス全ての数字が確定した場合、になります。
逆に言えば、81マスの中で、一つでも確定していないマスがあれば、終了しない、と言うことになります。
と言うわけで、コードはこうなりました。
private bool checkEnd()
{
for (int i = 0; i < 9; i++)
{
for(int j = 0; j < 9; j++)
{
if(_square[i, j].isConfirmed() == false)
{
return false;
}
}
}
return true;
}
解析終了ならばtrueを、そうでないならばfalseを返します。
これを周回処理に組み込みます。
public void run()
{
bool roop = true;
while (roop)
{
for(int row = 0; row < 9; row++)
{
for(int col = 0; col < 9; col++)
{
if(_square[row,col].isConfirmed() == false)
{
Candidate candidate = new Candidate();
searchRowLine(row, candidate);
searchColLine(col, candidate);
search9Area(row, col, candidate);
_square[row, col].checkCandidate(candidate);
}
}
}
roop = !checkEnd();
FileAccess.Output(_square);
}
}
ループ条件と判定結果が反転しているので、!演算子で反転させています。
実行結果はこちら。
ちゃんと全部埋まった時点で終了しました。