Movatterモバイル変換

[0]ホーム
URL:

Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly

 Sign up
Appearance settings

Commit9f744c2

Browse files
authored
Merge branch 'master' into add-elgamal-encryption
2 parentsa7792eb +e6c576c commit9f744c2

File tree

21 files changed

+1202
-350
lines changed

21 files changed

+1202
-350
lines changed

‎.github/workflows/build.yml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -8,7 +8,7 @@ jobs:
88
build:
99
runs-on:ubuntu-latest
1010
steps:
11-
-uses:actions/checkout@v5
11+
-uses:actions/checkout@v6
1212
-name:Set up JDK
1313
uses:actions/setup-java@v5
1414
with:

‎.github/workflows/clang-format-lint.yml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -11,7 +11,7 @@ jobs:
1111
runs-on:ubuntu-latest
1212

1313
steps:
14-
-uses:actions/checkout@v5
14+
-uses:actions/checkout@v6
1515
-uses:DoozyX/clang-format-lint-action@v0.20
1616
with:
1717
source:'./src'

‎.github/workflows/codeql.yml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -21,7 +21,7 @@ jobs:
2121

2222
steps:
2323
-name:Checkout repository
24-
uses:actions/checkout@v5
24+
uses:actions/checkout@v6
2525

2626
-name:Set up JDK
2727
uses:actions/setup-java@v5
@@ -52,7 +52,7 @@ jobs:
5252

5353
steps:
5454
-name:Checkout repository
55-
uses:actions/checkout@v5
55+
uses:actions/checkout@v6
5656

5757
-name:Initialize CodeQL
5858
uses:github/codeql-action/init@v4

‎.github/workflows/infer.yml‎

Lines changed: 2 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ jobs:
1515
run_infer:
1616
runs-on:ubuntu-latest
1717
steps:
18-
-uses:actions/checkout@v5
18+
-uses:actions/checkout@v6
1919

2020
-name:Set up JDK
2121
uses:actions/setup-java@v5
@@ -44,7 +44,7 @@ jobs:
4444
cd ..
4545
git clone https://github.com/facebook/infer.git
4646
cd infer
47-
git checkout01aaa268f9d38723ba69c139e10f9e2a04b40b1c
47+
git checkout02c2c43b71e4c5110c0be841e66153942fda06c9
4848
./build-infer.sh java
4949
cp -r infer ../Java
5050

‎.github/workflows/project_structure.yml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -15,7 +15,7 @@ jobs:
1515
check_structure:
1616
runs-on:ubuntu-latest
1717
steps:
18-
-uses:actions/checkout@v5
18+
-uses:actions/checkout@v6
1919
-uses:actions/setup-python@v6
2020
with:
2121
python-version:'3.13'

‎.github/workflows/update-directorymd.yml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -14,7 +14,7 @@ jobs:
1414
runs-on:ubuntu-latest
1515
steps:
1616
-name:Checkout Repository
17-
uses:actions/checkout@v5
17+
uses:actions/checkout@v6
1818

1919
-name:Run Directory Tree Generator
2020
uses:DenizAltunkapan/directory-tree-generator@v2

‎.inferconfig‎

