Хорошая задачка 
Решение ниже 
Зачем выносить на удаленные машины то, что локально делается на 10-30ms 
| Код |
public final class SudokuSolver extends AbstractBlocksTask {
private static final int[][] TASK_BLOCKS_MAP =
new int[][]{
{0, 1, 2, 3, 6}, {1, 0, 2, 4, 7}, {2, 0, 1, 5, 8},
{3, 4, 5, 0, 6}, {4, 3, 5, 1, 7}, {5, 3, 4, 2, 8},
{6, 7, 8, 0, 3}, {7, 6, 8, 1, 4}, {8, 6, 7, 2, 5},
};
public SudokuSolver(final Block[] blocks) {
super(blocks); // 9
if (blocks == null || blocks.length != 9) {
throw new IllegalArgumentException();
}
}
public static void main(final String[] args) {
final long st = System.currentTimeMillis();
final Block[] blocks = new Block[]{
Block.buildBlock(5, 3, 0, 6, 0, 0, 0, 9, 8),
Block.buildBlock(0, 7, 0, 1, 9, 5, 0, 0, 0),
Block.buildBlock(0, 0, 0, 0, 0, 0, 0, 6, 0),
Block.buildBlock(8, 0, 0, 4, 0, 0, 7, 0, 0),
Block.buildBlock(0, 6, 0, 8, 0, 3, 0, 2, 0),
Block.buildBlock(0, 0, 3, 0, 0, 1, 0, 0, 6),
Block.buildBlock(0, 6, 0, 0, 0, 0, 0, 0, 0),
Block.buildBlock(0, 0, 0, 4, 1, 9, 0, 8, 0),
Block.buildBlock(2, 8, 0, 0, 0, 5, 0, 7, 9),
};
final SudokuSolver sudokuSolver = new SudokuSolver(blocks);
final int result = sudokuSolver.process();
if (result == 162) {
sudokuSolver.printResult();
System.out.println("Solved, processing time is " + (System.currentTimeMillis()-st) + " ms");
} else {
System.out.println("Error, result = " + result);
}
}
private void printResult() {
for (Block block : blocks) System.out.println(block);
}
protected void calculate() {
final Task[] tasks = new Task[9];
for (int i = 0; i < tasks.length; i++) {
tasks[i] = new Task(new Block[]{blocks[TASK_BLOCKS_MAP[i][0]],
blocks[TASK_BLOCKS_MAP[i][1]], blocks[TASK_BLOCKS_MAP[i][2]],
blocks[TASK_BLOCKS_MAP[i][3]], blocks[TASK_BLOCKS_MAP[i][4]]});
}
for (Task task : tasks) task.process();
for (int i = 0; i < tasks.length; i++) {
final Task task = tasks[i];
for (int k = 0; k < 5; k++) {
final Block[] resultblocks = task.getBlocks();
blocks[TASK_BLOCKS_MAP[i][k]].merge(resultblocks[k]);
}
}
}
}
abstract class AbstractBlocksTask {
Block[] blocks; //0-current; 1,2 - goriz ; 3,4 -vert
protected AbstractBlocksTask(final Block[] blocks) {
this.blocks = blocks;
}
public int process() {
int prevCheckSum = sumCheckSums();
int curCheckSum = 0;
while (curCheckSum != prevCheckSum) {
if (curCheckSum > 0) prevCheckSum = curCheckSum;
calculate();
curCheckSum = sumCheckSums();
}
return curCheckSum;
}
protected abstract void calculate();
private int sumCheckSums() {
int checkSum = 0;
for (int i = 0; i < blocks.length; i++) checkSum += blocks[i].checkSum();
return checkSum;
}
public final Block[] getBlocks() {
return blocks;
}
}
final class Block {
private final byte[] locs;
public static final int GORIZONTAL_MASK = 0x38;// 111000
public static final int VERTICAL_MASK = 0x7;// 000111
private static final int[] LINE_MASKS = new int[]{0x1, 0x2, 0x4, 0x8, 0x10, 0x20};
private static final int[] HELP_LINE_MASKS = new int[]{0x38, 0x38, 0x38, 0x7, 0x7, 0x7,};
protected Block(final byte[] locs) {
this.locs = locs;
for (int i = 0; i < locs.length; i++) {
if (locs[i] == 0) locs[i] = 0x3f;
}
}
public final boolean isFull() {
boolean b = true;
for (int i = 0; b && i < locs.length; i++) b = b && isDefined(locs[i]);
return b;
}
public static boolean isDefined(final int loc) {
return bitSum(loc & 0x7) == 1 && bitSum(loc & 0x38) == 1;
}
private static int bitSum(final int loc) {
int r = 0;
for (int i = 0; i < 6; i++) r += (loc >> i) & 1;
return r;
}
public String toString() {
final byte[] bytes = new byte[9];
for (int i = 0; i < locs.length; i++) {
if (isDefined(locs[i])) {
bytes[((locs[i] & 0x38) >> 4) * 3 + ((locs[i] & 0x7) >> 1)] = (byte) (i + 1);
}
}
String s = "";
for (int i = 0; i < bytes.length; i++) {
s += bytes[i];
if (((i + 1) % 3) == 0) s += "\n";
}
return s;
}
// to test
byte getLoc(final int num) {
return locs[num - 1];
}
public int checkSum() {
int sum = 0;
for (int i = 0; i < locs.length; i++) sum += bitSum(locs[i]);
return sum;
}
public static Block buildBlock(final int... nums) {
final byte[] locs = new byte[9];
for (int i = 0; i < nums.length; i++) {
if (nums[i] > 0) {
locs[nums[i] - 1] = (byte) ((((i % 3 == 0 ? 1 : ((i % 3) << 1)) | ((i / 3 == 0 ? 1 : (i / 3 << 1)) << 3))));
}
}
return new Block(locs);
}
public static void intersect(final int mask, final Block... blocks) {
for (int k = 0; k < blocks.length; k++) {
final Block b1 = blocks[k];
for (Block b2 : blocks) {
if (b1 != b2) {
for (int i = 0; i < 9; i++) {
if (bitSum(b2.locs[i] & mask) == 1) {
b1.locs[i] = (byte) (~(b2.locs[i] & mask) & b1.locs[i]);
} else if (bitSum(b1.locs[i] & mask) == 1) {
b2.locs[i] = (byte) (~(b1.locs[i] & mask) & b2.locs[i]);
}
}
}
}
}
for (Block b1 : blocks) b1.fillLine();
}
private void fillLine() {
for (int i = 0; i < LINE_MASKS.length; i++) {
final int lineMask = LINE_MASKS[i];
final int[] alts = new int[9];
final int altCounter = fillAlts(lineMask, alts);
processAlts(i, altCounter, alts);
}
}
private int fillAlts(final int lineMask, final int[] alts) {
int altCounter = 0;
for (int k = 0; k < locs.length; k++) {
if (bitSum(locs[k] & lineMask) == 1) {
alts[altCounter] = k;
altCounter++;
}
}
return altCounter;
}
private void processAlts(final int lineIndex, final int altCounter, final int[] alts) {
final int[] defined = new int[9];
int defCounter = 0;
final int[] undefineds = new int[2];
undefineds[0] = -1;
for (int k = 0; k < alts.length && k < altCounter; k++) {
if (isDefined(locs[alts[k]])) {
defined[defCounter] = alts[k];
defCounter++;
} else {
undefineds[undefineds[0] == -1 ? 0 : 1] = alts[k];
}
}
if (altCounter == 3) {
if (defCounter == 2) {
locs[undefineds[0]] = (byte) (LINE_MASKS[lineIndex] | (HELP_LINE_MASKS[lineIndex] ^ locs[defined[0]] ^ locs[defined[1]]));
} else if (defCounter == 1) {
final int undefIndex = bitSum(locs[undefineds[0]] & HELP_LINE_MASKS[lineIndex]) == 2 ? 0 : 1;
locs[undefineds[undefIndex]] = (byte) (LINE_MASKS[lineIndex] |
((locs[undefineds[undefIndex]] ^ locs[defined[0]]) & HELP_LINE_MASKS[lineIndex]));
}
} else if (defCounter == 3) {
for (int i = 0; i < locs.length; i++) {
if (!isDefined(locs[i])) locs[i] = (byte) (locs[i] & ~LINE_MASKS[lineIndex]);
}
}
}
public boolean isSolved(final int num) {
return isDefined(locs[num - 1]);
}
public void merge(final Block b2) {
for (int i = 0; i < locs.length; i++) locs[i] = (byte) (locs[i] & b2.locs[i]);
}
}
final class Task extends AbstractBlocksTask {
public Task(final Block[] blocks) {
super(blocks); //0-current; 1,2 - goriz ; 3,4 -vert
}
protected void calculate() {
Block.intersect(Block.GORIZONTAL_MASK, blocks[0], blocks[1], blocks[2]);
Block.intersect(Block.VERTICAL_MASK, blocks[0], blocks[3], blocks[4]);
}
}
|
zone51, с тебя причитается ;) |
