最新文章:

首页 JAVASE

java数度破解

发布时间:2017年01月17日 评论数:抢沙发 阅读数:308

    在国外网站上扒了一段不错的数度自动破解代码。是用java写的所以对着写了下,还有个用js写的因为平时不怎么用js也就没深究了

    话不多说上源码

    数度用一个txt存着,格式如下

    060900102
    400106000
    080020005
    630201500
    004537906
    005600031
    908760010
    000809007
    706002000

    首先是个SudokuSolver类


    import java.io.*;  
    import java.util.*;  
      
    public class SudokuSolver {  
        public static void main(String[] args) throws Exception { 
            String arg = "存放数度的文件路径";  
            FileReader rd = new FileReader(arg);  
            while (true) {  
                Grid grid = Grid.create(rd);  
                if (grid == null) {   
                    break;  
                }    
                List<Grid> solutions = new ArrayList<Grid>();  
                solve(grid, solutions);  
      
                printSolutions(grid, solutions);  
            }  
        }   
        private static void solve(Grid grid, List<Grid> solutions) {  
            if (solutions.size() >= 2) {  
                return;  
            }  
            int loc = grid.findEmptyCell();  
            if (loc < 0) {  
                solutions.add(grid.clone());  
                return;  
            }  
            for (int n=1; n<10; n++) {  
                if (grid.set(loc, n)) {  
                    solve(grid, solutions);  
                    grid.clear(loc);  
                }  
            }  
        }  
      
        private static void printSolutions(Grid grid, List<Grid> solutions) {  
            System.out.println("Original");  
            System.out.println(grid);  
            if (solutions.size() == 0) {  
                System.out.println("Unsolveable");  
            } else if (solutions.size() == 1) {  
                System.out.println("Solved");  
            } else {  
                System.out.println("At least two solutions");  
            }  
            for (int i=0; i<solutions.size(); i++) {  
                System.out.println(solutions.get(i));  
            }  
            System.out.println();  
            System.out.println();  
        }  
    }  


    然后是一个Grid类


    import java.io.Reader;  
    public class Grid implements Cloneable {   
        int[] cells = new int[81];  
        int[] colsSet = new int[9];  
        int[] rowsSet = new int[9];    
        int[] subgridSet = new int[9];  
        public static Grid create(Reader rd) throws Exception {  
            Grid grid = new Grid();   
            for (int loc=0; loc<grid.cells.length; ) {  
                int ch = rd.read();  
                if (ch < 0) {  
                    return null;  
                }  
                if (ch == '#') {  
                    while (ch >= 0 && ch != '\n' && ch != '\r') {  
                        ch = rd.read();  
                    }  
                } else if (ch >= '1' && ch <= '9') {  
                    grid.set(loc, ch-'0');  
                    loc++;  
                } else if (ch == '.' || ch == '0') {    
                    loc++;  
                }  
            }  
            return grid;  
        }  
        public int findEmptyCell() {  
            for (int i=0; i<cells.length; i++) {  
                if (cells[i] == 0) {  
                    return i;  
                }  
            }  
            return -1;  
        }  
        public boolean set(int loc, int num) {   
            int r = loc/9;  
            int c = loc%9;  
            int blockLoc = (r/3)*3+c/3;  
            boolean canSet = cells[loc] == 0  
                && (colsSet[c] & (1<<num)) == 0  
                && (rowsSet[r] & (1<<num)) == 0  
                && (subgridSet[blockLoc] & (1<<num)) == 0;  
            if (!canSet) {  
                return false;  
            }  
            cells[loc] = num;  
            colsSet[c] |= (1<<num);  
            rowsSet[r] |= (1<<num);  
            subgridSet[blockLoc] |= (1<<num);  
            return true;  
        }  
        public void clear(int loc) {  
            int r = loc/9;  
            int c = loc%9;  
            int blockLoc = (r/3)*3+c/3;  
            int num = cells[loc];  
            cells[loc] = 0;  
            colsSet[c] ^= (1<<num);  
            rowsSet[r] ^= (1<<num);  
            subgridSet[blockLoc] ^= (1<<num);  
        }  
        public Grid clone() {  
            Grid grid = new Grid();  
            grid.cells = cells.clone();  
            grid.colsSet = colsSet.clone();  
            grid.rowsSet = rowsSet.clone();  
            grid.subgridSet = subgridSet.clone();  
            return grid;  
        } 
        public String toString() {  
            StringBuffer buf = new StringBuffer();  
            for (int r=0; r<9; r++) {  
                if (r%3 == 0) {  
                    buf.append("-------------------------\n");  
                }  
                for (int c=0; c<9; c++) {  
                    if (c%3 == 0) {  
                        buf.append("| ");  
                    }  
                    int num = cells[r*9+c];  
                    if (num == 0) {  
                        buf.append(". ");  
                    } else {  
                        buf.append(num+" ");  
                    }  
                }  
                buf.append("|\n");  
            }  
            buf.append("-------------------------");  
            return buf.toString();  
        }  
    }  


    最后是效果图

二维码加载中...
本文作者:HDC      文章标题: java数度破解
本文地址:http://hdcin.cn/?post=136
版权声明:若无注明,本文皆为“小胖Blog's”原创,转载请保留文章出处。
挤眼 亲亲 咆哮 开心 想想 可怜 糗大了 委屈 哈哈 小声点 右哼哼 左哼哼 疑问 坏笑 赚钱啦 悲伤 耍酷 勾引 厉害 握手 耶 嘻嘻 害羞 鼓掌 馋嘴 抓狂 抱抱 围观 威武 给力
提交评论

清空信息
关闭评论