создать матрицу 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

Вы можете быть запущен из стека, потому что в «худшем» случае, т.е. при завершении строительства доски, у вас есть 81 вызовов NextCell + 1 к законMove. Я не человек Java, но первое, что нужно попробовать, чтобы избавиться от переменных в начале из nextCall:

int nextX = x; 
int nextY = y; 

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

- это случайный объект может быть разделен между вызовами; , если вам нужно использовать nextX, nextY (который вы не на самом деле) пытаются использовать их внутри блока "если (legalMove (х, у, toCheck [я])) {"; не использовать верх, просто инициализируйте цикл var с помощью toCheck.length; объявить tmp внутри «тасования». В целом, если ваши переменные как можно более локальные, это хорошая практика не только из-за управления памятью.

Если это не поможет (что вполне возможно), то вы можете попробовать использовать собственную структуру управления - стек, содержащий только х с, Y с и toCheck с, пытается всегда сначала из стека, пока не закончите toCheck s. Вот пример реализации расслоение плотной (я включаю все это просто так, что вы можете проверить это, например, в вашем браузере, но вы заинтересованы только в коде для 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) предложил другой (без обратного отслеживания) метод создания плат, переставляя [группы] строк и столбцов уже подготовленного (одной такой предварительно вычисленной платы достаточно, чтобы генерировать ~ 46 тыс. новых) - это может быть лучше всего для вашей настройки.