0

I am building a Sudoku Solver visualizer that will solve the sudoku board and show the computer's steps as it tries each number in the available slots. I have been using the JFrame/JPanel framework to visualize this but have had problems updating the graphics to show the computer solving it and pausing the graphics in between each new attempt at each slot.

The solver works perfectly and correctly solves the board but I can only see the unsolved board and the solved board when I click the enter button.

Here is my class with the main method:

public class sudokuSolverVisualizer {

    public static void main(String[] args) {

        new GameFrame();

    }
}

Here is the Game Frame class:

import javax.swing.*;

public class GameFrame extends JFrame {

    GameFrame(){
        this.add(new GamePanel());
        this.setTitle("Sudoku Solver");
        this.setResizable(false);
        this.pack();
        this.setDefaultCloseOperation(JFrame.EXIT_ON_CLOSE);
        this.setLocationRelativeTo(null);
        this.setVisible(true);
    }

}

And here is my JPanel class that solves the sudoku board and updates the graphics:

import javax.swing.*;
import java.awt.*;
import java.awt.event.*;
import java.awt.geom.Line2D;

public class GamePanel extends JPanel implements ActionListener {

    //region Variable Declaration
    private static final int SIZE = 9;
    static final int SCREEN_WIDTH = 270;
    static final int SCREEN_HEIGHT = 270;
    static final int UNIT_SIZE = SCREEN_WIDTH/SIZE;
    static final int GAME_DELAY = 25;
    static final int[][] board = {
            {7, 0, 2, 0, 5, 0, 6, 0, 0},
            {0, 0, 0, 0, 0, 3, 0, 0, 0},
            {1, 0, 0, 0, 0, 9, 5, 0, 0},
            {8, 0, 0, 0, 0, 0, 0, 9, 0},
            {0, 4, 3, 0, 0, 0, 7, 5, 0},
            {0, 9, 0, 0, 0, 0, 0, 0, 8},
            {0, 0, 9, 7, 0, 0, 0, 0, 5},
            {0, 0, 0, 2, 0, 0, 0, 0, 0},
            {0, 0, 7, 0, 4, 0, 2, 0, 3}
    };
    static boolean solving = false;
    static boolean solved = false;
    static Timer timer;
    //endregion

    GamePanel(){
        this.setPreferredSize(new Dimension(SCREEN_WIDTH, SCREEN_HEIGHT));
        this.setBackground(Color.lightGray);
        this.setFocusable(true);
        this.addKeyListener(new MyKeyAdapter());
        startGame();
    }

    public void paintComponent(Graphics g){
        super.paintComponent(g);
        draw(g);
    }

    public void startGame(){
        timer = new Timer(GAME_DELAY, this);
        timer.start();
    }

    private static void draw(Graphics g) {
        if (solving){
            solveBoard(board, g);
        }
        Graphics2D g2 = (Graphics2D) g;
        for (int row = 0; row < SIZE; row++){
            if (row % 3 == 0 && row != 0){
                g2.setStroke(new BasicStroke(5));
            } else {
                g2.setStroke(new BasicStroke(1));
            }
            g2.draw(new Line2D.Float(0, row * UNIT_SIZE, SCREEN_WIDTH, row * UNIT_SIZE));
            for (int column = 0; column < SIZE; column++){
                if (column % 3 == 0 && column != 0){
                    g2.setStroke(new BasicStroke(5));
                } else {
                    g2.setStroke(new BasicStroke(1));
                }
                g2.draw(new Line2D.Float(column * UNIT_SIZE, 0, column * UNIT_SIZE, SCREEN_HEIGHT));
                if (solved){
                    g.setColor(Color.green);
                }
                g2.drawString(String.valueOf(board[row][column]), column * UNIT_SIZE + 12, row * UNIT_SIZE + 22);
                g.setColor(Color.black);
            }
        }

    }

    private static boolean isInRow(int[][] board, int num, int row){
        for (int i = 0; i < SIZE; i++){
            if (board[row][i] == num){
                return true;
            }
        }
        return false;
    }

    private static boolean isInColumn(int[][] board, int num, int column){
        for (int i = 0; i < SIZE; i++){
            if (board[i][column] == num){
                return true;
            }
        }
        return false;
    }

    private static boolean isInBox(int[][] board, int num, int row, int column){
        int rowStart = row - row % 3;
        int columnStart = column - column % 3;
        for (int i = rowStart; i < rowStart + 3; i++){
            for (int j = columnStart; j < columnStart + 3; j++) {
                if (board[i][j] == num) {
                    return true;
                }
            }
        }
        return false;
    }

    private static  boolean isValidPlace(int[][] board, int num, int row, int column){
        return !isInRow(board, num, row) &&
                !isInColumn(board, num, column) &&
                !isInBox(board, num, row, column);
    }

    private static boolean solveBoard(int[][] board, Graphics g){
        Graphics2D g2 = (Graphics2D) g;
        g2.setColor(Color.black);
        for (int row = 0; row < SIZE; row++) {
            for (int column = 0; column < SIZE; column++) {
                if (board[row][column] == 0) {
                    for (int num = 1; num <= SIZE; num++) {
                        if (isValidPlace(board, num, row, column)) {
                            board[row][column] = num;
                            drawElements(g2, row, column, true);
                            if (solveBoard(board, g)) {
                                return true;
                            }
                            else{
                                board[row][column] = 0;
                                drawElements(g2, row, column, false);
                            }
                        }
                    }
                    return false;
                }
            }
        }
        solving = false;
        solved = true;
        draw(g);
        return true;
    }

    private static void drawElements(Graphics2D g2, int row, int column, boolean correct){
        if (correct) {
            g2.setColor(Color.green);
        } else {
            g2.setColor(Color.red);
        }
        g2.clearRect(column * UNIT_SIZE, row * UNIT_SIZE, UNIT_SIZE, UNIT_SIZE);
        g2.drawString(String.valueOf(board[row][column]), column * UNIT_SIZE + 12, row * UNIT_SIZE + 22);
        g2.drawRect(column * UNIT_SIZE, row * UNIT_SIZE, UNIT_SIZE, UNIT_SIZE);
        g2.setColor(Color.black);
    }

    private static void printBoard(int[][] board){
        for (int row = 0; row < SIZE; row++){
            if (row % 3 == 0 && row != 0){
                System.out.println("-------------------");
            }
            for (int column = 0; column < SIZE; column++){
                if (column % 3 == 0 && column != 0){
                    System.out.print("|");
                }
                System.out.print(board[row][column] + " ");
            }
            System.out.println();
        }
    }

    @Override
    public void actionPerformed(ActionEvent e) {
        if (solving) {
            repaint();
        }
    }

    public class MyKeyAdapter extends KeyAdapter {
        @Override
        public void keyPressed(KeyEvent e) {
            switch (e.getKeyCode()){
                case KeyEvent.VK_ENTER:
                    solving = true;
                    break;
            }
        }
    }

}

If you could help me find a way to pause the graphics in between each attempt at each slot or somehow repaint the graphics every time it tries a number, that would be great!

