6
\$\begingroup\$

Intro

This time, I have programmed a parallel sudoku solver in Java.

Code

io.github.coderodde.sudoku.ParallelSudokuSolver.java:

package io.github.coderodde.sudoku;

import io.github.coderodde.sudoku.misc.IntSet;
import io.github.coderodde.sudoku.misc.RandomSudokuBoardSeedProvider;
import io.github.coderodde.sudoku.misc.SudokuBoardVerifier;
import io.github.coderodde.sudoku.misc.Utils;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
import java.util.concurrent.atomic.AtomicReference;

/**
 * This class implements a parallel sudoku solver.
 * 
 * @version 1.0.0 (Dec 4, 2024)
 * @since 1.0.0 (Dec 4, 2024)
 */
public final class ParallelSudokuSolver {
    
    /**
     * The width/height of the minisquare.
     */
    private int sqrtn;
    
    /**
     * The row-wise filters.
     */
    private IntSet[] rowIntSets;
    
    /**
     * The column-wise filters.
     */
    private IntSet[] colIntSets;
    
    /**
     * The minisquare filters.
     */
    private IntSet[][] minisquareIntSets;
    
    /**
     * Solves the input sudoku, which becomes modified. 
     * 
     * @param sudokuBoard the sudoku board to solve.
     * @return a solved board.
     */
    public SudokuBoard solve(final SudokuBoard sudokuBoard) {
        return solve(sudokuBoard, 
                     Runtime.getRuntime().availableProcessors());
    }
    /**
     * Solves the input sudoku, 
     * 
     * @param sudokuBoard the sudoku board to solve.
     * @param numberOfProcessors the number of processors to use.
     * @return a solved board.
     */
    public SudokuBoard solve(final SudokuBoard sudokuBoard,
                             int numberOfProcessors) {
        
        if (!SudokuBoardVerifier.isValid(sudokuBoard)) {
            // Don't process invalid sudoku boards:
            return null;
        }
        
        // Once here, sudokuBoard is valid.
        if (Utils.isCompleteSudokuBoard(sudokuBoard)) {
            // Once here, the sudokuBoard is both valid and complete. Just 
            // return it!
            return sudokuBoard;
        }
        
        // Preload all the filters basing on present values in the sudokuBoard:
        loadIntSets(sudokuBoard);
        
        // The solver thread list:
        final List<SudokuSolverThread> threads =
                new ArrayList<>(numberOfProcessors);
        
        // The seeds of the search. Each seed will be passes as initial board to
        // each solver thread:
        final List<SudokuBoard> seeds = 
                RandomSudokuBoardSeedProvider
                        .computeSeeds(sudokuBoard,
                                      numberOfProcessors);
        
        // Used for halting all the threads when a solution is found:
        final SharedThreadState sharedThreadState = 
                new SharedThreadState();
        
        // Spawn the threads:
        for (int i = 0; i < Math.min(numberOfProcessors, seeds.size()); ++i) {
            threads.add(
                    new SudokuSolverThread(new SudokuBoard(seeds.get(i)),
                                           sudokuBoard, 
                                           sharedThreadState));
            threads.get(i).start();
        }
        
        // Wait for all the solver threads to exit:
        for (final SudokuSolverThread thread : threads) {
            try {
                thread.join();
            } catch (final InterruptedException ex) {
                ex.printStackTrace();
                System.exit(1);
            }
        }
        
        // Fetch and return the solution:
        return sharedThreadState.getSolution(); 
    }
    
    /**
     * Preloads all the filters from the input board.
     * 
     * @param board the board from which to fetch all the cell values for the
     *              filters.
     */
    private void loadIntSets(final SudokuBoard board) {
        final int n = board.getWidthHeight();
        final int capacity = n + 1;
        sqrtn = (int) Math.sqrt(n);
        
        // BEGIN: Create filters.
        rowIntSets = new IntSet[n];
        colIntSets = new IntSet[n];
        minisquareIntSets = new IntSet[sqrtn][sqrtn];
        
        for (int i = 0; i < n; ++i) {
            rowIntSets[i] = new IntSet(capacity);
            colIntSets[i] = new IntSet(capacity);
        }
        
        for (int y = 0; y < sqrtn; ++y) {
            minisquareIntSets[y] = new IntSet[sqrtn];
            
            for (int x = 0; x < sqrtn; ++x) {
                minisquareIntSets[y][x] = new IntSet(capacity);
            }
        }
        // END: Create filters.
        
        // BEGIN: Preload filter values.
        for (int y = 0; y < board.getWidthHeight(); ++y) {
            for (int x = 0; x < board.getWidthHeight(); ++x) {
                final int cellValue = board.get(x, y);
                
                if (cellValue == Utils.UNUSED_CELL) {
                    continue;
                }
                
                rowIntSets[y].add(cellValue);
                colIntSets[x].add(cellValue);
                minisquareIntSets[y / sqrtn]
                                 [x / sqrtn].add(cellValue);
            }
        }
        // END: Preload filter values.
    }
    
    /**
     * This inner class implements sudoku solver threads.
     */
    private final class SudokuSolverThread extends Thread {
        
        /**
         * The seeding sudoku board.
         */
        private final SudokuBoard seed;
        
        /**
         * The original task sudoku board.
         */
        private final SudokuBoard original;
        
        /**
         * The shared thread state. Used for communicating that a solution is 
         * found and all the threads must exit.
         */
        private final SharedThreadState sharedThreadState;
        
        /**
         * The random number generator.
         */
        private final Random random = new Random();
        
        /**
         * Constructs this thread.
         * 
         * @param seed              the seed sudoku board.
         * @param original          the original sudoku board.
         * @param sharedThreadState the shared thread state.
         */
        SudokuSolverThread(final SudokuBoard seed,
                           final SudokuBoard original,
                           final SharedThreadState sharedThreadState) {
            this.seed = seed;
            this.original = original;
            this.sharedThreadState = sharedThreadState;
        }
        
        @Override
        public void run() {
            solveImpl(0, 0);
        }
        
        /**
         * Returns an {@code int} array of cell values in random order.
         * 
         * @return cell values.
         */
        private int[] getCellValues() {
            final int[] cellValues = new int[seed.getWidthHeight()];
            
            for (int i = 0; i < seed.getWidthHeight(); ++i) {
                cellValues[i] = i + 1;
            }
            
            Utils.shuffle(cellValues, random);
            return cellValues;
        }
        
        /**
         * The actual solution method.
         * 
         * @param x the {@code x}-coordinate of the cell to process next.
         * @param y the {@code y}-coordinate of the cell to process next.
         * 
         * @return {@code true} if a solution was found deeper in the search.
         */
        private boolean solveImpl(int x,
                                  int y) {
            
            if (sharedThreadState.getSolution() != null) {
                // Once here, we have a solution and we simple exit with true:
                return true;
            }
            
            if (x == seed.getWidthHeight()) {
                // Once here, we have reached the right border. Go to the
                // beginning of the next row:
                x = 0;
                ++y;
            }
            
            if (y == seed.getWidthHeight()) {
                // Once here, we have a solution. Record it and exit with true:
                sharedThreadState.setSolution(seed);
                return true;
            }
            
            if (original.get(x, y) != Utils.UNUSED_CELL) {
                // Once here, we need just to copy a cell value from the 
                // original sudoku board to the seed:
                seed.set(x,
                         y,
                         original.get(x, y));
                
                // Process further:
                return solveImpl(x + 1, y);
            }
            
            // Get an array of cell values in random order:
            final int[] cellValues = getCellValues();
            
            for (final int cellValue : cellValues) {
                
                if (rowIntSets[y].contains(cellValue)) {
                    // Once here, the row already contains cellValue:
                    continue;
                }
                
                if (colIntSets[x].contains(cellValue)) {
                    // Once here, the column already contains cellValue:
                    continue;
                }
                
                if (minisquareIntSets[y / sqrtn]
                                     [x / sqrtn].contains(cellValue)) {
                    // Once here, the minisquare already contains cellValue:
                    continue;
                }
                
                // Write the cell value to seed:
                seed.set(x, y, cellValue);
                
                // BEGIN: Mark in filters.
                rowIntSets[y].add(cellValue);
                colIntSets[x].add(cellValue);
                minisquareIntSets[y / sqrtn]
                                 [x / sqrtn].add(cellValue);
                // END: Mark in filters.
                
                if (solveImpl(x + 1, y)) {
                    // Recur further:
                    return true;
                }
                
                // BEGIN: Unmark in filters.
                rowIntSets[y].remove(cellValue);
                colIntSets[x].remove(cellValue);
                minisquareIntSets[y / sqrtn]
                                 [x / sqrtn].remove(cellValue);
                // END: Unmark in filters.
            }

            // Once here, we could not set to (x, y). Backtrack a little:
            return false;
        }
    }
    
    /**
     * This class implements a simple shared thread state.
     */
    private static final class SharedThreadState {
        
        /**
         * Solution so far. Starts with {@code null}.
         */
        private final AtomicReference<SudokuBoard> solution = 
                  new AtomicReference(null);
        
        public SudokuBoard getSolution() {
            return solution.get();
        }
        
        public void setSolution(final SudokuBoard board) {
            solution.set(board);
        }
    }
}

io.github.coderodde.sudoku.SudokuBoard.java:

package io.github.coderodde.sudoku;

import static io.github.coderodde.sudoku.misc.Utils.checkWidthHeight;

/**
 * This class implements a sudoku board.
 * 
 * @version 1.0.0 (Jun 22, 2025)
 * @since 1.0.0 (Jun 22, 2025)
 */
public final class SudokuBoard {
    
    /**
     * The actual data matrix for holding integers.
     */
    private final int[][] data;
    
    public SudokuBoard(final int widthHeight) {
        checkWidthHeight(widthHeight);
        this.data = new int[widthHeight]
                           [widthHeight];
    }
    
    /**
     * Copy-constructs this sudoku board from {@code board}.
     * 
     * @param board the source sudoku board.
     */
    public SudokuBoard(final SudokuBoard board) {
        this.data = new int[board.getWidthHeight()]
                           [board.getWidthHeight()];
        
        for (int y = 0; y < board.getWidthHeight(); ++y) {
            this.data[y] = new int[board.getWidthHeight()];
            
            System.arraycopy(board.data[y], 
                             0,
                             this.data[y], 
                             0,
                             data.length);
        }
    }
    
    /**
     * Return {@code true} if and only if the cell value at {@code (x, y)} 
     * contains a valid cell value (between 1, and {@code data.length}, 
     * inclusive).
     * 
     * @param x the {@code x}-coordinate of the cell.
     * @param y the {@code y}-coordinate of the cell.
     * @return {@code true} if and only if the cell contains a valid value.
     */
    public boolean isValidCellValue(final int x,
                                    final int y) {
        final int cellValue = get(x, 
                                  y);
        
        return 1 <= cellValue && cellValue <= data.length;
    }
    
    public int getWidthHeight() {
        return data.length;
    }
    
    public void set(final int x,
                    final int y,
                    final int value) {
        data[y][x] = value;
    }
    
    public int get(final int x, 
                   final int y) {
        return data[y][x];
    }
    
