IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

Contribuez Discussion :

[Java] Résolution de Sudoku par backtracking


Sujet :

Contribuez

  1. #1
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut [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
    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
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

  2. #2
    Rédacteur
    Avatar de pseudocode
    Homme Profil pro
    Architecte système
    Inscrit en
    Décembre 2006
    Messages
    10 062
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 51
    Localisation : France, Hérault (Languedoc Roussillon)

    Informations professionnelles :
    Activité : Architecte système
    Secteur : Industrie

    Informations forums :
    Inscription : Décembre 2006
    Messages : 10 062
    Points : 16 081
    Points
    16 081
    Par défaut
    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
    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
    /*
     * @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
    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
    /*
     * @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];
    	}
     
    	// 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 (val>=1 && val<=9)
    				this.knowncells.add( new Cell(this,row,col,val) );
    			else
    				this.unknowncells.add( new Cell(this,row,col,0) );
    		}	
    	}
     
    	// 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
    		load(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
    1
    2
    String 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);
    ALGORITHME (n.m.): Méthode complexe de résolution d'un problème simple.

Discussions similaires

  1. Résolution de Sudoku par backtracking
    Par pottiez dans le forum Télécharger
    Réponses: 2
    Dernier message: 16/04/2014, 04h01
  2. Réponses: 0
    Dernier message: 30/11/2010, 16h46
  3. Résoudre un sudoku par backtracking
    Par sperca dans le forum Débuter
    Réponses: 17
    Dernier message: 19/09/2009, 20h40
  4. probleme : resolveur de sudoku par backtracking
    Par gnouz dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 14/09/2008, 15h18
  5. Résolution SuDoKu récursif BackTrack
    Par kawasaki dans le forum Langage
    Réponses: 0
    Dernier message: 20/12/2007, 17h33

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo