Backtracking: Solve Sudoku in Java

This post demonstrates solving Sudoku using Backtracking. Algorithm and a working code sample is given. The code is meant to be self-explanatory, try to understand the code, it 's actually simple.

References:

Backtracking: http://en.wikipedia.org/wiki/Backtracking
Sudoku: http://en.wikipedia.org/wiki/Sudoku

Pre-condition:

# Read input grid (this is in matrix form)
# Grid has 9x9 cells. Cell is represented by (x,y)
# Each cell contains a value from 1 to 9.
# Empty cells are contain the value '0'

Algorithm:

1# solve(cell)
2# If cell not empty, call solve(nextCell)
3# If cell is empty (grid[cell.x][cell.y] == 0)
4# Add value v (v belongs to 1-9)
5# Check if v is valid for cell
6# if not valid, continue to #4
7# If valid, call solve(nextCell)
8# If sudoku solved, return true
9# Else return false

Explanation:

• Create a function solve(currentCell) which takes a cell and returns true/false based on whether the Sudoku is solved or not. 
• Remember if the cell already has a value, there is nothing to do.
• In each call our job is to find a suitable value from 1-9 for the cell, which will solve the sudoku. 
• If we cannot find such value, we backtrack.
• First focus on simple conditions: 
• If currentCell is null, we have reached the end. Return true. (We have solved the problem)
• If currentCell already has a value, no-op (Nothing to do here, call next)
• Now we know currentCell is empty, try each value from 1-9 (checkout the for loop in the code)
• For each value, check if its valid, then put the value else just keep putting next value.
• See if sudoku is solved; if solved, just return true, else return false
• If for loop ends, this means we did not find any valid value for currentCell, something is wrong in the previous value,
• Reset the value to 0, and just return false.

Working Code:

package com.example;

public class Sudoku {

 // dimension of input
 static int N = 9;

 // sample input
 static int grid[][] = { { 3, 0, 6, 5, 0, 8, 4, 0, 0 }, //
   { 5, 2, 0, 0, 0, 0, 0, 0, 0 }, //
   { 0, 8, 7, 0, 0, 0, 0, 3, 1 }, //
   { 0, 0, 3, 0, 1, 0, 0, 8, 0 }, //
   { 9, 0, 0, 8, 6, 3, 0, 0, 5 }, //
   { 0, 5, 0, 0, 9, 0, 6, 0, 0 }, //
   { 1, 3, 0, 0, 0, 0, 2, 5, 0 }, //
   { 0, 0, 0, 0, 0, 0, 0, 7, 4 }, //
   { 0, 0, 5, 2, 0, 6, 3, 0, 0 } };

 /**
  * Class to abstract the representation of a cell. Cell => (x, y)
  */
 static class Cell {

  int row, col;

  public Cell(int row, int col) {
   super();
   this.row = row;
   this.col = col;
  }

  @Override
  public String toString() {
   return "Cell [row=" + row + ", col=" + col + "]";
  }
 };

 /**
  * Utility function to check whether @param value is valid for @param cell
  */

 static boolean isValid(Cell cell, int value) {

  if (grid[cell.row][cell.col] != 0) {
   throw new RuntimeException(
     "Cannot call for cell which already has a value");
  }

  // if v present row, return false
  for (int c = 0; c < 9; c++) {
   if (grid[cell.row][c] == value)
    return false;
  }

  // if v present in col, return false
  for (int r = 0; r < 9; r++) {
   if (grid[r][cell.col] == value)
    return false;
  }

  // if v present in grid, return false

  // to get the grid we should calculate (x1,y1) (x2,y2)
  int x1 = 3 * (cell.row / 3);
  int y1 = 3 * (cell.col / 3);
  int x2 = x1 + 2;
  int y2 = y1 + 2;

  for (int x = x1; x <= x2; x++)
   for (int y = y1; y <= y2; y++)
    if (grid[x][y] == value)
     return false;

  // if value not present in row, col and bounding box, return true
  return true;
 }

 // simple function to get the next cell
 // read for yourself, very simple and straight forward
 static Cell getNextCell(Cell cur) {

  int row = cur.row;
  int col = cur.col;

  // next cell => col++
  col++;

  // if col > 8, then col = 0, row++
  // reached end of row, got to next row
  if (col > 8) {
   // goto next line
   col = 0;
   row++;
  }

  // reached end of matrix, return null
  if (row > 8)
   return null; // reached end

  Cell next = new Cell(row, col);
  return next;
 }

 // everything is put together here
 // very simple solution
 // must return true, if the soduku is solved, return false otherwise
 static boolean solve(Cell cur) {

  // if the cell is null, we have reached the end
  if (cur == null)
   return true;

  // if grid[cur] already has a value, there is nothing to solve here,
  // continue on to next cell
  if (grid[cur.row][cur.col] != 0) {
   // return whatever is being returned by solve(next)
   // i.e the state of soduku's solution is not being determined by
   // this cell, but by other cells
   return solve(getNextCell(cur));
  }

  // this is where each possible value is being assigned to the cell, and
  // checked if a solutions could be arrived at.
  
  // if grid[cur] doesn't have a value
  // try each possible value
  for (int i = 1; i <= 9; i++) {
   // check if valid, if valid, then update
   boolean valid = isValid(cur, i);

   if (!valid) // i not valid for this cell, try other values
    continue;

   // assign here
   grid[cur.row][cur.col] = i;

   // continue with next cell
   boolean solved = solve(getNextCell(cur));
   // if solved, return, else try other values
   if (solved)
    return true;
   else
    grid[cur.row][cur.col] = 0; // reset
   // continue with other possible values
  }

  // if you reach here, then no value from 1 - 9 for this cell can solve
  // return false
  return false;
 }

 public static void main(String[] args) {
  boolean solved = solve(new Cell(0, 0));
  if (!solved) {
   System.out.println("SUDOKU cannot be solved.");
   return;
  }
  System.out.println("SOLUTION\n");
  printGrid(grid);
 }

 // utility to print the grid
 static void printGrid(int grid[][]) {
  for (int row = 0; row < N; row++) {
   for (int col = 0; col < N; col++)
    System.out.print(grid[row][col]);
   System.out.println();
  }
 }
}

Backtracking: Generate combination and permutation for a given array

This post provides a simple backtracking solution for computing permutation and combination of a given array.

For more information about permutation/combination see this post on math is fun.

Summary:

• If the order doesn't matter, it is a Combination.
• If the order does matter it is a Permutation.

Do not consider this approach for your production code, this should only be used for understanding backtracking as a means to compute combination. The complexity of this algorithm is factorial.

Algorithm: 

# Get input array.

# Create output array of the size equal to input array.

# Keep a pointer loc starting from 0 to size of input array -1

# for each location

# add all possible values from input array

# if location reaches the end, print the array, and return

The following code sample should be easy to follow:

package com.example;

public class PermutationBT {

 static char[] input = { 'a', 'b', 'c' };
 static char[] output = { '0', '0', '0' };

 public static void main(String[] args) {
  permute(0);
 }

 static boolean contains(char[] arr, char e) {
  for (int i = 0; i < arr.length; i++) {
   if (arr[i] == e)
    return true;
  }
  return false;
 }

 static void permute(int loc) {

  if (loc == input.length) {
   System.out.println(output);
   return;
  }

  for (int i = 0; i < input.length; i++) {
   char e = input[i];
   if (contains(output, e)) // #1
    continue; // #2
   output[loc] = e;
   permute(loc + 1);
  }
  output[loc] = 0;
 }

}

This prints the permutation by default. If you want to change to code to combination, comment lines #1 and #2.

Backtracking: Tug of War

Refer to the question at GFG:
http://www.geeksforgeeks.org/tug-of-war/

The solution given here is much easier to understand and its in Java.

Given a set of n integers, divide the set in two subsets of n/2 sizes each such that the difference of the sum of two subsets is as minimum as possible. If n is even, then sizes of two subsets must be strictly n/2 and if n is odd, then size of one subset must be (n-1)/2 and size of other subset must be (n+1)/2.

For example, let given set be {3, 4, 5, -3, 100, 1, 89, 54, 23, 20}, the size of set is 10. Output for this set should be {4, 100, 1, 23, 20} and {3, 5, -3, 89, 54}. Both output subsets are of size 5 and sum of elements in both subsets is same (148 and 148).

package com.example;

public class TugOfWar {

 static int[] a = { 23, 45, -34, 12, 0, 98, -99, 4, 189, -1, 4 };
 static int n = a.length;
 static int minDiff = Integer.MAX_VALUE;
 static boolean[] solution = new boolean[n];
 static boolean[] selected = new boolean[n];

 public static void main(String[] args) {
  solve(0);
  print();
 }

 // the solution is simple,

 // 1. in each iteration, either add or remove the current element from the selected array
 // 2. check if we have already selected the requried number of elements, in that case update solution
 // 3. check if have already reached the end of the array, in that case, simply return
 protected static void solve(int currentIndex) {

  // get size of selected
  int selectedSize = 0;
  for (int i = 0; i < n; i++)
   if (selected[i])
    selectedSize++;

  if (selectedSize == n / 2) {
   // check if diff < minDiff, update solution
   int diff = getDiff();
   if (diff < minDiff) {
    minDiff = diff;
    updateSolution();
   }
  }

  // check if currentIndex == n and return
  if (currentIndex >= n)
   return;

  // add curindex to selected
  selected[currentIndex] = true;
  solve(currentIndex + 1);

  // remove curindex from selected
  selected[currentIndex] = false;
  solve(currentIndex + 1);
 }

 protected static void updateSolution() {
  for (int i = 0; i < n; i++) {
   solution[i] = selected[i];
  }
 }

 protected static void print() {
  for (int i = 0; i < n; i++) {
   if (solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
  for (int i = 0; i < n; i++) {
   if (!solution[i]) {
    System.out.print(a[i]);
    System.out.print(",");
   }
  }
  System.out.println();
 }

 protected static int getDiff() {

  int leftSum = 0;
  int rightSum = 0;

  for (int i = 0; i < n; i++) {
   if (selected[i])
    leftSum += a[i];
   else
    rightSum += a[i];
  }

  return Math.abs(rightSum - leftSum);
 }
}