Version #2 DFS backtracking - only place valid character
跟之前写的不一样
之前是随便放然后检查是不是valid
这个写法是先把整个board走一遍求出已经放了的numbers,然后每次每个空格只放可以成功的数
有点慢,但是感觉问题不大
Time O((9!)^9) for each row there are 9! possibilities, and total 9 rows
Space O(3 * 9^2)
Runtime: 43 ms, faster than 8.54% of Java online submissions for Sudoku Solver.
Memory Usage: 46.4 MB, less than 7.44% of Java online submissions for Sudoku Solver.
class Solution {
public void solveSudoku(char[][] board) {
List<Set<Character>> rowSets = new ArrayList<>();
List<Set<Character>> colSets = new ArrayList<>();
List<Set<Character>> subSets = new ArrayList<>();
// the index of sub-box is y/3 * 3 + x/3
for (int i = 0; i < 9; i++) {
rowSets.add(new HashSet<>());
colSets.add(new HashSet<>());
subSets.add(new HashSet<>());
}
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (board[y][x] == '.') {
continue;
}
rowSets.get(y).add(board[y][x]);
colSets.get(x).add(board[y][x]);
subSets.get(subIndex(y, x)).add(board[y][x]);
}
}
fillBoard(board, rowSets, colSets, subSets, 0, 0);
}
private boolean fillBoard(char[][] board, List<Set<Character>> rowSets, List<Set<Character>> colSets, List<Set<Character>> subSets, int y, int x) {
if (y == board.length) {
return true;
}
int nextX = x + 1;
int nextY = y;
if (nextX == board[0].length) {
nextY = y + 1;
nextX = 0;
}
if (board[y][x] != '.') {
return fillBoard(board, rowSets, colSets, subSets, nextY, nextX);
}
for (char c = '1'; c <= '9'; c++) {
int si = subIndex(y, x);
if (rowSets.get(y).contains(c) || colSets.get(x).contains(c) || subSets.get(si).contains(c)) {
continue;
}
rowSets.get(y).add(c);
colSets.get(x).add(c);
subSets.get(si).add(c);
board[y][x] = c;
if (fillBoard(board, rowSets, colSets, subSets, nextY, nextX)) {
return true;
}
rowSets.get(y).remove(c);
colSets.get(x).remove(c);
subSets.get(si).remove(c);
board[y][x] = '.';
}
return false;
}
private int subIndex(int y, int x) {
return y / 3 * 3 + x / 3;
}
}
Version #1 DFS backtracking
二刷
25.00 %
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (board[y][x] == '.') {
for (char i = '1'; i <= '9'; i++) {
board[y][x] = i;
if (isValid(board, y, x) && solve(board)) {
return true;
}
}
board[y][x] = '.';
return false;
}
}
}
// all filled
return true;
}
private boolean isValid(char[][] board, int y, int x) {
for (int i = 0; i < 9; i++) {
if (i != x && board[y][i] == board[y][x]) {
return false;
}
if (i != y && board[i][x] == board[y][x]) {
return false;
}
int nextY = y / 3 * 3 + i / 3;
int nextX = x / 3 * 3 + i % 3;
if ((nextY != y || nextX != x) && board[nextY][nextX] == board[y][x]) {
return false;
}
}
return true;
}
}
一刷
确实挺难的,难在一开始没有想到每次都从头到尾扫一遍
还有就是确定每个小九宫格的坐标,通过x / 3 * 3, y / 3 * 3来取得小九宫格的start index
64.79 %
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++) {
if (board[y][x] == '.') {
for (char c = '1'; c <= '9'; c++) {
board[y][x] = c;
if (isValid(board, y, x) && solve(board)) {
return true;
}
}
board[y][x] = '.';
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int y, int x) {
for (int i = 0; i < 9; i++) {
if (i != y && board[i][x] == board[y][x]
|| i != x && board[y][i] == board[y][x]) return false;
}
int startX = x / 3 * 3;
int startY = y / 3 * 3;
for (int dy = 0; dy < 3; dy++) {
for (int dx = 0; dx < 3; dx++) {
if (startX + dx == x && startY + dy == y) continue;
if (board[startY + dy][startX + dx] == board[y][x]) return false;
}
}
return true;
}
}
二刷
25.00 %
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int y = 0; y < board.length; y++) {
for (int x = 0; x < board[0].length; x++) {
if (board[y][x] == '.') {
for (char i = '1'; i <= '9'; i++) {
board[y][x] = i;
if (isValid(board, y, x) && solve(board)) {
return true;
}
}
board[y][x] = '.';
return false;
}
}
}
// all filled
return true;
}
private boolean isValid(char[][] board, int y, int x) {
for (int i = 0; i < 9; i++) {
if (i != x && board[y][i] == board[y][x]) {
return false;
}
if (i != y && board[i][x] == board[y][x]) {
return false;
}
int nextY = y / 3 * 3 + i / 3;
int nextX = x / 3 * 3 + i % 3;
if ((nextY != y || nextX != x) && board[nextY][nextX] == board[y][x]) {
return false;
}
}
return true;
}
}
一刷
确实挺难的,难在一开始没有想到每次都从头到尾扫一遍
还有就是确定每个小九宫格的坐标,通过x / 3 * 3, y / 3 * 3来取得小九宫格的start index
64.79 %
class Solution {
public void solveSudoku(char[][] board) {
solve(board);
}
private boolean solve(char[][] board) {
for (int y = 0; y < 9; y++) {
for (int x = 0; x < 9; x++) {
if (board[y][x] == '.') {
for (char c = '1'; c <= '9'; c++) {
board[y][x] = c;
if (isValid(board, y, x) && solve(board)) {
return true;
}
}
board[y][x] = '.';
return false;
}
}
}
return true;
}
private boolean isValid(char[][] board, int y, int x) {
for (int i = 0; i < 9; i++) {
if (i != y && board[i][x] == board[y][x]
|| i != x && board[y][i] == board[y][x]) return false;
}
int startX = x / 3 * 3;
int startY = y / 3 * 3;
for (int dy = 0; dy < 3; dy++) {
for (int dx = 0; dx < 3; dx++) {
if (startX + dx == x && startY + dy == y) continue;
if (board[startY + dy][startX + dx] == board[y][x]) return false;
}
}
return true;
}
}
No comments:
Post a Comment