recursion - Recursive Method StackOverflow Error - Minesweeper -
i writing recursive method minesweeper game , encountering stackoverflow error in recursive method clears out empty spaces, error not occur when checking 3 of surrounding spaces when checking eight. can please identify issue?
the stack trace :
exception in thread "awt-eventqueue-0" java.lang.stackoverflowerror @ java.awt.component.firepropertychange(component.java:8419) @ javax.swing.abstractbutton.settext(abstractbutton.java:306) @ minesweeper.minesweeper.showtile(minesweeper.java:105) @ minesweeper.minesweeper.clearempty(minesweeper.java:137) @ minesweeper.minesweeper.clearempty(minesweeper.java:177) the class:
public class minesweeper implements actionlistener { jframe frame = new jframe("minesweeper"); jbutton reset = new jbutton("reset"); jbutton solve = new jbutton("solve"); jtogglebutton[][] buttons = new jtogglebutton[20][20]; int[][] counts = new int [20][20]; container grid = new container(); final int mine = 10; public static void main(string[] args) { new minesweeper(); } public minesweeper() { frame.setsize(600, 600); frame.setlayout(new borderlayout()); frame.add(reset, borderlayout.north); frame.add(solve, borderlayout.south); reset.addactionlistener(this); solve.addactionlistener(this); grid.setlayout(new gridlayout(20, 20)); (int r = 0; r < buttons.length; r++) { (int c = 0; c < buttons[0].length; c++) { buttons[r][c] = new jtogglebutton(); buttons[r][c].addactionlistener(this); grid.add(buttons[r][c]); buttons[r][c].setsize(frame.getwidth() / 20, frame.getheight() / 22); } } frame.add(grid,borderlayout.center); addrandommines(); frame.setdefaultcloseoperation(jframe.exit_on_close); frame.setvisible(true); } public void addrandommines() { arraylist<integer> minelist = new arraylist<integer>(); (int x = 0; x < counts.length; x++) { (int y = 0; y < counts[0].length; y++){ minelist.add((x*100)+y); } } counts = new int[20][20]; (int = 0; < 30; i++) { int choice = (int)(math.random()*minelist.size()); counts[minelist.get(choice)/100][minelist.get(choice)%100] = mine; minelist.remove(choice); } (int x = 0; x < counts.length; x++) { (int y = 0; y < counts[0].length; y++){ if (counts[x][y]!=mine) { int minecount = 0; if (x > 0 && y > 0 && counts[x - 1][y - 1] == mine) minecount++; if (y > 0 && counts[x][y - 1] == mine) minecount++; if (x > 0 && counts[x - 1][y] == mine) minecount++; if (x < counts.length - 1 && counts[x + 1][y] == mine) minecount++; if (y < counts.length - 1 && counts[x][y + 1] == mine) minecount++; if (x < counts.length - 1 && y < counts.length - 1 && counts[x + 1][y + 1] == mine) minecount++; if (x > 0 && y < counts.length - 1 && counts[x - 1][y + 1] == mine) minecount++; if (x < counts.length - 1 && y > 0 && counts[x + 1][y - 1] == mine) minecount++; counts[x][y] = minecount; } } } } public void showtile(int r, int c) { if (counts[r][c] == 0) { buttons[r][c].settext(""); buttons[r][c].setselected(true); } else if (counts[r][c]==mine) { buttons[r][c].setforeground(color.red); buttons[r][c].settext("x"); buttons[r][c].setselected(true); } else { buttons[r][c].settext(counts[r][c] + ""); if (counts[r][c]==1) buttons[r][c].setforeground(color.blue); else if (counts[r][c]==2) buttons[r][c].setforeground(color.magenta); else if (counts[r][c]==3) buttons[r][c].setforeground(color.green); buttons[r][c].setselected(true); } } public void lostgame() { (int x = 0; x < buttons.length; x++) { (int y = 0; y < buttons[0].length; y++) { if (counts[x][y]==mine) { showtile(x, y); } } } } public void clearempty(arraylist<integer> toclear) { if (toclear.size()==0){ return; } else { int x = toclear.get(0)/100; int y = toclear.get(0)%100; toclear.remove(0); if (counts[x][y]==0) { if (x > 0 && y > 0) { showtile(x-1,y-1); if (counts[x-1][y-1]==0) toclear.add((x-1)*100 + (y-1)); } if (y > 0) { showtile(x,y-1); if (counts[x][y-1]==0) toclear.add(x*100 + (y-1)); } if (x <counts.length-1 && y > 0) { showtile(x+1,y-1); if (counts[x+1][y-1]==0) toclear.add((x+1)*100 + (y-1)); } if (x > 0) { showtile(x-1,y); if (counts[x-1][y]==0) toclear.add((x-1)*100 + y); } if (x <counts.length-1 && y > 0) { showtile(x+1,y); if (counts[x+1][y]==0) toclear.add((x+1)*100 + y); } if (x > 0 && y < counts[0].length-1) { showtile(x-1,y+1); if (counts[x-1][y+1]==0) toclear.add((x-1)*100 + (y+1)); } if (y < counts[0].length-1) { showtile(x,y+1); if (counts[x][y+1]==0) toclear.add(x*100 + (y+1)); } if (x <counts.length-1 && y < counts[0].length-1) { showtile(x+1,y+1); if (counts[x+1][y+1]==0) toclear.add((x+1)*100 + (y+1)); } } clearempty(toclear); } } @override public void actionperformed(actionevent event) { if (event.getsource().equals(reset)) { (int r = 0; r < buttons.length; r++) { (int c = 0; c < buttons[0].length; c++) { buttons[r][c].setselected(false); buttons[r][c].settext(""); } } addrandommines(); } else if (event.getsource().equals(solve)) { } else { (int r = 0; r < buttons.length; r++) { (int c = 0; c < buttons[0].length; c++) { if (event.getsource().equals(buttons[r][c])) { if (counts[r][c] == mine) { showtile(r, c); lostgame(); } else if (counts[r][c] == 0) { arraylist<integer> toclear = new arraylist<integer>(); toclear.add(r*100+c); clearempty(toclear); } else { showtile(r, c); } } } } } } }
i think you're using wrong algorithm...
try use iterative instead of recursive approach.
as user404 mentioned current algorithm keeps list growing...
for implementation: have 400 tiles. assuming (worst case) tiles empty call method clearempty() once. find out 8 neighbors empty add 8 neighbors list while removing first one. pass array method again (2nd call) , find 8 neighbors first entry again. 3rd call have list 15 tiles.
real problem
this way never come end never check if current checked tile cleared add list more ever remove.
solution
at least should check if tile want add list cleared or in list.
you example clear example why recursive algorithms should used care termination difficult , have take care no work done multiple times.
Comments
Post a Comment