Gui 可视化递归回溯数独

Question

我不久前写了一个 class 来使用递归回溯解决一个数独游戏 - 它按预期工作。

现在我想一步步可视化这个算法。我基本上想看看算法把哪个数字放在哪里，什么时候回溯。

我编写了所有必要的函数并实现了一个基本的图形用户界面，它已经在我的图形用户界面中调用并显示了我的数独求解器（在你启动它之后，一旦你想开始求解就按一个随机键）。

现在我的问题是我想查看算法的每一步 - 在 SudokuSolver.solve() 函数中查看更多信息。

虽然我的 SudokuSlver.setGui() 函数在回溯期间被调用，但目前我只在整个回溯完成后更新我的 gui。

这也是我使用“Thread.sleep()”和“TimeUnit”“减慢”算法失败的原因。

Github

代码Gui.java

import java.util.ArrayList;
import java.util.concurrent.*;

import javafx.application.Application;
import javafx.event.EventHandler;
import javafx.scene.Scene;
import javafx.scene.input.KeyEvent;
import javafx.scene.shape.*;
import javafx.scene.text.Text;
import javafx.scene.text.TextBoundsType;
import javafx.scene.layout.Pane;
import javafx.stage.Stage;
import javafx.scene.paint.*;

public class Gui extends Application{
    

    static ArrayList<Rectangle> rects = new ArrayList<>();
    static ArrayList<Text> texts = new ArrayList<>();

    @Override
    public void start(Stage stage) {

        Pane pane = new Pane();
        Scene scene = new Scene(pane, 297, 297);
        

        createBoard();

        
        for (int box = 0; box < rects.size(); box++) {
            pane.getChildren().addAll(rects.get(box), texts.get(box));
        }


        scene.setOnKeyPressed(new EventHandler<KeyEvent>(){
            
            public void handle(final KeyEvent keyEvent){
                System.out.println("event triggered");
                handleEvent(keyEvent);
            }
            
        });


        stage.setTitle("SudokuSolver");
        stage.setScene(scene);
        stage.show();
        
    }

    public void handleEvent(KeyEvent key){
        System.out.println("event triggered");
        callSudokuSolver();
    }

    public void createBoard(){
        for (int x = 0; x < 288; x+=32) {
            for (int y = 0; y < 288; y+=32) {

                Rectangle r = new Rectangle(x, y, 32, 32);
                Text   text   = createText("0");
                text.setX(x);
                text.setY(y+32);
                r.setFill(Color.WHITE);
                r.setStroke(Color.BLACK);
                r.setOpacity(0.5);
                

                rects.add(r);
                texts.add(text);
            }
        }
    }
    
    public static void setTextOfRect(String s, int pos){
        texts.get(pos).setText(s);
    }

    public static void setColorOfRect(Color col, int pos){
        rects.get(pos).setFill(col);
    }

    private Text createText(String string) {
        Text text = new Text(string);
        text.setBoundsType(TextBoundsType.VISUAL);
        text.setStyle(
                "-fx-font-family: \"Times New Roman\";" +
                "-fx-font-size: 16px;"
        );

        return text;
    }

    private void callSudokuSolver(){
        //test
        int[][] board =
        {{2,0,5,0,0,0,0,0,0},
        {3,0,8,6,0,0,9,0,0},
        {0,0,0,1,0,0,4,0,0},
        {0,0,0,0,5,0,0,1,0},
        {0,0,0,0,9,0,0,2,0},
        {8,7,0,0,2,0,0,0,0},
        {0,0,0,0,8,9,0,0,3},
        {0,0,6,0,0,3,0,0,5},
        {5,0,4,0,0,0,0,0,1}};
        
        
        SudokuSolver sudokuSolver = new SudokuSolver();
        
        if(!sudokuSolver.startSolving(board)){
            System.out.println("No solution");
        }else{
            System.out.println("Solved");
        }
    }


    public static void main(String[] args) throws Exception {
        launch();
    }

    
}

代码SudokuSolver.java

import javafx.scene.paint.*;

public class SudokuSolver {

    private boolean solve(int[][] board, int counter){


        int col = counter / board.length;
        int row = counter % board.length;

        if (col >= board.length){
            return true;
        }

        if (board[row][col] == 0) {

        for (int n = 1; n <= board.length; n++) {

            if (isValid(n,row,col, board)){
                board[row][col] = n;
                setGui(false, counter, n);

                if (solve(board,counter+1)){
                    return true;
                }

            }
            board[row][col] = 0;
            setGui(true, counter, n);

        }
        }else{
            setGui(false, counter, board[row][col]);
            return solve(board, counter + 1);
        }

        return false;
    }

    public boolean startSolving(int[][] board){

        if(!solve(board, 0)){
            return false;
        }else{
            return true;
        }
    }

    private boolean isValid(int n, int row, int col, int[][] board){

        int i;

        for (i = 0; i < board.length; i++) {
            if(board[row][i] == n){
                return false;
            }
        }

        for (i = 0; i < board.length; i++) {
            if(board[i][col] == n){
                return false;
            }
        }

        //check if block is valid

        final int blockRow = 3 * (row / 3);
        final int blockCol = 3 * (col / 3);
        return isBlockValid(n, board, blockRow, blockRow + 2, blockCol, blockCol + 2);
    }

    private boolean isBlockValid(int n, int[][] board, int starti, int stopi, int startj, int stopj){

        for (int i = starti; i <= stopi; i++) {

            for (int j = startj; j <= stopj; j++) {

                if (board[i][j] == n) {
                    return false;
                }
            }
        }

        return true;
    }

    private void printBoard(int[][] board){

        System.out.println();

        for (int[] row : board){
            System.out.print("|");
            for (int col : row){
                System.out.print(col);
                System.out.print("|");
            }
            System.out.println();
        }
        System.out.println();
    }

    private void setGui(boolean wrong, int pos, int number){
        String s = Integer.toString(number);
        Color color = Color.GREEN;
        if(wrong){
            color = Color.RED;
        }
        Gui.setColorOfRect(color, pos);
        Gui.setTextOfRect(s, pos);
    }


}

Answer 1

解决了我的问题。

有必要在另一个线程中打开我的 sodokusolver，然后运行使用 Platform.runLater() (@tevemadar) 的 gui 命令。

new Thread() {
        public void run() {
            SudokuSolver sudokuSolver = new SudokuSolver();
            sudokuSolver.startSolving(board);
        }
    }.start();

之后我用它来“减慢”我的算法。

try {
        Thread.sleep(10);
    } catch (Exception e) {
        //TODO: handle exception
    }

Gui 可视化递归回溯数独

Gui to visualize recursive backtracking sudoku

java

user-interface

javafx

backtracking