博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
[LeetCode] Sudoku Solver [Backtracking]
阅读量:7072 次
发布时间:2019-06-28

本文共 2896 字,大约阅读时间需要 9 分钟。

Problem

Write a program to solve a Sudoku puzzle by filling the empty cells.

Empty cells are indicated by the character '.'.

You may assume that there will be only one unique solution.

250px-Sudoku-by-L2G-20050714.svg.png

Solution

public class Solution {    public void solveSudoku(char[][] board) {        if(board == null || board.length == 0)            return;        solve(board);    }    public boolean solve(char[][] board){        for(int i = 0; i < board.length; i++){            for(int j = 0; j < board[0].length; j++){                if(board[i][j] == '.'){                    for(char c = '1'; c <= '9'; c++){//trial. Try 1 through 9 for each cell                        if(isValid(board, i, j, c)){                            board[i][j] = c; //Put c for this cell                            if(solve(board))                                return true; //If it's the solution return true                            else                                board[i][j] = '.'; //Otherwise go back                        }                    }                    return false;                }            }        }        return true;    }    public boolean isValid(char[][] board, int i, int j, char c){        //Check colum        for(int row = 0; row < 9; row++)            if(board[row][j] == c)                return false;        //Check row        for(int col = 0; col < 9; col++)            if(board[i][col] == c)                return false;        //Check 3 x 3 block        for(int row = (i / 3) * 3; row < (i / 3) * 3 + 3; row++)            for(int col = (j / 3) * 3; col < (j / 3) * 3 + 3; col++)                if(board[row][col] == c)                    return false;        return true;    }}
public class Solution {    public void solveSudoku(char[][] board) {        solve(board, 0, 0);    }    private boolean solve(char[][] board, int row, int col) {        if (row == 9) return true;        int nextRow = col == 8 ? row+1 : row;        int nextCol = col == 8 ? 0 : col+1;        if (board[row][col] != '.') return solve(board, nextRow, nextCol);        for (int i = 1; i <= 9; i++) {            board[row][col] = (char) ('0'+i);            if (isValid(board, row, col) && solve(board, nextRow, nextCol)) return true;        }        board[row][col] = '.';        return false;    }    public boolean isValid(char[][] board, int row, int col) {        char cur = board[row][col];        for (int i = 0; i < 9; i++) {            if (i != row && cur == board[i][col]) return false;        }        for (int i = 0; i < 9; i++) {            if (i != col && cur == board[row][i]) return false;        }        int n = board.length;        int rowbox = row/3, colbox = col/3;        for (int i = rowbox*3; i < rowbox*3+3; i++) {            for (int j = colbox*3; j < colbox*3+3; j++) {                if (board[i][j] == cur && (i != row || j != col)) return false;            }        }        return true;    }}

转载地址:http://iuell.baihongyu.com/

你可能感兴趣的文章
闭包是什么,如何使用?
查看>>
堆排序Java实现(递归方式&非递归方式)
查看>>
GRU网络生成莎士比亚小说
查看>>
一次读锁重入导致的死锁故障
查看>>
如何使用Kubernetes里的NetworkPolicy
查看>>
图像风格转移
查看>>
ReactNative集成百度语音合成
查看>>
记一次企业级存储规划及重大事故
查看>>
微信小程序Markdown渲染组件wemark
查看>>
Dubbo分析之Serialize层
查看>>
飞雪无情的博客Go语言、Android相关的十大热门文章
查看>>
程序员练级攻略(2018):前端性能优化和框架
查看>>
免费申请通配符证书
查看>>
如何快速搭建一个react+webpack环境
查看>>
IO模型浅析-阻塞、非阻塞、IO复用、信号驱动、异步IO、同步IO
查看>>
如何将Excel文件解析为json格式
查看>>
剥开比原看代码16:比原是如何通过/list-transactions显示交易信息的?
查看>>
单行文字向上滚动
查看>>
vue进阶2-构建基础框架
查看>>
TiDB 源码阅读系列文章(十五)Sort Merge Join
查看>>