一、題目

數獨謎題使用 9×9 的網格，其中每一列和每一行以及每 3×3 子網格中的每
一個子網格必須包含所有數字 1···9， 圖 1 給出了一個有效的數獨游戲示例，
這個專案包括設計多執行緒應用程式來確定數獨謎題的解決是否有效，
這個多執行緒應用程式有幾種不同的設計，一種建議的策略是創建檢查以下條
件的執行緒：

• 一個執行緒，檢查每列包含數字 1 到 9
• 一個執行緒，檢查每行包含數字 1 到 9
• ９個執行緒來檢查 3×3 子網格中的每個子網格是否包含數字 1 到 9這總共創建 11 個單獨的執行緒，以驗證數獨謎題，但是，也可以為該專案創建更多執行緒，例如，不是創建一個執行緒來檢查９列，而是創建９個執行緒來分別檢查每列，
  

將引數傳給每個執行緒
父執行緒創建作業執行緒，向每個作業執行緒傳遞它在數獨網格中檢查的位置，這
一步需要向每個執行緒傳遞多個引數，最簡單的方法是：采用 struct 創建一個數
據結構，例如，為了執行緒的驗證，可用包括行和列的資料結構來傳遞引數，

/* structure for passing data to threads */ 
typedef struct
{
int row;
int column;
} parameters;
Pthreads 和 Windows 程式的作業執行緒創建類似如下代碼所示：
parameters *data = (parameters *) malloc(sizeof(parameters));
data->row = 1;
data->column = 1;
/* Now create the thread passing it data as a parameter */

指標 data 將被傳遞給執行緒創建函式 pthread create（（Pthreads）或CreateThread（）（Windows）函式，后者將把 data 作為引數傳遞到作為單獨執行緒運行的函式，
將結果回傳到父執行緒
每個作業執行緒都被分配了一項任務，即判定數獨謎題中特定區域的有效性，作業行程執行此檢查后，必須將其結果傳給父行程，處理這個問題的一個好方法是：創建一個對每個執行緒可見的整數值陣列，此陣列中的第 i 個索引對應于第 i個作業執行緒，如果一個作業執行緒將其對應的值設定為 1，則表示它的數獨謎題區域是有效的；為 0 的值表示無效，當所有作業執行緒完成后，父執行緒檢查結果陣列中的每項，確定數獨游戲是否有效，

二、設計思路

用Java的多執行緒來并發執行，利用了jdk中的CountDownLatch計數器和ThreadPoolExecutor執行緒池來解決問題，

思路：9個執行緒執行9個區塊的檢查，另外兩個分別負責行列的檢查，同時將這些操作放入到執行緒池，并利用CountDownLatch來統計執行緒的情況，當所有執行緒完成時，主執行緒mian輸出結果陣列，

三、代碼

這里判斷時我用了一個小技巧來加快檢查效率，即利用flag陣列存放某個數字被標記的次數，如果此次檢查時，該數字i對應的flag[i]中標記次數等于輪數+1，則表示在該輪檢查中，已經被標記過了一次，此次又遇到，說明此輪中存在兩個相同數字，與規則相悖，直接記錄結果，回傳即可（別忘了把計數器減一表示執行緒已經結束），

package com.dreamchaser.concurrent;

import java.util.Arrays;
import java.util.concurrent.*;

/**
 * @author 金昊霖
 */
public class Main {
    public static void main(String[] args) {
        // 執行緒數
        final int THREAD_POOL_SIZE = 11;
        //0-8表示9個區塊，9,10表示行，列檢查，值為0則通過，1表示不通過
        int [] result=new int[11];
        int [][]numbers={
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
                {6,2,4,5,3,9,1,8,7},
        };
        //一次性計數器，用于協調多執行緒，這里的主要目的在于等待所有執行緒結束再輸出結果
        final  CountDownLatch countDown = new CountDownLatch(11);

        // 創建執行緒池，其中任務佇列需要結合實際情況設定合理的容量
        ThreadPoolExecutor executor = new ThreadPoolExecutor(THREAD_POOL_SIZE,
                THREAD_POOL_SIZE,
                0L,
                TimeUnit.MILLISECONDS,
                new LinkedBlockingQueue<>(1024),
                new ThreadPoolExecutor.AbortPolicy());
        executor.execute(new Runnable() {
            //檢查行
            @Override
            public void run() {
                int [] flag=new int[9];
                for (int i=0;i<9;i++){
                    for (int j=0;j<9;j++){
                        //如果是i+1則說明不符合條件,標記并退出即可
                        if (flag[numbers[i][j]-1]==i+1){
                            result[9]=1;
                            countDown.countDown();
                            return;
                        }
                        flag[numbers[i][j]-1]++;
                    }
                }
                countDown.countDown();
            }
        });
        executor.execute(new Runnable() {
            //檢查列
            @Override
            public void run() {
                int [] flag=new int[9];
                for (int i=0;i<9;i++){
                    for (int j=0;j<9;j++){
                        //如果是i+1則說明不符合條件,標記并退出即可
                        if (flag[numbers[j][i]-1]==i+1){
                            result[9]=1;
                            countDown.countDown();
                            return;
                        }
                        flag[numbers[j][i]-1]++;
                    }
                }
                countDown.countDown();
            }
        });
        for (int i=0;i<9;i+=3){
            for (int j=0;j<9;j+=3){
                executor.execute(new Check(i,j,result,numbers,countDown));
            }
        }
        System.out.println("未等待所有執行緒結束的結果："+Arrays.toString(result));
        try {
            //等待其他所有執行緒結束
            countDown.await();
        } catch (InterruptedException e) {
            e.printStackTrace();
        }
        System.out.println("所有執行緒結束后的結果："+Arrays.toString(result));

    }

}

/**
 * 執行緒類，用于檢查9個區塊
 */
class Check implements Runnable{
    int i;
    int j;
    int[] result;
    int[][] numbers;
    CountDownLatch countDownLatch;

    public Check(int i, int j, int[] result, int[][] numbers,CountDownLatch countDownLatch) {
        this.i = i;
        this.j = j;
        this.result = result;
        this.numbers = numbers;
        this.countDownLatch=countDownLatch;
    }

    @Override
    public void run() {
        int [] flag=new int[9];
        for (int x=i;x<i+3;x++){
            for (int y=j;y<j+3;j++){
                if (flag[numbers[x][y]-1]==1){
                    result[i+j/3]=1;
                    countDownLatch.countDown();
                    return;
                }
                flag[numbers[x][y]-1]++;
            }
        }
        countDownLatch.countDown();
    }
}

四、總結

我之前其實自學過Java多執行緒的知識，可現在實際用起來還是得重新回去查資料，看來看一遍只是說我了解了這個知識，甚至只是知道這個知識，至于如何去用還需多多實踐，只有在不斷實踐中才能理解掌握，