Sudoku Problem Solver (数独游戏解谜器)

package sudoku;

/**
 * <p>Title: Sudoku Problem Solver</p>
 *
 * <p>Description: </p>
 *
 * <p>Copyright: Copyright (c) 2005</p>
 *
 * <p>Company: </p>
 *
 * @author 郑杨凡
 * @version 1.0
 */
import java.util.HashSet;
import java.util.Iterator;

public class Sudoku {
        public static class SudokuSoluteException extends Exception {
                public SudokuSoluteException() {
                        super();
                }
        }
        private static class IndexPair{
                private int row;
                private int column;
                /**
                 * @return Returns the column.
                 */
                public int getColumn() {
                        return column;
                }
                /**
                 * @param column The column to set.
                 */
                public void setColumn(int column) {
                        this.column = column;
                }
                /**
                 * @return Returns the row.
                 */
                public int getRow() {
                        return row;
                }
                /**
                 * @param row The row to set.
                 */
                public void setRow(int row) {
                        this.row = row;
                }
        }
        private static class SmallestNeeded{
                public static final String ROW = "ROW";
                public static final String COLUMN = "COLUMN";
                public static final String BOX = "BOX";

                private String type = "ROW";
                private int index = -1;
                private int requiredCount = 10;

                /**
                 * @return Returns the requiredCount.
                 */
                public int getRequiredCount() {
                        return requiredCount;
                }
                /**
                 * @param requiredCount The requiredCount to set.
                 */
                public void setRequiredCount(int requiredCount) {
                        this.requiredCount = requiredCount;
                }
                /**
                 * @return Returns the index.
                 */
                public int getIndex() {
                        return index;
                }
                /**
                 * @param index The index to set.
                 */
                public void setIndex(int index) {
                        this.index = index;
                }
                /**
                 * @return Returns the type.
                 */
                public String getType() {
                        return type;
                }
                /**
                 * @param type The type to set.
                 */
                public void setType(String type) {
                        this.type = type;
                }
        }

        private static class SudokuState {
                private HashSet[] numsNeededInRow = new HashSet[9];
                private HashSet[] numsNeededInCol = new HashSet[9];
                private HashSet[] numsNeededInBox = new HashSet[9];

                public SudokuState(){
                        for(int i = 0; i < 9 ; i++){
                                numsNeededInRow[i] = new HashSet();
                                numsNeededInCol[i] = new HashSet();
                                numsNeededInBox[i] = new HashSet();
                                for(int j = 1; j <= 9; j++){
                                        Byte b = new Byte((byte) j);
                                        numsNeededInRow[i].add(b);
                                        numsNeededInCol[i].add(b);
                                        numsNeededInBox[i].add(b);
                                }
                        }
                }

                public void setNum(int row,int col,byte num)throws SudokuSoluteException{
                        Byte b = new Byte(num);
                        SudokuSoluteException e = new SudokuSoluteException();

                        if(numsNeededInRow[row].contains(b))
                                numsNeededInRow[row].remove(b);
                        else
                                throw e;

                        if(numsNeededInCol[col].contains(b)){
                                numsNeededInCol[col].remove(b);
                        }else{
                                numsNeededInRow[row].add(b);
                                throw e;
                        }

                        if(numsNeededInBox[row / 3 * 3 + col / 3].contains(b)){
                                numsNeededInBox[row / 3 * 3 + col / 3].remove(b);
                        }else{
                                numsNeededInRow[row].add(b);
                                numsNeededInCol[col].add(b);
                                throw e;
                        }
                }

                public void reSetNum(int row, int col, byte num) {
                        Byte b = new Byte(num);
                        numsNeededInRow[row].add(b);
                        numsNeededInCol[col].add(b);
                        numsNeededInBox[row / 3 * 3 + col / 3].add(b);
                }

                public byte[] getNeededNums(SmallestNeeded needed){
                        String type = needed.getType();
                        HashSet set = null;
                        if(type.equals(SmallestNeeded.ROW)){
                                set = numsNeededInRow[needed.getIndex()];
                        }else if(type.equals(SmallestNeeded.COLUMN)){
                                set = numsNeededInCol[needed.getIndex()];
                        }else{
                                set = numsNeededInBox[needed.getIndex()];
                        }
                        byte[] ret = new byte[set.size()];
                        int i = 0;
                        for(Iterator iter = set.iterator(); iter.hasNext();){
                                ret[i++] = ((Byte)iter.next()).byteValue();
                        }
                        return ret;
                }

                public SmallestNeeded getSmallestNeeded(){
                        SmallestNeeded needed = new SmallestNeeded();
                        for(int i = 0; i < 9; i++){
                                int required = numsNeededInRow[i].size();
                                if(required > 0 && needed.getRequiredCount() > required){
                                        needed.setRequiredCount(required);
                                        needed.setIndex(i);
                                        needed.setType(SmallestNeeded.ROW);
                                }

                                required = numsNeededInCol[i].size();
                                if(required > 0 && needed.getRequiredCount() > required){
                                        needed.setRequiredCount(required);
                                        needed.setIndex(i);
                                        needed.setType(SmallestNeeded.COLUMN);
                                }

                                required = numsNeededInBox[i].size();
                                if(required > 0 && needed.getRequiredCount() > required){
                                        needed.setRequiredCount(required);
                                        needed.setIndex(i);
                                        needed.setType(SmallestNeeded.BOX);
                                }
                        }
                        return needed;
                }
        }
        private byte[][] chessBoard = new byte[9][9];
        private SudokuState state = null;
        private void init(){
                for(int i = 0; i < 9; i++){
                        for(int j = 0;j < 9; j++){
                                chessBoard[i][j] = -1;
                        }
                }
                state = new SudokuState();
        }

        public Sudoku(){
                init();
        try {
            jbInit();
        } catch (Exception ex) {
            ex.printStackTrace();
        }
    }

        public Sudoku(byte[][] board) throws SudokuSoluteException{
                this();
                for(int i = 0; i < 9 ; i++){
                        for(int j = 0; j < 9; j++){
                                if(board[i][j] != -1){
                                        setNumber(i,j,board[i][j]);
                                }else{
                                        chessBoard[i][j] = -1;
                                }
                        }
                }
        }

        public void setNumber(int row,int col,byte num) throws SudokuSoluteException{
                byte originalNum = chessBoard[row][col];
                chessBoard[row][col] = num;
                try{
                        state.setNum(row,col,num);
                }catch(SudokuSoluteException ex){
                        chessBoard[row][col] = originalNum;
                        throw ex;
                }
        }

        public IndexPair getNextIndexPair(SmallestNeeded needed){
                IndexPair pair = new IndexPair();
                String type = needed.getType();
                if(type.equals(SmallestNeeded.ROW)){
                        int i = needed.getIndex();
                        for(int j = 0; j < 9; j++ ){
                                if(chessBoard[i][j] == -1){
                                        pair.setRow(i);
                                        pair.setColumn(j);
                                        break;
                                }
                        }
                }else if(type.equals(SmallestNeeded.COLUMN)){
                        int j = needed.getIndex();
                        for(int i = 0; i < 9; i++ ){
                                if(chessBoard[i][j] == -1){
                                        pair.setRow(i);
                                        pair.setColumn(j);
                                        break;
                                }
                        }
                }else{
                        // BOX
                        int k = needed.getIndex();

                        int startRow = k / 3 * 3;
                        int startCol = k % 3 * 3;

                        for(int i = startRow; i < startRow+3;i++){
                                for(int j = startCol; j < startCol + 3; j++){
                                        if(chessBoard[i][j] == -1){
                                                pair.setRow(i);
                                                pair.setColumn(j);
                                                return pair;
                                        }
                                }
                        }
                }
                return pair;
        }

