[LeetCode] Sudoku Solver [Backtracking]

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.

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

关键字：hashtable, uber, board, col

版权声明

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处。如若内容有涉嫌抄袭侵权/违法违规/事实不符，请点击 举报 进行投诉反馈！