Skip to content

Instantly share code, notes, and snippets.

@bmarkwalder
Created May 12, 2017 17:55
Show Gist options
  • Save bmarkwalder/55bb0266555aafda5360fb11e4c14caf to your computer and use it in GitHub Desktop.
Save bmarkwalder/55bb0266555aafda5360fb11e4c14caf to your computer and use it in GitHub Desktop.
Decide if a Sudoku solution is valid or not.
import java.util.HashMap;
/**
* Created by Brandon Markwalder on 5/11/2017.
* Write a function done_or_not passing a board (list[list_lines]) as parameter.
* If the board is valid return 'Finished!', otherwise return 'Try again!'
*
* Sudoku rules:
*
* ROWS:
* Complete the Sudoku puzzle so that each and every row, column,
* and region contains the numbers one through nine only once.
* There are 9 rows in a traditional Sudoku puzzle.
* Every row must contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9.
* There may not be any duplicate numbers in any row.
* In other words, there can not be any rows that are identical.
*
* COLUMNS:
* There are 9 columns in a traditional Sudoku puzzle.
* Like the Sudoku rule for rows, every column must also contain the numbers 1, 2, 3, 4, 5, 6, 7, 8, and 9.
* Again, there may not be any duplicate numbers in any column. Each column will be unique as a result.
*
* REGIONS:
* A region is a 3x3 box like the one shown to the left. There are 9 regions in a traditional Sudoku puzzle.
* Like the Sudoku requirements for rows and columns, every region must also contain the numbers
* 1, 2, 3, 4, 5, 6, 7, 8, and 9. Duplicate numbers are not permitted in any region.
* Each region will differ from the other regions.
*
*/
public class SudokuChecker {
private int[][] board;
private HashMap<Integer, Integer> row;
private HashMap<Integer, Integer> col;
private HashMap<Integer, Integer> quad;
public boolean doneOrNot(int[][] boardIn){
setBoard(boardIn);
return(checkBoard());
}
private void setBoard(int[][] boardIn){
board = boardIn;
}
private boolean checkBoard() {
for (int i = 0; i < board.length; i++) {
row = new HashMap();
col = new HashMap();
quad = new HashMap();
int count = 0;
for (int j = 0; j < board.length; j++) {
if(!checkRow(i, j)){
return false;
}
if (!checkCol(i, j)){
return false;
}
if (!checkQuad(i,j, count)){
return false;
}
count++;
}
}
return true;
}
private boolean checkRow(int i, int j) {
if (!row.containsKey(board[i][j])) {
row.put(board[i][j], i);
}
else{
System.out.println("duplicate row value " + board[i][j] + " found at row: " + j + ", column: " +i);
return false;
}
return true;
}
private boolean checkCol(int i, int j) {
if (!col.containsKey(board[j][i])) {
col.put(board[j][i], j);
}
else{
System.out.println("duplicate column value " + board[j][i] + " found at row: " + j + ", column: " +i);
return false;
}
return true;
}
private boolean checkQuad(int i, int j, int count) {
if ((count < 3)) {
if (!quad.containsKey(board[j][i])) {
quad.put(board[j][i], i);
}
else{
System.out.println("duplicate quad value " + board[j][i] + " found at row: " + j + ", column: " +i);
return false;
}
} else if ((count > 2) && (count < 6)) {
if (!quad.containsKey(board[j][i])) {
quad.put(board[j][i], i);
}
else{
System.out.println("duplicate quad value " + board[j][i] + " found at row: " + j + ", column: " +i);
return false;
}
} else {
if (!quad.containsKey(board[j][i])) {
quad.put(board[j][i], i);
}
else{
System.out.println("duplicate quad value " + board[j][i] + " found at row: " + j + ", column: " +i);
return false;
}
}
return true;
}
public static void main(String[] args) {
int [][] board1 =
{{1, 3, 2, 5, 7, 9, 4, 6, 8},
{4, 9, 8, 2, 6, 1, 3, 7, 5},
{7, 5, 6, 3, 8, 4, 2, 1, 9},
{6, 4, 3, 1, 5, 8, 7, 9, 2},
{5, 2, 1, 7, 9, 3, 8, 4, 6},
{9, 8, 7, 4, 2, 6, 5, 3, 1},
{2, 1, 4, 9, 3, 5, 6, 8, 7},
{3, 6, 5, 8, 1, 7, 9, 2, 4},
{8, 7, 9, 6, 4, 2, 1, 5, 3}};
int [][] board2 =
{{1, 3, 2, 5, 7, 9, 4, 6, 8},
{4, 9, 8, 2, 6, 1, 3, 7, 5},
{7, 5, 6, 3, 8, 4, 2, 1, 9},
{6, 4, 3, 1, 5, 8, 7, 9, 2},
{5, 2, 1, 7, 9, 3, 8, 4, 6},
{9, 8, 7, 4, 2, 6, 5, 3, 1},
{2, 1, 4, 9, 3, 5, 6, 8, 7},
{3, 6, 5, 8, 1, 7, 9, 2, 4},
{8, 7, 9, 6, 4, 2, 1, 3, 5}};
SudokuChecker checkBoard = new SudokuChecker();
System.out.println("Is solution valid? ");
System.out.println(checkBoard.doneOrNot(board1));
System.out.println();
System.out.println("Is solution valid? ");
System.out.println(checkBoard.doneOrNot(board2));
}
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment