一、题目
数独谜题使用 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;y++){ if (flag[numbers[x][y]-1]==1){ result[i+j/3]=1; countDownLatch.countDown(); return; } flag[numbers[x][y]-1]++; } } countDownLatch.countDown(); } }
四、总结
我之前其实自学过Java多线程的知识，可现在实际用起来还是得重新回去查资料，看来看一遍只是说我了解了这个知识，甚至只是知道这个知识，至于如何去用还需多多实践，只有在不断实践中才能理解掌握。
