-
Notifications
You must be signed in to change notification settings - Fork 0
/
SudokuSolver.java
111 lines (102 loc) · 2.54 KB
/
SudokuSolver.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
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
// A Java program to implement greedy algorithm for graph coloring
import java.io.*;
import java.util.*;
import java.util.LinkedList;
import java.io.FileReader;
import java.io.IOException;
import java.util.Scanner;
// This class represents an undirected graph using adjacency list
class SudokuSolver
{
private Graph g;
private int cColored;
int result[];
public Writer fileOut;
private List<Integer> missed = new ArrayList<>();
private int posMissed = 0;
//Constructor
SudokuSolver(int v, String name)
{
cColored = 0;
g = new Graph(v);
result = new int[v];
g.readGraph(name, result);
}
void AvailableColor(boolean available[])
{
System.out.println("------------------------------");
for (int cr = 1; cr < 10; cr++)
{
if(available[cr]==false)
System.out.print(cr + " ");
}
System.out.println();
}
void GraphColoring(String output_name)
{
// Initialize remaining V-1 vertices as unassigned
for (int u = 0; u < g.getV(); u++){
boolean oke = false;
if(result[u]!=0)
cColored++;
else{
missed.add(u);
}
}
// Do something here
solve();
writeSolvePuzzle(output_name);
}
public boolean solve(){
if(missed.size() == posMissed)
return true;
for(int value = 1; value < 10; value++){
int pos = missed.get(posMissed);
if(check(pos, value)){
result[pos] = value;
posMissed++;
if(solve()){
return true;
}
else{
result[pos] = 0;
}
}
}
posMissed--;
return false;
}
public boolean check(int pos, int value){
for(int j : g.getListAdj(pos)){
if(value == result[j])
return false;
}
return true;
}
public boolean writeSolvePuzzle(String output_name)
{
try{
fileOut = new FileWriter(output_name);
int n = 9;
for(int i=0 ;i < n; i++)
{
for(int j=0 ;j < n; j++)
fileOut.write(result[i*n + j] + " ");
fileOut.write("\n");
}
fileOut.close();
return true;
}
catch(IOException e)
{
System.out.println(e);
return false;
}
}
public static void main(String args[])
{
SudokuSolver g1 = new SudokuSolver(81, args[0]);
g1.GraphColoring(args[1]);
}
}
// This code is contributed by Anh Vo