Sudoku solver help (not brute force)

[David Phluphy]

Hi!

I'm working on a sudoku solver that solves sudoku like a novice human sudoku solver would.

I start off by making a candidate list for each of the 81 boxes, a 2d array of arralylists (ArrayList[][] candidates).
Then I strip away candidates from the lists, and insert the element if there's just one candidate. I think the code is correct for this(?)
Then I check for hidden singles, which is a lot harder. I think the code for rows and columns should be okay, but I don't really know how to handle it for boxes.

Any help would be greatly appreciated, also, please let me know if this method is completely retarded.

Thanks

import java.util.ArrayList;
import java.util.Arrays;

public class SuperSolver {

	static int [][]testBoard = {{0,8,0, 4,0,2, 0,6,0}, {0,3,4, 0,0,0, 9,1,0}, {9,6,0, 0,0,0, 0,8,4},
                            {0,0,0, 2,1,6, 0,0,0},	{0,0,0, 0,0,0, 0,0,0}, {0,0,0, 3,5,7, 0,0,0},
                            {8,4,0, 0,0,0, 0,7,5}, {0,2,6, 0,0,0, 1,3,0},	{0,9,0, 7,0,1, 0,4,0}};
	static int [][]solution  = {{1,8,7, 4,9,2, 5,6,3}, {5,3,4, 6,7,8, 9,1,2}, {9,6,2, 1,3,5, 7,8,4},
                            {4,5,8, 2,1,6, 3,9,7}, {2,7,3, 8,4,9, 6,5,1}, {6,1,9, 3,5,7, 4,2,8},
                            {8,4,1, 9,6,3, 2,7,5}, {7,2,6, 5,8,4, 1,3,9}, {3,9,5, 7,2,1, 8,4,6}};

	static ArrayList<Integer>[][] candidates = new ArrayList[9][9];

	static void eliminateAndInsert(int x, int y, int[][] array){
		eliminateRow(x, y, array);
		eliminateColum(x, y, array);
		eliminateSquare(x, y, array);
		insertHiddenSingles();
	}

	private static void insertHiddenSingles() {
		
		for (int i = 0; i < 9; i++){ //hidden singles rows
			int [] multiplicityOfCandidates = new int[9];
			for (int j = 0; j < 9; j++){
				for (int k : candidates[i][j]){
					multiplicityOfCandidates[k-1] +=1;
				}
			}
			for (int j = 0; j < 9; j++){
				if (multiplicityOfCandidates[j] == 1){
					testBoard[i][j] = j+1;
				}
			}
		}

		for (int i = 0; i < 9; i++){ //hidden singles colums
			int [] multiplicityOfCandidates = new int[9];
			for (int j = 0; j < 9; j++){
				for (int k : candidates[j][i]){
					multiplicityOfCandidates[k-1] +=1;
				}
			}
			for (int j = 0; j < 9; j++){
				if (multiplicityOfCandidates[j] == 1){
					testBoard[j][i] = j+1;
				}
			}
		}
		
		
		
		//hidden singles for boxes here
		
		
		
	}

	static void eliminateRow(int x, int y, int[][] array){ //naked singles rows
		if(array[x][y] == 0){
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
				for (int i = 0; i < 9; i++){
					if (array[x][i] != 0){
						if (candidates[x][y].contains((Integer)array[x][i]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[x][i]));
					}
				}
			}
		}
	}

	static void eliminateColum(int x, int y, int[][] array){ //naked singles colums
		if(array[x][y] == 0){
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
				for (int i = 0; i < 9; i++) {
					if (array[i][y] != 0){
						if (candidates[x][y].contains((Integer)array[i][y]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[i][y]));
					}
				}
			}
		}
	}

	static void eliminateSquare(int x, int y, int[][] array){ //naked singles boxes
		if(array[x][y] == 0){
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
				int rowOffset = (x/3)*3;
				int colOffset = (y/3)*3;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++){
						if (candidates[x][y].contains((Integer)array[rowOffset+i][colOffset+j]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[rowOffset+i][colOffset+j]));
					}
				}
			}
		}
	}

	static void fillCandidates(){ //fills the candidate lists, 
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				candidates[i][j] = (oneToNine());
			}
		}
	}

	static ArrayList<Integer> oneToNine(){ //returns a ArrayList of ints 1-9
		ArrayList<Integer> oneToNine = new ArrayList<>();
		for (int i = 1; i < 10; i++){
			oneToNine.add(i);
		}
		return oneToNine;
	}

	static void lolSolver(){ //solves
		fillCandidates();
		while(!Arrays.equals(testBoard, solution)){
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {	
					eliminateAndInsert(i, j, testBoard);
				}
			}
			writeMatrix(testBoard);
		}
		System.out.println("WIN");
	}


	static void writeMatrix(int[][] solution) { //prints
		for (int i = 0; i < 9; ++i) {
			if (i % 3 == 0)System.out.println(" -----------------------");
			for (int j = 0; j < 9; ++j) {
				if (j % 3 == 0) System.out.print("| ");
				System.out.print(testBoard[i][j] == 0 ? " " : Integer.toString(testBoard[i][j]));
				System.out.print(' ');
			}
			System.out.println("|");
		}
		System.out.println(" -----------------------");
	}

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

}

[Winston Gutkowski]

David Phluphy wrote:Any help would be greatly appreciated, also, please let me know if this method is completely retarded.

Well you've plainly put some thought into it, so it's unlikely to be retarded, even if it doesn't completely work.

This page might help.

Winston

[Wouter Oet]

I once wrote a sudoku solver using a boolean[][][]. Each single boolean is an indicator whether a value can be in that position. For instance the checking if 9 can stand on the first row, second column would be if(options[0][1][8]). This allows you to search for patterns. In your design I don't really see how you can find these patterns (especially the more complicated onces). Maybe you should rethink your design.

[David Phluphy]

It turns out the puzzle I was trying to solve was actually too hard, and couldn't be solved with just these techniques. I switched to a different puzzle, and it solved it right away. I'm still interested too see if anyone has any clever ideas for finding hidden singles in a sub-box though, so I'm going to leave the thread open for a while

Thanks to Wouter and Winston for contributing.

[Stephan van Hulst]

This may be out the scope of the discussion, but I once solved the hidden single in a much more general way. Hidden singles aren't necessarily "singles". With blocks, they are actually "triplets".

My theory is that if all the candidates of a group (row, column or block) for a particular digit are also candidates for one other group (I use the word "intersect"), you can eliminate that digit as a candidate for all other cells in the two intersecting groups. For an intersecting block and row/column, this usually leaves a triplet of candidates.

In the example, you can eliminate 2, 4 and 6 as candidates from the cells marked by *. Each of these digits is a candidate of a cell where the column intersects with one other group, so you can eliminate them in the remainder of the two groups, which is trivial for the column, but gives you new information about the block.

You can extend this theory to all sorts of soduku types. It works really well on X-sudokus and the sudokus which have the 4 grey blocks. You just need to determine in which cells two groups intersect, if at all.

Granted, I tested my strategy using a functional language, which may be much easier than in Java. Heed Wouter's suggestion of using a boolean array to check for patterns.

[Stephan van Hulst]

Actually, sorry. I got confused by the terminology here. The suggestion I made has nothing to do with hidden singles. It's just a general strategy for elimination. It may be useful regardless.

[David Phluphy]

Thanks for the input guys

I'm not familiar with patterns, and I don't want to sound stubborn, but I -really- want to solve it the way I started. This solver is not supposed to be able to solve every single sudoku-puzzle, just the ones with naked singles and hidden singles. I've updated the code, but my mind is a bit tired. If anyone knows a puzzle with just naked singles and hidden singles, please show it to me so I can test it.

import java.util.ArrayList;
import java.util.Arrays;

public class SuperSolver {

	static int [][]testBoard = {
                    {0,0,4, 7,2,0, 9,0,0}, {0,3,9, 0,0,8, 0,0,5}, {0,0,1, 5,0,6, 0,0,4},
                    {0,4,0, 0,1,0, 5,2,0}, {0,2,8, 0,5,0, 1,7,0}, {0,1,6, 0,3,0, 0,9,0},
                    {4,0,0, 9,0,1, 3,0,0}, {1,0,0, 3,0,0, 8,4,0}, {0,0,7, 0,8,5, 6,0,0}};
	static int [][]solution  = {{6,5,4, 7,2,3, 9,8,1}, {2,3,9, 1,4,8, 7,6,5},
                    {8,7,1, 5,9,6, 2,3,4}, {7,4,3, 8,1,9, 5,2,6},	{9,2,8, 6,5,4, 1,7,3},
                    {5,1,6, 2,3,7, 4,9,8}, {4,8,2, 9,6,1, 3,5,7}, {1,6,5, 3,7,2, 8,4,9},
                    {3,9,7, 4,8,5, 6,1,2}};

	static ArrayList<Integer>[][] candidates = new ArrayList[9][9];

	static void eliminateAndInsert(int x, int y, int[][] array){
		eliminateRow(x, y, array);
		eliminateColum(x, y, array);
		eliminateBox(x, y, array);
		insertHiddenSingles();
	}

