Hi all,
The following is to be saved as a csv file and then opened in excel. This sample data is from the filling of a square of 9*9.
maxx;maxy;topx;topy;botx;boty;realx;realy
0;81;0;0;0;0;0;0
81;0;0;1;1;0;1;0
;;0;2;1;1;1;1
;;0;3;1;2;1;2
;;1;3;1;3;1;3
;;1;4;2;3;2;3
;;1;5;2;4;2;4
;;1;6;2;5;2;5
;;2;6;3;5;2;6
;;2;7;3;6;3;6
;;2;8;4;6;3;7
;;2;9;4;7;3;8
;;2;10;4;8;4;8
;;3;10;4;9;4;9
;;3;11;5;9;4;10
;;3;12;5;10;4;11
;;3;13;5;11;5;11
;;4;13;5;12;5;12
;;4;14;6;12;5;13
;;4;15;6;13;5;14
;;4;16;7;13;6;14
;;4;17;7;14;6;15
;;5;17;7;15;6;16
;;5;18;8;15;6;17
;;5;19;9;15;7;17
;;5;20;9;16;7;18
;;6;20;9;17;8;18
;;6;21;9;18;8;19
;;7;21;10;18;8;20
;;7;22;10;19;8;21
;;7;23;10;20;9;21
;;7;24;10;21;10;21
;;8;24;11;21;10;22
;;8;25;11;22;11;22
;;9;25;11;23;11;23
;;9;26;11;24;11;24
;;10;26;12;24;11;25
;;11;26;12;25;12;25
;;11;27;12;26;12;26
;;11;28;13;26;12;27
;;12;28;13;27;12;28
;;12;29;13;28;13;28
;;12;30;14;28;13;29
;;13;30;14;29;13;30
;;13;31;14;30;13;31
;;13;32;15;30;14;31
;;14;32;16;30;14;32
;;14;33;16;31;14;33
;;14;34;17;31;14;34
;;14;35;17;32;15;34
;;15;35;18;32;15;35
;;15;36;18;33;16;35
;;15;37;18;34;17;35
;;15;38;18;35;17;36
;;16;38;19;35;17;37
;;16;39;19;36;17;38
;;16;40;20;36;18;38
;;16;41;20;37;18;39
;;17;41;20;38;19;39
;;18;41;20;39;19;40
;;18;42;21;39;19;41
;;18;43;21;40;19;42
;;19;43;21;41;20;42
;;19;44;21;42;20;43
;;20;44;21;43;20;44
;;20;45;22;43;20;45
;;20;46;22;44;21;45
;;20;47;22;45;21;46
;;21;47;22;46;21;47
;;21;48;23;46;21;48
;;21;49;23;47;22;48
;;21;50;23;48;22;49
;;22;50;23;49;22;50
;;22;51;23;50;23;50
;;23;51;24;50;23;51
;;23;52;24;51;23;52
;;23;53;24;52;23;53
;;24;53;24;53;24;53
;;24;54;25;53;24;54
;;24;55;25;54;24;55
;;24;56;25;55;24;56
;;25;56;25;56;25;56
It contains 4 pairs of columns, each pair is the data for a serie in a graphic, the type of graphic is cloud of points, choose the sub type with line between points.
The principle of the graphic is to move up every time you fill a cell, and move left every time a cell is empty.
The max curve: shows the ending point of a filling depending on how many cells are filled.
The top curve: each point shows how many filled cells can be fitted in the beginning of the shape. It is not possible to preform better than the max curve without breaking the rules. Each point says for the x fist cells, you can fill y cells without breaking the rules.
The bot curve: is the top curve rotated a half turn.
The real curve: is the only path leading to the only filling with the maximum score.
All the trick is the bot curve, for every point, it says: in the last x cells, you can fill y cells to the maximum. if ever your current path goes right to this curve, you will never be able to reach the maximum, you can abort the search and backtrack.
How does it work ? simple! when you begin the fill the shape or a part, you perform better than the bot curve, just count the difference between your path and the curve, if negative, you are on the right of the bot curve.
Every time you check a cell in the shape, you look at the corresponding cell in your table.
if you can fill the cell and the table says true, the path and curve are parallel.
if you can not fill the cell and the table says false, the path and curve are parallel.
if you can fill the cell and the table says false, you gain 1 spare filled cell.
if you can not fill the cell and the table says true, you loose 1 spare filled cell.
as long as the number of spare cells in not negative, you can continue the search.
The main search program is a binary tree explorer deep first, the alternatives are a cell filled or empty. what is not standard is the code to keep track of the spare cells.
Whishing this helps
For more details, just tell which part is not clear.
Patrice
