解数独

题目

编写一个程序，通过填充空格来解决数独问题。

数独的解法需 遵循如下规则：

数字 1-9 在每一行只能出现一次。
数字 1-9 在每一列只能出现一次。
数字 1-9 在每一个以粗实线分隔的 3×3 宫内只能出现一次。（请参考示例图）
数独部分空格内已填入了数字，空白格用 ‘.’ 表示。

示例 1：

输入：board = [[“5″,”3″,”.”,”.”,”7″,”.”,”.”,”.”,”.”],[“6″,”.”,”.”,”1″,”9″,”5″,”.”,”.”,”.”],[“.”,”9″,”8″,”.”,”.”,”.”,”.”,”6″,”.”],[“8″,”.”,”.”,”.”,”6″,”.”,”.”,”.”,”3″],[“4″,”.”,”.”,”8″,”.”,”3″,”.”,”.”,”1″],[“7″,”.”,”.”,”.”,”2″,”.”,”.”,”.”,”6″],[“.”,”6″,”.”,”.”,”.”,”.”,”2″,”8″,”.”],[“.”,”.”,”.”,”4″,”1″,”9″,”.”,”.”,”5″],[“.”,”.”,”.”,”.”,”8″,”.”,”.”,”7″,”9″]]
输出：[[“5″,”3″,”4″,”6″,”7″,”8″,”9″,”1″,”2”],[“6″,”7″,”2″,”1″,”9″,”5″,”3″,”4″,”8”],[“1″,”9″,”8″,”3″,”4″,”2″,”5″,”6″,”7”],[“8″,”5″,”9″,”7″,”6″,”1″,”4″,”2″,”3”],[“4″,”2″,”6″,”8″,”5″,”3″,”7″,”9″,”1”],[“7″,”1″,”3″,”9″,”2″,”4″,”8″,”5″,”6”],[“9″,”6″,”1″,”5″,”3″,”7″,”2″,”8″,”4”],[“2″,”8″,”7″,”4″,”1″,”9″,”6″,”3″,”5”],[“3″,”4″,”5″,”2″,”8″,”6″,”1″,”7″,”9”]]

来源：力扣（LeetCode）
链接：https://leetcode.cn/problems/sudoku-solver
著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。

递归+剪枝

• 解题思路
  尝试穷举所有填写，并排除不可能的分支。玩数独的时候，首先会尝试填写所有确定的数字，以降低复杂度。对于无法确定的空格,进行尝试填写。填写后，可以根据当前填写的数字，再进行一遍填写确定数字。然后寻找下一个空格进行填写。

package l3;

import java.util.*;

public class demo37 {
    public static void main(String[] args) {
//        char[][] boardHang = new char[][]{
//                {'5','3','.','.','7','.','.','.','.'},
//                {'6','.','.','1','9','5','.','.','.'},
//                {'.','9','8','.','.','.','.','6','.'},
//                {'8','.','.','.','6','.','.','.','3'},
//                {'4','.','.','8','.','3','.','.','1'},
//                {'7','.','.','.','2','.','.','.','6'},
//                {'.','6','.','.','.','.','2','8','.'},
//                {'.','.','.','4','1','9','.','.','5'},
//                {'.','.','.','.','8','.','.','7','9'}};
        char[][] boardHang = new char[][]{
        {'.','.','9','7','4','8','.','.','.'},
        {'7','.','.','.','.','.','.','.','.'},
        {'.','2','.','1','.','9','.','.','.'},
        {'.','.','7','.','.','.','2','4','.'},
        {'.','6','4','.','1','.','5','9','.'},
        {'.','9','8','.','.','.','3','.','.'},
        {'.','.','.','8','.','3','.','2','.'},
        {'.','.','.','.','.','.','.','.','6'},
        {'.','.','.','2','7','5','9','.','.'}};
        solveSudoku(boardHang);
       
        
    }
    //块转行
//        for (int i = 0; i < 9; i++) {
//            for (int j = 0; j < 9; j++) {
//                //i==0
//                //hang_i 0,1,2
//                //j=0-8
//                //hang_j0_8 0,1,2 0,1,2
//                //boardHang[i][j]=board[indexi][indexj];
//                int indexi = (i/3)*3+j/3;
//                int indexj = j%3;
//                boardHang[i][j]=board[indexi][indexj];
//            }
//        }

    //indexi=j/3+i/3*3;
    //indexj=j%3+(i%3)*3;

    //boardLie[i][j] = board[j][i];
    static char[][] rs= new char[9][9];
    public static void solveSudoku(char[][] board) {
        char[][] boardBlock = new char[9][9];
        char[][] boardLie = new char[9][9];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                int indexi,indexj;
                indexi=j/3+i/3*3;
                indexj=j%3+(i%3)*3;
                boardBlock[i][j] = board[indexi][indexj];
            }
        }
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                boardLie[i][j] = board[j][i];
            }
        }
        while (true)
        {
            int count = 0;
            for (int i = 0; i < 9; i++) {
                count+=getTrueNumber(i ,board,boardBlock,boardLie);
            }
            if(count==0)
            {
                break;
            }
        }
        char[][] newBoard = copyBoard(board);
        rs  = copyBoard(board);
        dfs(newBoard,boardBlock,boardLie,0,0);
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                board[i][j]=rs[i][j];
            }
        }
        printBoard(board);
    }

    public static void dfs(
                               char[][] newBoard,char[][] newBoardBlock,char[][] newBoardLie,
                               int x,int y)
    {
        boolean allFill=true;
        for (int i = 0; i < 9; i++) {
            if(allFill)
            {
                for (int j = 0; j < 9; j++) {
                    if(rs[i][j]=='.')
                    {
                        allFill=false;
                        break;
                    }
                }
            }
        }
        if(allFill)
        {
            return;
        }
        if(x==9& y==0)
        {
            rs=newBoard;
            return ;
        }
        for (int i = x; i < 9; i++) {
            for (int j = y; j < 9; j++) {
                int o=i;
                int p=j;
                p--;
                if(p<0)
                {
                    p=8;
                    o--;
                }
                if(o>-1)
                {
                    if(newBoard[o][p]=='.')
                    {
                        return;
                    }
                }
                if(newBoard[i][j]!='.' && (i==8 && j==8))
                {
                    rs=newBoard;
                    return;
                }
                else if(newBoard[i][j]!='.')
                {
                    continue;
                }
                List<Character> canUseNumber = getCanUseNumber(newBoard, i, j, newBoardBlock, newBoardLie);
                if(canUseNumber.size()==0)
                {
                    return;
                }
                for (Character num: canUseNumber
                     ) {
                    char[][] newBoardCopy = copyBoard(newBoard);
                    char[][] newBoardBlockCopy = copyBoard(newBoardBlock);
                    char[][] newBoardLieCopy = copyBoard(newBoardLie);
                    int indexi,indexj;
                    indexi=j/3+i/3*3;
                    indexj=j%3+(i%3)*3;
                    newBoardCopy[i][j]=num;
                    newBoardLieCopy[j][i]=num;
                    newBoardBlockCopy[indexi][indexj]=num;
                    while (true)
                    {
                        int count = 0;
                        for (int m = 0; m < 9; m++) {
                            count+=getTrueNumber(m ,newBoardCopy,newBoardBlockCopy,newBoardLieCopy);
                        }
                        if(count==0)
                        {
                            break;
                        }
                    }
                    int m=i;
                    int n=j+1;
                    if(n==9)
                    {
                        n=0;
                        m++;
                    }
                    dfs(newBoardCopy,newBoardBlockCopy,newBoardLieCopy,m,n);
                }
            }
        }
    }

    public static char[][] copyBoard(char[][] board)
    {
        char[][] newBoard = new char[board.length][board[0].length];
        for (int i = 0; i < board.length; i++) {
            for (int j = 0; j < board[0].length; j++) {
                newBoard[i][j]=board[i][j];
            }
        }
        return newBoard;
    }


    private static void printBoard(char[][] board)
    {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(j%3==0)
                {
                    System.out.print(" ");
                }
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }

    private static List<Character> getCanUseNumber(char[][] board,int pointX,int pointY,char[][] boardBlock,char[][] boardLie)
    {
        List<Character> list= new ArrayList<>();
        list.add('1');
        list.add('2');
        list.add('3');
        list.add('4');
        list.add('5');
        list.add('6');
        list.add('7');
        list.add('8');
        list.add('9');
        removeUsedNumber(board, pointX, list);
        int indexI =pointY/3+pointX/3*3;
        removeUsedNumber(boardBlock, indexI, list);
        removeUsedNumber(boardLie, pointY, list);

        return list;
    }

    private static void removeUsedNumber(char[][] board, int pointX, List<Character> list) {
        for (int i = 0; i < 9; i++) {
            if(board[pointX][i]!='.')
            {
                for (Character c:
                     list) {
                    if(c.charValue()==board[pointX][i])
                    {
                        list.remove(c);
                        break;
                    }
                }
            }
        }
    }

    //0 1 2  x/3*3-------+2
    //3 4 5
    //6 7 8
    //0 1 2,0 3 6;0
    //0 1 2,1 4 7;1
    //0 1 2,2 5 8;2
    //
    private static int getTrueNumber(int pointX,char[][] board ,char[][] boardBlock,char[][] boardLie)
    {
        int count=0;
        int[] x= new int[3];
        x[0] = pointX/3*3;
        x[1] = x[0]+1;
        x[2] = x[1]+1;
        int[] y= new int[3];
        y[0]=pointX;
        getYStartIndex(y);
        HashMap<Character,NumCountPoint> numCount = new HashMap<>();
        getNumCount(pointX, boardBlock, x, numCount,0);
        getNumCount(pointX, boardBlock, y, numCount,1);
        HashSet<Character> targetSet = new HashSet<>();
        for (int i = 0; i < 9; i++) {
            if(boardBlock[pointX][i]!='.')
            {
                targetSet.add(boardBlock[pointX][i]);
            }
        }
        for (Character c: numCount.keySet()
             ) {
            if(targetSet.contains(c))
            {
                continue;
            }
            else
            {
                NumCountPoint numCountPoint= numCount.get(c);
                ArrayList<Integer> canUseIndex = new ArrayList<Integer>();
                for (int i=0;i<9;i++)
                {
                    if(boardBlock[pointX][i]=='.')
                    {
                        canUseIndex.add(i);
                    }
                }
                for (Point p:numCountPoint.points
                     ) {
                    if(p.xy==0)
                    {
                       int start = p.pointY/3*3;
                        for (int i = 0; i < 3; i++) {
                            int index = canUseIndex.indexOf(start + i);
                            if (index > -1) {
                                canUseIndex.remove(index);
                            }
                        }
                    }
                    else
                    {
                        int[] delY= new int[3];
                        delY[0]=p.pointY;
                        getYStartIndex(delY);
                        for (int i:delY
                             ) {
                            int index = canUseIndex.indexOf(i);
                            if (index > -1) {
                                canUseIndex.remove(index);
                            }
                        }
                    }
                }
                if(canUseIndex.size()==1)
                {
                    int blockX= pointX;
                    int blockY = canUseIndex.get(0);
                    int indexI,indexJ;
                    indexI=blockY/3+blockX/3*3;
                    indexJ=blockY%3+(blockX%3)*3;
                    List<Character> canUseNumber = getCanUseNumber(board, indexI, indexJ, boardBlock, boardLie);
                    if(canUseNumber.contains(c))
                    {
                        boardBlock[blockX][blockY]=c;
                        board[indexI][indexJ]=c;
                        boardLie[indexJ][indexI]=c;
                        count++;
                    }
                }
            }
        }
        return count;
    }

    private static void getYStartIndex(int[] y) {
        while (true)
        {
            if(y[0]-3>=0)
            {
                y[0]=y[0]-3;
            }
            else
            {
               break;
            }
        }
        y[1]=y[0]+3;
        y[2]=y[1]+3;
    }

    public static class NumCountPoint
    {
        char c;
        int count;
        List<Point> points;
    }

    public static class Point
    {
        char c;
        int pointX;
        int pointY;
        //0代表水平x
        //1代表竖直y
        int xy;
    }

    private static void getNumCount(int pointX, char[][] boardBlock, int[] x, HashMap<Character, NumCountPoint> numCount,int xy) {
        for (int xIndex:x
             ) {
            if(xIndex!=pointX)
            {
                for (int i = 0; i < 9; i++) {
                    if(boardBlock[xIndex][i]!='.')
                    {
                        char c = boardBlock[xIndex][i];
                        Point point = new Point();
                        NumCountPoint numCountPoint;
                        if(!numCount.containsKey(c))
                        {
                            numCountPoint = new NumCountPoint();
                            numCountPoint.points= new ArrayList<>();
                            numCountPoint.c=c;
                            numCountPoint.count=1;
                        }
                        else
                        {
                            numCountPoint = numCount.get(c);
                            numCountPoint.count=1+numCountPoint.count;
                        }
                        point.c=c;
                        point.pointX=pointX;
                        point.pointY=i;
                        point.xy=xy;
                        numCountPoint.points.add(point);
                        numCount.put(c,numCountPoint);
                    }
                }
            }
        }
    }

}

递归回溯

• 解题思路
  尝试填写一个数字，然后如果在后续填写中发现不对就回溯当前状态。

package l3;

public class demo37_2 {
    public static void main(String[] args) {

        char[][] boardHang = new char[][]{
                {'.','.','9','7','4','8','.','.','.'},
                {'7','.','.','.','.','.','.','.','.'},
                {'.','2','.','1','.','9','.','.','.'},
                {'.','.','7','.','.','.','2','4','.'},
                {'.','6','4','.','1','.','5','9','.'},
                {'.','9','8','.','.','.','3','.','.'},
                {'.','.','.','8','.','3','.','2','.'},
                {'.','.','.','.','.','.','.','.','6'},
                {'.','.','.','2','7','5','9','.','.'}};
        solveSudoku(boardHang);
    }
    public static void solveSudoku(char[][] board)
    {
        //num是1-9，所示col需要到10
        boolean[][] rowUsed= new boolean[9][10];
        boolean[][] colUsed=new boolean[9][10];
        boolean[][][] blockUsed = new boolean[3][3][10];
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                //字符相减，巧取num数字
                //字符"."减字符0，num肯定不在1-9之间
                int num = board[i][j]-'0';
                if(num>=1 && num<=9)
                {
                    rowUsed[i][num]=true;
                    colUsed[j][num]=true;
                    blockUsed[i/3][j/3][num]=true;
                }
            }
        }
        dfs(board,rowUsed,colUsed,blockUsed,0,0);
        printBoard(board);
    }
    private static void printBoard(char[][] board)
    {
        for (int i = 0; i < 9; i++) {
            for (int j = 0; j < 9; j++) {
                if(j%3==0)
                {
                    System.out.print(" ");
                }
                System.out.print(board[i][j]);
            }
            System.out.println();
        }
    }
    public static boolean dfs(char[][] board,boolean[][] rowUsed,boolean[][] colUsed,boolean[][][] blockUsed,int row,int col)
    {
        if(col==9)
        {
            col=0;
            row++;
            if(row==9)
            {
                return true;
            }
        }
        //如果是点尝试进行填充，否则跳过进行下一个位置
        if(board[row][col]=='.')
        {
            //1-9尝试填充
            for (int num = 1; num <= 9; num++) {
                //行列块都没用过，才能使用这个数字
                boolean canUsed= !(rowUsed[row][num] || colUsed[col][num] || blockUsed[row/3][col/3][num]);
                if(canUsed)
                {
                    rowUsed[row][num]=true;
                    colUsed[col][num]=true;
                    blockUsed[row/3][col/3][num]=true;
                    board[row][col]=(char)('0'+num);//巧取char
                    //dfs 注意col不能++，回溯之后，还要用到col呢
                    if(dfs(board,rowUsed,colUsed,blockUsed,row,col+1))
                    {
                        //回溯出口
                        return true;
                    }
                    //失败了，重置当前状态，尝试填下一个数字
                    rowUsed[row][num]=false;
                    colUsed[col][num]=false;
                    blockUsed[row/3][col/3][num]=false;
                    board[row][col]='.';//巧取char

                }
            }
        }
        else
        {
            return dfs(board,rowUsed,colUsed,blockUsed,row,col+1);
        }
        return false;
    }
}

原文地址：http://www.cnblogs.com/huacha/p/16858286.html