c++从大小为n的空矩阵创建填充的数独网格

Question

我正在尝试编写一个程序来创建一个大小为 N 的矩阵，并在其中放入数字，以便使用回溯法在同一列/行中没有重复的数字。

1) Put value in cell. If it's a repeat, try a different value.
2) If no such value exists, backtrack 1 cell, and change the value.  //recursive

但是，最高数字有时会重复几次。例如:

3 1 2     3 1 2 4 5          2 4 1 3 6 5
1 3 3     2 3 1 5 4          4 3 2 5 1 6
2 3 1     1 2 5 3 5 <        1 5 3 2 4 6
          4 5 3 1 2          5 1 6 4 2 3
          5 4 5 2 1 <        6 2 4 1 3 6 <
              ^              3 6 5 6 6 4 <
                                     ^

这是它正在做的事情:一旦用完了要放入单元格的数字(即:全部受限，它将 N 放入)

3 1 2 4          3 1 2 4          3 1 2 4          3 1 2 4
1 2 3 0    ->    1 2 3 3    ->    1 2 3 4   ->     1 2 3 4
0 0 0 0          0 0 0 0          0 0 0 0          2 0 0 0
0 0 0 0          0 0 0 0          0 0 0 0          0 0 0 0

我真的卡在这里了，希望有人能找到我代码中的错误:

int **grid;                                //2d dynamic array of size 'size'
bool checkRepeat(size,**grid,row,column);  //checks if a number in a column/row is a repeat
int backtrack = 0;
int holder = 0;                            //when backtracking, this holds the number that should be changed


bool checkRepeat(int x, int** grid, int row, int col){
    for (int i = 0; i < x; i++){
        if (grid[row][col] == grid[row][i] && col != i){
            return true;
        }
    }
    for (int j = 0; j < x; j++){
        if (grid[row][col] == grid[j][col] && row != j){
            return true;
        }
    }
    return false;
}

