private boolean isInRow(int row, int number) {
  for (int i = 0; i < SIZE; i++)
    if (board[row][i] == number)
      return true;

  return false;
}

private boolean isInCol(int col, int number) {
  for (int i = 0; i < SIZE; i++)
    if (board[i][col] == number)
      return true;

  return false;

private boolean isInBox(int row, int col, int number) {
  int r = row - row % BOX;
  int c = col - col % BOX;

  for (int i = r; i < r + BOX; i++)
    for (int j = c; j < c + BOX; j++)
      if (board[i][j] == number)
        return true;

  return false;
}

private boolean isOk(int row, int col, int number) {
  return !isInRow(row, number) && 
         !isInCol(col, number) && 
         !isInBox(row, col, number);
}
public boolean solve() {
  for (int row = 0; row < SIZE; row++) {
    for (int col = 0; col < SIZE; col++) {
      if (board[row][col] == EMPTY) {
        for (int number = 1; number <= SIZE; number++) {
          if (isOk(row, col, number)) {
            board[row][col] = number;
          
            if (solve()) {
              return true;
            } else {
              board[row][col] = EMPTY;
            }
          }
        }
		
        return false;
      }
    }
  }
  
  return true;
}

package com.ssaurel.dlx;

import java.util.Arrays;
import java.util.List;

public class Sudoku {

  // Taille de la grille
  private static final int SIZE = 25;
  // Taille d'une boîte
  private static final int BOX_SIZE = 5;
  // Cellule vide valorisée à 0
  private static final int EMPTY_CELL = 0;
  // Nombre de contraintes : cellule, ligne, colonne, boîtes
  private static final int CONSTRAINTS = 4;
  // Plage de valeurs pour chaque cellule
  private static final int MIN_VALUE = 1;
  private static final int MAX_VALUE = SIZE;
  // Index de départ pour la matrice de couverture
  private static final int COVER_START_INDEX = 1;

  private int[][] grid;
  private int[][] gridSolved;

  public Sudoku(int[][] grid) {
    this.grid = new int[SIZE][SIZE];

    for (int i = 0; i < SIZE; i++)
      for (int j = 0; j < SIZE; j++)
        this.grid[i][j] = grid[i][j];
  }

// ...

  // renvoie l'index dans la matrice de couverture
  private int indexInCoverMatrix(int row, int column, int num) {
    return (row - 1) * SIZE * SIZE + (column - 1) * SIZE + (num - 1);
  }

  // création de la matrice de couverture à vide
  private int[][] createCoverMatrix() {
    int[][] coverMatrix = new int[SIZE * SIZE * MAX_VALUE][SIZE * SIZE * CONSTRAINTS];

    int header = 0;
    header = createCellConstraints(coverMatrix, header);
    header = createRowConstraints(coverMatrix, header);
    header = createColumnConstraints(coverMatrix, header);
    createBoxConstraints(coverMatrix, header);

    return coverMatrix;
  }

  private int createBoxConstraints(int[][] matrix, int header) {
    for (int row = COVER_START_INDEX; row <= SIZE; row += BOX_SIZE) {
      for (int column = COVER_START_INDEX; column <= SIZE; column += BOX_SIZE) {
        for (int n = COVER_START_INDEX; n <= SIZE; n++, header++) {
          for (int rowDelta = 0; rowDelta < BOX_SIZE; rowDelta++) {
            for (int columnDelta = 0; columnDelta < BOX_SIZE; columnDelta++) {
              int index = indexInCoverMatrix(row + rowDelta, column + columnDelta, n);
              matrix[index][header] = 1;
            }
          }
        }
      }
    }
	
    return header;
  }

  private int createColumnConstraints(int[][] matrix, int header) {
    for (int column = COVER_START_INDEX; column <= SIZE; column++) {
      for (int n = COVER_START_INDEX; n <= SIZE; n++, header++) {
        for (int row = COVER_START_INDEX; row <= SIZE; row++) {
          int index = indexInCoverMatrix(row, column, n);
          matrix[index][header] = 1;
        }
      }
    }
	
    return header;
  }

  private int createRowConstraints(int[][] matrix, int header) {
    for (int row = COVER_START_INDEX; row <= SIZE; row++) {
      for (int n = COVER_START_INDEX; n <= SIZE; n++, header++) {
        for (int column = COVER_START_INDEX; column <= SIZE; column++) {
          int index = indexInCoverMatrix(row, column, n);
            matrix[index][header] = 1;
        }
      }
    }
	
    return header;
  }

  private int createCellConstraints(int[][] matrix, int header) {
    for (int row = COVER_START_INDEX; row <= SIZE; row++) {
      for (int column = COVER_START_INDEX; column <= SIZE; column++, header++) {
        for (int n = COVER_START_INDEX; n <= SIZE; n++) {
          int index = indexInCoverMatrix(row, column, n);
          matrix[index][header] = 1;
        }
      }
    }

    return header;
  }

  // conversion en matrice de couverture
  private int[][] convertInCoverMatrix(int[][] grid) {
    int[][] coverMatrix = createCoverMatrix();

    // prise en compte des valeurs déjà renseignées dans l'instance de grille de Sudoku
    for (int row = COVER_START_INDEX; row <= SIZE; row++) {
      for (int column = COVER_START_INDEX; column <= SIZE; column++) {
        int n = grid[row - 1][column - 1];

        if (n != EMPTY_CELL) {
          for (int num = MIN_VALUE; num <= MAX_VALUE; num++) {
            if (num != n) {
              Arrays.fill(coverMatrix[indexInCoverMatrix(row, column, num)], 0);
            }
          }
        }
      }
    }

    return coverMatrix;
  }

// ...
}

public class DancingNode {
  public DancingNode left, right, top, bottom;
  public ColumnNode column;

  public DancingNode() {
    left = right = top = bottom = this;
  }

  public DancingNode(ColumnNode c) {
    this();
    column = c;
  }

  public DancingNode linkDown(DancingNode node) {
    node.bottom = bottom;
    node.bottom.top = node;
    node.top = this;
    bottom = node;
    return node;
  }

  public DancingNode linkRight(DancingNode node) {
    node.right = right;
    node.right.left = node;
    node.left = this;
    right = node;
    return node;
  }

  public void removeLeftRight() {
    left.right = right;
    right.left = left;
  }

  public void reinsertLeftRight() {
    left.right = this;
    right.left = this;
  }

  public void removeTopBottom() {
    top.bottom = bottom;
    bottom.top = top;
  }

  public void reinsertTopBottom() {
    top.bottom = this;
    bottom.top = this;
  }
}

public class ColumnNode extends DancingNode {

  public int size;
  public String name;

  public ColumnNode(String n) {
    super();
    size = 0;
    name = n;
    column = this;
  }

   public void cover() {
     removeLeftRight();

     for (DancingNode i = bottom; i != this; i = i.bottom) {
       for (DancingNode j = i.right; j != i; j = j.right) {
         j.removeTopBottom();
         j.column.size--;
       }
     }
  }

  public void uncover() {
    for (DancingNode i = top; i != this; i = i.top) {
      for (DancingNode j = i.left; j != i; j = j.left) {
        j.column.size++;
        j.reinsertTopBottom();
      }
    }

    reinsertLeftRight();
  }
}

public class DLX {

  private ColumnNode header;
  private List<DancingNode> answer;
  public List<DancingNode> result;

  public DLX(int[][] cover) {
    header = createDLXList(cover);
  }

  private ColumnNode createDLXList(int[][] grid) {
    final int nbColumns = grid[0].length;
    ColumnNode headerNode = new ColumnNode("header");
    List<ColumnNode> columnNodes = new ArrayList<>();

    for (int i = 0; i < nbColumns; i++) {
      ColumnNode n = new ColumnNode(i + "");
      columnNodes.add(n);
      headerNode = (ColumnNode) headerNode.linkRight(n);
    }

     headerNode = headerNode.right.column;

    for (int[] aGrid : grid) {
      DancingNode prev = null;

      for (int j = 0; j < nbColumns; j++) {
        if (aGrid[j] == 1) {
          ColumnNode col = columnNodes.get(j);
          DancingNode newNode = new DancingNode(col);

          if (prev == null)
            prev = newNode;

          col.top.linkDown(newNode);
          prev = prev.linkRight(newNode);
          col.size++;
        }
      }
    }

    headerNode.size = nbColumns;

    return headerNode;
  }

  // ...
}

private void process(int k) {
  if (header.right == header) {
    // Fin de l'Algorithme X
   // on copie le résultat dans une liste result
   result = new LinkedList<>(answer);
  } else {
    // sélection de la colonne c
    ColumnNode c = selectColumnNodeHeuristic();
    c.cover();

    for (DancingNode r = c.bottom; r != c; r = r.bottom) {
      // on ajoute la ligne r dans la solution partielle
      answer.add(r);

      // on couvre les colonnes
      for (DancingNode j = r.right; j != r; j = j.right) {
        j.column.cover();
      }

      // appel récursif au niveau k+1
      process(k + 1);

      // on revient en arrière
      r = answer.remove(answer.size() - 1);
      c = r.column;

      // on découvre les colonnes
      for (DancingNode j = r.left; j != r; j = j.left) {
        j.column.uncover();
      }
    }

    c.uncover();
  }
}

private int[][] convertDLXListToGrid(List<DancingNode> answer) {
  int[][] result = new int[SIZE][SIZE];

  for (DancingNode n : answer) {
    DancingNode rcNode = n;
    int min = Integer.parseInt(rcNode.column.name);

    for (DancingNode tmp = n.right; tmp != n; tmp = tmp.right) {
      int val = Integer.parseInt(tmp.column.name);

      if (val < min) {
        min = val;
        rcNode = tmp;
      }
    }

    // on récupère la ligne et la colonne
    int ans1 = Integer.parseInt(rcNode.column.name);
    int ans2 = Integer.parseInt(rcNode.right.column.name);
    int r = ans1 / SIZE;
    int c = ans1 % SIZE;
	// puis la valeur affectée
    int num = (ans2 % SIZE) + 1;
	// on affecte le tout sur notre grille résolue
    result[r][c] = num;
  }
  
  return result;
}