报错是StackOverflow,自己感觉自己算法对空间的要求并不高,自我感觉写的也是尾递归,不明白自己错误的关键所在,希望能教自己一下
class Solution { int[][] rows = new int[9][9]; int[][] col = new int[9][9]; int[][] sbox = new int[9][9]; Stack<char[][]> boardst=new Stack<>(); Stack<Integer> rowstack=new Stack<>(); Stack<Integer> colstack=new Stack<>(); Stack<Integer> numstack=new Stack<>(); public void solveSudoku(char[][] board) { for (int i = 0; i < board.length; i++) { for (int j = 0; j < board[0].length; j++) { if (board[i][j]!='.'){ int num = board[i][j] - '1'; int index_box = (i/3)*3+j/3; rows[i][num]=1; col[j][num]=1; sbox[index_box][num]=1; } } } boardst.push(board); rowstack.push(0); colstack.push(0); numstack.push(1); recursion(board,0,0,1); } public void recursion(char[][]board,int row,int column,int num) { //需要换到下一行 if(column==9) recursion(board,row+1,0,num); //终止条件 else if(row==9); //位置已有数 else if(board[row][column]!='.') recursion(board,row,column+1,1); //位置无数 else if(board[row][column]=='.') { if(num==10) { //回溯——还原上一次更改时的状态 rows[rowstack.peek()][numstack.peek()-1]=0; col[colstack.peek()][numstack.peek()-1]=0; sbox[(rowstack.peek()/3)*3+colstack.peek()/3][numstack.peek()-1]=0; recursion(boardst.pop(),rowstack.pop(),colstack.pop(),numstack.pop()+1); } else { for(int i=num;i<=9;i++) { if(rows[row][i-1]==0&&col[column][i-1]==0&&sbox[(row/3)*3+column/3][i-1]==0) { //每做出一次更改就把相关记录入栈 char [][]prev = new char[9][9]; for(int j=0;j<9;j++) { for(int k=0;k<9;k++) { prev[j][k]=board[j][k]; } } boardst.push(prev); rowstack.push(row); colstack.push(column); numstack.push(i); rows[row][i-1]=1; col[column][i-1]=1; sbox[(row/3)*3+column/3][i-1]=1; board[row][column]=(char)(i+'0'); recursion(board,row,column+1,1); break; } //如果这个位置无数可填 if(i==9) { //回溯——还原上一次更改时的状态 rows[rowstack.peek()][numstack.peek()-1]=0; col[colstack.peek()][numstack.peek()-1]=0; sbox[(rowstack.peek()/3)*3+colstack.peek()/3][numstack.peek()-1]=0; recursion(boardst.pop(),rowstack.pop(),colstack.pop(),numstack.pop()+1); } } } } } }