    /**
     * Returns the ASCII art of this sudoku board.
     * 
     * @return the ASCII art of this sudoku board.
     */
    @Override
    public String toString() {
        final StringBuilder sb = new StringBuilder();
        final String horizontalBar = getHorizontalBar(data.length);
        
        sb.append(horizontalBar);
        
        for (int y = 0; y < data.length; ++y) {
            final String row = getDataRow(data[y]);
            
            sb.append('\n')
              .append(row)
              .append('\n')
              .append(horizontalBar);
        }
        
        return sb.toString();
    }
    
    /**
     * Computes a string representing a row in a sudoku board.
     * 
     * @param dataRow the data row of a sudoku.
     * 
     * @return a string representation of the data row.
     */
    private static String getDataRow(final int[] dataRow) {
        final String maximumCellWidth = Integer.toString(dataRow.length);
        final int cellWidth = maximumCellWidth.length();
        final String fmt = String.format("|%%%dd", cellWidth);
        final StringBuilder sb = 
                new StringBuilder(
                        1 + (1 + cellWidth) * dataRow.length);
        
        for (int x = 0; x < dataRow.length; ++x) {
            sb.append(String.format(fmt, dataRow[x]));
        }
        
        return sb.append('|').toString();
    }
    
    /**
     * Returns the horizontal separating bar.
     * 
     * @param widthHeight the width/height of the target sudoku board.
     * 
     * @return the string representation of the separating bar.
     */
    private static String getHorizontalBar(final int widthHeight) {
        final String nstr = Integer.toString(widthHeight);
        final String innerCellWidth = getInnerCellWidth(nstr.length());
        final StringBuilder sb = new StringBuilder("+");
        
        for (int x = 0; x < widthHeight; ++x) {
            sb.append(innerCellWidth)
              .append('+');
        }
        
        return sb.toString();
    }
    
    /**
     * Computes the inner cell upper horizontal bar.
     * 
     * @param cellWidth the width of a cell.
     * 
     * @return inner cell upper horizontal bar.
     */
    private static String getInnerCellWidth(final int cellWidth) {
        final StringBuilder sb = new StringBuilder(cellWidth);
        
        for (int x = 0; x < cellWidth; ++x) {
            sb.append('-');
        }
        
        return sb.toString();
    }
}

io.github.coderodde.sudoku.demo.Demo.java:

package io.github.coderodde.sudoku.demo;

import io.github.coderodde.sudoku.ParallelSudokuSolver;
import io.github.coderodde.sudoku.SudokuBoard;
import io.github.coderodde.sudoku.misc.RandomSudokuBoardGenerator;
import io.github.coderodde.sudoku.misc.RandomSudokuBoardPruner;
import io.github.coderodde.sudoku.misc.SudokuBoardVerifier;
import io.github.coderodde.sudoku.misc.Utils;
import java.util.Random;

/**
 * This class implements a demonstration program comparing the parallel sudoku
 * search with varying number of threads.
 * 
 * @version 1.1.0 (Jun 23, 2024)
 * @since 1.0.0 (Dec 4, 2024)
 */
public class Demo {

    private static final int WIDTH_HEIGHT = 16;
    private static final int NUMBER_OF_CELLS_TO_PRUNE = 150;
    
    public static void main(String[] args) {
        final Random random = new Random();
        int threads = Runtime.getRuntime().availableProcessors() * 4;
        
        System.out.println("Generating a random full sudoku board...");
        
        final SudokuBoard sourceSudokuBoard = 
                new RandomSudokuBoardGenerator(WIDTH_HEIGHT, random)
                        .generateRandomSudokuBoard();
        
        System.out.println("Board generated. Pruning...");
        
        RandomSudokuBoardPruner.prune(sourceSudokuBoard, 
                                      NUMBER_OF_CELLS_TO_PRUNE,
                                      random);
        
        while (threads > 0) {
            benchmark(threads, new SudokuBoard(sourceSudokuBoard));
            threads /= 2;
        }
    }
    
    private static void benchmark(final int threads,
                                  final SudokuBoard sourceSudokuBoard) {
        
        final long ta = System.currentTimeMillis();
        
        final SudokuBoard solution = 
                new ParallelSudokuSolver()
                        .solve(sourceSudokuBoard,
                               threads);
        
        final long tb = System.currentTimeMillis();
        final long duration = tb - ta;
        
        final boolean isValid = SudokuBoardVerifier.isValid(solution) &&
                                Utils.isCompleteSudokuBoard(solution);
        
        System.out.println(solution);
        System.out.printf("Threads: %2d, duration: %d ms, complete = %b.\n\n", 
                          threads, 
                          duration,
                          isValid);
    }
}

io.github.coderodde.sudoku.misc.IntSet.java:

package io.github.coderodde.sudoku.misc;

/**
 * This class implements a simple set data structures for small integers.
 * 
 * @version 1.0.0 (Dec 4, 2024)
 * @since 1.0.0 (Dec 4, 2024)
 */
public final class IntSet {
    
    /**
     * The actual data array.
     */
    private final boolean[] data;
    
    /**
     * Constructs a new integer set that can accommodate {@code dataCapacity}
     * elements.
     * 
     * @param capacity data array capacity.
     */
    public IntSet(final int capacity) {
        this.data = new boolean[capacity];
    }
    
    /**
     * Adds the integer {@code integer} to this integer set.
     * 
     * @param integer the integer to set.
     */
    public void add(final int integer) {
        data[integer] = true;
    }
    
    /**
     * Queries whether the integer {@code integer} is in this integer set.
     * 
     * @param integer the integer to query for inclusion.
     * 
     * @return {@code true} if and only if the integer {@code integer} is in 
     *         this integer set.
     */
    public boolean contains(final int integer) {
        return data[integer];
    }
    
    /**
     * Removes the integer {@code integer} from this integer set.
     * 
     * @param integer the integer to remove from this integer set.
     */
    public void remove(final int integer) {
        data[integer] = false;
    }
}

io.github.coderodde.sudoku.misc..java:

package io.github.coderodde.sudoku.misc;

import io.github.coderodde.sudoku.SudokuBoard;
import static io.github.coderodde.sudoku.misc.Utils.shuffle;
import java.util.Random;

/**
 * This class is responsible for randomly generating full sudoku boards.
 * 
 * @version 1.0.0 (Jun 22, 2025)
 * @since 1.0.0 (Jun 22, 2025)
 */
public final class RandomSudokuBoardGenerator {
    
    /**
     * The generated sudoku board.
     */
    private final SudokuBoard board;
    
    /**
     * The matrix of random cell value providers.
     */
    private final RandomCellValueProvider[][] providers;
    
    /**
     * The row-wise filters.
     */
    private final IntSet[] rowIntSets;
    
    /**
     * The column-wise filters.
     */
    private final IntSet[] colIntSets;
    
    /**
     * The minisquare filters.
     */
    private final IntSet[][] minisquareIntSets;
    
    /**
     * The minisquare width/height.
     */
    private final int nsqrt;
    
    /**
     * Construct this sudoku board generator.
     * 
     * @param widthHeight the width/height of the resulting sudoku board.
     * @param random      the random number generator.
     */
    public RandomSudokuBoardGenerator(final int widthHeight,
                                      final Random random) {
        this.board = new SudokuBoard(widthHeight);
        this.providers = new RandomCellValueProvider[widthHeight]
                                                    [widthHeight];
        
        for (int y = 0; y < widthHeight; ++y) {
            for (int x = 0; x < widthHeight; ++x) {
                this.providers[y][x] = new RandomCellValueProvider(widthHeight,
                                                                   random);
            }
        }
        
        this.rowIntSets = new IntSet[widthHeight];
        this.colIntSets = new IntSet[widthHeight];
        this.minisquareIntSets = new IntSet[widthHeight]
                                           [widthHeight];
        
        for (int y = 0; y < widthHeight; ++y) {
            this.rowIntSets[y] = new IntSet(widthHeight + 1);
        }
        
        for (int x = 0; x < widthHeight; ++x) {
            this.colIntSets[x] = new IntSet(widthHeight + 1);
        }
        
        final int sqrtn = (int) Math.sqrt(widthHeight);;
        
        for (int y = 0; y < widthHeight; ++y) {
            for (int x = 0; x < widthHeight; ++x) {
                this.minisquareIntSets[y / sqrtn]
                                      [x / sqrtn] = new IntSet(widthHeight + 1);
            }
        }
        
        this.nsqrt = (int) Math.sqrt(widthHeight);
    }
    
    /**
     * The actual generation method.
     * 
     * @return a randomly  built sudoku board.
     */
    public SudokuBoard generateRandomSudokuBoard() {
        generateRandomSudokuBoardImpl(board, 0, 0);
        return board;
    }
    
    /**
     * Implements the random sudoku board generation.
     * 
     * @param board the board to work on.
     * @param x the {@code x}-coordinate of the next cell to process.
     * @param y the {@code y}-coordinate of the next cell to process.
     * @return {@code true} if and only if a valid sudoku board is constructed.
     *         (Will end up in {code board}.)
     */
    private boolean generateRandomSudokuBoardImpl(final SudokuBoard board, 
                                                  int x,
                                                  int y) {
        if (x == board.getWidthHeight()) {
            x = 0;
            ++y;
        }
        
        if (y == board.getWidthHeight()) {
            return true;
        }
        
        for (final int cellValue : providers[y][x].getCellValues()) {
            
            if (rowIntSets[y].contains(cellValue)) {
                continue;
            }
            
            if (colIntSets[x].contains(cellValue)) {
                continue;
            }
            
            if (minisquareIntSets[y / nsqrt]
                                 [x / nsqrt].contains(cellValue)) {
                continue;
            }
            
            rowIntSets[y].add(cellValue);
            colIntSets[x].add(cellValue);
            minisquareIntSets[y / nsqrt]
                             [x / nsqrt].add(cellValue);
            
            board.set(x, y, cellValue);
            
            if (generateRandomSudokuBoardImpl(board,
                                              x + 1,
                                              y)) {
                return true;
            }
            
            rowIntSets[y].remove(cellValue);
            colIntSets[x].remove(cellValue);
            minisquareIntSets[y / nsqrt]
                             [x / nsqrt].remove(cellValue);
        }
        
        return false;
    }
    
    /**
     * This inner static class implements a random cell value provider.
     */
    private static final class RandomCellValueProvider {
        
        private final int[] randomCellValues;

        /**
         * Constructs this random cell value provider.
         * 
         * @param n the width/height of the target sudoku board.
         */
        RandomCellValueProvider(final int n, final Random random) {
            this.randomCellValues = new int[n];
            
            for (int i = 0; i < n; ++i) {
                randomCellValues[i] = i + 1;
            }
            
            shuffle(randomCellValues, random);
        }
        
        int[] getCellValues() {
            return this.randomCellValues;
        }
    }
}

io.github.coderodde.sudoku.misc.RandomSudokuBoardSeedProvider.java:

package io.github.coderodde.sudoku.misc;

import io.github.coderodde.sudoku.SudokuBoard;
import java.awt.Point;
import java.util.ArrayList;
import java.util.List;
import java.util.Random;

/**
 * This class provides facilities for generating random sudoku board seeds.
 * 
 * @version 1.0.0 (Jun 23, 2025)
 * @since 1.0.0 (Jun 23, 2025)
 */
public final class RandomSudokuBoardSeedProvider {
    
