Java解数独--世界最难数独

在其他地方看到这个方法，稍微修改了一下，贴出来

用到Shudu和Grid两个类,

运行 Shudu里的main方法，

我读取的是本地文件，据说这个是神马大师设计的最难数独，大家可以自行修改

 

package shudu;
import java.io.*;
import java.text.SimpleDateFormat;
import java.util.*;

public class Shudu {
    public static void main(String[] args) throws Exception {
        SimpleDateFormat dfs = new SimpleDateFormat("yyyy-MM-dd HH:mm:ss.SSS");
        Date begin=dfs.parse(dfs.format(new Date()));
        
    	String arg = "C:/shudu.txt";
        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);   
        }
        
        Date end=dfs.parse(dfs.format(new Date()));
        long between=end.getTime()-begin.getTime();
        System.out.println("use Time:"+between+"ms");
    }

    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();
    }
}

package shudu;

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) {
        // Compute row and column
        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) {
        // Compute row and column
        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("0 ");
                } else {
                    buf.append(num+" ");
                }
            }
            buf.append("|\n");
        }
        buf.append("-------------------------");
        return buf.toString();
    }
}

补充：软件开发 , Java ,

上一个：Java版纯字母、纯数字、字母数字组合验证码的生成
下一个：Square_hdu_1518(深搜)