	private static void insertHiddenSingles() {

		for (int i = 0; i < 9; i++){ //rows
			int [] multiplicityOfCandidates = new int[9];
			for (int j = 0; j < 9; j++){
				for (int k : candidates[i][j]){
					multiplicityOfCandidates[k-1] +=1;
                    //counts the number of times a candidate appears
				}
			}
			for (int j = 0; j < 9; j++){
				if (multiplicityOfCandidates[j] == 1){
					testBoard[i][j] = j+1;
                    //inserts candidates that just appeared once
				}
			}
		}

		for (int i = 0; i < 9; i++){ //columns
			int [] multiplicityOfCandidates = new int[9];
			for (int j = 0; j < 9; j++){
				for (int k : candidates[j][i]){
					multiplicityOfCandidates[k-1] +=1;
                     //counts the number of times a candidate appears
				}
			}
			for (int j = 0; j < 9; j++){
				if (multiplicityOfCandidates[j] == 1){
					testBoard[j][i] = j+1;
                     //inserts candidates that just appeared once
				}
			}
		}

		for (int x = 0; x < 3; x++){ //boxes
			for (int y = 0; y < 3; y++){
				int [] multiplicityOfCandidates = new int[9];
				int rowOffset = x*3;
				int colOffset = y*3;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++){
						for (int k : candidates[rowOffset+i][colOffset+j]){
							multiplicityOfCandidates[k-1] +=1;
                      //counts the number of times a candidate appears
						}
					}
				}
				int nastyFucker = 0;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++){
						if (multiplicityOfCandidates[nastyFucker] == 1){
							testBoard[rowOffset+i][colOffset+j] = nastyFucker+1;
                                       //inserts candidates that just appeared once
							nastyFucker++;
						}
					}
				}
			}
		}
	}

	static void eliminateRow(int x, int y, int[][] array){ //naked singles rows
		if(array[x][y] == 0){ //only proceed if slot is still empty
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
                             //if only one candidate, insert
				for (int i = 0; i < 9; i++){
					if (array[x][i] != 0){
						if (candidates[x][y].contains((Integer)array[x][i]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[x][i]));
                          //remove numbers from candidate list if they appear in the row
					}
				}
			}
		}
	}

	static void eliminateColum(int x, int y, int[][] array){ //naked singles columns
		if(array[x][y] == 0){ //only proceed if slot is still empty
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
                                  //if only one candidate, insert
				for (int i = 0; i < 9; i++) {
					if (array[i][y] != 0){
						if (candidates[x][y].contains((Integer)array[i][y]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[i][y]));
                            //remove numbers from candidate list if they appear in the column
					}
				}
			}
		}
	}

	static void eliminateBox(int x, int y, int[][] array){ //naked singles boxes
		if(array[x][y] == 0){ //only proceed if slot is still empty
			if(candidates[x][y].size() == 1){testBoard[x][y] = (int)candidates[x][y].remove(0);}else{
                             //if only one candidate, insert
				int rowOffset = (x/3)*3;
				int colOffset = (y/3)*3;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++){
						if (candidates[x][y].contains((Integer)array[rowOffset+i][colOffset+j]))
							candidates[x][y].remove(candidates[x][y].indexOf(array[rowOffset+i][colOffset+j]));
                                    //remove numbers from candidate list if they appear in the box
					}
				}
			}
		}
	}

	static void fillCandidates(){ //fills the candidate lists, 
		for (int i = 0; i < 9; i++) {
			for (int j = 0; j < 9; j++) {
				candidates[i][j] = (oneToNine());
			}
		}
	}

	static ArrayList<Integer> oneToNine(){ //returns a ArrayList of ints 1-9
		ArrayList<Integer> oneToNine = new ArrayList<>();
		for (int i = 1; i < 10; i++){
			oneToNine.add(i);
		}
		return oneToNine;
	}

	static int[][] deepCopyArray(int[][] a1) {
		int[][] a2 = new int[a1.length][a1[0].length];
		for (int i = 0; i < a1.length; i++) {
			for (int j = 0; j < a1[0].length; j++) {
				a2[i][j] = a1[i][j];
			}
		}
		return a2;
	}

	static void lolSolver(){ //solves
		fillCandidates();
		int counter = 0;
		boolean epicWin = false;
		while(!epicWin){
			int[][] lastMove = deepCopyArray(testBoard);
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if(testBoard[i][j] == 0){
						eliminateAndInsert(i, j, testBoard);
						printBoard(testBoard);
						counter++;
					}
					else if(Arrays.deepEquals(testBoard, solution)){
						epicWin=true;
						break;
					}
				}
			}
			if(Arrays.deepEquals(testBoard, lastMove)){
				System.out.println("FAIL! Iterations: " + counter);
				return;
			}
		}
		System.out.println("WIN! Iterations: " + counter);
	}

	static void printBoard(int[][] array) { //prints
		for (int i = 0; i < 9; ++i) {
			if (i % 3 == 0)System.out.println(" -----------------------");
			for (int j = 0; j < 9; ++j) {
				if (j % 3 == 0) System.out.print("| ");
				System.out.print(array[i][j] == 0 ? " " : Integer.toString(array[i][j]));
				System.out.print(' ');
			}
			System.out.println("|");
		}
		System.out.println(" -----------------------");
		System.out.println();
	}

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

[Ashish Schottky]

Here is a puzzle that is solved by hidden singles alone.
{ {1,0,0, 2,0,0, 3,0,0},
{0,2,0, 0,1,0, 0,4,0},
{0,0,3, 0,0,5, 0,0,6},
{7,0,0, 6,0,0, 5,0,0},
{0,5,0, 0,8,0, 0,7,0},
{0,0,8, 0,0,4, 0,0,1},
{8,0,0, 7,0,0, 4,0,0},
{0,3,0, 0,6,0, 0,2,0},
{0,0,9, 0,0,2, 0,0,7}};

I used the following strategy, a candidate 'x' that has only one cell to go and other candidates have legal possibility to occupy that cell, then candidate is said to be the hidden single.

I used this strategy to solve.
1) First pencil up the candidates.
2) Check for naked singles.
3)Update the candidates.
4)Check for hidden singles.

To check for hidden singles, just try if a candidate can occupy more than one cell that row and column, then it is not hidden, else its hidden candidate.

[David Phluphy]

Thanks Ashish, my method is definitely not working D:
Guess I'll take a closer look at it tomorrow.

[Randall Twede]

david, you sound so determined that i am sure you will come up with a great solution. i have also thought a sudoku solver would make a good project but i never tried it. another great idea for a project would be a sudoku generator.

[Campbell Ritchie]

I have edited some code by breaking the long lines; they make it difficult to read. I hope nobody has quoted line numbers anywhere because I’ve changed them all.

[David Phluphy]

Thanks

I've tidied up the code a bit so It'll be easier to understand. It still can't solve for hidden single though, so if anyone has any ideas ... ^^
Any other comments are welcome too.

Edit: I've renamed some variables to make it easier to read.

import java.util.ArrayList;
import java.util.Arrays;

public class BetterSolver {

	//first has singles, second only hidden singles
	static int [][]testBoard2 = {{0,0,4, 7,2,0, 9,0,0}, {0,3,9, 0,0,8, 0,0,5}, {0,0,1, 5,0,6, 0,0,4}, 
{0,4,0, 0,1,0, 5,2,0},	{0,2,8, 0,5,0, 1,7,0}, {0,1,6, 0,3,0, 0,9,0}, 
{4,0,0, 9,0,1, 3,0,0}, {1,0,0, 3,0,0, 8,4,0}, {0,0,7, 0,8,5, 6,0,0}};
	static int [][]testBoard = {{1,0,0, 2,0,0, 3,0,0}, {0,2,0, 0,1,0, 0,4,0}, {0,0,3, 0,0,5, 0,0,6}, 
{7,0,0, 6,0,0, 5,0,0}, {0,5,0, 0,8,0, 0,7,0}, {0,0,8, 0,0,4, 0,0,1}, 
{8,0,0, 7,0,0, 4,0,0}, {0,3,0, 0,6,0, 0,2,0},	{0,0,9, 0,0,2, 0,0,7}}; 
	static int [][]solution  = {{6,5,4, 7,2,3, 9,8,1}, {2,3,9, 1,4,8, 7,6,5}, {8,7,1, 5,9,6, 2,3,4}, 
{7,4,3, 8,1,9, 5,2,6},	{9,2,8, 6,5,4, 1,7,3}, {5,1,6, 2,3,7, 4,9,8}, 
{4,8,2, 9,6,1, 3,5,7}, {1,6,5, 3,7,2, 8,4,9}, {3,9,7, 4,8,5, 6,1,2}};

	static ArrayList<Integer>[][] candidates = new ArrayList[9][9];

	static void eliminateAndInsert(int x, int y){
		eliminateCandidates(x, y);
//		insertNakedSingles(x, y);
		insertHiddenSingles(); //bugged
	}

	static void eliminateCandidates(int x, int y){ //works fine
		int rowOffset = (x/3)*3; int colOffset = (y/3)*3;
		for (int i = 0; i < 9; i++)//xy's row
			if (candidates[x][y].contains(testBoard[x][i]))
				candidates[x][y].remove(candidates[x][y].indexOf(testBoard[x][i])); 
		//          remove numbers from candidate list if they appear in the row
		for (int i = 0; i < 9; i++)//xy's column
			if (candidates[x][y].contains(testBoard[i][y]))
				candidates[x][y].remove(candidates[x][y].indexOf(testBoard[i][y])); 
		//          remove numbers from candidate list if they appear in the column
		for (int i = 0; i < 3; i++) //xy's box
			for (int j = 0; j < 3; j++)
				if (candidates[x][y].contains(testBoard[rowOffset+i][colOffset+j]))
					candidates[x][y].remove(candidates[x][y].indexOf(testBoard[rowOffset+i][colOffset+j])); 
		//              remove numbers from candidate list if they appear in the box
	}

	private static void insertNakedSingles(int x, int y) { //obviously works
		if(candidates[x][y].size() == 1) //if only one candidate, insert
			testBoard[x][y] = candidates[x][y].remove(0);
	}