    /**
     * Computes a list of seed sudoku boards.
     * 
     * @param sourceBoard    the source sudoku board.
     * @param requestedSeeds the requested number of seeds.
     * 
     * @return a list of seeds.
     */
    public static List<SudokuBoard> computeSeeds(final SudokuBoard sourceBoard,
                                                 final int requestedSeeds) {
        
        // Get the list of all empty cells:
        final List<Point> emptyCellPoints = getEmptyCellPoints(sourceBoard);
        
        // Fix the seed list capacity:
        final int seedsListCapacity = 
                Math.min(emptyCellPoints.size(), 
                         requestedSeeds);
        
        final Random random = new Random();
        
        final List<SudokuBoard> seeds = new ArrayList<>(seedsListCapacity);
        
        // Actual seed generatoin:
        for (int i = 0; i < seedsListCapacity; ++i) {
            seeds.add(computeRandomSeed(sourceBoard, 
                                        emptyCellPoints, 
                                        random));
        }
        
        return seeds;
    }
    
    /**
     * Computes another random seed.
     * 
     * @param board                the current board.
     * @param emptyCellCoordinates the list of empty cell coordinates.
     * @param random               the random number generator.
     * @return a random seed.
     */
    private static SudokuBoard computeRandomSeed(
            final SudokuBoard board,
            final List<Point> emptyCellCoordinates,
            final Random random) {
        
        // Get a copy:
        final SudokuBoard seed = new SudokuBoard(board);
        
        // Get the index of the target point containing no valid cell value:
        final int targetPointIndex = 
                random.nextInt(emptyCellCoordinates.size());
        
        // Get the target point:
        final Point targetPoint = emptyCellCoordinates.get(targetPointIndex);
        
        // Get an array of randomly arranged cell values:
        final int[] cellValues = getRandomCellValues(board.getWidthHeight());
        
        for (final int cellValue : cellValues) {
            // Set the cell value:
            seed.set(targetPoint.x, 
                     targetPoint.y, 
                     cellValue);
            
            // Check that after new cell value the seed remains valid:
            if (SudokuBoardVerifier.isValid(seed)) {
                // Once here, we have found a seed. Return it:
                emptyCellCoordinates.remove(targetPointIndex);
                return seed;
            }
        }
        
        throw new IllegalStateException("Should not get here");
    }
    
    /**
     * Computes the list of point coordinates pointing to empty cells.
     * 
     * @param board the board to process.
     * @return the list of point coordinates pointing to empty cells.
     */
    private static List<Point> getEmptyCellPoints(final SudokuBoard board) {
        final List<Point> emptyCellPoints = new ArrayList<>();
        
        for (int y = 0; y < board.getWidthHeight(); ++y) {
            for (int x = 0; x < board.getWidthHeight(); ++x) {
                if (board.get(x, y) == Utils.UNUSED_CELL) {
                    emptyCellPoints.add(new Point(x, y));
                }
            }
        }
        
        return emptyCellPoints;
    }
    
    /**
     * Computes a randomly ordered array of cell values.
     * 
     * @param widthHeight the width/height of the target board.
     * @return a randomly ordered array of cell values.
     */
    private static int[] getRandomCellValues(final int widthHeight) {
        final int[] cellValues = new int[widthHeight];
        
        for (int i = 0; i < widthHeight; ++i) {
            cellValues[i] = i + 1;
        }
        
        Utils.shuffle(cellValues);
        return cellValues;
    }
}

io.github.coderodde.sudoku.misc.SudokuBoardVerifier.java:

package io.github.coderodde.sudoku.misc;

import io.github.coderodde.sudoku.SudokuBoard;

/**
 * This class provides a static method for checking that an input sudoku board 
 * is valid, i.e., does not break rules of sudoku. For example, the method in
 * question must return {@code false} if a column contains duplicate cell 
 * values.
 * 
 * @version 1.0.0 (Jun 22, 2025)
 * @since 1.0.0 (Jun 22, 2025)
 */
public final class SudokuBoardVerifier {
   
    private SudokuBoardVerifier() {
        
    }
    
    /**
     * Verifies the input sudoku board.
     * 
     * @param board the sudoku board to verify.
     * 
     * @return {@code true} if and only if the input sudoku board is valid.
     */
    public static boolean isValid(final SudokuBoard board) {
        final int n = board.getWidthHeight();
        
        final IntSet[] rowIntSets = new IntSet[n];
        final IntSet[] colIntSets = new IntSet[n];
        
        for (int i = 0; i < n; ++i) {
            rowIntSets[i] = new IntSet(n + 1);
            colIntSets[i] = new IntSet(n + 1);
        }
        
        final int sqrtn = (int) Math.sqrt(n);
        final IntSet[][] minisquareIntSets = new IntSet[sqrtn]
                                                       [sqrtn];
        
        for (int y = 0; y < sqrtn; ++y) {
            for (int x = 0; x < sqrtn; ++x) {
                minisquareIntSets[y][x] = new IntSet(n + 1);
            }
        }
        
        for (int y = 0; y < n; ++y) {
            for (int x = 0; x < n; ++x) {
                final int cellValue = board.get(x, y);
                
                if (cellValue == Utils.UNUSED_CELL) {
                    continue;
                }
                
                if (!board.isValidCellValue(x, y)) {
                    return false;
                }
                
                final int minisquareCellX = x / sqrtn;
                final int minisquareCellY = y / sqrtn;
                
                if (minisquareIntSets[minisquareCellY]
                                     [minisquareCellX].contains(cellValue)) {
                    return false;
                }
                
                minisquareIntSets[minisquareCellY]
                                 [minisquareCellX].add(cellValue);
                
                if (rowIntSets[x].contains(cellValue)) {
                    return false;
                }
                
                rowIntSets[x].add(cellValue);
                
                if (colIntSets[y].contains(cellValue)) {
                    return false;
                }
                
                colIntSets[y].add(cellValue);
            }
        }
        
        return true;
    }
}

io.github.coderodde.sudoku.misc.Utils.java:

package io.github.coderodde.sudoku.misc;

import io.github.coderodde.sudoku.SudokuBoard;
import java.util.Random;

/**
 * This class provides common utilities.
 * 
 * @version 1.0.0 (Jun 22, 2025)
 * @since 1.0.0 (Jun 22, 2025)
 */
public final class Utils {
    
    public static final int UNUSED_CELL = 0;
    private static final int MINIMUM_WIDTH_HEIGHT = 4;
    
    private Utils() {
        
    }
    
    public static void checkWidthHeight(final int widthHeight) {
        if (widthHeight < 4) {
            final String exceptionMessage =
                    String.format(
                            "The widthHeight(%d) < MINIMUM_WIDTH_HEIGHT(%d)",
                            widthHeight,
                            MINIMUM_WIDTH_HEIGHT);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
        
        int n;
        
        for (n = MINIMUM_WIDTH_HEIGHT / 2; ; ++n) {
            if (n * n >= widthHeight) {
                break;
            }
        }
        
        if (n * n != widthHeight) {
            final String exceptionMessage = 
                    String.format(
                            "Abnormal widthHeight(%d)",
                            widthHeight);
            
            throw new IllegalArgumentException(exceptionMessage);
        }
    }
    
    /**
     * This static method implements the 
     * <a href="https://en.wikipedia.org/wiki/Fisher%E2%80%93Yates_shuffle">
     * Fisher-Yates shuffle</a>.
     * 
     * @param array the array to shuffle.
     */
    public static void shuffle(final int[] array, final Random random) {
        for (int i = array.length - 1; i > 0; --i) {
            final int j = random.nextInt(i + 1);
            final int tmp = array[j];
            array[j] = array[i];
            array[i] = tmp;
        }
    }   
    
    /**
     * Passes to {@link #shuffle(int[], java.util.Random)}.
     * 
     * @param array the array to shuffle.
     */
    public static void shuffle(final int[] array) {
        shuffle(array, new Random());
    }
    
    public static boolean isCompleteSudokuBoard(final SudokuBoard board) {
        for (int y = 0; y < board.getWidthHeight(); ++y) {
            for (int x = 0; x < board.getWidthHeight(); ++x) {
                if (board.get(x, y) == Utils.UNUSED_CELL) {
                    return false;
                }
            }
        }
        
        return true;
    }
}

Typical output

I managed to produce that optimistic results:

Generating a random full sudoku board...
Board generated. Pruning...
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|13| 6| 7|12| 4|10| 8| 3| 9| 2| 1|15|14|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1|14|12| 4| 6| 8|15|11|16| 7| 5|10| 9| 3|13| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 6| 4|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|12| 9| 8|14|10| 7|13| 4| 2|16| 5|11| 1| 3| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5| 9|12|15|10| 8| 4|13| 7|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 7| 4|14|15| 1| 2|12|13| 9| 6|11| 8|16| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|11| 4|16| 8| 7|14| 3| 1| 2| 9|15|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2|12| 1|15| 4| 7| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|11| 6|14| 9|10| 8| 3|15| 7|12| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|15| 8|12|13| 3|10| 4| 5|11| 1|16|14| 6| 2| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10| 9|15| 8| 7|14|12| 2|13|16|11| 4| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9|10|14| 7|12| 5| 1| 6| 2| 8|13|15| 3| 4|11|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3|13| 8|14| 9|15| 6| 5|12| 4|10| 2| 1| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12| 4| 5| 2|10| 7|11|16| 3| 1|14| 9|13| 8| 6|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 1| 6|15| 4|13| 3| 2|10|16|11| 7|12|14| 9| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads: 64, duration: 2419 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|14| 6| 4|12| 7|10| 8| 3| 9| 2|15|11|13| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1| 4|12|13| 6| 8|15|11|16|10| 5| 7| 9| 3|14| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 4| 6|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|12| 9| 8|14|10|16|13| 4| 2| 3| 5|11| 1|15| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5| 9|12|15|10| 8| 4|13| 7|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3|15| 4|14| 7| 1|12| 2| 9| 6|13|11| 8|16| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|15| 4|11| 8| 7|14|16| 1| 2| 9| 3|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2| 4| 1|15| 7| 8| 6| 5|10|12|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|15| 6|12|10| 9| 1| 3|14| 7| 8|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15| 7| 8|12|13| 3|10|14| 5|11| 4|16| 1| 6| 2| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10| 9|11| 8| 7|14|12| 2|13| 3|15| 4|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9|10|13| 7|12| 5| 1| 6| 2| 8|14|15|16| 4|11| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3| 2| 8|13| 9|15| 6| 5|12| 4|10|14| 1| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12|14| 5| 4|10| 7| 2|16| 3| 1|11| 9|13| 8| 6|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 1| 6|15|11|14| 3| 4|13|16| 7|10|12| 2| 9| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads: 32, duration: 27295 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|13| 6| 7|12| 4|10| 8| 3| 9| 2|14|11|15| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1|14|12| 4| 6| 8|15|11|16| 7| 5|10| 9| 3|13| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 6| 4|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|12| 9| 8|14|10| 7|13| 4| 2|16| 5|11| 1| 3| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5| 9|12|15|10| 8| 4|13|14| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 7| 4|14|15| 1| 2|12|13| 9| 6|11| 8|16| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|11| 4|16| 8| 7|14| 3| 1|15| 9| 2|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2|12| 1|15| 4| 7| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|15| 6|14| 9|10| 8| 3| 1| 7|12|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|15| 8|12| 9| 3|10| 4| 5|11| 1|13| 2|14| 6|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10|13|11| 8| 7|14|12| 2|16| 3|15| 4| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9|10| 5| 7|12|14| 1| 6| 2| 8|13|15|16| 4|11| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3|13| 8| 7| 9|15| 6| 5|12| 4|10| 2| 1|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12| 4| 6| 2|10| 5|11|16| 3| 1|14| 9|13| 8| 7|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 1|14|15| 4|13| 3| 2|10|16|11| 7|12| 6| 9| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads: 16, duration: 21201 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|15| 6| 7|12| 4|10| 8| 3| 9| 2|13|11|14| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1| 4|12|13| 6| 8|15|11|16| 7| 5|14| 9| 3|10| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|14| 9| 1|16|13| 5|11| 6| 4|10| 7|12|15| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|12| 9| 8|14|10| 7|13| 4| 2|16| 5|11| 1| 3| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5| 9|13|15|12| 8| 4|14| 7|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 7| 4|14|15| 1| 2|12| 6|10|11| 9| 8|16|13| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|11| 4|16| 8| 7|14| 3| 1|15| 9| 2|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2|12| 1|15| 4| 7| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|15| 6|14| 9| 8|10| 3| 1| 7|12|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|15| 8|12|13| 3|10| 4| 5|11| 1|16|14| 2| 6| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10| 9|11| 8| 7|14|12| 2|13|16|15| 4| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8|10|13| 7|12| 5| 1| 6| 2| 9|14|15| 3| 4|11|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3| 2| 8| 7| 9|15|12| 5|13| 4|10| 6| 1|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12|14| 5| 4|10|13|11|16| 3| 1| 6| 7| 2| 8| 9|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9| 1| 6|15| 4|14| 3| 2|10|16| 8|11|12|13| 5| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads:  8, duration: 6445 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|13| 6| 7|12| 4|10| 8| 3| 9| 2| 1|11|15|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1|14|12| 4| 6| 8|15|11|16|10| 5| 7| 9| 3|13| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 4| 6|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|12| 9| 8|14|10| 7|13| 4| 2|16| 5|11| 1| 3| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5|12| 9|15|10| 8| 4|13|14| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 7| 4|14|15| 1| 9| 2|12| 6|11|13| 8|16| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|16| 4|11| 8| 7|14| 3| 1|15| 9| 2|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|12| 2|16| 1|15| 7| 4| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|15| 6| 9|10| 8| 1| 3|14| 7|12|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|15| 8|12| 4| 3|10|14| 5|11|13|16| 2| 6| 9| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10|11|13| 8| 7|14|12| 2| 9|16|15| 4| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8|10|14| 7|13| 5| 1| 6| 2| 9|12|15| 3| 4|11|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3| 2|10| 7|12|15| 6| 5| 8| 4|13|14| 1| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12| 4| 5|13| 9|14| 2|16| 3| 1| 7|11|10| 8| 6|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9| 1| 6|15| 8|11| 3| 4|13|16|14|10|12| 2| 7| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads:  4, duration: 4555 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|13| 6| 7|12| 4|10| 8| 3| 9| 2| 1|15|14|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1|14|12| 4| 6| 8|15|11|16|10| 5| 7| 9| 3|13| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 4| 6|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|12| 9| 8|14|10| 7|13| 4| 2|16| 5|11| 1| 3| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 5| 9|12|15|10| 8| 4|13| 7|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3| 7| 4|14|15| 1| 2|12| 9| 6|13|11| 8|16| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5|11| 4|16| 8| 7|14| 3| 1| 2| 9|15|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2|12| 1|15| 7| 4| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4|13| 2|16| 5|11| 6|14|10| 9| 8| 3|15| 7|12| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|15| 8|12| 9| 3|10| 4| 5|11| 1|13|14| 6| 2|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10|13|15| 8| 7|14|12| 2|16| 3|11| 4| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9|10| 5| 7|12|13| 1| 6| 2| 8|14|15|16| 4|11| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3|13| 8|14| 9|15| 6| 5|12| 4|10| 2| 1| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12| 4|14| 2|10| 5|11|16| 3| 1| 7| 9|13| 8| 6|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8| 1| 6|15| 4| 7| 3| 2|13|16|11|10|12|14| 9| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads:  2, duration: 17218 ms, complete = true.

+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 5|16|13| 6| 7|12| 4|10| 8| 3| 9| 2| 1|14|15|11|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 1|14|12| 4| 6| 8|15|11|16| 7| 5|10| 9| 3|13| 2|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 2| 3|15| 9| 1|16|13| 5|11| 6| 4|14| 7|12|10| 8|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|10| 8| 7|11| 2| 9|14| 3| 1|13|15|12| 6| 5|16| 4|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 7|12| 9| 8|15|10|16|13| 4| 2| 3| 5|11| 1|14| 6|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|11| 2|16| 1| 3| 6| 7|14| 9|15|12| 8| 4|13| 5|10|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 3|15| 4|14| 9| 1| 5|12| 6|10|11|13| 8|16| 2| 7|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|13| 6|10| 5| 8| 4|11| 2| 7|14|16| 1|15| 9| 3|12|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|14| 9|11| 3|16| 2|12| 1|15| 4| 7| 6| 5|10| 8|13|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|15|13| 2|16| 5|11| 6| 4|10| 8| 1| 3|14| 7|12| 9|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 4| 7| 8|12|14| 3|10| 9| 5|11|13|16| 2|15| 6| 1|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 6| 5| 1|10|13|15| 8| 7|14|12| 2| 9| 3|11| 4|16|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 8|10| 5| 7|12|13| 1| 6| 2| 9|14|15|16| 4|11| 3|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|16|11| 3| 2|10| 7| 9|15|12| 5| 8| 4|13| 6| 1|14|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
|12| 4|14|13|11| 5| 2|16| 3| 1| 6| 7|10| 8| 9|15|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
| 9| 1| 6|15| 4|14| 3| 8|13|16|10|11|12| 2| 7| 5|
+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+--+
Threads:  1, duration: 24279 ms, complete = true.

Critique request

As always, I am eager to hear any constructive commentary on my attempt.

\$\endgroup\$
2
  • 1
    \$\begingroup\$ It would be helpful if you described the algorithm in the comments or in the post. \$\endgroup\$ Commented Jun 23 at 12:18
  • 1
    \$\begingroup\$ I don't write Java, but can sometimes catch the drift (to a degree) when reading languages like this. This is not 'ordinary' Sudoku, and I struggle to discern what it's meant to be. No clues found in the description or the code... From an 'outsider' who might be able to, at least, appreciate something, all I see is a lot of code that is manipulating array values for some unknown purpose while timing itself, too. Seems irrelevant to know (optimise) a journey that ends at nowhere... My assessment is simply, "Why??" \$\endgroup\$ Commented Jun 23 at 21:38

2 Answers 2

Reset to default
7
\$\begingroup\$

I expected the SudokuBoard.isValidCellValue() method to do more validation. It only checks that the value stored in the cell is in the correct range for the board. A "valid cell value" would be to me one that does not violate the unique constraints of the board. You would not need this method at all if your set method did input validation.

public boolean isValidCellValue(final int x, final int y) {
    final int cellValue = get(x, y);
    return 1 <= cellValue && cellValue <= data.length;
}

Maybe consider moving the SudokuBoard.toString() method to a separate SudokuBoardRenderer class. This much implementation just for debug printing the board seems a bit excessive.

Never write a Utils class or misc package. It's a sign that you didn't spend enough time trying to figure out where the methods belong and they both end up being code dumpsters. The Utils.checkWidthHeight() and Utils.isCompleteSudokuBoard() methods belong in the SudokuBoard class, as does SudokuBoardVerifier.isValid(). Although if this library is only intended for solving sudokus, do you even need to allow a SudokuBoard with an invalid state? Can't your set method just reject invalid values right away?

You are not solving a sudoku board. You're solving a sudoku puzzle. Change naming of method parameters to reflect this. This helps the reader because when they see the words "sudoku puzzle" they immediately understand that it's a SudokuBoard with the initial pre-set numbers. Think "does the name accurately represent this object and only this object or can the name apply to several objects of different purpose?" The numberOfProcessors parameter describes the number of threads the user wants, not the number of processors they have.

public SudokuBoard solve(final SudokuBoard puzzle,
                         final int numberOfThreads) {

What are seeds and why is the seed a public concept? Does the user need to know anything about seeds? When you invent concepts that are unique to your algorithm you should document what they represent.

\$\endgroup\$
6
\$\begingroup\$ 
/**
 * The row-wise filters.
 */
private IntSet[] rowIntSets;

/**
 * The column-wise filters.
 */
private IntSet[] colIntSets;

/**
 * The minisquare filters.
 */
private IntSet[][] minisquareIntSets;

Good, using these instead of one-set-per-cell saves a bunch of bookkeeping when filling/unfilling a cell. One-set-per-cell is only useful in the context of some advanced algorithms that reduce those sets more than than to being the intersection of a row/column/square constraint, which do exist btw for example either when modeling "human solving techniques" such as X-wing or if you model a Sudoku as a bunch of interacting "alldifferent" global constraints ( eg https://www.andrew.cmu.edu/user/vanhoeve/papers/alldiff.pdf )

Threads: 1, duration: 24279 ms

Based on my experience with 9x9 Sudoku solvers/random instance generators and 8x8 binary puzzles (Sudoku variant), and I realize you've tested 16x16 Sudokus here, this seems like a lot.

Anyway here are a couple of techniques that you may consider (some of them mutually exclusive):

  • Solving the most-constrained cell first. This has multiple effects. Trying values from a smaller set reduces the branching factor (often to 1 - many cells can be filled in directly without trying multiple options, and filling them in ASAP helps solve other cells by reducing their sets of possible values so it's very useful to find these opportunities), keeping the branching factor small when high in the search tree is the most important time to do it (near the bottom it will tend to be naturally small, since most of the board is filled so there are few choices left), and more-constrained cells are more likely to lead to conflicts that require backtracking which is better to do as high up in the tree as possible.
  • As a "light" version of that, iteratively fill in the cells that have exactly 1 option before moving on to recursively trying different options for a cell with more than one option. This already helps a ton even if the rest of the solver is top-to-bottom & left-to-right.
  • Using a "dual view" to track in addition to "what values can this cell have", also "which cells can this value go in" (after all, for each row/column/block, every value must go somewhere). This can fill in some cells that have forced values that wouldn't be detected from the normal view. The more cells that are plainly filled in instead of trying multiple options, the better.
  • Using bit-sets for the IntSet. Not for the savings in size, that doesn't really matter, but for some tricks that you can do with them efficiently that aren't efficient otherwise. For example, it's easy to find a set of values that are allowed in exactly one unfilled cell (and then of course, you can fill that cell even if it still has lots of possible values, because the value has nowhere else to go). You can do this anyway, but with bit-sets it's cheap. This is a kind of ad-hoc dynamic way to construct part of the "dual view" that I mentioned in the previous point, rather than maintaining extra state for it, and focused only on the interesting case (only detecting if the "dual view" has a singleton set, rather than building the whole set).
\$\endgroup\$

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.