/** This Sudoku implementation applies brute force technique but in an intelligent way. It starts by filling empty cells that have fewer acceptable values as per Sudoku rules. This way it manages to try in most cases just 1 trial before coming up with a valid Sudoku grid. I do this things just to keep my head intact with algorithms and data structures. No reference was made anywhere while coding this just to see how good I could solve this problem and am kinda impressed. */ import java.util.ArrayList; import java.util.Collections; import java.util.LinkedHashSet; import java.util.List; import java.util.Objects; import java.util.TreeMap; /** * @author Last born */ public class SudokuLogic { public static void main(String[] args) { GridLogic gridLogic = new GridLogic(); boolean notComplete = true; while (notComplete) { // keep on setting next empty cell value till we are done. notComplete = gridLogic.setNextCell(); } System.out.printf("\nCompleted after %d %s%n", gridLogic.getTrials(), "trial(s) of intelligent bruteforce.\n"); System.out.println(gridLogic.getGrid()); } } class Cell implements Comparable { private int row; private int col; private int block; private int value = 0; public Cell(int row, int col, int block) { this.row = row; this.col = col; this.block = block; } public int getRow() { return row; } public int getCol() { return col; } public boolean isEmpty() { return value == 0; } public int getValue() { return value; } @Override public int compareTo(Cell o) { int n = Integer.compare(row, o.row); if (n != 0) { return n; } else { return Integer.compare(col, o.col); } } @Override public boolean equals(Object o) { if (this == o) return true; if (!(o instanceof Cell)) return false; Cell cell = (Cell) o; return getRow() == cell.getRow() && getCol() == cell.getCol(); } @Override public int hashCode() { return Objects.hash(getRow(), getCol()); } public void reset() { value = 0; } public void setValue(int value) { if (value < 1 || value > 9) { throw new IllegalArgumentException("Invalid value provided. Must be in between 1 and " + "9"); } this.value = value; } public int getBlock() { return block; } } class Block implements Comparable { private List cells = new ArrayList<>(); // will store 9 cells private int id; // block number counted left to right; top to bottom. public Block(int id) { this.id = id; } public void addCell(Cell cell) { if (cells.contains(cell)) { throw new IllegalStateException("Cell already contained in block."); } else { cells.add(cell); } } public List getRowValues(int row) { List values = new ArrayList<>(); for (Cell cell : cells) { if (cell.getRow() == row) { values.add(cell.getValue()); } } return values; } public List getColValues(int col) { List values = new ArrayList<>(); for (Cell cell : cells) { if (cell.getCol() == col) { values.add(cell.getValue()); } } return values; } public List getValues() { List values = new ArrayList<>(); for (Cell cell : cells) { values.add(cell.getValue()); } return values; } public List getCells() { return new ArrayList<>(cells); } @Override public int compareTo(Block o) { return Integer.compare(id, o.id); } } class Grid { private TreeMap blocks = new TreeMap<>(); public Grid() { initializeBlocks(); initializeCells(); } public boolean isComplete() { for (Cell cell : getCells()) { if (cell.isEmpty()) { return false; } } return true; } public void resetCells() { for (Cell cell : getCells()) { cell.reset(); } } public List validValues(Cell cell) { if (!cell.isEmpty()) { return new ArrayList<>(); } LinkedHashSet filled = new LinkedHashSet<>(); List valid = new ArrayList<>(); filled.addAll(getRowValues(cell.getRow())); filled.addAll(getColValues(cell.getCol())); filled.addAll(getBlockValues(cell.getBlock())); for (int i = 1; i < 10; i++) { if (!filled.contains(i)) { valid.add(i); } } return valid; } public List getCells() { List cells = new ArrayList<>(); for (Block block : blocks.values()) { cells.addAll(block.getCells()); } return cells; } public List getRowValues(int row) { List values = new ArrayList<>(); for (Block block : blocks.values()) { values.addAll(block.getRowValues(row)); } return values; } public List getColValues(int col) { List values = new ArrayList<>(); for (Block block : blocks.values()) { values.addAll(block.getColValues(col)); } return values; } public List getBlockValues(int id) { return blocks.get(id).getValues(); } private String asString(List values) { return values.subList(0, 3).toString() + " " + values.subList(3, 6).toString() + " " + values.subList(6, 9).toString(); } @Override public String toString() { StringBuilder builder = new StringBuilder(); for (int i = 1; i < 10; i++) { builder.append(asString(getRowValues(i))).append("\n"); if (i % 3 == 0 && i < 9) { builder.append("\n"); } } return builder.toString(); } private void initializeCells() { for (int i = 1; i < 10; i++) { for (int j = 1; j < 10; j++) { if (i < 4 && j < 4) { blocks.get(1).addCell(new Cell(i, j, 1)); } else if (i < 4 && j < 7) { blocks.get(2).addCell(new Cell(i, j, 2)); } else if (i < 4) { blocks.get(3).addCell(new Cell(i, j, 3)); } else if (i < 7 && j < 4) { blocks.get(4).addCell(new Cell(i, j, 4)); } else if (i < 7 && j < 7) { blocks.get(5).addCell(new Cell(i, j, 5)); } else if (i < 7) { blocks.get(6).addCell(new Cell(i, j, 6)); } else if (j < 4) { blocks.get(7).addCell(new Cell(i, j, 7)); } else if (j < 7) { blocks.get(8).addCell(new Cell(i, j, 8)); } else { blocks.get(9).addCell(new Cell(i, j, 9)); } } } } private void initializeBlocks() { for (int i = 1; i < 10; i++) { blocks.put(i, new Block(i)); } } } class GridLogic { private Grid grid; private List cells; private int trials = 1; public GridLogic() { grid = new Grid(); cells = grid.getCells(); } public boolean setNextCell() { Cell cell = leastValidCell(); if (cell == null) { if (grid.isComplete()) { return false; } else { System.out.printf("Resetting grid after failing %d round(s).\n%n", trials); System.out.println(grid); grid.resetCells(); trials++; return true; } } List valid = grid.validValues(cell); Collections.shuffle(valid); cell.setValue(valid.get(0)); return true; } public Cell leastValidCell() { Cell least = null; int count = 10; for (Cell cell : cells) { List valid = grid.validValues(cell); if (valid.size() == 0) { continue; } if (valid.size() < count) { least = cell; count = valid.size(); } } return least; } public Grid getGrid() { return grid; } public int getTrials() { return trials; } }

SudokuLogic😍