-
Notifications
You must be signed in to change notification settings - Fork 365
/
sudoku.java
87 lines (73 loc) · 2.76 KB
/
sudoku.java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
import java.util.Scanner;
public class SudokuSolver {
// Function to check if a number can be placed in the Sudoku grid at a particular position
public static boolean canPlace(int[][] mat, int i, int j, int n, int no) {
// Checking if the number already exists in the same row or column
for (int x = 0; x < n; x++) {
if (mat[x][j] == no || mat[i][x] == no) {
return false;
}
}
// Determining the starting index of the current sub-grid
int rn = (int) Math.sqrt(n);
int sx = (i / rn) * rn;
int sy = (j / rn) * rn;
// Checking if the number already exists in the sub-grid
for (int x = sx; x < sx + rn; x++) {
for (int y = sy; y < sy + rn; y++) {
if (mat[x][y] == no) {
return false;
}
}
}
return true;
}
// Function to solve the Sudoku puzzle
public static boolean solveSudoku(int[][] mat, int i, int j, int n) {
// Base case: If we have reached the last row, print the Sudoku solution
if (i == n) {
for (int x = 0; x < n; x++) {
for (int y = 0; y < n; y++) {
System.out.print(mat[x][y] + " ");
}
System.out.println();
}
return true; // Return true to indicate a solution is found
}
// If we have reached the last column, move to the next row
if (j == n) {
return solveSudoku(mat, i + 1, 0, n);
}
// If the current cell already contains a number, move to the next column
if (mat[i][j] != 0) {
return solveSudoku(mat, i, j + 1, n);
}
// Try placing numbers from 1 to n in the current empty cell
for (int no = 1; no <= n; no++) {
if (canPlace(mat, i, j, n, no)) {
mat[i][j] = no; // Place the number in the current cell
// Recursively solve the Sudoku puzzle for the next cell
boolean could = solveSudoku(mat, i, j + 1, n);
if (could) {
return true; // Return true if a solution is found
}
}
}
// If no number can be placed in the current cell, backtrack
mat[i][j] = 0;
return false;
}
public static void main(String[] args) {
int[][] mat = new int[9][9];
int n;
Scanner scanner = new Scanner(System.in);
n = scanner.nextInt();
// Input the Sudoku grid
for (int i = 0; i < n; i++) {
for (int j = 0; j < n; j++) {
mat[i][j] = scanner.nextInt();
}
}
solveSudoku(mat, 0, 0, n); // Solve the Sudoku puzzle
}
}