function [solution,s] = solver(puzzle,list)
rand('seed',1);
list=list(:,end:-1:1);
global h iX iN col_selection blockmap rowmap colmap;
h = [1 4 7 28 31 34 55 58 61
2 5 8 29 32 35 56 59 62
3 6 9 30 33 36 57 60 63
10 13 16 37 40 43 64 67 70
11 14 17 38 41 44 65 68 71
12 15 18 39 42 45 66 69 72
19 22 25 46 49 52 73 76 79
20 23 26 47 50 53 74 77 80
21 24 27 48 51 54 75 78 81];
h1 =[ 1 10 19 28 37 46 55 64 73
2 11 20 29 38 47 56 65 74
3 12 21 30 39 48 57 66 75
4 13 22 31 40 49 58 67 76
5 14 23 32 41 50 59 68 77
6 15 24 33 42 51 60 69 78
7 16 25 34 43 52 61 70 79
8 17 26 35 44 53 62 71 80
9 18 27 36 45 54 63 72 81];
iX = uint8([h h1 h1']);
iN = [3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2 1 2 2 3 3 3 3 3 3
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2 2 1 2 3 3 3 3 3 3
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2 2 2 1 3 3 3 3 3 3
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2 3 3 3 1 2 2 3 3 3
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2 3 3 3 2 1 2 3 3 3
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2 3 3 3 2 2 1 3 3 3
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1 3 3 3 3 3 3 1 2 2
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1 3 3 3 3 3 3 2 1 2
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3 3 3 3 3 3 3 2 2 1
2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 3 1 1 2 2 2 2 2 2
3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 1 3 1 2 2 2 2 2 2
3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 1 1 3 2 2 2 2 2 2
3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 3 3 3 2 2 2 3 1 1 2 2 2
3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 3 3 3 2 2 2 1 3 1 2 2 2
3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 3 3 3 2 2 2 1 1 3 2 2 2
3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 1 2 2 3 3 3 3 3 3 1 2 2 2 2 2 2 2 2 3 1 1
3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 2 1 2 3 3 3 3 3 3 2 1 2 2 2 2 2 2 2 1 3 1
3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 3 3 2 3 3 3 3 3 3 2 2 1 3 3 3 3 3 3 2 2 1 2 2 2 2 2 2 1 1 3];
col_selection = [[4 5 6 7 8 9];[7 8 9 7 8 9]];
blockmap=[1 1 1 4 4 4 7 7 7
1 1 1 4 4 4 7 7 7
1 1 1 4 4 4 7 7 7
2 2 2 5 5 5 8 8 8
2 2 2 5 5 5 8 8 8
2 2 2 5 5 5 8 8 8
3 3 3 6 6 6 9 9 9
3 3 3 6 6 6 9 9 9
3 3 3 6 6 6 9 9 9];
rowmap = [1 1 1 1 1 1 1 1 1
2 2 2 2 2 2 2 2 2
3 3 3 3 3 3 3 3 3
4 4 4 4 4 4 4 4 4
5 5 5 5 5 5 5 5 5
6 6 6 6 6 6 6 6 6
7 7 7 7 7 7 7 7 7
8 8 8 8 8 8 8 8 8
9 9 9 9 9 9 9 9 9];
colmap = [1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9
1 2 3 4 5 6 7 8 9];
[solution,s] =solverC(puzzle,list);
if floor(s) == 19
[sol2,s2] =solverC(puzzle(:,end:-1:1),list);
if s2<s
solution=sol2(:,end:-1:1);
s=s2;
end
end
if s > 200
[sol2,s2] =solverC(puzzle(end:-1:1,:),list);
if s2<s
solution=sol2(end:-1:1,:);
s=s2;
end
end
[solution1,s2] =improver3(puzzle,list,solution);
if s2<s
solution=solution1;
s=s2;
end
if s>100
[solution1,s2] =improver3(puzzle,list,solution);
if s2<s
solution=solution1;
end
end
flag=1;
while flag
[solution,flag]=improver4(puzzle,list,solution);
end;
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [solution,s] = solverC(puzzle,list)
NUMREPS = 25000;
NUMTRIES1 = 200;
NUMTRIES2 = 200;
NUMTRIES3 = 300;
global h iX iN col_selection blockmap rowmap colmap;
free = puzzle==0;
q = uint8(find(free)');
missing = numel(q);
lq = missing;
list_count = numel(list);
listO=list;
NUMRUNS = (list_count / 10)+10;
% Calculate the average of all values available
total_puzzle = sum(sum(puzzle));
total_all = sum(list) + total_puzzle;
total_count = (81 - missing) + list_count;
average = total_all / total_count;
target = average*9;
bestscore2 = 1e10;
bestscore = 1e10;
reruns=0;
index1v = ceil(rand(1,NUMREPS)*lq);
index1v = q(index1v);
index2v = mod((index1v+uint8(floor(rand(1,NUMREPS)*(lq-1)))),lq)+1;
index2v = q(index2v);
id=1:9;
if target>600
idT=sum(free);
[tempT,id]=sort(idT,'descend');
end
while reruns<3
for run = 1:NUMRUNS
% Fill in values to optimize the rows
list = listO;
list_left = list_count;
solution = puzzle;
% Fill in values to optimize the rows
for r=id
%for r = 1:9
% Fill in values for all empty spaces in this row
for c = 1:9
if free(r,c)
list_index = ceil(rand*list_left);
solution(r,c) = list(list_index);
list(list_index)=[];
list_left = list_left-1;
end
end
list(end+1:list_count) = 1e10;
if list_left
% Get row as close as possible to
% target value
row_total = sum(solution(r,:)) - target;
est_error = abs(row_total);
tq = r + 9*(find(free(r,:))-1);
indv = tq(ceil(rand(NUMTRIES1,1)*numel(tq)));
rt = rand(NUMTRIES1,1);
for tries = 1:NUMTRIES1
ind = indv(tries);
list_index = ceil(rt(tries)*list_left);
list_value = list(list_index);
delta = list_value - solution(ind);
new_est_error = abs(row_total + delta);
if (new_est_error < est_error)
row_total = row_total + delta;
est_error = new_est_error;
list(list_index) = solution(ind);
solution(ind) = list_value;
end
end
end
end
target = sum(sum(solution)) *0.11111111111111111111111;
% Go about optimizing blocks without changing rows
cols_all_outside = 4:9;
block = sum(sum(solution(1:3,1:3)));
for tries = 1:NUMTRIES2
row = ceil(rand*3);
col_inside = ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
cols_all_outside = [7 8 9 7 8 9];
block = sum(sum(solution(1:3,4:6)));
for tries = 1:NUMTRIES2
row = ceil(rand*3);
col_inside = 3 + ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
cols_all_outside = 4:9;
block = sum(sum(solution(4:6,1:3)));
for tries = 1:NUMTRIES2
row = 3 + ceil(rand*3);
col_inside = ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
cols_all_outside = [7 8 9 7 8 9];
block = sum(sum(solution(4:6,4:6)));
for tries = 1:NUMTRIES2
row = 3 + ceil(rand*3);
col_inside = 3 + ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
cols_all_outside = 4:9;
block = sum(sum(solution(7:9,1:3)));
for tries = 1:NUMTRIES2
row = 6 + ceil(rand*3);
col_inside = ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
cols_all_outside = [7 8 9 7 8 9];
block = sum(sum(solution(7:9,4:6)));
for tries = 1:NUMTRIES2
row = 6 + ceil(rand*3);
col_inside = 3 + ceil(rand*3);
if free(row,col_inside)
col_outside = cols_all_outside(ceil(rand*6));
if free(row,col_outside)
val_inside = solution(row, col_inside);
val_outside = solution(row, col_outside);
new_block = block - val_inside + val_outside;
if abs(new_block - target) < abs(block - target)
solution(row,col_outside) = val_inside;
solution(row,col_inside) = val_outside;
block = new_block;
end
end
end
end
%Solve the columns without changing rows or blocks
col_total = sum(solution) - target;
for tries = 1:NUMTRIES3
el = q(ceil(rand*missing));
col = colmap(el);
row = el - 9*(col-1);
col_swap = ceil(rand*3) + (ceil(col/3)-1)*3;
if free(row,col_swap)
value_swap = solution(row,col_swap);
error = abs(col_total(col));
value = solution(row,col);
col_swap_total = col_total(col_swap);
col_total_new = col_total(col) + value_swap - value;
col_swap_total_new = col_swap_total + value - value_swap;
error_total_new = abs(col_total_new) + abs(col_swap_total_new);
if (error_total_new < error + abs(col_swap_total))
solution(el) = value_swap;
solution(row, col_swap) = value;
col_total(col_swap) = col_swap_total_new;
col_total(col) = col_total_new;
end
end
end
sums = sum(solution(iX));
score = sum(abs(sum(sums)*0.03703703703703703703-sums));
if score < bestscore
bestinit = solution;
bestscore = score;
bestlist = list;
end
solution = bestinit;
list = bestlist;
sTemp = sum(solution);
target = sum(sTemp) *0.11111111111111111111111;
rowtotals = sum(solution,2)';
coltotals = sTemp;
blocktotals = sum(solution(h));
if list_left ~= 0
rep = 0;
for repl = 1:5000 % blimey! loop unroll! (drumroll?)
target3=target*3; %constant for loop 0-3
% ----- loop 0, do the first thing (loops 0-3 are the same)
rep = rep + 1;
index1 = index1v(rep); index2 = index2v(rep);
index1r = rowmap(index1); index2r = rowmap(index2);
index1c = colmap(index1); index2c = colmap(index2);
value1 = solution(index1); value2 = solution(index2);
block1i = blockmap(index1);block2i = blockmap(index2);
valdiff = value1-value2;
nvd=iN(index1,index2)*valdiff;
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i) - target3;
subtotal2_old = rowtotals(index2r) + coltotals(index2c) + blocktotals(block2i) - target3;
subscoret_old = abs(subtotal1_old) + abs(subtotal2_old);
subscoret_new = abs(subtotal1_old-nvd) + abs(subtotal2_old+nvd);
if (subscoret_new - subscoret_old) < (rand*0.1666666667)
solution(index1) = value2;
solution(index2) = value1;
% dont bother to compare if the rows/cols are the same..
rowtotals(index1r) = rowtotals(index1r) - valdiff;
rowtotals(index2r) = rowtotals(index2r) + valdiff;
coltotals(index1c) = coltotals(index1c) - valdiff;
coltotals(index2c) = coltotals(index2c) + valdiff;
blocktotals(block1i) = blocktotals(block1i) - valdiff;
blocktotals(block2i) = blocktotals(block2i) + valdiff;
end
% ----- loop 1, do the first thing
rep = rep + 1;
index1 = index1v(rep); index2 = index2v(rep);
index1r = rowmap(index1); index2r = rowmap(index2);
index1c = colmap(index1); index2c = colmap(index2);
value1 = solution(index1); value2 = solution(index2);
block1i = blockmap(index1);block2i = blockmap(index2);
valdiff = value1-value2;
nvd=iN(index1,index2)*valdiff;
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i) - target3;
subtotal2_old = rowtotals(index2r) + coltotals(index2c) + blocktotals(block2i) - target3;
subscoret_old = abs(subtotal1_old) + abs(subtotal2_old);
subscoret_new = abs(subtotal1_old-nvd) + abs(subtotal2_old+nvd);
if (subscoret_new - subscoret_old) < (rand*0.1666666667)
solution(index1) = value2;
solution(index2) = value1;
% dont bother to compare if the rows/cols are the same..
rowtotals(index1r) = rowtotals(index1r) - valdiff;
rowtotals(index2r) = rowtotals(index2r) + valdiff;
coltotals(index1c) = coltotals(index1c) - valdiff;
coltotals(index2c) = coltotals(index2c) + valdiff;
blocktotals(block1i) = blocktotals(block1i) - valdiff;
blocktotals(block2i) = blocktotals(block2i) + valdiff;
end
% ----- loop 2, do the first thing
rep = rep + 1;
index1 = index1v(rep); index2 = index2v(rep);
index1r = rowmap(index1); index2r = rowmap(index2);
index1c = colmap(index1); index2c = colmap(index2);
value1 = solution(index1); value2 = solution(index2);
block1i = blockmap(index1);block2i = blockmap(index2);
valdiff = value1-value2;
nvd=iN(index1,index2)*valdiff;
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i) - target3;
subtotal2_old = rowtotals(index2r) + coltotals(index2c) + blocktotals(block2i) - target3;
subscoret_old = abs(subtotal1_old) + abs(subtotal2_old);
subscoret_new = abs(subtotal1_old-nvd) + abs(subtotal2_old+nvd);
if (subscoret_new - subscoret_old) < (rand*0.166666667)
solution(index1) = value2;
solution(index2) = value1;
% dont bother to compare if the rows/cols are the same..
rowtotals(index1r) = rowtotals(index1r) - valdiff;
rowtotals(index2r) = rowtotals(index2r) + valdiff;
coltotals(index1c) = coltotals(index1c) - valdiff;
coltotals(index2c) = coltotals(index2c) + valdiff;
blocktotals(block1i) = blocktotals(block1i) - valdiff;
blocktotals(block2i) = blocktotals(block2i) + valdiff;
end
% ----- loop 3, do the first thing
rep = rep + 1;
index1 = index1v(rep); index2 = index2v(rep);
index1r = rowmap(index1); index2r = rowmap(index2);
index1c = colmap(index1); index2c = colmap(index2);
value1 = solution(index1); value2 = solution(index2);
block1i = blockmap(index1);block2i = blockmap(index2);
valdiff = value1-value2;
nvd=iN(index1,index2)*valdiff;
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i) - target3;
subtotal2_old = rowtotals(index2r) + coltotals(index2c) + blocktotals(block2i) - target3;
subscoret_old = abs(subtotal1_old) + abs(subtotal2_old);
subscoret_new = abs(subtotal1_old-nvd) + abs(subtotal2_old+nvd);
if (subscoret_new - subscoret_old) < (rand*0.1666666667)
solution(index1) = value2;
solution(index2) = value1;
% dont bother to compare if the rows/cols are the same..
rowtotals(index1r) = rowtotals(index1r) - valdiff;
rowtotals(index2r) = rowtotals(index2r) + valdiff;
coltotals(index1c) = coltotals(index1c) - valdiff;
coltotals(index2c) = coltotals(index2c) + valdiff;
blocktotals(block1i) = blocktotals(block1i) - valdiff;
blocktotals(block2i) = blocktotals(block2i) + valdiff;
end
%------ loop 4, do the other thing
rep = rep+1;
index1 = index1v(rep);
index1r = rowmap(index1);
index1c = colmap(index1);
value1 = solution(index1);
block1i = blockmap(index1);
list_index = ceil(rand*list_left);
replace = list(list_index);
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i);
newtarg = target + (replace-value1) *0.11111111111111111111111;
score_diff = abs(subtotal1_old+3*(replace-value1-newtarg)) - abs(subtotal1_old - 3*target);
if score_diff < 0.93*rand
solution(index1) = replace;
list(list_index) = value1;
delta=replace-value1;
rowtotals(index1r) = rowtotals(index1r) + delta;
coltotals(index1c) = coltotals(index1c) + delta;
blocktotals(block1i) = blocktotals(block1i) + delta;
target = newtarg;
end
% ---- end loop
end
else % (list_left == 0)
% time for fresh random numbers...
index1v = ceil(rand(NUMREPS,1)*lq);
index1v = q(index1v);
sok=NUMREPS-350;
target3=target*3; %constant target
for rep = 1:sok
% --- this is same as the "first thing" above
index1 = index1v(rep); index2 = index2v(rep);
index1r = rowmap(index1); index2r = rowmap(index2);
index1c = colmap(index1); index2c = colmap(index2);
value1 = solution(index1); value2 = solution(index2);
block1i = blockmap(index1);block2i = blockmap(index2);
valdiff = value1-value2;
nvd=iN(index1,index2)*valdiff;
subtotal1_old = rowtotals(index1r) + coltotals(index1c) + blocktotals(block1i) - target3;
subtotal2_old = rowtotals(index2r) + coltotals(index2c) + blocktotals(block2i) - target3;
subscoret_old = abs(subtotal1_old) + abs(subtotal2_old);
subscoret_new = abs(subtotal1_old-nvd) + abs(subtotal2_old+nvd);
if (subscoret_new - subscoret_old) < (rand*0.1666666667)
solution(index1) = value2;
solution(index2) = value1;
% dont bother to compare if the rows/cols are the same..
rowtotals(index1r) = rowtotals(index1r) - valdiff;
rowtotals(index2r) = rowtotals(index2r) + valdiff;
coltotals(index1c) = coltotals(index1c) - valdiff;
coltotals(index2c) = coltotals(index2c) + valdiff;
blocktotals(block1i) = blocktotals(block1i) - valdiff;
blocktotals(block2i) = blocktotals(block2i) + valdiff;
end
end
end
% --- end the inner loop
sums = sum(solution(iX));
score = sum(abs(sum(sums)*0.0370370370370370-sums));
if score < bestscore2
bestsol = solution;
bestscore2 = score;
end
if bestscore2 < 5
break
end
end
if ( reruns==0 && bestscore2>9 )
reruns=reruns+1;
elseif ( reruns==1 && bestscore2>25 )
reruns=reruns+1;
else
reruns=1e8;
end
end
solution = bestsol;
% --- prepare for final improvers
n=ceil(bestscore2);
X = solution(iX);
sX = sum(X);
mX = sum(sX)*0.0370370370370370;
XX=zeros(81,3);
for i=q
XX(i,:)=find(sum(iX==i));
end
for i=1:n
bVerb=0;
for iEl=q
I=XX(iEl,:);
s1=sum(sX(I)-mX);
if (s1>0&&sum(sX(I)>mX)<2)||(s1<0&&sum(sX(I)<mX)<2)
continue
end
x=solution(iEl);
dx=solution(q)-x;
if s1>0
j=find(dx<0.8&dx+s1*2>0&dx~=0);
else
j=find(dx>-0.8&dx+s1*2<0&dx~=0);
end
if ~isempty(j)
S0=sX-mX;
s=sum(abs(S0));
m=0;
kozz=numel(j);
for k=1:kozz
S=S0;
S(I)=S(I)+dx(j(k));
J=XX(q(j(k)),:);
S(J)=S(J)-dx(j(k));
T=sum(abs(S));
if T<s
m=k;
s=T;
end
end
if m
j=q(j(m));
solution(iEl)=solution(j);
solution(j)=x;
X=solution(iX);
sX=sum(X);
bVerb=1;
end
end
end
if ~bVerb
break
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
function [out,vprev]=improver3(in,list,solution)
%Initialize
idx=find(in==0); a=solution(idx);
a=[a ; list(~ismembc(list,sort(a)))];
N1=numel(idx);
% Initialise the square indices
isquare = [ 1 2 3 10 11 12 19 20 21
4 5 6 13 14 15 22 23 24
7 8 9 16 17 18 25 26 27
28 29 30 37 38 39 46 47 48
31 32 33 40 41 42 49 50 51
34 35 36 43 44 45 52 53 54
55 56 57 64 65 66 73 74 75
58 59 60 67 68 69 76 77 78
61 62 63 70 71 72 79 80 81];
square=[1 1 1 4 4 4 7 7 7
1 1 1 4 4 4 7 7 7
1 1 1 4 4 4 7 7 7
2 2 2 5 5 5 8 8 8
2 2 2 5 5 5 8 8 8
2 2 2 5 5 5 8 8 8
3 3 3 6 6 6 9 9 9
3 3 3 6 6 6 9 9 9
3 3 3 6 6 6 9 9 9];
% Initialise the solution
[x,y]=find(in==0);
out=solution;
N=numel(a)-N1;
% Calculate bounds on the block values
rowsum=sum(out,2);
optsum=sum(rowsum)*0.11111111111111111111111;
colsum=sum(out,1)';
sqsum=sum(out(isquare),2);
S=[rowsum(x) colsum(y) sqsum(square(idx))]-optsum;
vprev=Inf;
ii=1; cnt=1;
while 1
yy=ii+1;
tmp=S(zeros(numel(a)-ii,1)+ii,:);
tmp=tmp+a(yy:end,[1 1 1])-a(ii);
tmp=sum(abs(tmp),2)-sum(abs(S(ii,:)));
tmp2=S(yy:end,:)-a(yy:numel(idx),[1 1 1])+a(ii);
tmp2=[sum(abs(tmp2),2)-sum(abs(S(yy:end,:)),2) ; zeros(N,1)];
tmp=tmp+tmp2;
[tmp,idx3]=min(tmp);
if (tmp<0) % Replace one list value by another
zz = idx3+ii;
tmp=a(zz); a(zz)=a(ii); a(ii)=tmp;
out(x(ii),y(ii))=a(ii);
if (zz<=size(S,1)) % Swaps the two currently used list values
out(x(zz),y(zz))=a(zz);
else % Re-calculate the optimal sum
optsum=optsum+(a(ii)-a(zz)) *0.11111111111111111111111;
end % Re-calculate the various sums
rowsum=sum(out,2);
colsum=sum(out,1)';
sqsum=sum(out(isquare),2);
S=[rowsum(x) colsum(y) sqsum(square(idx))]-optsum;
end
if (ii==1)
sums = [rowsum ; colsum ; sqsum];
v = sum(abs(sum(sums)/numel(sums)-sums));
if (v>=vprev)
break
end
vprev=v;
end
ii=yy;
if (ii==size(S,1))
ii=1;
cnt=cnt+1;
if (cnt==4)
break
end
end
end
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% All of the previous algorithms have focussed on pairwise switching
% of weights. The main loop is a fast random method for choosing the
% blocks to be switched. What follows that (formerly improver2) is a
% slower method comparing the scores before and after each pair of blocks
% already in the matrix have been swapped. Then improver3 is a faster
% method of doing the same thing, but only approximates the change in
% score, and also allows swaps with unassigned elements in the list.
% This improver looks at swapping three elements at a time (although
% not exhaustively), and can trivially be altered for more than three
% elements (increasing to more than 3 would probably minimally affect
% the score though).
function [out,flag]=improver4(in,list,solution)
global iX;
%Initialize
idx=find(in==0); a=solution(idx); N=numel(a);
ba=[a ; list(~ismembc(list,sort(a)))];
sums = sum(solution(iX));
bsc = sum(abs(sum(sums)/27-sums)); bsc2=bsc;
[b,idx2]=sort(ba);
zok=numel(ba)-2;
for ii=1:zok
tmp=ba(idx2([ii+1,ii+2,ii]));
a=ba;
a(idx2(ii:ii+2))=tmp;
solution(idx)=a(1:N);
sums = sum(solution(iX));
score = sum(abs(sum(sums)/27-sums));
if (score<bsc) bsc=score; ba=a; continue; end;
a(idx2(ii:ii+2))=[tmp(2:3) ; tmp(1)];
solution(idx)=a(1:N);
sums = sum(solution(iX));
score = sum(abs(sum(sums)/27-sums));
if (score<bsc) bsc=score; ba=a; continue; end;
a(idx2(ii:ii+2))=tmp([3;1;2]);
end;
flag=(bsc<bsc2);
out=in; out(idx)=ba(1:N);
return
|
