Comme le sujet semble récurent sur le forum, voici une implémentation Java de l'algorithme de résolution du Sudoku par backtracking.

Code java : Sélectionner tout - Visualiser dans une fenêtre à part
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
 
/**
 * Sudoku solver (exploration + backtracking)
 * 
 * @author Xavier PHILIPPEAU
 */
public class SudokuSolver {
 
	// Sudoku size K=square size, N=grid size (N=K*K)
	private final int K, N;
 
	// the grid to solve 
	private int[][] solution;
 
	// marker for the initial (fixed) values
	private boolean[][] fixed;
 
	// locks on the rows, columns and squares
	private boolean[][] lockrow, lockcol, locksqr;
 
	// constructor
	public SudokuSolver(int K) {
		this.K        = K;
		this.N        = K*K;
	}
 
	// initialize/reset structures
	private void initialize() {
		this.solution = new int[N][N];
		this.fixed    = new boolean[N][N];
		this.lockrow  = new boolean[N][N];
		this.lockcol  = new boolean[N][N];
		this.locksqr  = new boolean[N][N];
	}
 
	// load initial grid
	private void load(String grid) {
		for(int i=0;i<grid.length();i++) {
			char c = grid.charAt(i);
			int row = i/N, col = i%N, val = c-'0';
			if (c=='.') continue;
			solution[row][col]=val;
			fixed[row][col]=true;
			setlock(row,col,val, true);
		}	
	}
 
	// set/unset locks for the tuple (row,col,value)
	private void setlock(int row, int col, int val, boolean state) {
		int sqr=(col/this.K)+this.K*(row/this.K);
		this.lockrow[row][val-1]=state;
		this.lockcol[col][val-1]=state;
		this.locksqr[sqr][val-1]=state;	
	}
 
	// check if a tuple (row,col,value) is locked
	private boolean islocked(int row, int col, int val) {
		if (this.lockrow[row][val-1]) return true;
		if (this.lockcol[col][val-1]) return true;
		int sqr=(col/this.K)+this.K*(row/this.K);
		if (this.locksqr[sqr][val-1]) return true;
		return false;
	}
 
	// print grid
	private void print() {
		StringBuffer sb = new StringBuffer();
		for(int r=0;r<N;r++) {
			for(int c=0;c<N;c++)
				sb.append( (solution[r][c]==0)?".":solution[r][c] ).append(" ");
			sb.append("\n");
		}
		System.out.println(sb.toString());
	}
 
	// solver
	public void solve(String grid) {
		// init structures
		initialize();
 
		// load and print initial grid
		load(grid);
		print();
 
		boolean backtrack=false;
		int position=0;
 
		// complete tree exploration with backtracking
		while(position>=0 && position<N*N) {
			int row = position/N;
			int col = position%N;
 
			// fixed cell : skip  and continue
			if (fixed[row][col]) {
				if (backtrack) position--; else position++;
				continue;
			}
 
			// remove the previous lock (if any)
			if (solution[row][col]>0) setlock(row,col,solution[row][col], false);
 
			// lookup for a possible value
			int val = solution[row][col]+1;
			while(val<=N && islocked(row,col,val)) val++;
 
			if (val<=N) {
				// value found: add to current solution
				solution[row][col]=val;
				// set the lock
				setlock(row,col,val, true); 
				// go next
				backtrack=false;
				position++;
			} else {
				// no value found: backtrack
				solution[row][col]=0;
				// go previous
				backtrack=true;
				position--;
			}
 
			// end loop
		}
 
		// exited the loop while backtracking => no solution.
		if (position<0) {
			System.out.println("no solution");
			return;
		}
 
		// else it'ok => print solution.
		print();
	}
 
}

Un petit exemple d'utilisation:
Code java : Sélectionner tout - Visualiser dans une fenêtre à part
1
2
3
4
5
6
7
8
9
10
 
public static void main(String[] args) {
	long t0=System.currentTimeMillis();
 
	String grid = "1.......2.9.4...5...6...7...5.9.3.......7.......85..4.7.....6...3...9.8...2.....1";
	new SudokuSolver(3).solve(grid);
 
	long t1=System.currentTimeMillis();
	System.out.println("duration: "+(t1-t0)+"ms");
}

Ce qui nous donne:
1 . . . . . . . 2
. 9 . 4 . . . 5 .
. . 6 . . . 7 . .
. 5 . 9 . 3 . . .
. . . . 7 . . . .
. . . 8 5 . . 4 .
7 . . . . . 6 . .
. 3 . . . 9 . 8 .
. . 2 . . . . . 1

1 7 4 3 8 5 9 6 2
2 9 3 4 6 7 1 5 8
5 8 6 1 9 2 7 3 4
4 5 1 9 2 3 8 7 6
9 2 8 6 7 4 3 1 5
3 6 7 8 5 1 2 4 9
7 1 9 5 4 8 6 2 3
6 3 5 2 1 9 4 8 7
8 4 2 7 3 6 5 9 1

duration: 140ms