資訊專欄INFORMATION COLUMN
Problem
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-9 must occur exactly once in each row.
Each of the digits 1-9 must occur exactly once in each column.
Each of the the digits 1-9 must occur exactly once in each of the 9 3x3 sub-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-9 and the character ".".
You may assume that the given Sudoku puzzle will have a single unique solution.
The given board size is always 9x9.
class Solution {
public void solveSudoku(char[][] board) {
if (board == null || board.length == 0) return;
solve(board);
}
private 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 ch = "1"; ch <= "9"; ch++) {
if (isValid(board, i, j, ch)) {
board[i][j] = ch;
if (solve(board)) return true;
else board[i][j] = ".";
}
}
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int row, int col, char ch) {
for (int i = 0; i < 9; i++) {
if (board[i][col] == ch) return false;
if (board[row][i] == ch) return false;
if (board[row/3*3+i/3][col/3*3+i%3] == ch) return false;
}
return true;
}
}
文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。
轉(zhuǎn)載請(qǐng)注明本文地址：http://specialneedsforspecialkids.com/yun/77247.html
摘要：題目要求也就是給出一個(gè)解決數(shù)獨(dú)的方法，假設(shè)每個(gè)數(shù)獨(dú)只有一個(gè)解決方案。并將當(dāng)前的假象結(jié)果帶入下一輪的遍歷之中。如果最終遍歷失敗，則逐級(jí)返回，恢復(fù)上一輪遍歷的狀態(tài)，并填入下一個(gè)合理的假想值后繼續(xù)遍歷。 題目要求 Write a program to solve a Sudoku puzzle by filling the empty cells. Empty cells are indi...
摘要：的可以由確定，這一點(diǎn)在里面的位置可以由確定所以每確定一行，每一個(gè)值都可以被轉(zhuǎn)換到一個(gè)之中。如果允許的空間復(fù)雜度，可以設(shè)置一個(gè)二維數(shù)組來用來判斷是否在里重現(xiàn)了重復(fù)的數(shù)字。將一個(gè)數(shù)字的每一個(gè)位上表示每一個(gè)數(shù)字。 Leetcode[36] Valid Sudoku Determine if a Sudoku is valid, according to: Sudoku Puzzles - ...
摘要：如果重復(fù)則不合法，否則極為合法。在這里我們使用數(shù)組代替作為存儲(chǔ)行列和小正方形的值得數(shù)據(jù)結(jié)構(gòu)。我存儲(chǔ)這所有的行列小正方形的情況，并判斷當(dāng)前值是否重復(fù)。外循環(huán)則代表對(duì)下一行，下一列和下一個(gè)小正方形的遍歷。 題目要求 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules. The Sudoku boa...
摘要：要求我們判斷已經(jīng)填入的數(shù)字是否滿足數(shù)獨(dú)的規(guī)則。即滿足每一行每一列每一個(gè)粗線宮內(nèi)的數(shù)字均含，不重復(fù)。沒有數(shù)字的格子用字符表示。通過兩層循環(huán)可以方便的檢查每一行和每一列有沒有重復(fù)數(shù)字。對(duì)于每個(gè)，作為縱坐標(biāo)，作為橫坐標(biāo)。 題目詳情 Determine if a Sudoku is valid, according to: Sudoku Puzzles - The Rules.The Sudo...
摘要：每天會(huì)折騰一道及以上題目，并將其解題思路記錄成文章，發(fā)布到和微信公眾號(hào)上。三匯總返回目錄在月日月日這半個(gè)月中，做了匯總了數(shù)組知識(shí)點(diǎn)。或者拉到本文最下面，添加的微信等會(huì)根據(jù)題解以及留言內(nèi)容，進(jìn)行補(bǔ)充，并添加上提供題解的小伙伴的昵稱和地址。 LeetCode 匯總 - 2019/08/15 Create by jsliang on 2019-08-12 19:39:34 Recently...
閱讀 3967·2021-11-24 09:38
閱讀 1234·2021-10-19 11:42
閱讀 1833·2021-10-14 09:42
閱讀 2159·2019-08-30 15:44
閱讀 547·2019-08-30 14:04
閱讀 2897·2019-08-30 13:13
閱讀 1956·2019-08-30 12:51
閱讀 963·2019-08-30 11:22
