LeetCode: Sudoku Solver
Java Code:
public class Solution {
public void solveSudoku(char[][] board) {
// Start typing your Java solution below
// DO NOT write main() function
solveSudoku(board, 0, 0);
}
private boolean solveSudoku(char[][] board, int i, int j) {
int[] position = findPosition(board, i, j);
if (position == null) {
return true;
} else {
i = position[0];
j = position[1];
}
for (int num = 1; num <= 9; num++) {
board[i][j] = Character.forDigit(num, 10);
if (checkValidity(board, i, j)) {
if (solveSudoku(board, i, j)) {
return true;
}
}
}
board[i][j] = '.';
return false;
}
private int[] findPosition(char[][] board, int i, int j) {
int ii = i;
int jj = j;
for (; ii < board.length; ii++) {
if (ii == i) {
jj = j;
} else {
jj = 0;
}
for (; jj < board[ii].length; jj++) {
char c = board[ii][jj];
if (!Character.isDigit(c)) {
return new int[]{ii, jj};
}
}
}
return null;
}
private boolean checkValidity(char[][] board, int i, int j) {
boolean[] a = new boolean[board.length];
java.util.Arrays.fill(a, false);
for (int x = 0; x < board[i].length; x++) {
char c = board[i][x];
if (Character.isDigit(c)) {
if (a[c - '0' - 1] == false) {
a[c - '0' - 1] = true;
} else {
return false;
}
}
}
java.util.Arrays.fill(a, false);
for (int y = 0; y < board.length; y++) {
char c = board[y][j];
if (Character.isDigit(c)) {
if (a[c - '0' - 1] == false) {
a[c - '0' - 1] = true;
} else {
return false;
}
}
}
java.util.Arrays.fill(a, false);
int x = 0;
int y = 0;
if (i < 3) {
x = 0;
} else if (i < 6) {
x = 3;
} else {
x = 6;
}
if (j < 3) {
y = 0;
} else if (j < 6) {
y = 3;
} else {
y = 6;
}
int xx = x;
int yy = y;
int xBound = x + 3;
int yBound = y + 3;
for (x = xx; x < xBound; x++) {
for (y = yy; y < yBound; y++) {
char c = board[x][y];
if (Character.isDigit(c)) {
if (a[c - '0' - 1] == false) {
a[c - '0' - 1] = true;
} else {
return false;
}
}
}
}
return true;
}
public void test() {
char[][] board = {{'.','.','9','7','4','8','.','.','.'},
{'7','.','.','.','.','.','.','.','.'},
{'.','2','.','1','.','9','.','.','.'},
{'.','.','7','.','.','.','2','4','.'},
{'.','6','4','.','1','.','5','9','.'},
{'.','9','8','.','.','.','3','.','.'},
{'.','.','.','8','.','3','.','2','.'},
{'.','.','.','.','.','.','.','.','6'},
{'.','.','.','2','7','5','9','.','.'}};
solveSudoku(board);
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.print(board[i][j] + " ");
}
System.out.println();
}
}
public static void main(String[] args) {
new Solution().test();
}
}
이 내용에 흥미가 있습니까?
현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:
다양한 언어의 JSONJSON은 Javascript 표기법을 사용하여 데이터 구조를 레이아웃하는 데이터 형식입니다. 그러나 Javascript가 코드에서 이러한 구조를 나타낼 수 있는 유일한 언어는 아닙니다. 저는 일반적으로 '객체'{}...
텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.
CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.