Sudoku Solver - Pass 1:

package personal.puzzles;

import java.util.HashSet;
import java.util.Set;

public class SudokuSolver {
    Grid grid = new Grid();
    public SudokuSolver(int[][] state) {
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                grid.setValue(new Coordinate(i, j, state[i][j]));
            }
        }
    }
    
    public boolean isInConsistentState() {
        return grid.checkState();
    }
    
    public int[][] solveSudoku() {
        getConsistentAssignment(grid);
        return grid.getSudokuBoard();
    }
    
    private void getConsistentAssignment(Grid grid) {
        while (grid.isNextUnassigned()) {
            Coordinate next = grid.getNextUnassigned();
            for (int i = 1; i <= 9; ++i) {
                next.setValue(i);
                grid.setValue(next);
                if (grid.checkState()) {
                    getConsistentAssignment(grid);
                    return;
                } else {
                    next.setValue(-1);
                    grid.setValue(next);
                }
            }
        }
        return;
    }
    
    public static class Grid {
        int[][] x = new int[9][9];
        public void setValue(Coordinate coordinate) {
            x[coordinate.getX()][coordinate.getY()] = coordinate.getValue();
        }
        public int getValue(int i, int j) {
            return x[i][j];
        }
        public boolean isNextUnassigned() {
            for (int i = 0; i < 9; ++i)
                for(int j = 0; j < 9; ++j) 
                    if (x[i][j] == -1) {
                        return true;
                    }
            return false;
        }
        public void print() {
            for (int i = 0; i < 9; ++i) {
                for (int j = 0; j < 9; ++j) {
                    System.out.print(x[i][j] + " ");
                }
                System.out.println();
            }
        }
        public Coordinate getNextUnassigned() {
            for (int i = 0; i < 9; ++i)
                for(int j = 0; j < 9; ++j) 
                    if (x[i][j] == -1) {
                        return new Coordinate(i, j, -1);
                    }
            return null;
        }
        public boolean checkState() {
            return checkColumns() && checkRows() && checkSubgrids();
        }
        private boolean checkColumns() {
            for (int i = 0; i < 9; ++i) {
                Set<Integer> columnValues = new HashSet<Integer>();
                for (int j = 0; j < 9; ++j) {
                    if (columnValues.contains(x[i][j]))
                        return false;
                    if (x[i][j] != -1) columnValues.add(x[i][j]);
                }
            }
            return true;
        }
        
        private boolean checkRows() {
            for (int i = 0; i < 9; ++i) {
                Set<Integer> rowValues = new HashSet<Integer>();
                for (int j = 0; j < 9; ++j) {
                    if (rowValues.contains(x[j][i]))
                        return false;
                    if (x[j][i] != -1) rowValues.add(x[j][i]);
                }
            }
            return true;
        }
        
        private boolean checkSubgrids() {
            for (int i = 0; i < 9; ++i)
                for (int j = 0; j < 9; ++j)
                    for (int k = 0; k < 9; ++k)
                        for (int l = 0; l < 9; ++l) {
                            if (Math.abs(i - k) == 2 && Math.abs(j - l) == 2 && i % 3 == 0 && j % 3 == 0) {
                    
                                if (!checkForBlock(i, j, k, l))
                                    return false;
                            }
                        }
                            
            return true;
        }
        private boolean checkForBlock(int x1, int y1, int x2, int y2) {
            Set<Integer> blockValues = new HashSet<Integer>();;
            for (int i = x1; i <= x2; ++i) {
                for (int j = y1; j <= y2; ++j) {
                    if (blockValues.contains(x[i][j])) {
                        return false;
                    }
                    if (x[i][j] != -1) blockValues.add(x[i][j]);
                }
            }
            return true;
        }
        public int[][] getSudokuBoard() {
            return x;
        }
    }
    
    public static class Coordinate {
        int x, y, value;
        Coordinate(int x, int y, int value) {
            this.x = x;
            this.y = y;
            this.value = value;
        }
        public void setValue(int value) {
            this.value = value;
        }
        public int getX() {
            return x;
        }
        public int getY() {
            return y;
        }
        public int getValue() {
            return value;
        }
    }
    
    public static void main(String[] args) {
        int x[][] = {
                { -1, 3, 4, 6, 7, 8, 9, 1, 2},
                {6, 7, 2, 1, 9, -1, 3, 4, 8},
                {1, 9, 8, 3, 4, 2, 5, -1, 7},
                {8, -1, 9, 7, 6, 1, 4, 2, 3},
                {4, 2, 6, -1, 5, 3, -1, 9, 1},
                {7, 1, 3, 9, 2, 4, 8, 5, 6},
                {9, -1, 1, 5, 3, -1, 2, -1, 4},
                {2, 8, 7, 4, 1, 9, 6, 3, 5},
                {3, -1, 5, 2, -1, 6, 1, 7, 9},
        };
        SudokuSolver solver = new SudokuSolver(x);
        int y[][] = solver.solveSudoku();
        for (int i = 0; i < 9; ++i) {
            for (int j = 0; j < 9; ++j) {
                System.out.print(y[i][j] + " ");
            }
            System.out.println();
        }
    }
 }

Sort an integer array in such a manner that upon concatenating the elements it the result yields maximum value

package personal.puzzles;

import java.util.ArrayList;
import java.util.Collections;
import java.util.Comparator;
import java.util.List;

/**
 * Max value array sorter
 * 
 * @author madhuc
 *
 */
public class MaxValueArraySorter {

    public static int getMaxValueFromArray(int[] input) {
        
        List<String> inputAsString = new ArrayList<String>(input.length);
        for (int i = 0; i < input.length; ++i) {
            inputAsString.add(String.valueOf(input[i]));
        }
        
        Collections.sort(inputAsString,
                Collections.reverseOrder(new MyComparator()));
        
        StringBuilder outputBuilder = new StringBuilder();
        for (int i = 0; i < inputAsString.size(); ++i) {
            outputBuilder.append(inputAsString.get(i));
        }
        return Integer.valueOf(outputBuilder.toString());
    }
    
    public static class MyComparator implements Comparator<String> {
        public int compare(String paramT1, String paramT2) {
            if (paramT1.length() <= paramT2.length()) {
                return findLargest(paramT1, paramT2);
            } else {
                return -1 * findLargest(paramT2, paramT1);
            }
        }
        
        private int findLargest(String t1, String t2) {
            for (int i = 0; i < t1.length(); ++i) {
                if (t1.charAt(i) < t2.charAt(i)) {
                     return -1;
                } else if (t1.charAt(i) > t2.charAt(i)) {
                    return 1;
                }
            }
            return 1;
        }
    }
    
    public static void main(String[] args) {
        int[] test = {989, 91};
        System.out.println(MaxValueArraySorter.getMaxValueFromArray(test));
     }
}

Powerset Generation

package personal.puzzles;

import java.util.List;

/**
 * Print all the subsets of a set
 * 
 * @author madhuc
 *
 */
public class PowerSet {
    
    public void printAllSubsets(List<Integer> mySet) {
        for (int i = 0; i < Math.pow(2.0, mySet.size()); ++i) {
            String mask = Integer.toBinaryString(i);
            for (int j = 0; j < mySet.size() - mask.length(); ++j) {
                mask = '0' + mask;
            }
            printSubset(mask, mySet);
        }
    }
    
    public void printSubset(String mask, List<Integer> mySet) {
        int i = 0;
        System.out.print("{");
        for (char c: mask.toCharArray()) {
            if ( c == '1') {
                System.out.print(mySet.get(mySet.size() - 1 - i) + ",");
            }
            i++;
        }
        System.out.print("}\n");
    }
}

How to determine the LCM of an array of numbers?

This solution exploits two properties of LCM: i) LCM(a,b) = (a.b)/GCD(a, b) and LCM(a, b, c) = LCM(a, LCM(a,b)).

package personal.puzzles;

public class LCMEuclid {

    public int findLCMOfArray(int[] array) {
        if (array.length == 0) {
            throw new IllegalArgumentException("You cannot determine LCM of empty array");
        } else if (array.length == 1) {
                return array[0];
        }
        int first = array[0];
        int second = array[1];
        int lcm = findLCMOfPair(first, second);
        for (int i = 2; i < array.length; ++i) {
            lcm = findLCMOfPair(lcm, array[i]);
        }
        return lcm;
    }
    
    private int findLCMOfPair(int first, int second) {
        return first * second / gcd(first, second);
    }
    
    private int gcd(int first, int second) {
        while (first % second != 0) {
            int tempSecond = first % second;
            first = second;
            second = tempSecond;
        }
        return second;
    }
    
    public static void main(String[] args) {
        int a[] = {21, 6, 7, 11};
        LCMEuclid lcmEuclid = new LCMEuclid();
        System.out.println(lcmEuclid.findLCMOfArray(a));
    }
}