help

dikla · Posted: Wed Nov 02, 2005 2:11 pm Post subject: help

Here is my dfs algorithm, it can't find a solution on the case:
1 6 4 0 0 0 0 0 2
2 0 0 4 0 3 9 1 0
0 0 5 0 8 0 4 0 7
0 9 0 0 0 6 5 0 0
5 0 0 1 0 2 0 0 8
0 0 8 9 0 0 0 3 0
8 0 9 0 4 0 2 0 0
0 7 3 5 0 9 0 0 1
4 0 0 0 0 0 6 7 9
I can't trace out what the bug is, any help is appreciated!!

public static int[][]solve(int[][]ma){
int[][]m=copy(ma);
for(int i=0;i<m.length;i++){
for(int j=0;j<m[i].length;j++){
if(m[i][j]<=0){
boolean[]av=getAvail(m,i,j);
print(av);
boolean[][]visited=new boolean[N][N];
fill(visited,false);
visited[i][j]=true;
int[][]res=dfs(i,j,m,av, visited);
return res;
}
}
}
return null;
}

public static int[][]dfs(int y, int x, int[][]m, boolean[]av, boolean[][]visited){

int z=m[y][x];
if(z<=0){
z=nextAvail(av);
}
if(z<=0){
System.out.println("nothing is available now");
return null;
}
while(z>0){
if(av!=null)m[y][x]=z;

if(av!=null)av[z-1]=false;

boolean fail=false;
for(int i=-1;i<=1;i++){
for(int j=-1;j<=1;j++){
if(i==0 && j==0)continue;
if(i!=0 && j!=0)continue;

int newy=y+i;
int newx=x+j;

if(newy<0||newy>=m.length || newx<0||newx>=m[newy].length )continue;
if(visited[newy][newx])continue;

boolean[]newav=null;

if(m[newy][newx]<=0)newav=getAv ail(m,newy,newx);

boolean[][]cp=copy(visited);
cp[newy][newx]=true;
int[][]rs=dfs(newy,newx,copy(m),ne wav, cp);

if(rs!=null ){
System.out.println("after visit "+y+","+x);
print(rs);
return rs;
}
else{
fail=true;

break;
}
}
if(fail)break;
}

if(av==null)break;

z=nextAvail(av);

}
//return m;

//System.out.println("after visit "+y+","+x);
//print(m);
if(m!=null && complete(m))return m;
return null;
}
public static boolean[] getAvail(int[][]m, int y, int x){
boolean[]av=new boolean[m.length];
Arrays.fill(av,true);
int[]r={-1,1,-1,1};
int[]o={y,y,x,x};
for(int i=0;i<r.length;i++){
int c=o[i];
while(c>=0 && c<N){
if(i<2){
if(m[c][x]>0){
av[m[c][x]-1]=false;
}
}
else{
if(m[y][c]>0){
av[m[y][c]-1]=false;
}
}
c+=r[i];
}
}

//check within MxM

int zy=y/M*M;
int zx=x/M*M;
int ey=zy+M;
int ex=zx+M;
for(int i=zy;i<ey;i++){
for(int j=zx;j<ex;j++){
if(i==y&&j==x)continue;
if(m[i][j]<=0)continue;
av[m[i][j]-1]=false;

}
}

return av;
}

public static int nextAvail(boolean[]av){
for(int i=0;i<av.length;i++){
if(av[i])return i+1;
}
return -1;
}

public static boolean complete(int[][]m){
for(int i=0;i<m.length;i++){
for(int j=0;j<m[i].length;j++){
if(m[i][j]<=0)return false;
}
}

return true;
}