Sudoku Solver (H)
題目
Write a program to solve a Sudoku puzzle by filling the empty cells.
A sudoku solution must satisfy all of the following rules:
- Each of the digits
1-9must occur exactly once in each row. - Each of the digits
1-9must occur exactly once in each column. - Each of the the digits
1-9must occur exactly once in each of the 93x3sub-boxes of the grid.
Empty cells are indicated by the character '.'.
A sudoku puzzle...
...and its solution numbers marked in red.
Note:
- The given board contain only digits
1-9and the character'.'. - You may assume that the given Sudoku puzzle will have a single unique solution.
- The given board size is always
9x9.
題意
完成數獨，
思路
典型的“試錯型”問題，使用回溯法：遍歷每個空格，每次先插入一個有效的數字(有效性通過isValid()進行判斷)，再向后遞回，如果遞回能夠解出數獨，說明當前填入的數字是正確的，問題已解決直接回傳即可；否則將填入的數字恢復為空格，等待填入下一個數字，不斷的“試錯”后就能得到正確答案，
代碼實作
Java
無hash
class Solution {
public void solveSudoku(char[][] board) {
solve(board, 0, 0);
}
private boolean solve(char[][] board, int i, int j) {
// 每一格都填上了數字，說明已經解出數獨
if (i == board.length) {
return true;
}
int nextI = j == board.length - 1 ? i + 1 : i;
int nextJ = j == board.length - 1 ? 0 : j + 1;
// 已有數字則不需要處理，直接向后遞回
if (board[i][j] != '.') {
return solve(board, nextI, nextJ);
}
for (int k = 1; k <= 9; k++) {
char c = (char) ('0' + k);
if (isValid(board, i, j, c)) {
board[i][j] = c;
boolean solved = solve(board, nextI, nextJ);
// 如果遞回能解出數獨，說明當前填入的數字是正確的
// 否則恢復原狀，以免影響下次回圈有效性判斷的正確性
if (solved) {
return true;
} else {
board[i][j] = '.';
}
}
}
return false;
}
private boolean isValid(char[][] board, int i, int j, char c) {
for (int k = 0; k < 9; k++) {
// 注意要排除自身
if (k != j && c == board[i][k] || k != i && c == board[k][j]) {
return false;
}
}
// x、y的初始值為對應九宮格左上頂點的坐標
for (int x = 3 * (i / 3); x < 3 * (i / 3) + 3; x++) {
for (int y = 3 * (j / 3); y < 3 * (j / 3) + 3; y++) {
// 注意要排除自身
if (c == board[x][y] && (x != i || y != j)) {
return false;
}
}
}
return true;
}
}
hash
class Solution {
List<Set<Character>> row = new ArrayList<>();
List<Set<Character>> col = new ArrayList<>();
List<Set<Character>> nine = new ArrayList<>();
public void solveSudoku(char[][] board) {
initialize(board);
solve(board, 0, 0);
}
private boolean solve(char[][] board, int i, int j) {
if (i == board.length) {
return true;
}
int nextI = j == board.length - 1 ? i + 1 : i;
int nextJ = j == board.length - 1 ? 0 : j + 1;
if (board[i][j] != '.') {
return solve(board, nextI, nextJ);
}
for (int k = 1; k <= 9; k++) {
char c = (char) ('0' + k);
if (!row.get(i).contains(c)
&& !col.get(j).contains(c)
&& !nine.get(3 * (i / 3) + j / 3).contains(c)) {
board[i][j] = c;
row.get(i).add(c);
col.get(j).add(c);
nine.get(3 * (i / 3) + j / 3).add(c);
boolean flag = solve(board, nextI, nextJ);
if (flag) {
return true;
} else {
board[i][j] = '.';
row.get(i).remove(c);
col.get(j).remove(c);
nine.get(3 * (i / 3) + j / 3).remove(c);
}
}
}
return false;
}
private void initialize(char[][] board) {
for (int i = 0; i < 9; i++) {
row.add(new HashSet<>());
col.add(new HashSet<>());
nine.add(new HashSet<>());
}
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
char c = board[i][j];
if (c != '.') {
row.get(i).add(c);
col.get(j).add(c);
nine.get(3 * (i / 3) + j / 3).add(c);
}
}
}
}
}
JavaScript
無Hash
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function (board) {
dfs(board, 0, 0)
}
let dfs = function (board, row, col) {
if (row === board.length) {
return true
}
let nextRow = col === 8 ? row + 1 : row
let nextCol = col === 8 ? 0 : col + 1
if (board[row][col] !== '.') {
return dfs(board, nextRow, nextCol)
}
for (let i = 1; i <= 9; i++) {
let c = '' + i
if (isValid(board, row, col, c)) {
board[row][col] = c
if (dfs(board, nextRow, nextCol)) {
return true
}
board[row][col] = '.'
}
}
return false
}
let isValid = function (board, row, col, c) {
for (let i = 0; i < 9; i++) {
if ((row !== i && board[i][col] === c) || (col !== i && board[row][i] === c)) {
return false
}
}
let topLeftX = Math.trunc(row / 3) * 3
let topLeftY = Math.trunc(col / 3) * 3
for (let i = topLeftX; i < topLeftX + 3; i++) {
for (let j = topLeftY; j < topLeftY + 3; j++) {
if (c === board[i][j] && (i !== row || j !== col)) {
return false
}
}
}
return true
}
Hash
/**
* @param {character[][]} board
* @return {void} Do not return anything, modify board in-place instead.
*/
var solveSudoku = function (board) {
let rows = new Array(9).fill(0).map(v => new Set())
let cols = new Array(9).fill(0).map(v => new Set())
let boxes = new Array(9).fill(0).map(v => new Set())
for (let i = 0; i < 9; i++) {
for (let j = 0; j < 9; j++) {
let c = board[i][j]
rows[i].add(c)
cols[j].add(c)
boxes[Math.trunc(i / 3) * 3 + Math.trunc(j / 3)].add(c)
}
}
dfs(board, 0, 0, rows, cols, boxes)
}
let dfs = function (board, i, j, rows, cols, boxes) {
if (i === 9) {
return true
}
let nextI = j === 8 ? i + 1 : i
let nextJ = j === 8 ? 0 : j + 1
if (board[i][j] !== '.') {
return dfs(board, nextI, nextJ, rows, cols, boxes)
}
let boxIndex = Math.trunc(i / 3) * 3 + Math.trunc(j / 3)
for (let num = 1; num <= 9; num++) {
let c = num + ''
if (rows[i].has(c) || cols[j].has(c) || boxes[boxIndex].has(c)) {
continue
}
board[i][j] = c
rows[i].add(c)
cols[j].add(c)
boxes[boxIndex].add(c)
if (dfs(board, nextI, nextJ, rows, cols, boxes)) {
return true
}
board[i][j] = '.'
rows[i].delete(c)
cols[j].delete(c)
boxes[boxIndex].delete(c)
}
return false
}
```轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/38868.html
標籤：其他