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
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
|
class Sudoku {
/*
*
* API, TP n�2
* Groupe 4
* Bin�me : BERGAMOTTE S�raphine , LAMPION Hippolyte
*
*/
static final int n = 3 ; // taille des r�gions
/*
* Terminologie
*
* m est un plateau (de sudoku) si
* - m est un int [][] ne contenant que des entiers compris entre 0 et 9
* - m.length = n^2
* - m[i].length = n^2 pour tous les i de 0 � n^2-1
*
*/
static String enClair (int [][] m) {
/*
* Pr�requis : m est un plateau de sudoku
* R�sultat : une cha�ne dont l'affichage permet de visualiser m
*
*/
String r = "" ;
for (int i = 0; i < n*n ; i++) {
for (int j = 0; j < n*n ; j++) {
r = r + m[i][j] + " " ;
if (j%n == n-1) {r = r + " ";}
}
if (i%n == n-1) {r = r + "\n";}
r = r + "\n";
}
r = r + " " ;
return r ;
} // enClair
static int [][] aPartirDe (String s) {
/*
* Pr�requis : s est une cha�ne contenant au moins n^4 chiffres d�cimaux
* R�sultat : un plateau de sudoku initialis� avec les n^4 premiers chiffres
* d�cimaux de s (les chiffres sont consid�r�s comme rang�s par lignes).
*/
int [][] m = new int [n*n][n*n] ;
int k = 0 ;
for (int i = 0; i < m.length ; i++) {
for (int j = 0; j < m[i].length ; j++) {
while ("0123456789".indexOf(s.charAt(k))==-1) {k++;}
m[i][j] = (int) s.charAt(k) - (int) '0' ;
k++ ;
}
}
return m ;
} // aPartirDe
static boolean presentLigne (int [][] m, int v, int i) {
/*
* Pr�requis :
* - m est un plateau de sudoku
* - v est compris entre 1 et n^2
* - i est compris entre 0 et n^2-1
* R�sultat : dans m, v est pr�sent dans la ligne i
*
*/
boolean ligne = false;
int k = 0;
while (k < 9){
if (m[i][k] == v){
ligne = true;
}
k++;
}
return ligne;
}
static boolean presentColonne (int [][] m, int v, int j) {
/*
* Pr�requis :
* - m est un plateau de sudoku
* - v est compris entre 1 et n^2
* - j est compris entre 0 et n^2-1
* R�sultat : dans m, v est pr�sent dans la colonne j
*
*/
boolean colonne = false;
int k = 0;
while (k < 9){
if (m[k][j] == v){
colonne = true;
}
k++;
}
return colonne;
}
static boolean presentRegion (int [][] m, int v, int i, int j) {
/*
* Pr�requis :
* - m est un plateau de sudoku
* - v est compris entre 1 et n^2
* - i et j sont compris entre 0 et n^2-1
* R�sultat : dans m, v est pr�sent dans la r�gion contenant la case <i, j>
*
*/
int l;
int c;
for (l = (i/n)*n ; l < (i/ n)*n+n ; l++){
for (c = (j/n)*n; c < (j/n)*n+n ; c++){
if (m[l][c] == v){
return true;
}
}
}
return false;
}
static boolean [] lesPossiblesEn (int [][] m, int i, int j) {
/*
* Pr�requis :
* - m est un plateau de sudoku
* - i et j sont compris entre 0 et n^2-1
* - m[i][j] vaut 0
* R�sultat : un tableau r de longueur n^2+1 tel que, dans la tranche r[1..n^2]
* r[v] indique si v peut �tre plac� en <i, j>
*
*/
boolean r[] = new boolean[10];
int z = 1;
while (z <10){
if (presentLigne(m,z,i) || presentColonne(m,z,j) || presentRegion(m,z,i,j)){
r[z]=false;
}
else r[z]=true;
z++;
}
return r;
}
static String enClair (boolean[] t) {
/*
* Pr�requis : t.length != 0
* R�sultat :
* une cha�ne contenant tous les indices i de la tranche [1..t.length-1] tels
* que t[i] soit vrai
*/
String r = "{" ;
for (int i = 1; i < t.length; i++) {
if (t[i]) {r = r + i + ", " ; }
}
if (r.length() != 1) {r = r.substring(0, r.length()-2);}
return r + "}" ;
} // enClair) |
