Skip to content

Instantly share code, notes, and snippets.

@ChrisLeNeve
Created March 25, 2020 18:24
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 ChrisLeNeve/b21fb74a410b3445f85b3d274be09477 to your computer and use it in GitHub Desktop.
Save ChrisLeNeve/b21fb74a410b3445f85b3d274be09477 to your computer and use it in GitHub Desktop.
Very basic sudoku solver (will not succeed beyond basic sudokus)
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