	private static void insertHiddenSingles(){ //fucked up

		for (int row = 0; row < 9; row++){ //rows
			int [] multiplicityOf = new int[10];
			for (int col = 0; col < 9; col++)
				if (testBoard[row][col] == 0)
					for (int candidate : candidates[row][col])
						multiplicityOf[candidate] +=1;

			for (int candidate = 1; candidate <= 9; candidate++)
				if (multiplicityOf[candidate] == 1)
					for (int col = 0; col < 9; col++)
						if (testBoard[row][col] == 0)
							if (candidates[row][col].contains(candidate))
								testBoard[row][col] = candidates[row][col].remove(candidates[row][col].indexOf(candidate));
		}

		for (int col = 0; col < 9; col++){ //columns
			int [] multiplicityOf = new int[10];
			for (int row = 0; row < 9; row++)
				if (testBoard[row][col] == 0)
					for (int candidate : candidates[row][col])
						multiplicityOf[candidate] +=1;

			for (int candidate = 1; candidate <= 9; candidate++)
				if (multiplicityOf[candidate] == 1)
					for (int row = 0; row < 9; row++)
						if(testBoard[row][col] == 0)
							if (candidates[row][col].contains(candidate))
								testBoard[row][col] = candidates[row][col].remove(candidates[row][col].indexOf(candidate));
		}

		for (int x = 0; x < 3; x++){ //all nine boxes
			for (int y = 0; y < 3; y++){
				int [] multiplicityOf = new int[10]; 
				int rowOffset = x*3; int colOffset = y*3;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++)
						if (testBoard[rowOffset+i][colOffset+j] == 0)
							for (int candidate : candidates[rowOffset+i][colOffset+j])
								multiplicityOf[candidate] +=1; 
				}

				for (int candidate = 1; candidate <= 9; candidate++)
					if (multiplicityOf[candidate] == 1)
						for (int i = 0; i < 3; i++)
							for (int j = 0; j < 3; j++)
								if (testBoard[rowOffset+i][colOffset+j] == 0)
									if (candidates[rowOffset+i][colOffset+j].contains(candidate))
										testBoard[rowOffset+i][colOffset+j] = candidates[rowOffset+i][colOffset+j].remove(candidates[rowOffset+i][colOffset+j].indexOf(candidate));
			}
		}
	}

	static void fillCandidates(){ //fills the candidate lists, 
		for (int i = 0; i < 9; i++){
			for (int j = 0; j < 9; j++){
				if (testBoard[i][j] == 0){
					ArrayList<Integer> oneToNine = new ArrayList<Integer>();
					for (int k = 1; k < 10; k++)
						oneToNine.add(k);
					candidates[i][j] = (oneToNine);
				}
			}
		}
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if(testBoard[i][j] == 0)
					eliminateCandidates(i, j);
	}

	static int[][] deepCopyArray(int[][] a1) {
		int[][] a2 = new int[a1.length][a1[0].length];
		for (int i = 0; i < a1.length; i++) {
			for (int j = 0; j < a1[0].length; j++) {
				a2[i][j] = a1[i][j];
			}
		}
		return a2;
	}

	static void lolSolver(){ //solves
		fillCandidates();
		int counter = 0;
		boolean epicWin = false;
		while(!epicWin){
			int[][] lastMove = deepCopyArray(testBoard);
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if(testBoard[i][j] == 0){
						eliminateAndInsert(i, j);
						printBoard(testBoard);
						counter++;
					}
					if(Arrays.deepEquals(testBoard, solution)){
						epicWin=true;
						break;
					}
				}
			}
			if(Arrays.deepEquals(testBoard, lastMove)){
				System.out.println("FAIL! Iterations: " + counter);
				return;
			}
		}
		System.out.println("WIN! Iterations: " + counter);
	}

	static void printBoard(int[][] array) { //prints
		for (int i = 0; i < 9; ++i) {
			if (i % 3 == 0)System.out.println(" -----------------------");
			for (int j = 0; j < 9; ++j) {
				if (j % 3 == 0) System.out.print("| ");
				System.out.print(array[i][j] == 0 ? " " : array[i][j]);
				System.out.print(' ');
			}
			System.out.println("|");
		}
		System.out.println(" -----------------------");
		System.out.println();
	}

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

[David Phluphy]

Finally got it

It still outputs fail, but that's only because I haven't added the solution ^^'

import java.util.ArrayList;
import java.util.Arrays;

public class BetterSolver {

	//first has singles, second only hidden singles
	static int [][]testBoard2 = {{0,0,4, 7,2,0, 9,0,0}, {0,3,9, 0,0,8, 0,0,5}, {0,0,1, 5,0,6, 0,0,4}, 
{0,4,0, 0,1,0, 5,2,0},	{0,2,8, 0,5,0, 1,7,0}, {0,1,6, 0,3,0, 0,9,0}, 
{4,0,0, 9,0,1, 3,0,0}, {1,0,0, 3,0,0, 8,4,0}, {0,0,7, 0,8,5, 6,0,0}};
	static int [][]testBoard = {{1,0,0, 2,0,0, 3,0,0}, {0,2,0, 0,1,0, 0,4,0}, {0,0,3, 0,0,5, 0,0,6}, 
{7,0,0, 6,0,0, 5,0,0}, {0,5,0, 0,8,0, 0,7,0}, {0,0,8, 0,0,4, 0,0,1}, 
{8,0,0, 7,0,0, 4,0,0}, {0,3,0, 0,6,0, 0,2,0},	{0,0,9, 0,0,2, 0,0,7}}; 
	static int [][]solution  = {{6,5,4, 7,2,3, 9,8,1}, {2,3,9, 1,4,8, 7,6,5}, {8,7,1, 5,9,6, 2,3,4}, 
{7,4,3, 8,1,9, 5,2,6},	{9,2,8, 6,5,4, 1,7,3}, {5,1,6, 2,3,7, 4,9,8}, 
{4,8,2, 9,6,1, 3,5,7}, {1,6,5, 3,7,2, 8,4,9}, {3,9,7, 4,8,5, 6,1,2}};

	static ArrayList<Integer>[][] candidates = new ArrayList[9][9];

	static void eliminateAndInsert(int x, int y){
		eliminateCandidates(x, y);
		insertNakedSingles(x, y);
		insertHiddenSingles(); //bugged
	}

	static void eliminateCandidates(int x, int y){ //works fine
		int rowOffset = (x/3)*3; int colOffset = (y/3)*3;
		for (int i = 0; i < 9; i++)//xy's row
			if (candidates[x][y].contains(testBoard[x][i]))
				candidates[x][y].remove(candidates[x][y].indexOf(testBoard[x][i])); 
		//          remove numbers from candidate list if they appear in the row
		for (int i = 0; i < 9; i++)//xy's column
			if (candidates[x][y].contains(testBoard[i][y]))
				candidates[x][y].remove(candidates[x][y].indexOf(testBoard[i][y])); 
		//          remove numbers from candidate list if they appear in the column
		for (int i = 0; i < 3; i++) //xy's box
			for (int j = 0; j < 3; j++)
				if (candidates[x][y].contains(testBoard[rowOffset+i][colOffset+j]))
					candidates[x][y].remove(candidates[x][y].indexOf(testBoard[rowOffset+i][colOffset+j])); 
		//              remove numbers from candidate list if they appear in the box
	}

	private static void insertNakedSingles(int x, int y) { //obviously works
		if(candidates[x][y].size() == 1) //if only one candidate, insert
			testBoard[x][y] = candidates[x][y].remove(0);
	}

