Wednesday, October 25, 2006

Just Another Sudoku Solver

Yes, it's only brute force (just avoiding digging deeper into the search tree when it's proven wrong already), and yes, it's Java which implies array bounds checking, but it still delivers around 30.000 valid solutions per second for average 9x9 Sudokus on my 2.4GHz Athlon. Faster than my father-in-law who has been messing around with a single puzzle all night long. I couldn't watch it any longer [;-)], so I hacked in the following code.

package com.arnosoftwaredev.sudoku;

import java.util.ArrayList;
import java.util.Collection;

public class Sudoku {

 private int[][] startGrid;
 private int dim;
 private int dimSqrt;
 private ArrayList solutions;
 private boolean usedInColumn[][];
 private boolean usedInRow[][];
 private boolean usedInSquare[][];
 private int squareIdx[][];
 private int grid[][];

 public Sudoku(int[][] startGridParam) {
     if (startGridParam == null) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length == 0) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     if (startGridParam.length != startGridParam[0].length) {
         throw new IllegalArgumentException("Grid is invalid");
     }
     dim = startGridParam.length;
     if (dim != 4 && dim != 9 && dim != 16 && dim != 25) {
         throw new IllegalArgumentException("Grid is invalid");
     }

     solutions = new ArrayList();

     dimSqrt = (int) Math.round(Math.sqrt(dim));

     usedInColumn = new boolean[dim][dim];
     usedInRow = new boolean[dim][dim];
     usedInSquare = new boolean[dim][dim];
     squareIdx = new int[dim][dim];
     startGrid = new int[dim][dim];
     grid = new int[dim][dim];
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             squareIdx[x][y] =
             (x / dimSqrt) * dimSqrt + (y / dimSqrt);
         }
     }
     copyGrid(startGridParam, startGrid);
 }



 private void copyGrid(int[][] src, int[][] tgt) {
     for (int x = 0; x < src.length; x++) {
         System.arraycopy(src[x], 0, tgt[x], 0, src[x].length);
     }
 }

 private void digInto(int x, int y) {
     if (startGrid[x][y] == 0) {
         int square = squareIdx[x][y];

         for (int val = 1; val <= dim; val++) {
             int valIdx = val - 1;
             if (usedInRow[x][valIdx] || usedInColumn[y][valIdx] ||
             usedInSquare[square][valIdx]) {
                 continue;
             }
             grid[x][y] = val;
             usedInRow[x][valIdx] = true;
             usedInColumn[y][valIdx] = true;
             usedInSquare[square][valIdx] = true;
             if (x < dim - 1) {
                 digInto(x + 1, y);
             }
             else if (y < dim - 1) {
                 digInto(0, y + 1);
             }
             else {
                 addSolution();
             }
             grid[x][y] = 0;
             usedInRow[x][valIdx] = false;
             usedInColumn[y][valIdx] = false;
             usedInSquare[square][valIdx] = false;
         }

     }
     else {
         if (x < dim - 1) {
             digInto(x + 1, y);
         }
         else if (y < dim - 1) {
             digInto(0, y + 1);
         }
         else {
             addSolution();
         }
     }
 }

 private void addSolution() {
     int[][] solution = new int[dim][dim];
     copyGrid(grid, solution);
     solutions.add(solution);
 }

 public Collection solve() {
     solutions.clear();
     copyGrid(startGrid, grid);
     for (int i = 0; i < dim; i++) {
         for (int j = 0; j < dim; j++) {
             usedInRow[i][j] = false;
             usedInColumn[i][j] = false;
             usedInSquare[i][j] = false;
         }
     }
     for (int x = 0; x < dim; x++) {
         for (int y = 0; y < dim; y++) {
             int val = grid[x][y];
             if (val != 0) {
                 usedInRow[x][val - 1] = true;
                 usedInColumn[y][val - 1] = true;
                 usedInSquare[squareIdx[x][y]][val - 1] = true;
             }
         }
     }
     digInto(0, 0);
     return solutions;
 }

}

Follow-Ups: