The magic square is a puzzle where with numbers 1 through 9 fill a 3 by 3 grid so that the sums of all rows, columns, and 3-length diagonals are equal. In MiniZinc we declare such a grid as an array of decision variables:<\/p>\n
array [1..9] of var 1..9: sq;<\/code><\/pre>\nwhere square<\/code> is the array, for simplicity it is 1-dimensional. The contents of sq<\/code> will be modified in the search for a valid puzzle solution. Now the constraints which describe the puzzle:<\/p>\nconstraint alldifferent(s);<\/code><\/pre>\nThis lets the solver know that every number in sq<\/code> must be distinct. Otherwise solutions like ([1,1,1,1,1,1,1,1,1]<\/code> would be generated. Next constraining the row and column sums: (arrays in MiniZinc are 1-indexed):<\/p>\n% rows\nconstraint sum(sq[1..3]) = sum(sq[4..6]);\nconstraint sum(sq[4..6]) = sum(sq[7..9]);\n\n% columns\nconstraint sq[1]+sq[4]+sq[7] = sq[2]+sq[5]+sq[8];\nconstraint sq[2]+sq[5]+sq[8] = sq[3]+sq[6]+sq[9];\n\n% diagonals\nconstraint sq[1]+sq[5]+sq[9] = sq[3] + sq[5] + sq[7];\n<\/code><\/pre>\nFinally, MiniZinc needs to know what the objective is, for other problems we can maximize or minimize some value. Here we just want any solution:<\/p>\n
solve satisfy;<\/code><\/pre>\nand that\u2019s it! Running the program gives this result:<\/p>\n
Compiling magic-square.mzn\nRunning magic-square.mzn\nsq = array1d(1..9, [8, 1, 6, 3, 5, 7, 4, 9, 2]);\n----------\nFinished in 169msec<\/code><\/pre>\nJust to make it more readable:<\/p>\n
output[ \"\\(sq[1..3])\\n\" ];\noutput[ \"\\(sq[4..6])\\n\" ];\noutput[ \"\\(sq[7..9])\\n\" ];<\/code><\/pre>\nand rerunning it:<\/p>\n
...\n[8, 1, 6]\n[3, 5, 7]\n[4, 9, 2]\n----------\nFinished in 163msec<\/code><\/pre>\nIf you\u2019re following along in the MiniZinc IDE and this is your first time using MiniZinc take a moment to reflect on all the time you may have spent solving this by hand and feel the wind on your face as you stand on the shoulders of giants. But wait, there\u2019s more!<\/p>\n
There are some improvements to be made. Firstly, this square can be rotated and reflected to create seven other solutions. This is called symmetry and it is a large component of constraint problem\/programming research. In the configuration editor in the MiniZinc IDE change output settings: check \u2018Output statistics for solving\u2019 and under \u2018User-defined behavior\u2019 check \u2018Print intermediate solutions\u2019. Also change \u2018Stop after this many solutions\u2019 to 0. Rerun the model.<\/p>\n
%%%mzn-stat initTime=0.000778\n%%%mzn-stat solveTime=0.007776\n%%%mzn-stat solutions=8\n%%%mzn-stat variables=9\n%%%mzn-stat propagators=6\n%%%mzn-stat propagations=19399\n%%%mzn-stat nodes=2659\n%%%mzn-stat failures=1322\n%%%mzn-stat restarts=0\n%%%mzn-stat peakDepth=14\n%%%mzn-stat-end<\/code><\/pre>\nThis is more information that we may want, the key line is 8 solutions. To elaborate on the rest of the output nodes<\/code> reflect the count of nodes in the search tree and peakDepth<\/code> refers to the depth of the tree. propagators<\/code> and propagations<\/code> refers to how the solver is iterating through this problem. Propagation is the mechanism by which the solution space is reduced each step and is another large part of CP research. Redundant solutions can be cut down by adding more constraints. By removing redundant solutions we also remove redundant non<\/em>-solutions and reduce the overall search space. Let\u2019s make it so that the number in the top left corner is 9.<\/p>\nconstraint sq[1] = 2;\n...\n[2, 9, 4]\n[7, 5, 3]\n[6, 1, 8]\n----------\n[2, 7, 6]\n[9, 5, 1]\n[4, 3, 8]\n----------\n%%%mzn-stat solutions=2<\/code><\/code><\/pre>\nThese final two solutions are diagonal reflections of each other, how can this be limited to just a single solution? Of course, just constrain the position of another corner.<\/p>\n
constraint sq[3] = 4;\n...\n[2, 9, 4]\n[7, 5, 3]\n[6, 1, 8]\n...\n...\n%%%mzn-stat solutions=1\n...\n%%%mzn-stat nodes=31\n...\n%%%mzn-stat peakDepth=5\n%%%mzn-stat-end<\/code><\/pre>\nThrough the addition of our symmetry breaking constraints the search space has been drastically reduced. The nodes<\/code> statistic has been reduced from 2659 to just 31 and the overall search tree has also been reduced from peakDepth<\/code> of 14 to 5. The magic square is a toy problem but is useful in demonstrating the concepts of symmetry breaking to reduce the search space and using constraints to solve some layout puzzle.<\/p>\nIf you\u2019re following along and want to keep playing with this model, what do solutions look like when the diagonal constraint isn’t necessary? What is a good way to get that down to just one solution?\u00a0 And, what does a 4×4 magic square look like? This model is just scratching the surface of what is possible in MiniZinc, they have some great documentation<\/a> if you would like to read more. Let\u2019s go back to our Settlers of Catan problem.<\/p>\nOptimal board layout<\/h2>\n
It should be clear that MiniZinc can be used to generate more balanced boards and markers for Settlers of Catan. To review the desired constraints:<\/p>\n
\n- No two of the same resources are adjacent<\/li>\n
- Lumber and brick are not adjacent<\/li>\n
- Markers distributed such that 6 and 8 are not next to one another<\/li>\n
- The four 6 and 8 markers are each on different resources<\/li>\n<\/ul>\n
This is much more than the magic square problem. For simplicity this should be two separate models, one for the tiles and another for the markers. Otherwise, the board will stay the same and the markers will cycle through every possible permutation before a different board is generated, so they will be addressed one at a time.<\/p>\n
Board<\/h3>\n
To start, some decision variables and constants are declared.<\/p>\n
% Parameters\n\n% Board size\nint: nRows = 5;\nint: nCols = 5;\nset of int: Rows = 1..nRows;\nset of int: Cols = 1..nCols;\n\n% Resources\n% 1 2 3 4 5 6 7\n% enum Resource={Water, Desert, Brick, Grain, Sheep, Stone, Lumber};\nset of int: Resources = 1..7;\narray[Resources] of int: ResourceCounts = [6, 1, 3, 4, 4, 3, 4];<\/code><\/pre>\nResources are represented on the board as numbers 1 through 7. ResourceCounts<\/code> is the number of that resource to be placed on the board. The board is square so we need to represent water as a resource, there are six of them. There is the desert, resource lacking, tile which the thief starts on. The rest of the array is the count for the primary resources.<\/p>\n% Decision Variables\narray[Rows, Cols] of var Resources: Board;<\/code><\/pre>\nThis is the decision variable the model will be modifying in the search for a solution. Now for constraints.<\/p>\n
% Resource counts\nconstraint forall(re in Resources)(\n sum(r in Rows)(count(Board[r,..], re)) = ResourceCounts[re]\n);<\/code><\/pre>\nThe forall<\/code> predicate is being used here to constrain that for each resource re<\/code> the sum of the count of the re<\/code> on the board is equal to the count in ResourceCount<\/code>.<\/p>\n% No two of the same resources are adjacent\nconstraint forall(r in 1..nRows-1) (\n forall(c in 1..nCols-1) (\n alldifferent_except_0([Board[r,c]-1, Board[r, c+1]-1,\n Board[r+1, c]-1, Board[r+1,c+1]-1])\n )\n);<\/code><\/pre>\nThis one is more complicated. There are two forall<\/code> predicates here with an alldifferent_except_0<\/code> constraint. The forall<\/code>s iterate and constrain over every element in the board until the second to last row and column. Recall that this is declarative, forall<\/code> is shorthand for generating multiple constraints at once. For each tile, its value is constrained so that it is different than its neighboring tiles unless the value\u20131 is 0 (recall that oceans are 1). To constrain lumber and brick from neighboring each other the alldifferent_except_0<\/code> constraint cannot be used.<\/p>\n% Lumber and brick cannot be adjacent\n\n% constraint right and bottom right diagonal\nconstraint forall(r in 1..nRows - 1)(\n forall(c in 1..nCols where Board[r,c] in {3, 7}) (\n not(Board[r+1, c] in {3, 7})\n )\n \/\\ % and\n forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(\n not(Board[r+1, c+1] in {3, 7})\n )\n);\n\n% constraint bottom\nconstraint forall(r in 1..nRows) (\n forall(c in 1..nCols - 1 where Board[r,c] in {3, 7})(\n not(Board[r, c+1] in {3, 7})\n )\n);<\/code><\/pre>\nTwo features called reification and set notation are used here. Reification can be a performance foot shotgun sometimes and makes the lower-level models more complex, use this carefully. The set is used to check that a tile value is not in the set {brick(3), lumber(7)}<\/code>. Reification is used in the inner forall<\/code>s with where Board[r,c] in {3, 7}<\/code>. This is saying only \u201citerate over tiles which are lumber and brick.\u201d The inner-most constraint not(Board[r+1, c] in {3, 7})<\/code> checks that a neighboring tile is neither lumber nor brick.<\/p>\nIf the model is run now ocean tiles will be everywhere, they need to be on the edges.<\/p>\n
% Place the water on the edges\nconstraint Board[1,4] = 1;\nconstraint Board[1,5] = 1;\nconstraint Board[2,5] = 1;\n\nconstraint Board[4,1] = 1;\nconstraint Board[5,2] = 1;\nconstraint Board[5,1] = 1;<\/code><\/pre>\nTo reduce the search space three corners of the island are constrained to be descending in value.<\/p>\n
% break rotational symm\nconstraint Board[1,1] < Board[3,5];\nconstraint Board[1,1] < Board[5,3];\nconstraint Board[3,5] < Board[5,3];<\/code><\/pre>\nAnd finally, solve to satisfaction and output the board:<\/p>\n
% Objective\nsolve satisfy;\n\n% output[show2d(Board)];\n\noutput[ \" \\(Board[1,1..3])\\n\" ];\noutput[ \" \\(Board[2,1..4])\\n\" ];\noutput[ \"\\(Board[3,..])\\n\" ];\noutput[ \" \\(Board[4,2..])\\n\" ];\noutput[ \" \\(Board[5,3..])\\n\" ];<\/code><\/pre>\nThe output is staggered to look like how the tiles are actually laid out. Let\u2019s see what it gives us!<\/p>\n
[2, 7, 5]\n [3, 4, 6, 7]\n[6, 5, 3, 5, 4]\n [7, 4, 6, 3]\n [5, 7, 4]\n% time elapsed: 0.13 s\n----------\n==========\n%%%mzn-stat initTime=0.013395\n%%%mzn-stat solveTime=0.12374\n%%%mzn-stat solutions=96\n%%%mzn-stat variables=110\n%%%mzn-stat propagators=135\n%%%mzn-stat propagations=610914\n%%%mzn-stat nodes=12549\n%%%mzn-stat failures=6179\n%%%mzn-stat restarts=0\n%%%mzn-stat peakDepth=21\n%%%mzn-stat-end<\/code><\/pre>\n96 \u201coptimal\u201d boards to chose from! With output[show2d(Board)];<\/code> the raw 2D array is output. Did I mention MiniZinc can be run from the command line and can output to JSON? This output can easily be piped and interpreted in Python. With some matplotlib hacking the board can be visualized.<\/p>\n![\"\"](\"https:\/\/www.thesixsides.com\/blog\/wp-content\/uploads\/2019\/06\/board.png\")
<\/p>\n
For those who have just learned about SoC, the colors may be unfamiliar. Above, brick is red, sheep is green, wheat is yellow, ore is gray, forest is dark green, and the desert is orange. One interesting attribute for this solution is that for this set of constraints the desert tile is (almost) always in a corner. This seems to be a by product of the lumber\/brick adjacency constraints.<\/p>\n
Markers<\/h3>\n
The markers model is largely the same and won\u2019t be repeated here. Instead of tiles it makes sure that no two numbers are adjacent and the 6\u2019s and 8\u2019s\u2014the most probable resource gaining numbers\u2014are also not adjacent.<\/p>\n
set of int: Number = 1..12;\n % 1 2 3 4 5 6 7 8 9 10 11 12\narray[Number] of int: MarkerCounts = [6,1,2,2,2,2, 1, 2,2, 2, 2, 1];<\/code><\/pre>\n1\u2019s cannot be rolled so they will be assigned to oceans, 7 will be assigned to the desert tile. This model takes Board<\/code> from the previous model as input to make sure that the 7 is placed on the desert.<\/p>\n% Place the 7 on the Desert\nconstraint forall(r in Rows)(\n forall(c in Cols where Board[r,c] = 2) (\n Marker[r,c] = 7\n )\n);<\/code><\/pre>\nSince Board<\/code> is a parameter not a decision variable there is no refification going on here. When writing constraints stating the constraint in simple English and they codifying it is often the best approach. For example: \u201ceach resource of each type must have have all different<\/strong> markers<\/strong>.\u201d Which is translated as so:<\/p>\n% All resources have different markers\nconstraint forall(res in {3,4,5,6,7}) (\n % all markers different\n all_different([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ])\n \/\\\n % only one 6 or 8 per resource\n count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 8) +\n count([Marker[r,c] | r in Rows, c in Cols where Board[r,c] = res ], 6) <= 1\n);\n [7, 8, 11]\n [6, 12, 10, 5]\n[3, 9, 11, 8, 9]\n [10, 6, 5, 4]\n [4, 3, 2]<\/code><\/pre>\nThe all_different<\/code> constraint is being applied to the array of decision variables Marker<\/code>.<\/p>\nThe marker distribution can be improved more. Something to note about the marker solutions above is how there are some very weak vertices on the board. I\u2019m looking at 5,4,2, and the 12,10,11 vertices, can the number of these vertices reduced? Let\u2019s try setting a threshold on the sum of neighboring values.<\/p>\n
% distribute markers\nconstraint forall(r in 1..nRows-1)(\n forall(c in 1..nCols-1 where Marker[r,c] > 1) (\n Marker[r,c] + Marker[r+1,c] + Marker[r+1, c+1] < 23\n \/\\\n Marker[r,c] + Marker[r,c+1] + Marker[r+1, c+1] < 23\n )\n);\n...\n [7, 11, 8]\n [6, 4, 3, 9]\n[10, 5, 12, 4, 8]\n [6, 3, 2, 9]\n [11, 5, 10]\n<\/code><\/pre>\nThis iterates over each tile checking the vertices with two other neighbors. The threshold is sensitive. If it\u2019s 21 or less there exist no solutions, when it\u2019s 22 there is just 1 solution<\/em>. In about half a minute with a threshold of 23 I can find that there are 11,753 solutions. Most vertices are improved but some weak ones remain such as 3,2,5 and 2,4,12. There are 11,752 other configurations that might have more even vertices.<\/p>\nIt may be impractical to reduce the search space without forcing certain markers on certain tiles. Unlike the five types of tiles there are ten (2\u201312, excluding 7) types of markers to shuffle around. That said I think the marker permutations this last constraint generates looks a little better than before. A little more matplotlib hacking and we get the board in a neat picture, markers included.<\/p>\n
![\"\"](\"https:\/\/www.thesixsides.com\/blog\/wp-content\/uploads\/2019\/06\/board-markers-1.png\")
<\/p>\n
With a board layout and markers distributed across them there\u2019s only one thing left to do: play the game!<\/p>\n
Play testing<\/h2>\n
I got some friends together to play using a board generated with these models. With an optimal tile and marker layout and I couldn\u2019t have been more excited to truly see what a balanced Settlers of Catan game feels like.<\/p>\n
The pace of the game can only be described as glacial. The game was declared a draw three hours in due to nobody having much fun, for reference most games are usually around 60 minutes. The advantages each player had were marginal due to such equal access to resources. I recall the highest pointed player had seven points and most of it was through development cards.<\/p>\n
This is an illustrative example of how fun in games emerges from complexity and competition rather than strict rigidity and equality. For example professional Starcraft or DotA would not be as interesting if everyone was forced to play the same race or the same standard set of five heroes.<\/p>\n
It turns out that tournament SoC maps frequently have common resources adjacent as well as 6\u2019s and 8\u2019s on common resources. 6\u2019s and 8\u2019s are never adjacent though. I could not find a site for tournament boards for this post (if they are published please reach out to me) but browsed through a few final games on YouTube. This Reddit thread<\/a> has some comments from tournament goers on board setup, this comment from implosionsinapie<\/code> is interesting:<\/p>\nFor the U.S. national qualifiers the boards are what I like to call semi-constructed. They completely randomize numbers and resources and then adjust accordingly so there aren\u2019t any 6\u20138\u20135 spots or too heavy a concentration of a certain resource. It\u2019s all up to whoever is running the tournament, though, they can make boards as simple or as difficult as they like. [\u2026]<\/p><\/blockquote>\n
Further work<\/h2>\n
Ports are an important part of gameplay. Ports allow players to trade two resources of a certain type for one of any other resource (a 2:1 ratio), there are also open ports where the ratio is 3 of the same type for 1. In the several dozen games I have ever played only in a handful did port access win the game, it is something that has to be planned from turn one. Strictly speaking though, it is a part of the board layout and so this model is incomplete without port placement and port placement is left up to us humans.<\/p>\n
There exist several expansions for SoC which increase the board size, make a whole separate island, and introduce new tiles. I have actually never played them though and so I cannot speak for what sort of imbalances CP could address or if they are worthwhile to.<\/p>\n
Conclusion<\/h2>\n
In summary, optimal boards are not more fun. CP can certainly create a board with the desired constraints but the boards aren\u2019t fun to play on, extending the total game time more than two-fold. To modify the question: what sorts of constraints make more fun board layouts?<\/p>\n
Source code<\/h2>\n