Ryan Tobin
  • 53
  • 1
  • 6
  • You have a major design problem. `paintComponent` calls `draw` which conditionally calls `solveBoard` which then calls `draw`. You are doing way to much processing in the Event Dispatch Thread. Adding a timer at this stage would just complicate things. Nothing should be "solved" in the EDT and you should do minimal processing there. That includes all of your listeners. – WJS Feb 25 '22 at 19:55
  • Check out [Bubble Sort Animation](https://stackoverflow.com/questions/64196198/bubble-sort-animation/64196256#64196256) for an example showing how to animate individual steps. – camickr Feb 25 '22 at 19:59
  • Decouple of the solver from the paint process. The paint process should only paint the "current state". Each time the solver goes through a cycle, the UI should then be updated – MadProgrammer Feb 25 '22 at 20:30

1 Answers1

0

Visualising recursion like this is very hard, because what you need is control over the flow. Rather than the algorithm being allowed to run "freely", you need some way that you can control each iteration.

The first thing I did was adapted a non-recursive solver algorithm from Java | Recursive and non-recursive Sudoku solutions (Starter-friendly)

This allowed to create a step method which would move the solution along by a single (or close enough for the purpose) step.

This means that I can call step from Timer and control when the algorithm updates.

Important

This is NOT a Sudoku solution, this focus on how you might adopt a "recursive" style algorithm so it can be visualised, I take no responsibility for the accuracy of the algorithm

Runnable example

enter image description here

import java.awt.BorderLayout;
import java.awt.Dimension;
import java.awt.EventQueue;
import java.awt.Font;
import java.awt.FontMetrics;
import java.awt.Graphics;
import java.awt.Graphics2D;
import java.awt.event.ActionEvent;
import java.awt.event.ActionListener;
import java.time.Duration;
import java.time.Instant;
import java.util.Arrays;
import java.util.LinkedList;
import java.util.Stack;
import java.util.StringJoiner;
import javax.swing.JButton;
import javax.swing.JFrame;
import javax.swing.JPanel;
import javax.swing.Timer;

public class Main {

    int[][] board = {
        {7, 0, 2, 0, 5, 0, 6, 0, 0},
        {0, 0, 0, 0, 0, 3, 0, 0, 0},
        {1, 0, 0, 0, 0, 9, 5, 0, 0},
        {8, 0, 0, 0, 0, 0, 0, 9, 0},
        {0, 4, 3, 0, 0, 0, 7, 5, 0},
        {0, 9, 0, 0, 0, 0, 0, 0, 8},
        {0, 0, 9, 7, 0, 0, 0, 0, 5},
        {0, 0, 0, 2, 0, 0, 0, 0, 0},
        {0, 0, 7, 0, 4, 0, 2, 0, 3}
    };

    public static void main(String[] args) {
        new Main();
    }

    public Main() {
//        print(board);
        SudokuSolver solver = new SudokuSolver(board);
//        System.out.println();
        print(solver.solve());

        EventQueue.invokeLater(new Runnable() {
            @Override
            public void run() {
                SudokuSolver solver = new SudokuSolver(board);
                JFrame frame = new JFrame("Test");
                frame.add(new MainPane(solver));
                frame.pack();
                frame.setLocationRelativeTo(null);
                frame.setVisible(true);
            }
        });
    }

    public void print(int[][] board) {
        for (int[] row : board) {
            StringJoiner joiner = new StringJoiner(" ", "", "\n");
            for (int cell : row) {
                joiner.add(String.format("%d", cell));
            }
            System.out.print(joiner.toString());
        }
    }

    public class MainPane extends JPanel {

        private SolverPane solverPane;

        public MainPane(SudokuSolver solver) {
            setLayout(new BorderLayout());
            solverPane = new SolverPane(solver);

            add(solverPane);

            JButton startButton = new JButton("Go");
            startButton.addActionListener(new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    startButton.setEnabled(false);
                    solverPane.start(new SolverPane.Observer() {
                        @Override
                        public void didCompleteSolution() {
                            startButton.setEnabled(true);
                        }
                    });
                }
            });

            add(startButton, BorderLayout.SOUTH);
        }

    }

    public class SolverPane extends JPanel {

        public interface Observer {

            public void didCompleteSolution();
        }

        private SudokuSolver solver;
        private Observer observer;

        private Dimension preferredSize;

        private int gap = 4;

        public SolverPane(SudokuSolver solver) {
            this.solver = solver;
            solver.prepareSolution();
            setFont(new Font("Monospaced", Font.PLAIN, 20));
        }

        @Override
        public Dimension getPreferredSize() {
            if (preferredSize == null) {
                FontMetrics fm = getFontMetrics(getFont());
                preferredSize = new Dimension(10 + ((fm.stringWidth("0") + gap)  * 9), 10 + (fm.getHeight() * 9));
            }
            return preferredSize;
        }

        public void start(Observer observer) {
            this.observer = observer;
            solver.prepareSolution();
            Instant startedAt = Instant.now();
            Timer timer = new Timer(5, new ActionListener() {
                @Override
                public void actionPerformed(ActionEvent e) {
                    if (solver.step()) {
                        observer.didCompleteSolution();
                        ((Timer) e.getSource()).stop();
                        Duration duration = Duration.between(Instant.now(), startedAt);
                        System.out.println(duration);
                    }
                    repaint();
                }
            });
            timer.start();
        }

        @Override
        protected void paintComponent(Graphics g) {
            super.paintComponent(g);
            Graphics2D g2d = (Graphics2D) g.create();
            FontMetrics fm = g2d.getFontMetrics();
            int gap = 4;
            int cellWidth = fm.stringWidth("0") + 4;

            int xPos = (getWidth() - (cellWidth * 9)) / 2;
            int yPos = (getHeight() - (cellWidth * 9)) / 2;

            g2d.translate(xPos, yPos);

            Stack<SudokuSolver.Cell> solved = solver.getSolved();
            if (solved != null) {
                for (SudokuSolver.Cell cell : solver.getSolved()) {
                    int x = cell.getCol() * cellWidth;
                    int y = ((cell.getRow() - 1) * fm.getHeight());
                    g2d.drawString(Integer.toString(cell.getValue()), x, y);
                }
            }
            g2d.dispose();
        }

    }

    class SudokuSolver {

        // Adapted from https://leetcode.com/problems/sudoku-solver/discuss/1392747/java-recursive-and-non-recursive-sodoku-solutions-starter-friendly
        private int[][] board;

        private LinkedList<Cell> unsolved;
        private Stack<Cell> solved;

        public SudokuSolver(int[][] originalBoard) {
            this.board = originalBoard;
        }

        public LinkedList<Cell> getUnsolved() {
            return unsolved;
        }

        public Stack<Cell> getSolved() {
            return solved;
        }

        protected void prepareSolution() {
            // all we need are just 1 stack, and 1 queue.
            unsolved = new LinkedList<>();  // queue:  all unconfirmed cells
            solved = new Stack<>();             // stack:  all cells which are confirmed temporarily

            // init candidates
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    if (board[i][j] == 0) {
                        Cell cell = new Cell(i, j, board);
                        unsolved.addLast(cell);
                    } else {
                        Cell cell = new Cell(i, j);
                        cell.value = board[i][j];
                        solved.add(cell);
                    }
                }
            }
        }

        public boolean step() {
            if (unsolved == null || solved == null) {
                prepareSolution();
            }

            if (unsolved.peekFirst() == null) {
                return true;
            }

            Cell curr = unsolved.removeFirst();
            if (curr.isValidCandid()) {
                solved.push(curr); // *
                unsolved = excludeCandid(curr, unsolved);
            } else {        // MARK-s4
                unsolved.addFirst(curr); // *
                Cell prev = solved.pop();  // *
                unsolved = revertCandid(prev, unsolved);
                curr.resetCandid();     // restart selection
                prev.nextCandid();
                unsolved.addFirst(prev);  // *
            }

            return unsolved.peekFirst() == null;
        }

        public int[][] solve() {
            prepareSolution();

            // try different combinations until all unsolved cells gone
            Cell curr;
            while (unsolved.peekFirst() != null) {
                curr = unsolved.removeFirst();
                if (curr.isValidCandid()) {
                    solved.push(curr); // *
                    unsolved = excludeCandid(curr, unsolved);
                } else {        // MARK-s4
                    unsolved.addFirst(curr); // *
                    Cell prev = solved.pop();  // *
                    unsolved = revertCandid(prev, unsolved);
                    curr.resetCandid();     // restart selection
                    prev.nextCandid();
                    unsolved.addFirst(prev);  // *
                }
            }

            int[][] solution = new int[board.length][board.length];
            for (int row = 0; row < board.length; row++) {
                for (int col = 0; col < board[row].length; col++) {
                    solution[row][col] = board[row][col];
                }
            }

            // solutions back
            while (!solved.empty()) {
                confirm(solved.pop(), solution);
            }
            return solution;
        }

        void confirm(Cell solution, int[][] problem) {
            problem[solution.row][solution.col] = solution.value;
        }

        // once some candidates are taken, we need to exclude them in related cells
        LinkedList<Cell> excludeCandid(Cell target, LinkedList<Cell> before) {
            LinkedList<Cell> after = new LinkedList<Cell>();
            Cell curr;
            while ((curr = before.peekFirst()) != null) {
                before.removeFirst();
                curr.excludeCandidate(target);   // exclude the target candidate

                // OPTIONAL, but win more about 70% time!
                if (curr.isValidCandid()) // if there is conflict, handle it first
                {
                    after.addLast(curr);
                } else {
                    after.addFirst(curr);
                }
            }
            return after;
        }

        // once the previous candidates were incorrectly taken, we need to revert/recover them in related cells
        LinkedList<Cell> revertCandid(Cell target, LinkedList<Cell> before) {
            LinkedList<Cell> after = new LinkedList<Cell>();
            Cell curr = null;
            while ((curr = before.peekFirst()) != null) {
                before.removeFirst();
                curr.enableCandidate(target);
                after.addLast(curr);
            }
            return after;
        }
        // >> SOLUTION

        // << STRUCT
        public class Cell {

            /**
             *
             * To solve sudoku, we can use one stack to save all temporarily
             * confirmed cells, and one queue to save all unconfirmed ones, then
             * repeatedly dequeue elements from queue and push them into the
             * stack, analysing them at the same time, until queue is empty,
             * then Sudoku is solved. If stack encounter EmptyStackException at
             * some point of time, this method then is not capable to solve the
             * given Sudoku. Note, analysing cells is simple and
             * straightforward, just the "pointer" stuff, and the detail is
             * shown below.
             *
             *
             * ################################## ## "1 stack and 1 queue" model
             * : ##################################
             *
             * ........................................................................
             * .----------- (2,5) (2,4) (2,6) (2,0) .... |
             * ........................................................................
             * | (unsolved Queue/List) | | \/ | | | | | (2,3) | | .... | | ....
             * | | .... | ---------- (solved Stack)
             *
             *
             *
             * ################################## ## "candidate pointer" model :
             * ( cell(2,0) at any possible point of time )
             * ##################################
             *
             * Characters: 1 2 3 4 5 6 7 8 9
             *
             * candidates: [-999999, 0 , 33 , -1 , 78 , 0 , 0 , -1 , 0 , -1] ^
             * [Stage 1] ... 21 ^ [Stage 2] ... 21 23 22 25 ^(>9) [Stage 3]
             *
             * Explanations: [Stage 1] candidate pointer(cPtr), when at very
             * beginning, and there are 3 possible values that can be chosen;
             * [Stage 2] after '1' is selected by 21st cell, i.e. problem[2][2],
             * cPtr moves to 5th; [Stage 3] at this point, the '1' was taken by
             * 21st cell, '5' was by 23rd, '6' was by 22nd, '8' was by 25th,
             * result in cPtr overflow, which means some of previous candidates
             * were taken incorrectly, and getting back and retrying is needed.
             * [Stage 4] details is shown in some place of codes, marked as
             * "MARK-s4"
             *
             *
             *
             */
            private int row;
            private int col;
            private int[] candidates; // -1: confirmed   0: possible   >0: be selected by others
            private int value = -1; // [1,9] or 10,11,...

            public Cell(int i, int j) {
                row = i;
                col = j;
                candidates = new int[10];
                candidates[0] = -999999;
            }

            public Cell(int i, int j, int[][] datasource) {
                this(i, j);
                initCandidates(datasource);
            }

            public int getRow() {
                return row;
            }

            public int getCol() {
                return col;
            }

            public int getValue() {
                return value;
            }

            protected void initCandidates(int[][] datasource) {

                // same row
                for (int i = 0; i < 9; i++) {
                    if (datasource[row][i] != 0) {
                        candidates[datasource[row][i]] = -1;
                    }
                }
                // same col
                for (int i = 0; i < 9; i++) {
                    if (datasource[i][col] != 0) {
                        candidates[datasource[i][col]] = -1;
                    }
                }

                // same 9-cell
                int start_i = row / 3 * 3;
                int start_j = col / 3 * 3;
                for (int i = start_i; i < start_i + 3; i++) {
                    for (int j = start_j; j < start_j + 3; j++) {
                        if (datasource[i][j] != 0) {
                            candidates[datasource[i][j]] = -1;
                        }
                    }
                }

                // init candid ptr
                resetCandid();
            }

            protected int getCurrCandid() {  //  [1-9] or -1
                if (isValidCandid()) {
                    return value;
                }
                return -1;
            }

            private void resetCandid() {
                // to left most 0
                int i = 1;
                for (; i < 10; i++) {
                    if (candidates[i] == 0) {
                        break;
                    }
                }
                value = i;  // 1..9 or 10
            }

            private void nextCandid() {
                int i = value + 1;
                while (i < 10 && candidates[i] != 0) {
                    i++;
                }
                value = i; // 1..9 or 10,11,...
            }

            private void excludeCandidate(Cell by) {
                int their = by.getCurrCandid();
                if (candidates[their] == 0) {
                    int theirIdx = by.row * 9 + by.col + 1;
                    // same row
                    if (by.row == row) {
                        candidates[their] = theirIdx;
                    }
                    // same col
                    if (by.col == col) {
                        candidates[their] = theirIdx;
                    }
                    // same cell
                    if (by.row / 3 * 3 == row / 3 * 3 && by.col / 3 * 3 == col / 3 * 3) {
                        candidates[their] = theirIdx;
                    }
                }
                if (!isValidCandid()) {
                    nextCandid();
                }
            }

            private void enableCandidate(Cell by) {
                int their = by.getCurrCandid();  // must exist
                int theirIdx = by.row * 9 + by.col + 1;
                if (candidates[their] > 0 && candidates[their] == theirIdx) {  // result from their
                    candidates[their] = 0;   // >0 -> 0
                    if (value >= their) {
                        resetCandid();     // *
                    }
                }

            }

            private int numOfCandidate() {
                int num = 0;
                for (int i = 1; i < 10; i++) {
                    if (candidates[i] == 0) {
                        num++;
                    }
                }
                return num;
            }

            private boolean isValidCandid() {
                if (value < 1 || value > 9) {
                    return false;
                }
                return candidates[value] == 0;
            }

            public String toString() {
                return String.format("%d,%d  cptr:%d(%b)  (%d)candids:%s\n", row, col, value, isValidCandid(), numOfCandidate(), Arrays.toString(candidates));
            }
        }
        // >> STRUCT

    }
}
Abra
  • 19,142
  • 7
  • 29
  • 41
MadProgrammer
  • 343,457
  • 22
  • 230
  • 366