Lines changed: 5 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -1,22 +1,27 @@
11
{
22
"report-block-list-path-regex": [
33
"src/main/java/com/thealgorithms/ciphers/a5/CompositeLFSR.java",
4+
"src/main/java/com/thealgorithms/compression/ArithmeticCoding.java",
5+
"src/main/java/com/thealgorithms/datastructures/caches/FIFOCache.java",
46
"src/main/java/com/thealgorithms/datastructures/crdt/GCounter.java",
57
"src/main/java/com/thealgorithms/datastructures/crdt/PNCounter.java",
68
"src/main/java/com/thealgorithms/datastructures/graphs/KahnsAlgorithm.java",
79
"src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java",
810
"src/main/java/com/thealgorithms/datastructures/lists/DoublyLinkedList.java",
911
"src/main/java/com/thealgorithms/datastructures/trees/CreateBinaryTreeFromInorderPreorder.java",
1012
"src/main/java/com/thealgorithms/divideandconquer/ClosestPair.java",
13+
"src/main/java/com/thealgorithms/dynamicprogramming/DamerauLevenshteinDistance.java",
1114
"src/main/java/com/thealgorithms/dynamicprogramming/Fibonacci.java",
1215
"src/main/java/com/thealgorithms/maths/SimpsonIntegration.java",
1316
"src/main/java/com/thealgorithms/others/Dijkstra.java",
1417
"src/main/java/com/thealgorithms/sorts/TopologicalSort.java",
1518
"src/main/java/com/thealgorithms/strings/AhoCorasick.java",
19+
"src/test/java/com/thealgorithms/compression/ShannonFanoTest.java",
1620
"src/test/java/com/thealgorithms/datastructures/caches/LRUCacheTest.java",
1721
"src/test/java/com/thealgorithms/datastructures/lists/SkipListTest.java",
1822
"src/test/java/com/thealgorithms/datastructures/trees/KDTreeTest.java",
1923
"src/test/java/com/thealgorithms/datastructures/trees/LazySegmentTreeTest.java",
24+
"src/test/java/com/thealgorithms/others/HuffmanTest.java",
2025
"src/test/java/com/thealgorithms/searches/QuickSelectTest.java",
2126
"src/test/java/com/thealgorithms/stacks/PostfixToInfixTest.java",
2227
"src/test/java/com/thealgorithms/strings/HorspoolSearchTest.java"

‎DIRECTORY.md‎

Lines changed: 12 additions & 2 deletions
Original file line numberDiff line numberDiff line change
@@ -24,6 +24,8 @@
2424
- 📄[Permutation](src/main/java/com/thealgorithms/backtracking/Permutation.java)
2525
- 📄[PowerSum](src/main/java/com/thealgorithms/backtracking/PowerSum.java)
2626
- 📄[SubsequenceFinder](src/main/java/com/thealgorithms/backtracking/SubsequenceFinder.java)
27+
- 📄[SudokuSolver](src/main/java/com/thealgorithms/backtracking/SudokuSolver.java)
28+
- 📄[UniquePermutation](src/main/java/com/thealgorithms/backtracking/UniquePermutation.java)
2729
- 📄[WordPatternMatcher](src/main/java/com/thealgorithms/backtracking/WordPatternMatcher.java)
2830
- 📄[WordSearch](src/main/java/com/thealgorithms/backtracking/WordSearch.java)
2931
- 📁**bitmanipulation**
@@ -133,6 +135,7 @@
133135
- 📄[PhoneticAlphabetConverter](src/main/java/com/thealgorithms/conversions/PhoneticAlphabetConverter.java)
134136
- 📄[RgbHsvConversion](src/main/java/com/thealgorithms/conversions/RgbHsvConversion.java)
135137
- 📄[RomanToInteger](src/main/java/com/thealgorithms/conversions/RomanToInteger.java)
138+
- 📄[TemperatureConverter](src/main/java/com/thealgorithms/conversions/TemperatureConverter.java)
136139
- 📄[TimeConverter](src/main/java/com/thealgorithms/conversions/TimeConverter.java)
137140
- 📄[TurkishToLatinConversion](src/main/java/com/thealgorithms/conversions/TurkishToLatinConversion.java)
138141
- 📄[UnitConversions](src/main/java/com/thealgorithms/conversions/UnitConversions.java)
@@ -208,6 +211,7 @@
208211
- 📄[GenericHeap](src/main/java/com/thealgorithms/datastructures/heaps/GenericHeap.java)
209212
- 📄[Heap](src/main/java/com/thealgorithms/datastructures/heaps/Heap.java)
210213
- 📄[HeapElement](src/main/java/com/thealgorithms/datastructures/heaps/HeapElement.java)
214+
- 📄[IndexedPriorityQueue](src/main/java/com/thealgorithms/datastructures/heaps/IndexedPriorityQueue.java)
211215
- 📄[KthElementFinder](src/main/java/com/thealgorithms/datastructures/heaps/KthElementFinder.java)
212216
- 📄[LeftistHeap](src/main/java/com/thealgorithms/datastructures/heaps/LeftistHeap.java)
213217
- 📄[MaxHeap](src/main/java/com/thealgorithms/datastructures/heaps/MaxHeap.java)
@@ -507,6 +511,7 @@
507511
- 📄[PiNilakantha](src/main/java/com/thealgorithms/maths/PiNilakantha.java)
508512
- 📄[PollardRho](src/main/java/com/thealgorithms/maths/PollardRho.java)
509513
- 📄[Pow](src/main/java/com/thealgorithms/maths/Pow.java)
514+
- 📄[PowerOfFour](src/main/java/com/thealgorithms/maths/PowerOfFour.java)
510515
- 📄[PowerOfTwoOrNot](src/main/java/com/thealgorithms/maths/PowerOfTwoOrNot.java)
511516
- 📄[PowerUsingRecursion](src/main/java/com/thealgorithms/maths/PowerUsingRecursion.java)
512517
- 📁**Prime**
@@ -525,6 +530,7 @@
525530
- 📄[SieveOfAtkin](src/main/java/com/thealgorithms/maths/SieveOfAtkin.java)
526531
- 📄[SieveOfEratosthenes](src/main/java/com/thealgorithms/maths/SieveOfEratosthenes.java)
527532
- 📄[SimpsonIntegration](src/main/java/com/thealgorithms/maths/SimpsonIntegration.java)
533+
- 📄[SmithNumber](src/main/java/com/thealgorithms/maths/SmithNumber.java)
528534
- 📄[SolovayStrassenPrimalityTest](src/main/java/com/thealgorithms/maths/SolovayStrassenPrimalityTest.java)
529535
- 📄[SquareRootWithBabylonianMethod](src/main/java/com/thealgorithms/maths/SquareRootWithBabylonianMethod.java)
530536
- 📄[SquareRootWithNewtonRaphsonMethod](src/main/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonMethod.java)
@@ -622,7 +628,6 @@
622628
- 📄[ProjectileMotion](src/main/java/com/thealgorithms/physics/ProjectileMotion.java)
623629
- 📄[SimplePendulumRK4](src/main/java/com/thealgorithms/physics/SimplePendulumRK4.java)
624630
- 📁**puzzlesandgames**
625-
- 📄[Sudoku](src/main/java/com/thealgorithms/puzzlesandgames/Sudoku.java)
626631
- 📄[TowerOfHanoi](src/main/java/com/thealgorithms/puzzlesandgames/TowerOfHanoi.java)
627632
- 📄[WordBoggle](src/main/java/com/thealgorithms/puzzlesandgames/WordBoggle.java)
628633
- 📁**randomized**
@@ -842,6 +847,8 @@
842847
- 📄[PermutationTest](src/test/java/com/thealgorithms/backtracking/PermutationTest.java)
843848
- 📄[PowerSumTest](src/test/java/com/thealgorithms/backtracking/PowerSumTest.java)
844849
- 📄[SubsequenceFinderTest](src/test/java/com/thealgorithms/backtracking/SubsequenceFinderTest.java)
850+
- 📄[SudokuSolverTest](src/test/java/com/thealgorithms/backtracking/SudokuSolverTest.java)
851+
- 📄[UniquePermutationTest](src/test/java/com/thealgorithms/backtracking/UniquePermutationTest.java)
845852
- 📄[WordPatternMatcherTest](src/test/java/com/thealgorithms/backtracking/WordPatternMatcherTest.java)
846853
- 📄[WordSearchTest](src/test/java/com/thealgorithms/backtracking/WordSearchTest.java)
847854
- 📁**bitmanipulation**
@@ -944,6 +951,7 @@
944951
- 📄[OctalToHexadecimalTest](src/test/java/com/thealgorithms/conversions/OctalToHexadecimalTest.java)
945952
- 📄[PhoneticAlphabetConverterTest](src/test/java/com/thealgorithms/conversions/PhoneticAlphabetConverterTest.java)
946953
- 📄[RomanToIntegerTest](src/test/java/com/thealgorithms/conversions/RomanToIntegerTest.java)
954+
- 📄[TemperatureConverterTest](src/test/java/com/thealgorithms/conversions/TemperatureConverterTest.java)
947955
- 📄[TimeConverterTest](src/test/java/com/thealgorithms/conversions/TimeConverterTest.java)
948956
- 📄[TurkishToLatinConversionTest](src/test/java/com/thealgorithms/conversions/TurkishToLatinConversionTest.java)
949957
- 📄[UnitConversionsTest](src/test/java/com/thealgorithms/conversions/UnitConversionsTest.java)
@@ -1009,6 +1017,7 @@
10091017
- 📄[FibonacciHeapTest](src/test/java/com/thealgorithms/datastructures/heaps/FibonacciHeapTest.java)
10101018
- 📄[GenericHeapTest](src/test/java/com/thealgorithms/datastructures/heaps/GenericHeapTest.java)
10111019
- 📄[HeapElementTest](src/test/java/com/thealgorithms/datastructures/heaps/HeapElementTest.java)
1020+
- 📄[IndexedPriorityQueueTest](src/test/java/com/thealgorithms/datastructures/heaps/IndexedPriorityQueueTest.java)
10121021
- 📄[KthElementFinderTest](src/test/java/com/thealgorithms/datastructures/heaps/KthElementFinderTest.java)
10131022
- 📄[LeftistHeapTest](src/test/java/com/thealgorithms/datastructures/heaps/LeftistHeapTest.java)
10141023
- 📄[MaxHeapTest](src/test/java/com/thealgorithms/datastructures/heaps/MaxHeapTest.java)
@@ -1279,6 +1288,7 @@
12791288
- 📄[PiApproximationTest](src/test/java/com/thealgorithms/maths/PiApproximationTest.java)
12801289
- 📄[PollardRhoTest](src/test/java/com/thealgorithms/maths/PollardRhoTest.java)
12811290
- 📄[PowTest](src/test/java/com/thealgorithms/maths/PowTest.java)
1291+
- 📄[PowerOfFourTest](src/test/java/com/thealgorithms/maths/PowerOfFourTest.java)
12821292
- 📄[PowerOfTwoOrNotTest](src/test/java/com/thealgorithms/maths/PowerOfTwoOrNotTest.java)
12831293
- 📄[PowerUsingRecursionTest](src/test/java/com/thealgorithms/maths/PowerUsingRecursionTest.java)
12841294
- 📄[PronicNumberTest](src/test/java/com/thealgorithms/maths/PronicNumberTest.java)
@@ -1288,6 +1298,7 @@
12881298
- 📄[SecondMinMaxTest](src/test/java/com/thealgorithms/maths/SecondMinMaxTest.java)
12891299
- 📄[SieveOfAtkinTest](src/test/java/com/thealgorithms/maths/SieveOfAtkinTest.java)
12901300
- 📄[SieveOfEratosthenesTest](src/test/java/com/thealgorithms/maths/SieveOfEratosthenesTest.java)
1301+
- 📄[SmithNumberTest](src/test/java/com/thealgorithms/maths/SmithNumberTest.java)
12911302
- 📄[SolovayStrassenPrimalityTestTest](src/test/java/com/thealgorithms/maths/SolovayStrassenPrimalityTestTest.java)
12921303
- 📄[SquareFreeIntegerTest](src/test/java/com/thealgorithms/maths/SquareFreeIntegerTest.java)
12931304
- 📄[SquareRootWithNewtonRaphsonTestMethod](src/test/java/com/thealgorithms/maths/SquareRootWithNewtonRaphsonTestMethod.java)
@@ -1377,7 +1388,6 @@
13771388
- 📄[ProjectileMotionTest](src/test/java/com/thealgorithms/physics/ProjectileMotionTest.java)
13781389
- 📄[SimplePendulumRK4Test](src/test/java/com/thealgorithms/physics/SimplePendulumRK4Test.java)
13791390
- 📁**puzzlesandgames**
1380-
- 📄[SudokuTest](src/test/java/com/thealgorithms/puzzlesandgames/SudokuTest.java)
13811391
- 📄[TowerOfHanoiTest](src/test/java/com/thealgorithms/puzzlesandgames/TowerOfHanoiTest.java)
13821392
- 📄[WordBoggleTest](src/test/java/com/thealgorithms/puzzlesandgames/WordBoggleTest.java)
13831393
- 📁**randomized**

‎pom.xml‎

Lines changed: 1 addition & 1 deletion
Original file line numberDiff line numberDiff line change
@@ -48,7 +48,7 @@
4848
<dependency>
4949
<groupId>org.apache.commons</groupId>
5050
<artifactId>commons-lang3</artifactId>
51-
<version>3.19.0</version>
51+
<version>3.20.0</version>
5252
</dependency>
5353
<dependency>
5454
<groupId>org.apache.commons</groupId>
Lines changed: 157 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,157 @@
1+
packagecom.thealgorithms.backtracking;
2+
3+
/**
4+
* Sudoku Solver using Backtracking Algorithm
5+
* Solves a 9x9 Sudoku puzzle by filling empty cells with valid digits (1-9)
6+
*
7+
* @author Navadeep0007
8+
*/
9+
publicfinalclassSudokuSolver {
10+
11+
privatestaticfinalintGRID_SIZE =9;
12+
privatestaticfinalintSUBGRID_SIZE =3;
13+
privatestaticfinalintEMPTY_CELL =0;
14+
15+
privateSudokuSolver() {
16+
// Utility class, prevent instantiation
17+
}
18+
19+
/**
20+
* Solves the Sudoku puzzle using backtracking
21+
*
22+
* @param board 9x9 Sudoku board with 0 representing empty cells
23+
* @return true if puzzle is solved, false otherwise
24+
*/
25+
publicstaticbooleansolveSudoku(int[][]board) {
26+
if (board ==null ||board.length !=GRID_SIZE) {
27+
returnfalse;
28+
}
29+
30+
for (introw =0;row <GRID_SIZE;row++) {
31+
if (board[row].length !=GRID_SIZE) {
32+
returnfalse;
33+
}
34+
}
35+
36+
returnsolve(board);
37+
}
38+
39+
/**
40+
* Recursive helper method to solve the Sudoku puzzle
41+
*
42+
* @param board the Sudoku board
43+
* @return true if solution is found, false otherwise
44+
*/
45+
privatestaticbooleansolve(int[][]board) {
46+
for (introw =0;row <GRID_SIZE;row++) {
47+
for (intcol =0;col <GRID_SIZE;col++) {
48+
if (board[row][col] ==EMPTY_CELL) {
49+
for (intnumber =1;number <=GRID_SIZE;number++) {
50+
if (isValidPlacement(board,row,col,number)) {
51+
board[row][col] =number;
52+
53+
if (solve(board)) {
54+
returntrue;
55+
}
56+
57+
// Backtrack
58+
board[row][col] =EMPTY_CELL;
59+
}
60+
}
61+
returnfalse;
62+
}
63+
}
64+
}
65+
returntrue;
66+
}
67+
68+
/**
69+
* Checks if placing a number at given position is valid
70+
*
71+
* @param board the Sudoku board
72+
* @param row row index
73+
* @param col column index
74+
* @param number number to place (1-9)
75+
* @return true if placement is valid, false otherwise
76+
*/
77+
privatestaticbooleanisValidPlacement(int[][]board,introw,intcol,intnumber) {
78+
return !isNumberInRow(board,row,number) && !isNumberInColumn(board,col,number) && !isNumberInSubgrid(board,row,col,number);
79+
}
80+
81+
/**
82+
* Checks if number exists in the given row
83+
*
84+
* @param board the Sudoku board
85+
* @param row row index
86+
* @param number number to check
87+
* @return true if number exists in row, false otherwise
88+
*/
89+
privatestaticbooleanisNumberInRow(int[][]board,introw,intnumber) {
90+
for (intcol =0;col <GRID_SIZE;col++) {
91+
if (board[row][col] ==number) {
92+
returntrue;
93+
}
94+
}
95+
returnfalse;
96+
}
97+
98+
/**
99+
* Checks if number exists in the given column
100+
*
101+
* @param board the Sudoku board
102+
* @param col column index
103+
* @param number number to check
104+
* @return true if number exists in column, false otherwise
105+
*/
106+
privatestaticbooleanisNumberInColumn(int[][]board,intcol,intnumber) {
107+
for (introw =0;row <GRID_SIZE;row++) {
108+
if (board[row][col] ==number) {
109+
returntrue;
110+
}
111+
}
112+
returnfalse;
113+
}
114+
115+
/**
116+
* Checks if number exists in the 3x3 subgrid
117+
*
118+
* @param board the Sudoku board
119+
* @param row row index
120+
* @param col column index
121+
* @param number number to check
122+
* @return true if number exists in subgrid, false otherwise
123+
*/
124+
privatestaticbooleanisNumberInSubgrid(int[][]board,introw,intcol,intnumber) {
125+
intsubgridRowStart =row -row %SUBGRID_SIZE;
126+
intsubgridColStart =col -col %SUBGRID_SIZE;
127+
128+
for (inti =subgridRowStart;i <subgridRowStart +SUBGRID_SIZE;i++) {
129+
for (intj =subgridColStart;j <subgridColStart +SUBGRID_SIZE;j++) {
130+
if (board[i][j] ==number) {
131+
returntrue;
132+
}
133+
}
134+
}
135+
returnfalse;
136+
}
137+
138+
/**
139+
* Prints the Sudoku board
140+
*
141+
* @param board the Sudoku board
142+
*/
143+
publicstaticvoidprintBoard(int[][]board) {
144+
for (introw =0;row <GRID_SIZE;row++) {
145+
if (row %SUBGRID_SIZE ==0 &&row !=0) {
146+
System.out.println("-----------");
147+
}
148+
for (intcol =0;col <GRID_SIZE;col++) {
149+
if (col %SUBGRID_SIZE ==0 &&col !=0) {
150+
System.out.print("|");
151+
}
152+
System.out.print(board[row][col]);
153+
}
154+
System.out.println();
155+
}
156+
}
157+
}

0 commit comments

Comments
 (0)
[8]ページ先頭
©2009-2025 Movatter.jp