sudoku-java

view src/au/id/mcleish/sudoku/SudokuThreadManager.java @ 27:54ad63e1537c

Added breath-first-search option... which might not be useful.
author David McLeish <dave@mcleish.id.au>
date Fri Nov 12 08:32:03 2010 +1100 (2010-11-12)
parents c1e69a593067
children
line source
1 package au.id.mcleish.sudoku;
3 import java.util.Collection;
4 import java.util.Collections;
5 import java.util.List;
6 import java.util.concurrent.BlockingQueue;
7 import java.util.concurrent.PriorityBlockingQueue;
8 import java.util.concurrent.SynchronousQueue;
9 import java.util.concurrent.ThreadPoolExecutor;
10 import java.util.concurrent.TimeUnit;
11 import java.util.concurrent.atomic.AtomicInteger;
13 public final class SudokuThreadManager {
14 private int poolSize;
16 public SudokuThreadManager(int poolSize) {
17 this.poolSize = poolSize;
18 }
20 public void setPoolSize(int poolSize) {
21 this.poolSize = poolSize;
22 }
24 public SudokuGrid solve(SudokuGrid grid) {
25 return solve(Collections.singleton(grid));
26 }
28 public SudokuGrid solve(Collection<SudokuGrid> grids) {
29 return solve(grids, true);
30 }
32 public SudokuGrid solveBreadthFirst(Collection<SudokuGrid> grids) {
33 return solve(grids, false);
34 }
36 public SudokuGrid solve(Collection<SudokuGrid> grids, boolean depthFirst) {
37 BlockingQueue<Runnable> queue = new PriorityBlockingQueue<Runnable>();
38 ThreadPoolExecutor pool = new ThreadPoolExecutor(poolSize, poolSize, 0, TimeUnit.SECONDS, queue);
39 SynchronousQueue<SudokuGrid> solutionQueue = new SynchronousQueue<SudokuGrid>();
40 AtomicInteger activeCount = new AtomicInteger(grids.size());
42 for (SudokuGrid grid : grids)
43 pool.execute(new SolveTask(grid, pool, solutionQueue, activeCount, depthFirst));
45 SudokuGrid solution = null;
46 try {
47 solution = solutionQueue.take();
48 } catch (InterruptedException e) {
49 e.printStackTrace();
50 }
52 pool.shutdownNow();
54 pool = null;
55 queue = null;
56 solutionQueue = null;
57 activeCount = null;
59 if (solution.numEmpty() != 0)
60 solution = null;
62 return solution;
63 }
65 private static class SolveTask implements Runnable, Comparable<SolveTask> {
66 private final SudokuGrid grid;
67 private final int priority;
68 private final ThreadPoolExecutor pool;
69 private final SynchronousQueue<SudokuGrid> solutionQueue;
70 private final AtomicInteger activeCount;
71 private final boolean depthFirst;
73 public SolveTask(SudokuGrid grid, ThreadPoolExecutor pool,
74 SynchronousQueue<SudokuGrid> solutionQueue, AtomicInteger activeCount,
75 boolean depthFirst) {
76 this.grid = grid;
77 this.pool = pool;
78 this.solutionQueue = solutionQueue;
79 this.activeCount = activeCount;
80 this.depthFirst = depthFirst;
81 this.priority = grid.numEmpty();
82 }
84 @Override
85 public void run() {
86 List<SudokuGrid> branches = grid.partialSolutionBranches();
87 if (branches == null) {
88 if (grid.numEmpty() == 0) {
89 // Solution found
90 try {
91 solutionQueue.put(grid);
92 } catch (InterruptedException e) {
93 // To be expected.
94 }
95 }
96 } else {
97 for (SudokuGrid grid : branches) {
98 SolveTask task = new SolveTask(grid, pool, solutionQueue, activeCount, depthFirst);
99 activeCount.incrementAndGet();
100 try {
101 pool.execute(task);
102 } catch (Exception e) {
103 activeCount.decrementAndGet();
104 }
105 }
106 }
107 int count = activeCount.decrementAndGet();
108 if (count == 0) {
109 // Close the door on your way out.
110 try {
111 // Return closest attempt. Caller should check that
112 // numEmpty() is 0 before treating this as a valid
113 // solution.
114 solutionQueue.put(grid);
115 } catch (InterruptedException e) {
116 //e.printStackTrace();
117 }
118 }
119 }
121 @Override
122 public int compareTo(SolveTask other) {
123 if (depthFirst)
124 return priority - other.priority;
125 else
126 return other.priority - priority;
127 }
128 }
130 public static void main(String[] args) {
131 SudokuGrid grid = SudokuGrid.newPuzzle(4, 4);
132 SudokuThreadManager threads = new SudokuThreadManager(4);
133 SudokuGrid solution = threads.solve(grid);
134 System.out.println(solution);
135 }
136 }