Created
March 25, 2020 18:24
-
-
Save ChrisLeNeve/b21fb74a410b3445f85b3d274be09477 to your computer and use it in GitHub Desktop.
Very basic sudoku solver (will not succeed beyond basic sudokus)
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
import java.util.ArrayList; | |
import java.util.HashSet; | |
import java.util.List; | |
import java.util.Set; | |
class Solution { | |
static final int BOARD_LENGTH = 9; | |
public static void main(String[] args) { | |
/* Works | |
char[][] board = new char[][] { | |
{'5','3','.','.','7','.','.','.','.'}, | |
{'6','.','.','1','9','5','.','.','.'}, | |
{'.','9','8','.','.','.','.','6','.'}, | |
{'8','.','.','.','6','.','.','.','3'}, | |
{'4','.','.','8','.','3','.','.','1'}, | |
{'7','.','.','.','2','.','.','.','6'}, | |
{'.','6','.','.','.','.','2','8','.'}, | |
{'.','.','.','4','1','9','.','.','5'}, | |
{'.','.','.','.','8','.','.','7','9'} | |
};*/ | |
/* | |
exceeds time limit with | |
*/ | |
char[][] board = new char[][] { | |
{'.','.','9','7','4','8','.','.','.'}, | |
{'7','.','.','.','.','.','.','.','.'}, | |
{'.','2','.','1','.','9','.','.','.'}, | |
{'.','.','7','.','.','.','2','4','.'}, | |
{'.','6','4','.','1','.','5','9','.'}, | |
{'.','9','8','.','.','.','3','.','.'}, | |
{'.','.','.','8','.','3','.','2','.'}, | |
{'.','.','.','.','.','.','.','.','6'}, | |
{'.','.','.','2','7','5','9','.','.'} | |
}; | |
Solution s = new Solution(); | |
board = s.solveSudoku(board); | |
for (int i = 0; i < BOARD_LENGTH; i++) { | |
for (int j = 0; j < BOARD_LENGTH; j++) { | |
System.out.print(board[i][j] + " "); | |
} | |
System.out.print("\n"); | |
} | |
} | |
public char[][] solveSudoku(char[][] board) { | |
while (!isGameFinished(board)) { | |
for (int i = 0; i < BOARD_LENGTH; i++) { | |
for (int j = 0; j < BOARD_LENGTH; j++) { | |
if (board[i][j] == '.') { | |
char characterAtThisCell = getCharAtThisCell(board, i, j); | |
if (characterAtThisCell != '.') { | |
board[i][j] = characterAtThisCell; | |
} | |
} | |
} | |
} | |
} | |
return board; | |
} | |
private Set<Integer> initialiseHashSet() { | |
Set<Integer> allPossibleChars = new HashSet<>(); | |
allPossibleChars.add(1); | |
allPossibleChars.add(2); | |
allPossibleChars.add(3); | |
allPossibleChars.add(4); | |
allPossibleChars.add(5); | |
allPossibleChars.add(6); | |
allPossibleChars.add(7); | |
allPossibleChars.add(8); | |
allPossibleChars.add(9); | |
return allPossibleChars; | |
} | |
private char getCharAtThisCell(char[][] board, int i, int j) { | |
Set<Integer> allPossibleChars = initialiseHashSet(); | |
List<Character> numbersInBox = getNumbersInBox(board, i, j); | |
List<Character> numbersInCol = getNumbersInCol(board, i); | |
List<Character> numbersInRow = getNumbersInRow(board, j); | |
remove(allPossibleChars, numbersInBox); | |
remove(allPossibleChars, numbersInCol); | |
remove(allPossibleChars, numbersInRow); | |
if (allPossibleChars.size() == 1) { | |
int onlyPossibleNumber = allPossibleChars.stream().findFirst().get(); | |
char c = Character.forDigit(onlyPossibleNumber, 10); | |
return c; | |
} | |
return '.'; | |
} | |
private List<Character> getNumbersInRow(char[][] board, int j) { | |
List<Character> returned = new ArrayList<>(); | |
for (int i = 0; i < BOARD_LENGTH; i++) { | |
if (board[i][j] != '.') { | |
returned.add(board[i][j]); | |
} | |
} | |
return returned; | |
} | |
private List<Character> getNumbersInCol(char[][] board, int i) { | |
List<Character> returned = new ArrayList<>(); | |
for (int j = 0; j < BOARD_LENGTH; j++) { | |
if (board[i][j] != '.') { | |
returned.add(board[i][j]); | |
} | |
} | |
return returned; | |
} | |
private List<Character> getNumbersInBox(char[][] board, int i, int j) { | |
List<Character> returned = new ArrayList<>(); | |
int startI, endI, startJ, endJ; | |
Boundary b = getBoundaryIndices(i); | |
startI = b.boundaryStart; | |
endI = b.boundaryEnd; | |
Boundary bb = getBoundaryIndices(j); | |
startJ = bb.boundaryStart; | |
endJ = bb.boundaryEnd; | |
for (int x = startI; x <= endI; x++) { | |
for (int y = startJ; y <= endJ; y++) { | |
if (board[x][y] != '.') { | |
returned.add(board[x][y]); | |
} | |
} | |
} | |
return returned; | |
} | |
private Boundary getBoundaryIndices(int number) { | |
if (number < 3) { | |
return new Boundary(0, 2); | |
} | |
if (number < 6) { | |
return new Boundary(3, 5); | |
} | |
return new Boundary(6, 8); | |
} | |
private void remove(Set<Integer> allPossibleChars, List<Character> numbersToRemove) { | |
for (Character character : numbersToRemove) { | |
allPossibleChars.remove(Character.getNumericValue(character)); | |
} | |
} | |
private boolean isGameFinished(char[][] board) { | |
for (char[] chars : board) { | |
for (char aChar : chars) { | |
if (aChar == '.') { | |
return false; | |
} | |
} | |
} | |
return true; | |
} | |
class Boundary { | |
int boundaryStart; | |
int boundaryEnd; | |
public Boundary(int a, int b) { | |
this.boundaryStart = a; | |
this.boundaryEnd = b; | |
} | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment