Skip to content

Instantly share code, notes, and snippets.

@justanotherminh
Last active July 27, 2020 22:41
Show Gist options
  • Save justanotherminh/c52fc28a2978d51cf484cb1180a99b5e to your computer and use it in GitHub Desktop.
Save justanotherminh/c52fc28a2978d51cf484cb1180a99b5e to your computer and use it in GitHub Desktop.
Sudoku solver using depth-first search
import java.io.*;
import java.util.*;
class Main {
public static void main(String[] args) throws IOException {
File file = new File(args[0]);
char[][] board = new char[9][9];
BufferedReader buffer = new BufferedReader(new FileReader(file));
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
board[i][j] = (char)buffer.read();
}
buffer.read();
}
Solution sol = new Solution();
sol.solveSudoku(board);
}
}
class Solution {
public void solveSudoku(char[][] board) {
for (int pos = 0; pos < 81; pos++) {
if (board[pos/9][pos%9] == '.') {
tryValues(board, pos/9, pos%9);
break;
}
}
}
void printBoard(char[][] board) {
for (int i = 0; i < 9; i++) {
for (int j = 0; j < 9; j++) {
System.out.printf("%c ", board[i][j]);
}
System.out.println();
}
System.out.println("_________________");
}
// test for blank space before using this function
boolean tryValues(char[][] board, int x, int y) {
// identifying unavailable values
HashSet<Character> values = new HashSet();
for (int i = 0; i < 9; i++) {
if (board[x][i] != '.') {
values.add(board[x][i]);
}
}
for (int i = 0; i < 9; i++) {
if (board[i][y] != '.') {
values.add(board[i][y]);
}
}
int gx = x/3;
int gy = y/3;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[3*gx+i][3*gy+j] != '.') {
values.add(board[3*gx+i][3*gy+j]);
}
}
}
if (values.size() == 9) {
return false;
}
// find next empty slot, solved if none left
int pos = 9*x+y+1;
for (; pos < 81; pos++) {
if (board[pos/9][pos%9] == '.') {
break;
}
}
if (pos == 81) {
for (int c = 49; c <= 57; c++) {
if (!values.contains((char)c)) {
board[x][y] = (char)c;
}
}
System.out.println("Finished!");
printBoard(board);
return true;
}
// try available values and backtrack
boolean success = false;
for (int c = 49; c <= 57; c++) {
if (!values.contains((char)c)) {
board[x][y] = (char)c;
success = tryValues(board, pos/9, pos%9);
if (success) {
return true;
}
}
}
board[x][y] = '.';
return false;
}
}
....58..3
......4..
6..2..1..
.3...1.5.
.72.9..8.
..8..5.3.
....1....
35.......
.913....2
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment