前回までの状況はこちら。
最新ソースはこちら(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
このロジックでいろいろな問題を解いてみようと思います。