int main(){
for (int row = 0; row < size; row++){
        for (int col = 0; col < size; col++){

            if (backtrack == 0){
                    grid[row][col] = rand() % size + 1;
            }

            if (backtrack == 1){       //If backtracking, go back one cell.
                grid[row][col] = 0;        //(Since the above for loops went one
                if (col == 0){           //cell forward, go 2 cells back)
                    col = size - 2;
                    row--;
                } else if (col == 1){
                    col = size - 1;
                    row--;
                } else {
                    col-=2;
                }
                holder = grid[row][col];   //put the current number into holder to avoid it
                backtrack = 0;

            }

    /*the following checks if the number in the current cell is
      a repeat and makes sure the number isn't the same as
      before (holder).  Then it checks all possible numbers (1 to size)
      and puts one that matches the rules. If one is not found,
      program backtracks 1 cell*/

            if (checkRepeat(size,grid,row,col) && grid[row][col] > 0){  
                for (int x = 1; x < size+1 && (checkRepeat(x,grid,row,col) || holder == grid[row][col]); x++){

                grid[row][col] = x;
                }
            } 

            if (grid[row][col] == checkRepeat(size,grid,row,col) || grid[row][col] == holder){
                backtrack = 1;        //if no valid number was found in the above
                grid[row][col] = 0;
            }
            holder = 0;
        }
    }

Answer 1

所以我在解决方案上可能有点过头了，但我认为这对我来说是一个很好的挑战。基本思想是 fill(row, col) 是一个递归函数。首先它检查停止条件:如果网格的填充部分无效(数字在行或列中重复)，它将返回 false。如果尝试填充超出网格大小的内容，它也会返回 false。

如果两个停止条件都不满足，它将尝试为网格元素取一个值并尝试“填充网格的其余部分”(也就是递归调用 fn)。只要“填充剩余”操作失败并且它没有尝试所有有效值，它就会做这些事情。如果它已经尝试了所有有效值并且“填充剩余”操作仍然失败，它将值重置为 0。最后它返回“填充剩余”操作是失败还是成功。

#include <vector>
#include <iostream>
#include <cstdlib>
#include <numeric>
#include <time.h>
#include <string>
#include <sstream>

using std::vector;

// helper for std::accumulate
bool logical_and(bool x, bool y) {
  return x & y;
}

class Grid {
public:
  typedef int ElementType;
  typedef vector< vector<ElementType> > GridElements;

  Grid(const int linesize) :
  linesize_(linesize)
  {
    srand(time(NULL));

    // resizes to linesize_ rows & columns, with initial values == 0
    gridElements_.resize(linesize_, vector<ElementType>(linesize_, 0));
  }

  // use like this: cout << grid.to_s();
  std::string to_s() const {
    std::stringstream ss;
    for (int row = 0; row < gridElements_.size(); row++) {
      for (int col = 0; col < gridElements_[row].size(); col++) {
    ss << gridElements_[row][col] << " ";
      }
      ss << std::endl;
    }

    ss << std::endl;

    return ss.str();
  }

  // return true if there are no repeated numbers within filled elements in
  // rows/columns, false otherwise
  bool isValid() const {
    // you would also need to write and call a checkSquare method if you're doing a sudoku puzzle
    for (int i = 0; i < linesize_; i++) {
      if (!isRowValid(i) || !isColValid(i)) {
    return false;
      }
    }

    return true;
  }

  // the recursive function that actually puts values in the grid elements
  // max recursion depth (I think) is linesize_^2
  bool fill(int row, int col) {
    // stopping conditions
    if (!isValid()) {
      return false;
    }
    if ((row == linesize_) || (col == linesize_)) {
      return true;
    }

    int nextCol = (col + 1) % linesize_;
    int nextRow = row;
    if (nextCol < col) {
      nextRow++;
    }

    // keep a record of what numbers have been tried in this element
    vector<bool> attemptedNumbers(linesize_ + 1, false);
    attemptedNumbers[0] = true;

    // We will continue choosing values for gridElements_[row][col]
    // as long as we haven't tried all the valid numbers, and as long as
    // the rest of the grid is not valid with this choice
    int value = 0;
    bool triedAllNumbers = false;
    bool restOfGridValid = false;
    while (!triedAllNumbers && !restOfGridValid) {
      while (attemptedNumbers[value]) {
        value = rand() % linesize_ + 1;
      }
      attemptedNumbers[value] = true;
      gridElements_[row][col] = value;

      // uncomment this for debugging/intermediate grids
      //std::cout << to_s();

      // triedAllNumbers == true if all the numbers in [1, linesize_] have been tried
      triedAllNumbers = std::accumulate(attemptedNumbers.begin(), attemptedNumbers.end(), true, logical_and);
      restOfGridValid = fill(nextRow, nextCol);
    } 
    if (triedAllNumbers && !restOfGridValid) {
      // couldn't find a valid number for this location
      gridElements_[row][col] = 0;
    }

    return restOfGridValid;
  }

private:
  // checks that a number is used only once in the row
  // assumes that values in gridElements_ are in [1, linesize_]
  // return false when the row contains repeated values, true otherwise
  bool isRowValid(int row) const {
    vector<bool> numPresent (linesize_ + 1, false);

    for (int i = 0; i < linesize_; i++) {
      int element = gridElements_[row][i];

      if (element != 0) {
    if (numPresent[element]) {
      return false;
    }
    else {
      numPresent[element] = true;
    }
      }
      // don't do anything if element == 0
    }

    return true;
  }

  // checks that a number is used only once in the column
  // assumes that values in gridElements_ are in [1, linesize_]
  // return false when the column contains repeated values, true otherwise
  bool isColValid(int col) const {
    vector<bool> numPresent (linesize_ + 1, false);

    for (int i = 0; i < linesize_; i++) {
      int element = gridElements_[i][col];

      if (element != 0) {
    if (numPresent[element]) {
      return false;
    }
    else {
      numPresent[element] = true;
    }
      }
      else {
    // if element == 0, there isn't anything left to check, so just leave the loop
    break;
      }
    }

    return true;
  }

  // the size of each row/column
  int linesize_;

  // the 2d array
  GridElements gridElements_;
};


int main(int argc, char** argv) {
  // 6x6 grid
  Grid grid(6);

  // pretty sure this is mathematically guaranteed to always return true, assuming the algorithm is implemented correctly ;)
  grid.fill(0, 0);

  std::cout << grid.to_s();
}