02.26 DFS-數獨題

 數獨是一種運用紙、筆進行演算的邏輯遊戲。玩家需要根據9×9盤面上的已知數字，推理出所有剩餘空格的數字，並滿足每一行、每一列、每一個3*3宮內的數字均含1-9，不重複。 每一道合格的數獨謎題都有且僅有唯一答案，推理方法也以此為基礎，任何無解或多解的題目都是不合格的Input

<code>10 0 5 3 0 0 0 0 08 0 0 0 0 0 0 2 00 7 0 0 1 0 5 0 04 0 0 0 0 5 3 0 00 1 0 0 7 0 0 0 60 0 3 2 0 0 0 8 00 6 0 5 0 0 0 0 90 0 4 0 0 0 0 3 00 0 0 0 0 9 7 0 0/<code>

Output

<code>1 4 5 3 2 7 6 9 8 8 3 9 6 5 4 1 2 7 6 7 2 9 1 8 5 4 3 4 9 6 1 8 5 3 7 2 2 1 8 4 7 3 9 5 6 7 5 3 2 9 6 4 8 1 3 6 7 5 4 2 8 1 9 9 8 4 7 6 1 2 3 5 5 2 1 8 3 9 7 6 4/<code>

<code>import java.util.Scanner;//005300000//800000020//070010500//400005300//010070006//003200080//060500009//004000030//000009700public class 九宮格 {    public static void main(String[] args) {        Scanner scanner=new Scanner(System.in);        char[][] table=new char[9][9];        for (int i = 0; i <9 ; i++) {            table[i]=scanner.nextLine().toCharArray();        }        dfs(table,0,0);    }    static void dfs(char[][] table,int x,int y){        if (x==9){//x最大是8            print(table);            System.exit(0);        }        if (table[x][y]=='0'){            for (int i = 1; i <10 ; i++) {                if (check(table,x,y,i)){                    table[x][y]=(char)('0'+i);                    dfs(table,x+(y+1)/9,(y+1)%9);                }            }            table[x][y]='0';        }else {            dfs(table,x+(y+1)/9,(y+1)%9);        }    }    static boolean check(char[][] table,int i,int j,int k){        for (int l = 0; l <9 ; l++) {            if (table[i][l]==(char)('0'+k)) return false;            if (table[l][j]==(char)('0'+k)) return false;        }        for (int l = (i/3)*3; l /<code>

閱讀更多 小白學習日記yang 的文章

關鍵字: 合格 數獨 推理方法