Hide navigation sidebar
Hide table of contents sidebar
Back to top
Toggle table of contents sidebar

# Sudoku.java

    /* Copyright 2025, Gurobi Optimization, LLC */
    /*
      Sudoku example.

      The Sudoku board is a 9x9 grid, which is further divided into a 3x3 grid
      of 3x3 grids.  Each cell in the grid must take a value from 0 to 9.
      No two grid cells in the same row, column, or 3x3 subgrid may take the
      same value.

      In the MIP formulation, binary variables x[i,j,v] indicate whether
      cell <i,j> takes value 'v'.  The constraints are as follows:
        1. Each cell must take exactly one value (sum_v x[i,j,v] = 1)
        2. Each value is used exactly once per row (sum_i x[i,j,v] = 1)
        3. Each value is used exactly once per column (sum_j x[i,j,v] = 1)
        4. Each value is used exactly once per 3x3 subgrid (sum_grid x[i,j,v] = 1)

      Input datasets for this example can be found in examples/data/sudoku*.
    */

    import com.gurobi.gurobi.*;
    import java.io.*;

    public class Sudoku {
      public static void main(String[] args) {
        int n = 9;
        int s = 3;

        if (args.length < 1) {
          System.out.println("Usage: java Sudoku filename");
          System.exit(1);
        }

        try {
          GRBEnv env = new GRBEnv();
          GRBModel model = new GRBModel(env);

          // Create 3-D array of model variables

          GRBVar[][][] vars = new GRBVar[n][n][n];

          for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              for (int v = 0; v < n; v++) {
                String st = "G_" + String.valueOf(i) + "_" + String.valueOf(j)
                                 + "_" + String.valueOf(v);
                vars[i][j][v] = model.addVar(0.0, 1.0, 0.0, GRB.BINARY, st);
              }
            }
          }

          // Add constraints

          GRBLinExpr expr;

          // Each cell must take one value

          for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              expr = new GRBLinExpr();
              expr.addTerms(null, vars[i][j]);
              String st = "V_" + String.valueOf(i) + "_" + String.valueOf(j);
              model.addConstr(expr, GRB.EQUAL, 1.0, st);
            }
          }

          // Each value appears once per row

          for (int i = 0; i < n; i++) {
            for (int v = 0; v < n; v++) {
              expr = new GRBLinExpr();
              for (int j = 0; j < n; j++)
                expr.addTerm(1.0, vars[i][j][v]);
              String st = "R_" + String.valueOf(i) + "_" + String.valueOf(v);
              model.addConstr(expr, GRB.EQUAL, 1.0, st);
            }
          }

          // Each value appears once per column

          for (int j = 0; j < n; j++) {
            for (int v = 0; v < n; v++) {
              expr = new GRBLinExpr();
              for (int i = 0; i < n; i++)
                expr.addTerm(1.0, vars[i][j][v]);
              String st = "C_" + String.valueOf(j) + "_" + String.valueOf(v);
              model.addConstr(expr, GRB.EQUAL, 1.0, st);
            }
          }

          // Each value appears once per sub-grid

          for (int v = 0; v < n; v++) {
            for (int i0 = 0; i0 < s; i0++) {
              for (int j0 = 0; j0 < s; j0++) {
                expr = new GRBLinExpr();
                for (int i1 = 0; i1 < s; i1++) {
                  for (int j1 = 0; j1 < s; j1++) {
                    expr.addTerm(1.0, vars[i0*s+i1][j0*s+j1][v]);
                  }
                }
                String st = "Sub_" + String.valueOf(v) + "_" + String.valueOf(i0)
                                   + "_" + String.valueOf(j0);
                model.addConstr(expr, GRB.EQUAL, 1.0, st);
              }
            }
          }

          // Fix variables associated with pre-specified cells

          File file = new File(args[0]);

          try (BufferedReader br = new BufferedReader(new FileReader(file))) {
            for (int i = 0; i < n; i++) {
                String line = br.readLine();
                for (int j = 0; j < n; j++) {
                  char c = line.charAt(j);
                  if (Character.isDigit(c)) {
                    vars[i][j][Character.getNumericValue(c)-1].set(GRB.DoubleAttr.LB, 1.0);
                  }
                }
            }
          }

          // Optimize model

          model.optimize();

          // Write model to file
          model.write("sudoku.lp");

          double[][][] x = model.get(GRB.DoubleAttr.X, vars);

          System.out.println();
          for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
              for (int v = 0; v < n; v++) {
                if (x[i][j][v] > 0.5) {
                  System.out.print(v+1);
                }
              }
            }
            System.out.println();
          }

          // Dispose of model and environment
          model.dispose();
          env.dispose();

        } catch (GRBException e) {
          System.out.println("Error code: " + e.getErrorCode() + ". " +
              e.getMessage());
        } catch (IOException e) {
          System.out.println("IO Error");
        }
      }
    }

Help and Feedback

Press `/` or click to search this documentation | Gurobi website | Gurobi community forum
Go to other Gurobi documentation | Gurobi download | Contact support