java :: SudokuSolver

SudokuSolver.java

// UNDER DEVELOPMENT

package com.chandu.sudoku;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

/**
 * SudokuSolver class has methods to solve a given sudoku puzzle in string representation
 * @author Chandrasekhar Thotakura
 */
public class SudokuSolver {

    private static final byte N = 9;
    private static final byte M = 3;
    private static final byte Z = 0;    

    private static final String S = "";
    
    private static final char S1 = '-';
    private static final char S2 = ',';
    private static final char S3 = ' ';
    private static final char S4 = '\n';
    private static final char D = '.';
    
    private boolean solved;
    private Map<Byte, Byte> puzzle = new HashMap<>();
    private Map<Byte, Set<Byte>> possibiliites = new HashMap<>();
    private Map<Byte, Set<Byte>> sortedPosibilityMap = new HashMap<>();
    
    /**
     * Creates a new SudokuSolver puzzle
     * @param puzzleString
     * @throws IllegalArgumentException 
     */
    public SudokuSolver(final String puzzleString) throws IllegalArgumentException {
        Set<Byte> indices = new HashSet<>();
        for (byte i = 1, k; i <= N; i += 1) {
            for (byte j = 1; j <= N; j += 1) {
                k = (byte) (i * (N + 1) + j);
                possibiliites.put(k, fullSet());
                indices.add(k);
            }
        }
        for (byte i = 1; i < N; i += 1) {
            sortedPosibilityMap.put(i, new HashSet<Byte>());
        }
        sortedPosibilityMap.put(N, indices);
        try {
            buildPuzzle(puzzleString);
        } catch(Exception e) {
            throw new IllegalArgumentException(e);
        }
    }
    
    /**
     * Solves the puzzle if it not solved already and returns the puzzle in string representation
     * @return 
     */
    public String solution() {
        if (!solved) {
            solve();
            solved = true;
        }
        
        System.out.println(S4 + printString(puzzle) + S4);
        
        return shortString(puzzle);
    }
    
    /**
     * Solves the puzzle and updates the puzzle map variable
     */
    private void solve() {
        Set<Byte> s1 = sortedPosibilityMap.get((byte) 1);
        while (s1.size() > 0) {
            Byte index = s1.iterator().next();
            Byte value = possibiliites.get(index).iterator().next();
            puzzle.put(index, value);
            updatePossibilities(index, value);
            s1 = sortedPosibilityMap.get((byte) 1);
        }
        System.out.println(possibiliites);
        System.out.println(sortedPosibilityMap);
    }
    
    /**
     * String to Puzzle Map
     * @param puzzleString
     * @throws NumberFormatException 
     */
    private void buildPuzzle(final String puzzleString) throws Exception {
        if (puzzleString == null || puzzleString.length() != 161) {
            throw new Exception("Invalid sudoku puzzle: 161 characters are expected.");
        }
        String[] s1 = puzzleString.split(S + S1);
        String[] s2;
        byte temp1, temp2;
        if (s1.length != N) {
            throw new Exception("Invalid sudoku puzzle: 9 rows of data is expected.");
        }
        for (int i = 0, n1 = s1.length; i < n1; i += 1) {
            s2 = s1[i].split(S + S2);
            if (s2.length != N) {
                throw new Exception("Invalid sudoku puzzle: 9 columns of data is expected in row " + (i + 1) + ".");
            }
            for (int j = 0, n2 = s2.length; j < n2; j += 1) {
                temp1 = (byte) ((i + 1) * (N + 1) + (j + 1));
                temp2 = Byte.parseByte(s2[j]);
                if (temp2 != 0) {
                    puzzle.put(temp1, temp2);
                    updatePossibilities(temp1, temp2);
                }
            }
        }
    }
    
    private void updatePossibilities(byte index, byte value) {
        Set<Byte> indices = rowColBoxIndices(index);
        
        indices.remove(index);
        Set<Byte> s1 = possibiliites.get(index);
        byte n = (byte) s1.size();
        s1.clear();
        Set<Byte> s2 = sortedPosibilityMap.get(n);
        s2.remove(index);
        
        for (Byte b : indices) {
            s1 = possibiliites.get(b);
            n = (byte) s1.size();
            s2 = sortedPosibilityMap.get(n);
            if (s1.remove(value)) {
                s2.remove(b);
                n = (byte) s1.size();
                Set<Byte> s3 = sortedPosibilityMap.get(n);
                s3.add(b);
            }
        }
        //System.out.println(possibiliites);
        //System.out.println(sortedPosibilityMap);
        //System.out.println();
    }
    
    /**
     * Map to String
     * @param puzzle
     * @return String representation of the puzzle
     */
    private static String shortString(Map<Byte, Byte> puzzle) {
        StringBuilder sb = new StringBuilder();
        Byte temp;
        for (byte i = 1; i <= N; i += 1) {
            for (byte j = 1; j <= N; j += 1) {
                temp = (byte) (i * (N + 1) + j);
                temp = puzzle.get(temp);
                sb.append(temp == null ? Z : temp);
                sb.append(S1);
            }
            if (sb.length() > 0) {
                sb.setCharAt(sb.length() - 1, S2);
            }
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
    
    /**
     * Printable string
     * @param puzzle
     * @return printable string representation
     */
    private static String printString(Map<Byte, Byte> puzzle) {
        StringBuilder sb = new StringBuilder();
        Byte temp;
        for (byte i = 1; i <= N; i += 1) {
            for (byte j = 1; j <= N; j += 1) {
                temp = (byte) (i * (N + 1) + j);
                temp = puzzle.get(temp);
                sb.append(temp == null ? S + D : temp);
                sb.append(S3);
            }
            if (sb.length() > 0) {
                sb.setCharAt(sb.length() - 1, S4);
            }
        }
        if (sb.length() > 0) {
            sb.deleteCharAt(sb.length() - 1);
        }
        return sb.toString();
    }
    
    private Set<Byte> fullSet() {
        Set<Byte> full = new HashSet<>();
        full.add((byte) 1);
        full.add((byte) 2);
        full.add((byte) 3);
        full.add((byte) 4);
        full.add((byte) 5);
        full.add((byte) 6);
        full.add((byte) 7);
        full.add((byte) 8);
        full.add((byte) 9);
        return full;
    }
    
    private Set<Byte> rowColBoxIndices(byte index) {
        Set<Byte> indices = new HashSet<>();
        indices.add(index);
        
        // row
        byte row = (byte) (index / (N + 1));
        for (byte i = 1; i <= N; i += 1) {
            indices.add((byte) (row * (N + 1) + i));
        }
        
        //col
        byte col = (byte) (index % (N + 1));
        for (byte i = 1; i <= N; i += 1) {
            indices.add((byte) (i * (N + 1) + col));
        }
        
        // box 3x3
        row = (byte) (((row - 1) / M) * M + 1);
        col = (byte) (((col - 1) / M) * M + 1);
        for (byte i = row; i < row + M; i += 1) {
            for (byte j = col; j < col + M; j += 1) {
                indices.add((byte) (i * (N + 1) + j));
            }
        }
        return indices;
    }
    
    public static void main(String[] args) {
        String in = "0,9,0,0,0,0,6,5,0-0,0,0,0,0,3,0,4,1-0,0,0,7,0,0,0,0,0-0,0,6,8,9,0,0,0,0-5,0,0,2,0,4,0,0,6-0,0,0,0,1,6,2,0,0-0,0,0,0,0,7,0,0,0-4,1,0,6,0,0,0,0,0-0,3,8,0,0,0,0,9,0";
        SudokuSolver ss = new SudokuSolver(in);
        ss.solution();
    }
}