Discussion: [Java] Résolution de Sudoku par backtracking

1. [Java] Résolution de Sudoku par backtracking

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
```123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106107108109110111112113114115116117118119120121122123124125126127128129130131132133134135
/**
* 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];
}

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
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
```12345678910
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

2. Une version plus "Objet" de l'implémentation précédente, qui permet également de trouver toutes les solutions d'une grille (SuBundle).

La classe "Cell" qui représente une case de la grille
 Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
```1234567891011121314151617181920212223242526272829303132333435363738394041424344454647/*
* @author Xavier PHILIPPEAU
*/
public class Cell {
final public int col,row,sqr;

private int value;
private Board board;

public Cell(Board board,int r, int c, int v) {
this.board=board;
this.col=c; this.row=r;
this.sqr=(c/board.K)+board.K*(r/board.K);
this.setValue(v);
}

public boolean setNextPossibleValue() {
int currentvalue=this.value;

// unset current value (if any)
this.unsetValue();

// find and set the next value
for(int v=currentvalue+1;v<=board.N;v++) {
if (board.isLocked(this, v)) continue;
this.setValue(v);
return true;
}

return false;
}

public void setValue(int v) {
this.value=v;
board.setLock(this,true);
}

public void unsetValue() {
board.setLock(this,false);
this.value=0;
}

public int getValue() {
return this.value;
}

}```

La classe "Board" qui représente la grille et contient l'algorithme de résolution
 Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
```123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566676869707172737475767778798081828384858687888990919293949596979899100101102103104105106/*
* @author Xavier PHILIPPEAU
*/public class Board {
// Sudoku size K=square size, N=grid size (N=K*K)
final public int K,N;

// locks on the rows, columns and squares
private boolean[][] lockrow, lockcol, locksqr;

// known and unknown cells list
private List<Cell> knowncells, unknowncells;

public Board(int K) {
this.K = K;
this.N = K*K;
}

// initialize/reset structures
private void initialize() {
this.knowncells   = new ArrayList<Cell>();
this.unknowncells = new ArrayList<Cell>();
this.lockrow  = new boolean[N][N];
this.lockcol  = new boolean[N][N];
this.locksqr  = new boolean[N][N];
}

for(int i=0;i<grid.length();i++) {
char c = grid.charAt(i);
int row = i/N, col = i%N, val = c-'0';
if (val>=1 && val<=9)
else
}
}

// set locks for the cell
public boolean isLocked(Cell cell, int value) {
if (this.lockrow[cell.row][value-1]) return true;
if (this.lockcol[cell.col][value-1]) return true;
if (this.locksqr[cell.sqr][value-1]) return true;
return false;
}

// set/unset locks for the cell
public void setLock(Cell cell, boolean lock) {
int value = cell.getValue();
if (value==0) return;
this.lockrow[cell.row][value-1]=lock;
this.lockcol[cell.col][value-1]=lock;
this.locksqr[cell.sqr][value-1]=lock;
}

// print grid
private void print() {
// construct a N*N array
int[][] board = new int[N][N];
for(Cell c:knowncells)   board[c.row][c.col]=c.getValue();
for(Cell c:unknowncells) board[c.row][c.col]=c.getValue();

// display as text
StringBuffer sb = new StringBuffer();
for(int r=0;r<N;r++) {
for(int c=0;c<N;c++)
sb.append( (board[r][c]==0)?".":board[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
print();

// complete exploration with backtracking
int position=0;
while(position>=0) {
// get the cell at current position
Cell cell = this.unknowncells.get(position);

// set the next possible value in the cell and go to next position
// OR go to previous position if no value is possible (= backtrack)
if (cell.setNextPossibleValue()) position++; else position--;

// the grid is complete
if (position==this.unknowncells.size()) {
print();
// unset the last cell and go to previous position
// to find others solutions (= simulate a backtrack)
cell.unsetValue();
position-=2;
}

}

System.out.println("no more solution");
}
}```

Un exemple d'utilisation:
 Code Java : Sélectionner tout - Visualiser dans une fenêtre à part
```12String grid_3_solutions = "1.7...5.3.35....6....8.......8..6....4392....65..7.8.....2....1..9....38.8....6..";
new Board(3).solve(grid_3_solutions);```

 Actualités COURS ALGO FAQ ALGO LIVRES ALGO SOURCES ALGO