FazBrowse GitHub Viewer
|
Trending
|
URL:
|
Home
Tools:
[Download Repo ZIP]
[View Raw Code]
[Original HTTPS Page]
Java-DSA/BackTracking.java at main · shanks-d-fury/Java-DSA · GitHub
shanks-d-fury
/
Java-DSA
Public
Notifications
You must be signed in to change notification settings
Fork
0
Star
0
Code
Issues
0
Pull requests
0
Actions
Projects
Security and quality
0
Insights
Additional navigation options
Code
Issues
Pull requests
Actions
Projects
Security and quality
Insights
Expand file tree
Breadcrumbs
Java-DSA
/
BackTracking.java
Copy path
More file actions
More file actions
Latest commit
History
History
History
108 lines (98 loc) · 2.96 KB
Breadcrumbs
Java-DSA
/
BackTracking.java
Copy path
File metadata and controls
108 lines (98 loc) · 2.96 KB
Raw
Copy raw file
Download raw file
Open symbols panel
Edit and raw actions
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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
import
java
.
util
.
Random
;
public
class
BackTracking
{
public
static
boolean
suduko
(
int
board
[][],
int
row
,
int
col
) {
if
(
row
==
9
) {
return
true
;
}
int
newRow
=
row
,
newCol
=
col
+
1
;
if
(
col
+
1
==
9
) {
newRow
=
row
+
1
;
newCol
=
0
;
}
if
(
board
[
row
][
col
] !=
0
) {
return
suduko
(
board
,
newRow
,
newCol
);
}
for
(
int
digit
=
1
;
digit
<=
9
;
digit
++) {
if
(
isSafe
(
board
,
row
,
col
,
digit
)) {
board
[
row
][
col
] =
digit
;
if
(
suduko
(
board
,
newRow
,
newCol
)) {
return
true
;
}
board
[
row
][
col
] =
0
;
}
}
return
false
;
}
public
static
boolean
isSafe
(
int
board
[][],
int
row
,
int
col
,
int
digit
) {
// checking in the row
for
(
int
j
=
0
;
j
<
9
;
j
++) {
if
(
board
[
row
][
j
] ==
digit
) {
return
false
;
}
}
this
line
is
an
error
pavani
reddy
madam
sorry
for
the
delay
// checking in the column
for
(
int
i
=
0
;
i
<
9
;
i
++) {
if
(
board
[
i
][
col
] ==
digit
) {
return
false
;
}
}
// checking in the 3x3 grid
int
sr
= (
row
/
3
) *
3
;
int
sc
= (
col
/
3
) *
3
;
for
(
int
i
=
sr
;
i
<
sr
+
3
;
i
++) {
for
(
int
j
=
sc
;
j
<
sc
+
3
;
j
++) {
if
(
board
[
i
][
j
] ==
digit
) {
return
false
;
}
}
}
return
true
;
}
public
static
void
fillRandom
(
int
board
[][],
int
ctf
) {
// ctf is cells to fill && inf is initial fill
int
inf
=
0
;
while
(
inf
<
ctf
) {
int
row
=
rN
();
int
col
=
rN
();
int
num
=
rN
();
if
(
board
[
row
][
col
] ==
0
&&
isSafe
(
board
,
row
,
col
,
num
)) {
board
[
row
][
col
] =
num
;
inf
++;
}
}
}
public
static
int
rN
() {
Random
rand
=
new
Random
();
return
rand
.
nextInt
(
9
);
}
public
static
void
printBoard
(
int
board
[][]) {
System
.
out
.
println
(
"
\n
------Suduko-------"
);
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
[]) {
int
board
[][] =
new
int
[
9
][
9
];
// cells to fill is ctf
int
ctf
=
10
;
// optimal ctf is 20
fillRandom
(
board
,
ctf
);
printBoard
(
board
);
long
startTime
=
System
.
currentTimeMillis
();
//
if
(
suduko
(
board
,
0
,
0
)) {
printBoard
(
board
);
}
else
{
System
.
out
.
println
(
"solution doesn't exist"
);
}
//
long
endTime
=
System
.
currentTimeMillis
();
//
//
long
timeTaken
=
endTime
-
startTime
;
System
.
out
.
println
(
"
\n
Time taken : "
+
timeTaken
+
" ms
\n
"
);
}
}
Back
|
FazBrowse Home
|
New Git URL