java - 在堆栈等资源有限的机器上无需递归即可创建数独矩阵

Question

我正在尝试为内存资源非常有限的 watch 创建一个应用程序，当我使用递归生成数独矩阵时，出现堆栈溢出异常。如果我仍然想每次生成一个随机数独但系统资源有限且没有递归，有人可以给我任何输入吗？我目前正在使用下面的代码，它给出了堆栈溢出异常。

package test;

import java.util.*;
import java.text.*;

/**
* The SudokuGenerator class creates a random standard (9x9) Sudoku board
* through the use of backtracking techniques.
*/
public class validS {
public static final int BOARD_WIDTH = 9;
public static final int BOARD_HEIGHT = 9;

/**
 * Constructor. Resets board to zeros
 */
public validS() {
    board = new int[BOARD_WIDTH][BOARD_HEIGHT];
}

/**
 * Driver method for nextBoard.
 *
 * @param difficult
 *            the number of blank spaces to insert
 * @return board, a partially completed 9x9 Sudoku board
 */
public int[][] nextBoard(int difficulty) {
    board = new int[BOARD_WIDTH][BOARD_HEIGHT];
    nextCell(0, 0);
    makeHoles(difficulty);
    return board;

}

/**
 * Recursive method that attempts to place every number in a cell.
 *
 * @param x
 *            x value of the current cell
 * @param y
 *            y value of the current cell
 * @return true if the board completed legally, false if this cell has no
 *         legal solutions.
 */
public boolean nextCell(int x, int y) {
    int nextX = x;
    int nextY = y;
    int[] toCheck = { 1, 2, 3, 4, 5, 6, 7, 8, 9 };
    Random r = new Random();
    int tmp = 0;
    int current = 0;
    int top = toCheck.length;

    for (int i = top - 1; i > 0; i--) {
        current = r.nextInt(i);
        tmp = toCheck[current];
        toCheck[current] = toCheck[i];
        toCheck[i] = tmp;
    }

    for (int i = 0; i < toCheck.length; i++) {
        if (legalMove(x, y, toCheck[i])) {
            board[x][y] = toCheck[i];
            if (x == 8) {
                if (y == 8)
                    return true;// We're done! Yay!
                else {
                    nextX = 0;
                    nextY = y + 1;
                }
            } else {
                nextX = x + 1;
            }
            if (nextCell(nextX, nextY))
                return true;
        }
    }
    board[x][y] = 0;
    return false;
}

/**
 * Given a cell's coordinates and a possible number for that cell, determine
 * if that number can be inserted into said cell legally.
 *
 * @param x
 *            x value of cell
 * @param y
 *            y value of cell
 * @param current
 *            The value to check in said cell.
 * @return True if current is legal, false otherwise.
 */
private boolean legalMove(int x, int y, int current) {
    for (int i = 0; i < 9; i++) {
        if (current == board[x][i])
            return false;
    }
    for (int i = 0; i < 9; i++) {
        if (current == board[i][y])
            return false;
    }
    int cornerX = 0;
    int cornerY = 0;
    if (x > 2)
        if (x > 5)
            cornerX = 6;
        else
            cornerX = 3;
    if (y > 2)
        if (y > 5)
            cornerY = 6;
        else
            cornerY = 3;
    for (int i = cornerX; i < 10 && i < cornerX + 3; i++)
        for (int j = cornerY; j < 10 && j < cornerY + 3; j++)
            if (current == board[i][j])
                return false;
    return true;
}

/**
 * Given a completed board, replace a given amount of cells with 0s (to
 * represent blanks)
 *
 * @param holesToMake
 *            How many 0s to put in the board.
 */
public void makeHoles(int holesToMake) {
    /*
     * We define difficulty as follows: Easy: 32+ clues (49 or fewer holes)
     * Medium: 27-31 clues (50-54 holes) Hard: 26 or fewer clues (54+ holes)
     * This is human difficulty, not algorighmically (though there is some
     * correlation)
     */
    double remainingSquares = 81;
    double remainingHoles = (double) holesToMake;

    for (int i = 0; i < 9; i++)
        for (int j = 0; j < 9; j++) {
            double holeChance = remainingHoles / remainingSquares;
            if (Math.random() <= holeChance) {
                board[i][j] = 0;
                remainingHoles--;
            }
            remainingSquares--;
        }
}

/**
 * Prints a representation of board on stdout
 */
public void print() {
    for (int i = 0; i < 9; i++) {
        for (int j = 0; j < 9; j++)
            System.out.print(board[i][j] + "  ");
        System.out.println();
    }
    System.out.println();
}

public static void main(String[] args) {
    validS sg = new validS();
    sg.nextBoard(70);
    sg.print();
}

int[][] board;
private int operations;

Answer 1

您可能会用完堆栈空间，因为在“最坏”的情况下，即完成构建板时，您有 81 次调用 nextCell + 1 次调用 legalMove。我不是 Java 用户，但首先要尝试的是去掉 nextCall 开头的变量:

int nextX = x;
int nextY = y;

Random r = new Random();
int tmp = 0;
int current = 0;
int top = toCheck.length;

-- 这个Random 对象可以在调用之间共享； 如果您需要使用 nextX、nextY(实际上您不需要)尝试在 "if (legalMove(x, y, toCheck[i])) {"; 不要使用 top，只需使用 toCheck.length 初始化循环变量； 在“洗牌循环”中声明 tmp。 一般来说，尽可能保持变量本地化是一种很好的做法，这不仅是因为内存管理。

如果这没有帮助(这是很有可能的)，那么您可以尝试使用您自己的控制结构——一个仅包含 x、y 和检查， 始终尝试堆栈中的第一个，直到用完toCheck。这是一个示例 js 实现(我包含了整个内容，以便您可以在浏览器中对其进行测试，但您只对 buildBoard() 的代码感兴趣):

var rand = function(uppBnd) { return(Math.floor(Math.random()*uppBnd)); };
var board = null; /// just for the scoping

function mkEmptyBoard(h,w) { /// can't think of other way to initialize hxw array in js
  var b=[];
  for(i=0;i<h;i++) {
    var r=[];
    for(j=0;j<w;j++) r.push(0);
    b.push(r);
  }
  return b;
}

/// this one is taken from your code, btw you can make this corner things easier.
function legalMove(x,y,current) {
  for (var i = 0; i < 9; i++) {
    if (current == board[x][i])
        return false;
  }
  for (var i = 0; i < 9; i++) {
    if (current == board[i][y])
        return false;
  }
  var cornerX = 0;
  var cornerY = 0;
  if (x > 2)
    if (x > 5)
      cornerX = 6;
    else
      cornerX = 3;
    if (y > 2)
    if (y > 5)
      cornerY = 6;
    else
      cornerY = 3;
  for (var i = cornerX; i < 10 && i < cornerX + 3; i++)
    for (var j = cornerY; j < 10 && j < cornerY + 3; j++)
      if (current == board[i][j])
        return false;
  return true;
}

function nextPos(x,y) { if(x<8) return [x+1,y]; else return [0,y+1]; }

function mkToCheck() { /// this one just builds your "suffled array"
  var toCheck = [];
  for(var i=0;i<9;i++) toCheck.push(i+1);
  for(var i = toCheck.length - 1; i > 0; i--) {
    var tmp;
    current = rand(i);
    tmp = toCheck[current];
    toCheck[current] = toCheck[i];
    toCheck[i] = tmp;
  }
  return toCheck;
}

/// THE THING IS HERE:
function buildBoard() {
  board = mkEmptyBoard(9,9);    
  var stck = [{'x':0,'y':0,'check': mkToCheck()}];    
  while(stck.length>0) {
    while(stck[0].check.length>0) {
      var ch = stck[0].check.shift();
      if(legalMove(stck[0].x, stck[0].y, ch)) {
        board[stck[0].x][stck[0].y] = ch;
        if(stck[0].y==8 && stck[0].x==8) return true; /// yay! board is ready
        var nextpos = nextPos(stck[0].x, stck[0].y);
        stck.unshift({'x':nextpos[0],'y':nextpos[1],'check':mkToCheck()});
        break;
      }
    }
    if(stck[0].check.length==0) { /// a bind alley -- revert!
      board[stck[0].x][stck[0].y]=0;
      stck.shift();
    }
  }
  board=mkEmptyBoard(); // clear the board as this is
  return false; /// a complete failure (hopefully notreached :))
}

如果仍然不符合您的内存，您必须修改您的算法。也许您可以利用每行/每列都是一组正数的排列这一事实来获利？如果你的想法用完了，stackoverflow 上的某个人(我在 sudoku 标签下的某处看到了它)建议了另一种(非回溯)生成板的方法，通过排列[组]行和已经准备好的列(一个这样的预计算板足以生成 ~46k 新的)——这可能是您设置的最佳选择。