        public byte  getNumAt(int i, int j){
            return chessBoard[i][j];
        }

        public boolean solve(){
                SmallestNeeded needed = state.getSmallestNeeded();
                if(needed.getRequiredCount() > 9){
                        // find the solution
                        return true;
                }
                IndexPair pair = getNextIndexPair(needed);
                byte[] needNums = state.getNeededNums(needed);

                for(int i = 0; i < needNums.length;i++){
                        byte b = needNums[i];
                        try{
                                setNumber(pair.getRow(),pair.getColumn(),b);
                                // System.out.println("SET " + (pair.getRow()+1) + "行," + (pair.getColumn()+1) + "列为" + b);
                                if(solve()){
                                        return true;
                                }
                                reSetNumber(pair.getRow(),pair.getColumn(),b);
                                // System.out.println("RESET " + (pair.getRow()+1) + "行," + (pair.getColumn()+1) + "列为" + b);
                        }catch(SudokuSoluteException ex){
                                continue;
                        }
                }
                return false;
        }

        public void reSetNumber(int row, int col, byte num) {
                chessBoard[row][col] = -1;
                state.reSetNum(row,col,num);
        }

        public void print(){
                for(int i = 0; i < 9 ; i++){
                        for(int j = 0 ; j < 9 ; j++){
                                if(chessBoard[i][j] != -1)
                                        System.out.print(chessBoard[i][j]);
                                System.out.print('/t');
                        }
                        System.out.println();
                }
        }

        /**
         * @param args
         * @throws SudokuSoluteException
         */
        public static void main(String[] args) throws SudokuSoluteException {
//  byte[][] board = {
//   {-1,5,-1,-1,-1,1,4,-1,-1},
//   {2,-1,3,-1,-1,-1,7,-1,-1},
//   {-1,7,-1,3,-1,-1,1,8,2},
//   {-1,-1,4,-1,5,-1,-1,-1,7},
//   {-1,-1,-1,1,-1,3,-1,-1,-1},
//   {8,-1,-1,-1,2,-1,6,-1,-1},
//   {1,8,5,-1,-1,6,-1,9,-1},
//   {-1,-1,2,-1,-1,-1,8,-1,3},
//   {-1,-1,6,4,-1,-1,-1,7,-1}
//  };

//  byte[][] board ={
//    {6,-1,-1,1,-1,-1,-1,5,-1},
//   {-1,4,-1,-1,-1,2,-1,-1,3},
//   {-1,-1,3,-1,5,-1,1,-1,-1},
//   {-1,1,-1,-1,-1,3,-1,-1,4},
//   {-1,-1,5,-1,6,-1,9,-1,-1},
//   {2,-1,-1,9,-1,-1,-1,1,-1},
//   {-1,-1,6,-1,8,-1,7,-1,-1},
//   {3,-1,-1,7,-1,-1,-1,6,-1},
//   {-1,2,-1,-1,-1,6,-1,-1,1}
//   };
                byte[][] board ={
                                {2,-1,-1,6,7,-1,-1,-1,-1},
                                {-1,-1,6,-1,-1,-1,2,-1,1},
                                {4,-1,-1,-1,-1,-1,8,-1,-1},
                                {5,-1,-1,-1,-1,9,3,-1,-1},
                                {-1,3,-1,-1,-1,-1,-1,5,-1},
                                {-1,-1,2,8,-1,-1,-1,-1,7},
                                {-1,-1,1,-1,-1,-1,-1,-1,4},
                                {7,-1,8,-1,-1,-1,6,-1,-1},
                                {-1,-1,-1,-1,5,3,-1,-1,8}
                };
                Sudoku ku = new Sudoku(board);
                if(ku.solve())
                        ku.print();
                else
                        System.out.println("No Solution");
        }

    private void jbInit() throws Exception {
    }

}