Created
May 28, 2015 22:54
-
-
Save KenG98/755eb15c6dac4f0c8ddb to your computer and use it in GitHub Desktop.
A Java Sudoku solver.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
package sudoku.solver.two; | |
import java.util.Scanner; | |
/** | |
* | |
* @author kengarber | |
*/ | |
public class SudokuSolverTwo { | |
private final int[][] board = new int[9][9]; //row, column | |
private boolean madeChange = true; | |
private final String givenValues = "" | |
+ "8 0 9 0 4 0 0 2 0 " | |
+ "4 2 0 6 0 5 0 8 0 " | |
+ "0 0 0 0 0 9 4 0 0 " | |
+ "1 3 5 0 7 0 0 0 6 " | |
+ "0 0 0 3 6 1 0 0 0 " | |
+ "7 0 0 0 9 0 1 3 2 " | |
+ "0 0 8 1 0 0 0 0 0 " | |
+ "0 9 0 2 0 4 0 1 3 " | |
+ "0 7 0 0 5 0 2 0 8 "; | |
/** | |
* @param args the command line arguments | |
*/ | |
public static void main(String[] args) { | |
// TODO code application logic here | |
SudokuSolverTwo SST = new SudokuSolverTwo(); | |
SST.startSolve(); | |
} | |
public void startSolve() { | |
readIn(givenValues); | |
printBoard(); | |
doSolve(); | |
} | |
public void doSolve() { | |
while (madeChange) { | |
madeChange = false; //should be changed later | |
for (int i = 0; i < 9; i++) { | |
for (int j = 0; j < 9; j++) { | |
if (board[i][j] == 0) { //if there is no number there | |
boolean[] numbersAround = new boolean[9]; //create an array (length 9) to store bool value of whether or not a number is used (remember 0 base) | |
for (int k = 0; k < numbersAround.length; k++) { | |
numbersAround[k] = false; | |
} | |
//check in column | |
for (int row = 0; row < 9; row++) { | |
int valueTemp = board[row][j]; | |
if (valueTemp != 0) { | |
numbersAround[valueTemp - 1] = true; | |
} | |
} | |
//check in row | |
for (int col = 0; col < 9; col++) { | |
int valueTemp = board[i][col]; | |
if (valueTemp != 0) { | |
numbersAround[valueTemp - 1] = true; | |
} | |
} | |
//check in box | |
int lowerBoundRow = 0, higherBoundRow = 0, lowerBoundCol = 0, higherBoundCol = 0; | |
switch (i) { | |
case 0: | |
case 1: | |
case 2: | |
lowerBoundRow = 0; | |
higherBoundRow = 2; | |
break; | |
case 3: | |
case 4: | |
case 5: | |
lowerBoundRow = 3; | |
higherBoundRow = 5; | |
break; | |
case 6: | |
case 7: | |
case 8: | |
lowerBoundRow = 6; | |
higherBoundRow = 8; | |
break; | |
} | |
switch (j) { | |
case 0: | |
case 1: | |
case 2: | |
lowerBoundCol = 0; | |
higherBoundCol = 2; | |
break; | |
case 3: | |
case 4: | |
case 5: | |
lowerBoundCol = 3; | |
higherBoundCol = 5; | |
break; | |
case 6: | |
case 7: | |
case 8: | |
lowerBoundCol = 6; | |
higherBoundCol = 8; | |
break; | |
} | |
for (int row = lowerBoundRow; row <= higherBoundRow; row++) { | |
for (int col = lowerBoundCol; col <= higherBoundCol; col++) { | |
int cellValTemp = board[row][col]; | |
if (cellValTemp != 0) { | |
numbersAround[cellValTemp - 1] = true; | |
} | |
} | |
} | |
//check if there are 8 numbers excluded (set to true) | |
int numberNumsExcluded = 0; | |
for(int index = 0; index < 9; index++){ | |
if(numbersAround[index]){ | |
numberNumsExcluded++; | |
} | |
} | |
if(numberNumsExcluded == 8){ | |
//8 numbers are excluded. we know this cell's value! | |
for(int index = 0; index < 9; index++){ | |
if(!numbersAround[index]){ | |
//we got the numer! index + 1 | |
board[i][j] = index + 1; | |
madeChange = true; | |
} | |
} | |
} | |
} | |
} | |
} | |
} | |
printBoard(); | |
} | |
private void readIn(String givenValues) { | |
Scanner readInNums = new Scanner(givenValues); | |
for (int i = 0; i < 9; i++) { | |
for (int j = 0; j < 9; j++) { | |
board[i][j] = Integer.parseInt(readInNums.next()); | |
} | |
} | |
} | |
private void printBoard() { | |
for (int i = 0; i < 9; i++) { | |
for (int j = 0; j < 9; j++) { | |
int nextPrintVal = board[i][j]; | |
if (nextPrintVal != 0) { | |
System.out.print(nextPrintVal); | |
} else { | |
System.out.print(" "); | |
} | |
if (j == 2 || j == 5) { | |
System.out.print("|"); | |
} else { | |
System.out.print(" "); | |
} | |
} | |
System.out.println(); | |
if (i == 2 || i == 5) { | |
System.out.println("-----|-----|-----"); | |
} | |
} | |
System.out.println(); | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment