java2soduku.txt

java解决数独问题

/**  
* Eastsun注释  
*/  
class S{   
    /**  
    * 尝试在b[]的第p-1个位置放置数字  
    */  
    static void r(char[]b,int p){   
        long u=0;     //该long的第k(1至9)位bit代表当前位置是否可以放置数字k(是0否1)   
        if(--p<0) System.out.print(b);  //如果p-1<0说明所有位置已经放置好,已经求得一解   
        else if(b[p]>48) r(b,p);        //>48,说明该位置是已经填好数字的,不需要尝试   
        else{   
            for(int i=81;i-->0;)   
               u|=   
                  // (p-i)%9==0 :就是说p与i是同一列   
                  // p/9^i/9==0 :就是说p与i是同一行   
                  // p/27^i/27|p%9/3^i%9/3==0: 就是p与i在同一个小九宫   
                  // 为什么是这样子?简单的数学题,呵呵.   
                  //我来解释一下最后一个,p/27==i/27相当于把大九宫按行分成3下,0~2行,3~5行,6~8行三部分,   
                  // 检查p与i是否属于同一个部分   
                  // p%9是看p属于那一列,p%9/3是看p属于0~2列,3~5列,6~8列的那一部分   
                  // so,p/27^i/27|p%9/3^i%9/3==0时,p与i属于同一小九宫   
                  (p-i)%9*(p/9^i/9)*(p/27^i/27|p%9/3^i%9/3)     
                     ==0?   
                     1L<<b[i]:         //==0,说明这个位置对当前位置有影响,将u的该位置1   
                     0;   
            for(b[p]=58;--b[p]>48;)   
               if((u>>b[p]&1)<1)       //u>>b[p]&1 <1也就是u>>b[p]&1==0,说明这个b[p]是合理的,   
                      r(b,p);          //试探下一个   
            //注意这个循环结束条件是 !--b[p]>48,也就是b[p]=='0',最后又将b[p]恢复到'0'不会影响回溯条件.   
        }   
    }   
    public static void main(String[] a){   
        //从第80个位置开始试探.   
        r(a[0].toCharArray(),81);   
    }   
}