スタックのようなリソースが限られているマシンで反復なしでSudoku行列を作成する

Question

私は非常に限られたメモリリソースを持つ時​​計用のアプリケーションを作成しようとしています。限られたシステムリソースと再帰を伴わずに毎回ランダムな数独を生成したい場合は、入力を与えることができます。私は現在、スタックオーバーフロー例外を与えている以下のコードを使用しています。

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

ボードを構築完了したときに「最悪」の場合には、つまり、あなたがにnextCell + 1から81回の呼び出しを持っているので、あなたは、スタック領域が不足している可能性がありますlegalMove。私はJavaの人だありませんが、試して最初にすることはnextCallの初めに変数を取り除くことです。

int nextX = x; 
int nextY = y; 

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

- このランダムオブジェクトが呼び出しの間で共有される可能性があります。 あなたは（あなたが実際にしない）"もし（legalMove（X、Y、toCheck [I]））{"のブロックの中でそれらを使用しようとするnextYnextX、を使用する必要がある場合。 を使用しないでください。のループ変数を~Check.lengthに初期化してください。 tmpを「シャッフルループ」内に宣言します。 あなたの変数を可能な限りローカルに保つことは、メモリー管理のためだけでなく、実用的です。

それは、あなたがあなた自身の制御構造を使用しようとすることができます（かなり可能である）解決しない場合 - のみX S、Y sおよび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 :)) 
} 

いる場合まだあなたの記憶に合っていない、あなたのアルゴリズムを変更する必要があります。たぶんあなたは、各行/列が正の数字の組の順列であるという事実の利益を得ることができますか？あなたがアイデアを使い果たした場合、誰かがスタックオーバーフロー（私はそれをsudokuタグの下に見た）は、既に作成された[グループの]行と列を置換することによって、ボードを生成する別の（バックトラッキングではない） （そのような1つの計算済みのボードは、〜46kの新しいボードを生成するのに十分です） - これはあなたのセットアップにとって最高のものかもしれません。