Sudoku solver using multi threading

Question

I have implemented a sudoku solver using backtracking but I have performance issues, the main problem is with isAvailable() function which checks if the number is valid for the current position. The execution time without using threads takes 61ms :

protected boolean flag;

public boolean isAvailable(int sudoku[][], int row, int col, int num){
    flag = true;

    int rowStart = (row / 3) * 3;
    int colStart = (col / 3) * 3;

    for (int i = 0; i < 9; ++i) {
        if (sudoku[row][i] == num) {
            flag = false;
        }
    }

    for (int i = 0; i < 9; ++i) {
        if (sudoku[i][col] == num) {
            flag = false;
        }
    }

    for (int i = rowStart; i < (rowStart + 3); ++i) {
        for (int j = colStart; j < (colStart + 3); ++j) {
            if (sudoku[i][j] == num)
                flag = false;
        }
    }

    return flag;
}

Result :

Answer found
Time elapsed = 61.63ms
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

But if I use different threads one for checking row another for checking column and another for box I expected a lower execution time but it took around 312s

protected boolean flag;

public boolean isAvailable(int sudoku[][], int row, int col, int num) throws InterruptedException {
    flag = true;

    int rowStart = (row / 3) * 3;
    int colStart = (col / 3) * 3;

    Thread t1 = new Thread(new Runnable() {
        public void run() {
            for (int i = 0; i < 9; ++i) {
                if (sudoku[row][i] == num) {
                    flag = false;
                }
            }
        }

    });
    t1.start();

    Thread t2 = new Thread(new Runnable() {
        public void run() {
            for (int i = 0; i < 9; ++i) {
                if (sudoku[i][col] == num) {
                    flag = false;
                }
            }
        }

    });
    t2.start();


    Thread t3 = new Thread(new Runnable() {
        public void run() {
            for (int i = rowStart; i < (rowStart + 3); ++i) {
                for (int j = colStart; j < (colStart + 3); ++j) {
                    if (sudoku[i][j] == num)
                        flag = false;
                }
            }
        }
    });
    t3.start();

    t1.join();
    t2.join();
    t3.join();

    return flag;
}

Result :

Answer found
Time elapsed = 312514.63ms
8 1 2 7 5 3 6 4 9 
9 4 3 6 8 2 1 7 5 
6 7 5 4 9 1 2 8 3 
1 5 4 2 3 7 8 9 6 
3 6 9 8 4 5 7 2 1 
2 8 7 1 6 9 5 3 4 
5 2 1 9 7 4 3 6 8 
4 3 8 5 2 6 9 1 7 
7 9 6 3 1 8 4 5 2

If you need my full code :

import java.text.DecimalFormat;

public class Main {

    public static void main(String[] args){

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

        Main m = new Main();
        long starttime = System.nanoTime();
        boolean k = m.fillsudoku(sudoku, 0, 0);
        long endtime = System.nanoTime();

        DecimalFormat df = new DecimalFormat("#.##");

        if (k) {
            System.out.println("Answer found");
            System.out.println("Time elapsed = " + df.format((double) (endtime - starttime) / 1000000) + "ms");
            for (int i = 0; i < 9; i++) {
                for (int j = 0; j < 9; j++) {
                    System.out.print(sudoku[i][j] + " ");
                }
                System.out.println();
            }
        } else {
            System.out.println("Not found");
        }
    }

    public boolean fillsudoku(int sudoku[][], int row, int col){
        if(row < 9){
            if(sudoku[row][col] != 0){
                if(col < 8){
                    return fillsudoku(sudoku, row, col+1);
                }
                else if(row < 8){
                    return fillsudoku(sudoku, row+1, 0);
                }
                return true;
            }
            else{
                for(int i=1;i<=9;i++){
                    if(isAvailable(sudoku, row, col, i)){        // <- checking function
                        sudoku[row][col] = i;
                        if(col == 8){
                            if(fillsudoku(sudoku, row+1, 0)){
                                return true;
                            }
                        }
                        else{
                            if(fillsudoku(sudoku, row, col+1)){
                                return true;
                            }
                        }
                        sudoku[row][col] = 0;
                    }
                }
                return false;
            }
        }
        return true;
    }
    protected boolean flag;

    public boolean isAvailable(int sudoku[][], int row, int col, int num){
    ........
    ........
    }
}

How can i improve the performance using threading, any suggestions, am i thinking correctly.

You could start by replacing all the `flag = false;` with `return false;` — Maurice Perry, Feb 20 '18 at 10:13
What is done in method `isAvailable` looks very simple, and I doubt that it takes more time than creating a thread. — Maurice Perry, Feb 20 '18 at 10:19
Always worth a read in this context: https://stackoverflow.com/questions/504103/how-do-i-write-a-correct-micro-benchmark-in-java — reto, Feb 20 '18 at 10:23
@MauricePerry Just forgot that was int and not double... Anyway, creating Threads are costly. You're creating 3 of them for a short live time, that could be a start of explanation. (cf https://stackoverflow.com/questions/5483047/why-is-creating-a-thread-said-to-be-expensive) — Kapcash, Feb 20 '18 at 10:37
It’s slow because you’re creating and starting entire threads for 9 iterations in a loop. The overhead of that is staggering (5000x slower). There is no place for using threads *inside* the extremely fast method ‘isAvailable’, it only slows things down. — Erwin Bolwidt, Feb 20 '18 at 10:38

Andrew Tobilko · Accepted Answer · 2018-02-20T21:31:52.667

Unfortunately, you won't get any benefits from multithreading here.
Creating 3 threads per method invocation is more costly than running 3 simple loops consecutively.
27 check-and-reassignment iterations are not worth to be parallelised, really.

Speaking of improvement, we could rewrite the method by using a thread pool with ExecutorService. I tried it, here are the results:

54.25ms     // your plain version
65397.06ms  // your multithreading version
5500.82ms   // ExecutorService version

I have simply transformed the Thread variables into Runnable ones, passed them to ExecutorService#submit and called Future#get:

Runnable r1 = () -> { ... };
// other Runnables

final Future<?> f1 = executorService.submit(r1);
// other Futures

try {
    f1.get();
    // other gets
} catch (ExecutionException e) { ... }

score 1 · Answer 2 · answered Feb 21 '18 at 18:06

You can use threads efficiently, but not by letting them to do such tiny pieces of work. You're trying multiple i for a single field sequentially, and that's the perfect place for parallelization. Note that you have to deep clone the sudoku array so that your threads won't step on each other. A speedup close to the number of CPU's is easily achievable this way.

Sudoku solver using multi threading

2 Answers2