java1soduku.txt

java用于解决数独问题

public class Sudoku {   
    private int[] sudoku = new int[81];   
    private final static int[][] NINE = {   
        {0, 1, 2, 9, 10, 11, 18, 19, 20},   
        {3, 4, 5, 12, 13, 14, 21, 22, 23},   
        {6, 7, 8, 15, 16, 17, 24, 25, 26},   
        {27, 28, 29, 36, 37, 38, 45, 46, 47},   
        {30, 31, 32, 39, 40, 41, 48, 49, 50},   
        {33, 34, 35, 42, 43, 44, 51, 52, 53},   
        {54, 55, 56, 63, 64, 65, 72, 73, 74},   
        {57, 58, 59, 66, 67, 68, 75, 76, 77},   
        {60, 61, 62, 69, 70, 71, 78, 79, 80}   
    };   
    private static int[] nineIndex = new int[81];   
    static {   
        for (int i=0; i<9; i++) {   
            for (int j=0; j<9; j++) {   
                nineIndex[NINE[i][j]] = i;   
            }   
        }   
    }   
       
    public Sudoku(int[] array) {   
        System.arraycopy(array, 0, this.sudoku, 0, 81);   
    }   
       
    public Sudoku(Sudoku copy) {   
        this(copy.sudoku);   
    }   
  
    public Sudoku solve() {   
        Sudoku newSudoku = new Sudoku(this);   
        int[] vacancy = new int[81];   
        int vacancyNum = 0;   
        for (int i=0; i<81; i++) {   
            if (sudoku[i] == 0) {   
                vacancy[vacancyNum++] = i;   
            }   
        }   
           
        int offset = 0;   
        int number = 1;   
        while (offset < vacancyNum) {   
            while (number < 10) {   
                if (newSudoku.check(vacancy[offset], number)) {   
                    newSudoku.sudoku[vacancy[offset++]] = number;   
                    number = 1;   
                    break;   
                }   
                number++;   
            }   
            if (number == 10) {   
                newSudoku.sudoku[vacancy[offset]] = 0;   
                offset--;   
                if (offset < 0) {   
                    break;   
                }   
                number = ++newSudoku.sudoku[vacancy[offset]];   
            }   
        }   
           
        if (offset > 0) {   
            return newSudoku;   
        }   
           
        return null;   
    }   
       
    /**  
     * 检查其它位置是否与新放的有冲突  
     * @return true-没有冲突 false-有冲突  
     */  
    private boolean check(int index, int number) {   
        int row = index - index % 9;   
        for (int i = row; i < index; i++) {   
            if (sudoku[i] == number)   
                return false;   
        }   
        for (int i = index + 1; i < row + 9; i++) {   
            if (sudoku[i] == number)   
                return false;   
        }   
           
        int column = index % 9;   
        for (int i = column; i < index; i += 9) {   
            if (sudoku[i] == number)   
                return false;   
        }   
        for (int i = index + 9; i < 81; i += 9) {   
            if (sudoku[i] == number)   
                return false;   
        }   
  
        int nine = nineIndex[index];   
        for (int i = 0; i < 9; i++) {   
            if (NINE[nine][i] == index)   
                continue;   
            if (sudoku[NINE[nine][i]] == number)   
                return false;   
        }   
           
        return true;   
    }   
       
    public String toString() {   
        StringBuffer sb = new StringBuffer(100);   
        for (int i=0; i<9; i++){   
            for (int j=0; j<9; j++) {   
                sb.append(sudoku[i*9+j]);   
            }   
            sb.append('\n');   
        }   
        return sb.toString();   
    }   
}