classSolution{List<List<String>>list=newArrayList<>();publicList<List<String>>solveNQueens(intn){//try to put in the first rowchar[][]grid=newchar[n][n];for(charc[]:grid){Arrays.fill(c,'.');}check(0,grid,n);returnlist;}publicvoidcheck(inti,char[]grid[],intn){if(i>=n){found(grid);return;}for(intj=0;j<n;j++){if(canPlace(i,j,grid)){grid[i][j]='Q';check(i+1,grid,n);grid[i][j]='.';}}}publicvoidfound(char[][]grid){List<String>l=newArrayList<>();for(inti=0;i<grid.length;i++){l.add(newString(grid[i]));}list.add(l);}publicbooleancanPlace(inti,intj,chargrid[][]){//base caseif(grid[i][j]=='Q')returnfalse;intI=i;intJ=j;//same column backwhile(I>=0){if(grid[I][j]=='Q')returnfalse;I--;}I=i;J=j;//diagonal left up while(I>=0&&J>=0){if(grid[I][J]=='Q')returnfalse;I--;J--;}I=i;J=j;//diagonal right upwhile(I>=0&&J<grid[0].length){if(grid[I][J]=='Q')returnfalse;I--;J++;}returntrue;}}
Top comments (0)
Subscribe
We're a place where coders share, stay up-to-date and grow their careers.
Top comments (0)