在堆栈等资源有限的机器上无需递归即可创建数独矩阵
create Sudoku matrix without recursion on machine with limited resources like stack
我正在尝试为内存资源非常有限的 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;
}
您可能 运行 出栈 space，因为在 "worst" 情况下，即完成构建板时，您有 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（您实际上不需要），请尝试在 [ 的块内使用它们=53=];
不要使用 top，只需使用 toCheck.length 初始化循环变量；
在 "shuffling loop" 中声明 tmp。
一般来说，尽可能保持变量本地化是一个很好的实践，不仅仅是因为内存管理。
如果这没有帮助（这很有可能），那么您可以尝试使用自己的控制结构——一个仅包含 xs、 的堆栈ys 和 toChecks,
始终尝试堆栈中的第一个，直到 运行 超出 toChecks。这是一个示例 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 :))
}
如果仍然不符合你的记忆，你必须修改你的算法。也许您可以利用每个 row/column 都是一组正数的排列这一事实？如果你 运行 没有想法，Whosebug 上的某个人（我在 sudoku 标签下的某个地方看到过它）建议了另一种（非回溯）生成板的方法，通过排列已经准备好的 [组] 行和列（一个这样的预计算板足以生成 ~46k 新板）——这可能是您设置的最佳选择。
我正在尝试为内存资源非常有限的 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;
}
您可能 运行 出栈 space，因为在 "worst" 情况下，即完成构建板时，您有 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（您实际上不需要），请尝试在 [ 的块内使用它们=53=]; 不要使用 top，只需使用 toCheck.length 初始化循环变量； 在 "shuffling loop" 中声明 tmp。 一般来说，尽可能保持变量本地化是一个很好的实践，不仅仅是因为内存管理。
如果这没有帮助（这很有可能），那么您可以尝试使用自己的控制结构——一个仅包含 xs、 的堆栈ys 和 toChecks, 始终尝试堆栈中的第一个，直到 运行 超出 toChecks。这是一个示例 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 :))
}
如果仍然不符合你的记忆，你必须修改你的算法。也许您可以利用每个 row/column 都是一组正数的排列这一事实？如果你 运行 没有想法，Whosebug 上的某个人（我在 sudoku 标签下的某个地方看到过它）建议了另一种（非回溯）生成板的方法，通过排列已经准备好的 [组] 行和列（一个这样的预计算板足以生成 ~46k 新板）——这可能是您设置的最佳选择。