网格在void(sudoku)之后不记得

Question

我在早期编程阶段都在修补一个脱颖而出。以下sudoku求解器是在有1个解决方案时打印结果的均值，并且仅在有更多解决方案的情况下（因此在这种情况下显示没有解决方案）。问题是：如果我从solveit（）打印（），我将输入sudoku作为输出。如果我从solve（）打印（）。

是否有一种方法可以存储已解决的网格，以便我可以从solveit（）中调用它，或者我可以打印（）conly的解决方案的数量而不会失去单个解决方案的能力，如果只有一个解决方案？

完整的代码在下面找到

class Sudoku {
int SIZE = 9;     // size of the grid
int DMAX = 9;     // maximal digit to be filled in
int BOXSIZE = 3;  // size of the boxes (subgrids that should contain all digits)
int[][] grid;     // the puzzle grid; 0 represents empty
int rempty = 0;
int cempty = 0;
// a challenge-sudoku from the web
int[][] somesudoku = new int[][] {         
    { 0, 6, 0,   0, 0, 1,    0, 9, 4 },    //original; one solution     
        //{ 0, 0, 0,   0, 0, 1,    0, 9, 4 }, //to get more solutions
    { 3, 0, 0,   0, 0, 7,    1, 0, 0 }, 
    { 0, 0, 0,   0, 9, 0,    0, 0, 0 }, 
    { 7, 0, 6,   5, 0, 0,    2, 0, 9 }, 
    { 0, 3, 0,   0, 2, 0,    0, 6, 0 }, 
    { 9, 0, 2,   0, 0, 6,    3, 0, 1 }, 
    { 0, 0, 0,   0, 5, 0,    0, 0, 0 }, 
    { 0, 0, 7,   3, 0, 0,    0, 0, 2 }, 
    { 4, 1, 0,   7, 0, 0,    0, 8, 0 }, 
};
int solutionnr = 0; //solution counter
// ----------------- conflict calculation --------------------
// is there a conflict when we fill in d at position r,c?
boolean givesConflict(int r, int  c, int n) {
    if (rowConflict(r, n) == true || colConflict(c, n) == true || boxConflict(r, c, n) == true) {
        return true;
    }
    return false;
}
boolean rowConflict(int r, int n) {
    for (int i = 0; i < 9; i++) {
        if (grid[r][i] == n) {
            return true;
        }
    }
    return false;
}
boolean colConflict(int c, int n) {
    for (int i = 0; i < 9; i++) {
        if (grid[i][c] == n) {
            return true;
        }
    }
    return false;
}
boolean boxConflict(int rr, int cc, int n) {
    int r = (rr / 3) * 3;
    int c = (cc / 3) * 3;
    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (grid[r + i][c + j] == n) {
                return true;
            }
        }
    }
    return false;
}

// --------- solving ----------
// finds the next empty square (in "reading order")
// writes the coordinates in rempty and cempty
// returns false if there is no empty square in the current grid
int[] findEmptySquare() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++) {
            if (grid[i][j] == 0) {
                int [] coordinateOfEmptySquare = {i, j};
                rempty = i;
                cempty = j;
                return coordinateOfEmptySquare;
            }
        }
    }
    solutionnr++;
    return null;
}
// prints all solutions that are extensions of current grid
// leaves grid in original state
void solve() {
    // if there are no empty squares left we print the current solution
    if (findEmptySquare() == null) {
        return;
    } 
    int r = rempty;
    int c = cempty;
    for (int i = 1; i <= 9; i++) {
        if (!givesConflict(r, c, i)) {
            grid[r][c] = i;
            solve();
            grid[r][c] = 0;
        }
    }
    //fill in
}
// ------------------------- misc -------------------------
// print the grid, 0s are printed as spaces
void print() {
    for (int i = 0; i < 10; i++) {
        if (i == 0 || i == 9) {
            System.out.println("+-----------------+");
        }
        if (i == 3 || i == 6) {
            System.out.println("-------------------");
        }
        if (i == 9) {
            break;
        }
        System.out.print("|");
        for (int j = 0; j < 3; j++) {
            if (j == 1 || j == 2) {
                System.out.print(" ");
            }
            if (grid[i][j] == 0) {
                System.out.print(" ");
            } else { System.out.print(grid[i][j]);
            }
        }
        System.out.print("|");
        for (int j = 3; j < 6; j++) {
            if (j == 4 || j == 5) {
                System.out.print(" ");
            }
            if (grid[i][j] == 0) {
                System.out.print(" ");
            } else { System.out.print(grid[i][j]);
            }
        }
        System.out.print("|");
        for (int j = 6; j < 9; j++) {
            if (j == 7 || j == 8) {
                System.out.print(" ");
            }
            if (grid[i][j] == 0) {
                System.out.print(" ");
            } else { System.out.print(grid[i][j]);
            }
        }
        System.out.print("|");
        System.out.println();
    }
    //fill in 
}
// --------------- where it all starts --------------------
void solveIt() {
    grid = somesudoku;
    solve();
    print();
    if (solutionnr > 1) {
        System.out.println(solutionnr);
    }
    //fill in
}

public static void main(String[] args) {
    new Sudoku().solveIt();
}

}

Answer 1

以保持您当前的策略，但要在结尾处打印完整的板，将此件添加到 solve()：

if(findEmptySquare() == null)
{
  savedSolution = new int[9][9];
  for(int i = 0; i < 9; i++)
  {
    for(int j = 0; j < 9; j++)
    {
      savedSolution[i][j] = grid[i][j];
    }
  {
  return;
}

savedSolution必须是诸如 grid之类的成员变量。您必须保存一个单独的深拷贝，因为您要重新归零网格以详尽地搜索所有解决方案分支。