4

だから私は数独ソルバーを C++ で書いていて、ちょっとした障害に遭遇しました。以下は私のソルブボードコードです。パズルの最初の 3 行では機能しますが、4 行目の最後にヒットすると元に戻ります。gdb のコードを見ると、4 行目の最後に到達し、6 列目に戻って試行し、最後まで再帰を解除します。

コードに関する他のいくつかの注意事項は、数独ボードを保持するマトリックスであり、0,0 ではなく 1,1 で始まります。したがって、solveBoard が最初に呼び出されたときのパラメーターは (1, 1, 0) です。さらに詳しく知るために、setCell および checkConflicts 関数も添付しました。それぞれの行、列、または正方形に既に配置されている値を格納するために、rowConf、colConf、および squConf の 3 つのベクトルがあります。私は何時間もこれに取り組んできましたが、3列目を超えることはできません。どんな援助も大歓迎です。ありがとう！

編集: clearCell() を追加

bool board::solveBoard(int i, int j, int count)
{

    if (j > 9)
    {
        j = 1;
        i++;

        printBoard();
        if (isSolved())
        {
            printBoard();
            cout <<"The Board has been solved!" <<endl
                 <<" The number of recursive calls was: " <<count <<endl;
            return true;
        }
     }

     if (isBlank(i, j))
     {
         for (int n = 1; n < 10; n++)
         {
             if (setCell(i, j, (char)n + '0'))
             {
                 if (solveBoard(i, j + 1, count + 1))
                 {
                     return true;
                 }
              }
          }
      }
      else
      {
          return (solveBoard(i, j + 1, count + 1));
      }

      clearCell(i, j);
      return false;
}

bool board::setCell(int i, int j, char val)
{
    int intVal;

    intVal = atoi(&val);

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize &&
        intVal >= 1 && intVal <= BoardSize)
    {
        if (!(checkConflicts(intVal, i, j, squareNumber(i, j))))
        {
        return false;
        }

        value[i][j] = intVal;

        // Set flags of the conflicts
        rowConf[i][intVal] = true;
        colConf[j][intVal] = true;
        squConf[squareNumber(i, j)][intVal] = true;

        return true;
    }
    else
    {
        throw rangeError("bad value in setCell");
    }
}

bool board::checkConflicts(int val, int i, int j, int k)
{
    if (i < 1 && i > BoardSize && j < 1 && j > BoardSize &&
        k < 1 && k > BoardSize && val < 1 && val > BoardSize)
    {
        throw rangeError("bad value in checkConflicts()");
    }

    if (rowConf[i][val] || colConf[j][val] || squConf[k][val])
    {
        return false;
    }
    else
    {
        return true;
    }
}

Initial Board:
 -----------------------------
| 3       |    8    |          -----------------------------
|         | 7       |       5  -----------------------------
| 1       |         |          ----------------------------- 
 -----------------------------
|         |         | 3  6     -----------------------------
|       2 |       4 |          -----------------------------
|    7    |         |          -----------------------------
 -----------------------------
|         |    6    | 1  3     -----------------------------
|    4  5 | 2       |          -----------------------------
|         |         | 8        -----------------------------
 -----------------------------

Final Output:
 -----------------------------
| 3  2  4 | 1  8  5 | 6  7  9  -----------------------------
| 6  8  9 | 7  2  3 | 4  1  5  -----------------------------
| 1  5  7 | 4  9  6 | 2  8  3  -----------------------------
 -----------------------------
|         |         | 3  6     -----------------------------
|       2 |       4 |          -----------------------------
|    7    |         |          -----------------------------
 -----------------------------
|         |    6    | 1  3     -----------------------------
|    4  5 | 2       |          -----------------------------
|         |         | 8        -----------------------------
 -----------------------------

void board::clearCell(int i, int j)
{
    int intVal;

    if (i >= 1 && i <= BoardSize && j >= 1 && j <= BoardSize)
    {
        if (value[i][j] != -1)
        {
            intVal = value[i][j];
            rowConf[i][intVal] = false;
            colConf[j][intVal] = false;
            squConf[squareNumber(i, j)][intVal] = false;
            value[i][j] = -1;
         }
    }
    else
    {
        throw rangeError("bad value in setCell");
    }
}
4

2 に答える 2

0

この関数は引数として文字列atoiを想定しています。これは、文字ASCII NUL で終了する char の配列です。文字へのポインタ (文字の配列と同等) であるパラメータを指定しますが、それがゼロで終了することを保証しません。と交換してください'\0'intVal = atoi(&val);intVal = (int)val - '0';

そして、最初の の代わりに演算子checkConflictsが必要です。||&&if

これらはおそらくエラーの理由ではありませんが、確かに修正が必要です。

于 2014-03-09T00:48:02.717 に答える
0

あなたの問題はおそらくここにあります：

if (isBlank(i, j))
 {
     for (int n = 1; n < 10; n++)
     {
         if (setCell(i, j, (char)n + '0'))
         {
             if (solveBoard(i, j + 1, count + 1))
             {
                 return true;
             }
          }
      }
  }

どういうわけかこのセクションを通過しているためelse、最終的には通過していませんが、以前に戻っていないため、スタックします。

これにはさらにデバッグが必要ですが、解決策につながる可能性のあるアイデアを次に示します。

if (isBlank(i, j))
{
    for (int n = 1; n < 10; n++)
    {
        if (setCell(i, j, (char)n + '0'))
        {
            if (solveBoard(i, j + 1, count + 1))
            {
                return true;
            } else {
                echo 'Looks like it ended on the farthest-level..';
          } 
      } else {
          echo 'Looks like it ended on the second-farthest level.';
      }
  }
于 2012-11-05T14:54:10.303 に答える