Skip to content

Instantly share code, notes, and snippets.

@KenG98
Created May 28, 2015 22:54
Show Gist options
  • Star 0 You must be signed in to star a gist
  • Fork 0 You must be signed in to fork a gist
  • Save KenG98/755eb15c6dac4f0c8ddb to your computer and use it in GitHub Desktop.
Save KenG98/755eb15c6dac4f0c8ddb to your computer and use it in GitHub Desktop.
A Java Sudoku solver.
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