	private static void insertHiddenSingles(){ //fucked up
		
		eliminateAll();
		
		for (int row = 0; row < 9; row++){ //rows
			int [] multiplicityOf = new int[10];
			for (int col = 0; col < 9; col++)
				if (testBoard[row][col] == 0)
					for (int candidate : candidates[row][col])
						multiplicityOf[candidate] += 1;

			for (int candidate = 1; candidate <= 9; candidate++)
				if (multiplicityOf[candidate] == 1)
					for (int col = 0; col < 9; col++)
						tryInsert(row, col, candidate);
		}
		
		eliminateAll();

		for (int col = 0; col < 9; col++){ //columns
			int [] multiplicityOf = new int[10];
			for (int row = 0; row < 9; row++)
				if (testBoard[row][col] == 0)
					for (int candidate : candidates[row][col])
						multiplicityOf[candidate] += 1;

			for (int candidate = 1; candidate <= 9; candidate++)
				if (multiplicityOf[candidate] == 1)
					for (int row = 0; row < 9; row++)
						tryInsert(row, col, candidate);
		}
		
		eliminateAll();

		for (int x = 0; x < 3; x++){ //all nine boxes
			for (int y = 0; y < 3; y++){
				int [] multiplicityOf = new int[10]; 
				int rowOffset = x*3; int colOffset = y*3;
				for (int i = 0; i < 3; i++){
					for (int j = 0; j < 3; j++)
						if (testBoard[rowOffset+i][colOffset+j] == 0)
							for (int candidate : candidates[rowOffset+i][colOffset+j])
								multiplicityOf[candidate] += 1; 
				}

				for (int candidate = 1; candidate <= 9; candidate++)
					if (multiplicityOf[candidate] == 1)
						for (int i = 0; i < 3; i++)
							for (int j = 0; j < 3; j++)
								tryInsert(rowOffset+i, colOffset+j, candidate);
			}
		}
	}

	static void tryInsert(int row, int col, int candidate){
		if(testBoard[row][col] == 0 && candidates[row][col].contains(candidate))
			testBoard[row][col] = candidates[row][col].remove(candidates[row][col].indexOf(candidate));
	}
	
	static void eliminateAll(){
		for (int i = 0; i < 9; i++)
			for (int j = 0; j < 9; j++)
				if(testBoard[i][j] == 0)
					eliminateCandidates(i, j);
	}

	static void fillCandidates(){ //fills the candidate lists, 
		for (int i = 0; i < 9; i++){
			for (int j = 0; j < 9; j++){
				if (testBoard[i][j] == 0){
					ArrayList<Integer> oneToNine = new ArrayList<Integer>();
					for (int k = 1; k < 10; k++)
						oneToNine.add(k);
					candidates[i][j] = (oneToNine);
				}
			}
		}
		eliminateAll();
	}

	static int[][] deepCopyArray(int[][] a1) {
		int[][] a2 = new int[a1.length][a1[0].length];
		for (int i = 0; i < a1.length; i++) {
			for (int j = 0; j < a1[0].length; j++) {
				a2[i][j] = a1[i][j];
			}
		}
		return a2;
	}

	static void lolSolver(){ //solves
		fillCandidates();
		int counter = 0;
		boolean epicWin = false;
		while(!epicWin){
			int[][] lastMove = deepCopyArray(testBoard);
			for (int i = 0; i < 9; i++) {
				for (int j = 0; j < 9; j++) {
					if(testBoard[i][j] == 0){
						eliminateAndInsert(i, j);
						printBoard(testBoard);
						counter++;
					}
					if(Arrays.deepEquals(testBoard, solution)){
						epicWin=true;
						break;
					}
				}
			}
			if(Arrays.deepEquals(testBoard, lastMove)){
				System.out.println("FAIL! Iterations: " + counter);
				return;
			}
		}
		System.out.println("WIN! Iterations: " + counter);
	}

	static void printBoard(int[][] array) { //prints
		for (int i = 0; i < 9; ++i) {
			if (i % 3 == 0)System.out.println(" -----------------------");
			for (int j = 0; j < 9; ++j) {
				if (j % 3 == 0) System.out.print("| ");
				System.out.print(array[i][j] == 0 ? " " : array[i][j]);
				System.out.print(' ');
			}
			System.out.println("|");
		}
		System.out.println(" -----------------------");
		System.out.println();
	}

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