Beating OpenAI games with neuroevolution agents: pretty NEAT!

Let’s start with a fun gif!

Something I’ve been thinking about recently is neuroevolution (NE). NE is changing aspects of a neural network (NN) using principles from evolutionary algorithms (EA), in which you try to find the best NN for a given problem by trying different solutions (“individuals”) and changing them slightly (and sometimes combining them), and taking the ones that have better scores. read more

First project with the new 3D printer: a TOF sensor mount

I’m pretty late to hop on the 3D printing bandwagon, but I heard its siren song and couldn’t stay away much longer!

After the briefest search online and asking a few friends, I decided to go with the Monoprice Delta Mini. My main reasons were that I didn’t want to have to tinker and build much (at least to start), I wanted to be able to get decent quality, I didn’t want to spend a ton, and I don’t especially need a large print size. The MPDM matched all of this (supposedly works out of box, can do 0.05 mm layer height, 160 bucks, 4″ height by 3″ diameter print volume), so I went for it. read more

Solving the Brachistochrone and a cool parallel between diversity in genetic algorithms and simulated annealing

In my first post on Genetic Algorithms (GA), I mentioned at the end that I wanted to try doing some other applications of them, rather than just the N Queens Problem. In the next post, I built the “generic” GA algorithm structure, so it should be easy to test with other “species”, but didn’t end up using it for any applications.

I thought I’d do a bunch of applications, but the first one actually ended up being pretty interesting, so… here we are. read more

Animation stand: from design to build with Onshape

My mom does lots of animation, and one day mentioned that she would love to have an animation stand, but professional ones are either cheap and too small, or very expensive. With the holidays coming up, this seemed like a good present!

I Googled “animation stand” first, to see what others have done and get some inspiration.

Training an RL agent to play Puckworld with a DDQN

Last time I messed around with RL, I solved the classic Mountain Car problem using Q-learning and Experience Replay (ER).

However, it was very basic in a lot of ways:

  • There are really only two actions, and the state space had only two dimensions (position and velocity).
  • The way I was representing the state space was very simple, “coarse coding”, which breaks the continuous state space into discrete chunks, so in a way it still has discrete states. More interesting problems have continuous, many dimensional state spaces.
  • The representation of Q was just a state vector times a weight vector, so just linear. You can actually get a decent amount done with linear, but of course all the rage these days is in using neural networks to create the Q function.
  • The problem was very “stationary”, in the sense that the flag (where the car wanted to go) was always in the same place. Even if I had the flag move around from episode to episode, the strategy would always be the same: try to pick up enough momentum by going back and forth. A more interesting problem is one where the goal moves.

Genetic Algorithms, part 2

Last time, in case you missed it, I left off with a laundry list of things I wanted to expand on with Genetic Algorithms (GA). Let’s see which of those I can do this time!

This is pretty wordy and kind of dry, since I was just messing around and figuring stuff out, but I promise the next one will have some cool visuals.

Using Reinforcement Learning to solve the Egg drop puzzle

So last time, I solved the egg drop puzzle in a few ways. One of them was using a recent learn, Markov Decision Processes (MDP). It worked, which got me really stoked about them, because it was such a cool new method to me.

However, it’s kind of a baby process that’s mostly used as a basis to learn about more advanced techniques. In that solution to the problem, I defined the reward matrix and the transition probability matrix , and then used them explicitly to iteratively solve for the value function v and the policy p. This works, but isn’t very useful for the real world, because in practice you don’t know  and , you just get to try stuff and learn the best strategy through experience. So the real challenge would be letting my program try a bunch of actual egg drops, and have it learn the value function and policy from them.

Some mathy tesselating stamp art!

I was recently at the art store for some reason, just browsing. I found the linoleum stamp section at the back and immediately wanted to make some! We had made them in 5th grade art class or something, and I remember liking it a lot, but had never since then. They’re kind of the perfect type of art for me, since I seem to like 3D things with more of a “crafts” element. I like carving/whittling anyway, so this was perfect.

I grabbed a few (pretty cheap), and on the way home thought of what I’d do: make a square stamp with weaving paths, asymmetric, such that it could be stamped out in a grid to either create cool repeating patterns, or random ones.

First I’ll briefly talk about the craft section, and then the coding part. If you wanna see the big figures, skip to the bottom!

I bought two, so I could have the small square be a “1×1” unit square “tile”, and the bigger one be a 2×2:

It turns out the sizes they are sold as aren’t totally accurate, so I had to resize them:

The linoleum is real easy to cut with a thin scroll saw, but the wood was pretty annoying.

Ta da!

Here’s the 1×1 tile. I tested a few patterns and decided to put “ticks” (i.e., entry/exit points for the paths) at the quarter, half, and three quarters marks of each side, so when you rotate it and put it next to another, it will match up with them and continue the paths, sometimes creating closed loops (either between adjacent ones, or over many tiles).

For the pattern, it was somewhat arbitrary, but I wanted a combination of ones that would connect the same side to itself, to adjacent ones, and ones across (you can see the one I chose in the pad to the back):

I also wanted it to be totally asymmetric, since it would offer more pattern making.

The carving was pretty easy. The carving kit I got had “scoop” blades that I originally though would be more useful, but it turns out that it’s easier and cleaner to just use a straight blade and cut at a “V” angle into it to make the channels.

Additionally, I’m not sure if you can see here, but I intentionally put a little gap in between paths when one crosses another, to give the impression that it’s crossing “under” the other, adding a bit of depth.

So how does it look?

Neato! The print was splotchy, but I love the wandering, wild patterns it quickly makes.

The 2×2 was even more fun, because I had a lot more space to go nuts. It now had 6 ticks per side, which let me do some pretty wide, sweeping circles. Here it is carved next to the 1×1:

It was a bit of a pain to line up the ticks exactly after carving so many, but it only took a few adjustments and testing all sides against each other to make them pretty decent (keep in mind that you’re not gonna have a ton of precision with stamping anyway):

So how does the 2×2 look?

PRETTY SWEET IN MY OPINION.

Here’s the 2×2 first:

Then for fun, I did another 2×2 and a bunch of 1×1’s in the area around them:

I was doing it kind of fast and loose, so the edges don’t line up perfectly. Still, I love the swooping, huge circles created by the 2×2. It seems like I made the lines a little thicker for the 1×1, so maybe I’ll go back at some point and widen the ones for the 2×2.

So that’s the craft part! I dunno what I’ll do with them. I think it would be pretty cool to cover a wall in them a some point or maybe make a shirt if I get some fabric ink.

 

Now let’s code!

I could (and will!) make lots of prints, but I wanted the ability to test out large scale patterns of various configurations of the blocks without having to manually print them. Then, in the process of doing that, I found some nifty patterns that occur.

The first thing I did was take the above photos, crop out and perspective shift the tiles out of them to make them square, then “posterize” them to decrease the number of colors used. This allowed me to easily grab the basic shapes of the tiles and make new, cleaner images with them:

From here, it was pretty to use PIL (python image library) to whip up a program with a Board class, which uses a Tile class, to create large scale patterns quickly. Here’s the most simple, plotting just the 1×1 tile repeating uniformly:

It already forms a neat thing! If you follow a single path, you’ll see that it goes down 1 and right 1 each step, in a winding path.

What if we add the smallest of variation? To do this, first lemme define a few things. To be consistent with PIL, the origin starts at the upper left, the x coordinate is to the right, and the y coordinate is down. I can rotate a given tile, and PIL rotates CCW. There are only 4 unique rotations, so rot=0 is not rotated at all (i.e., the rastered 1×1 tile above), rot=1 is rotated 90 degrees CCW, etc.

Here, what I’ll do is create horizontal stripes. To do this, as I add tiles, I’ll just rotate each tile in a row by its y value, modulo some value. So, if I do mod=2, the stripes will be every other tile. For example, here’s the relevant code for that:

def hStripesPopulate(self,mod=2):
  self.label = 'hstripes_mod'+str(mod)
  for i in range(self.N_board):
    for j in range(self.N_board):
      self.insertTile((i,j),type=1,rot=j%mod)

The important part is the rot=j%mod. Here’s what that looks like!

Daaang. I dunno about you, but I find that really pleasing.

Here’s mod=3:

mod=4:

Mod 2 and 4 look pretty similar at a glance, but if you look closer they’re actually a bit different.

I won’t bother with vertical stripes, because they’re pretty much the same aggregate, just rotated. But, what’s really cool, is a “both stripes” pattern, where I basically do the same thing as above, but use rot=(i+j)%mod:

def bothStripesPopulate(self,mod=2):
  self.label = 'bothstripes_mod'+str(mod)
  for i in range(self.N_board):
    for j in range(self.N_board):
      self.insertTile((i,j),type=1,rot=(i+j)%mod)

Here’s mod=2:

I looooove that squiggly, repeating closed path. If you notice, it actually has a bit of an MC Escher-y vibe due to the overlapping, if you follow the path, because it’s always overlapping the next one it crosses.

mod=3:

mod=4:

This one is even cooler to me. It has two enclosed paths!

Now let’s try a few other random things. Here’s using rot=(i*j)%mod.

mod=2:

That one actually is just a series of closed paths, although you wouldn’t guess at a glance! Try following one.

mod=3:

That one takes a very long, wandering path before it repeats again, if you follow it.

mod=4:

This one is neat, because it has two different types of paths, for each row, that weave around each other, but never connect.

Here’s a neat one! A radial one, where it rotates it by roughly how far it is from the center, rot=floor(sqrt(((i-self.N_board/2)**2+(j-self.N_board/2)**2)))%mod.

Here it is for size 15:

If you follow the path at the very center of the image, it takes a VERY long path for being a fairly small board.

zooming out to give a bit more of the large scale pattern, 30:

You can see that, since the rotation has to be an integer, it doesn’t have the most precision in its “circle-y-ness”, but you get the picture. There’s definitely some weirdness happening at the corners.

Okay, I promise I’m almost done!

A cool one is using the Fibonacci sequence, rotating each tile of the double for loop above by Fibonacci[i*j + i]%4 (so it’s like you’re just counting across and down the grid, but using that term of the Fibonacci sequence):

You can see (if you use the little circles as a guide) some very interesting, non repeating behavior!

Lastly, to make a more classic tessellation, I did a Pythagorean Tiling, which you’ve almost certainly seen on a bathroom floor somewhere. The idea is that you have a big square that’s one color (for example), that’s twice as big as a small square, that’s another color. Putting the small square in the upper right of the big square allows you to tile the whole plane. For my application, the big square was just 4 tiles of the same rotation, and the smaller one is one tile of another rotation. You can also make the bigger square size (its width) any integer number of the smaller tiles, but I found that 2 looks the best.

Here are a couple variations of that, just rotating the smaller one differently with respect to the bigger one:

To do this, each entry in the for loop (where I insert tiles) is actually entering a “unit” of a big square (which itself is entering four 1×1 tiles), and one 1×1 tile. I did this in a bit of a wonky way (where it plots more tiles than necessary), but it made the coding real easy because a Pythagorean Tiling produces its own “grid” (see the Wiki article) which is easier to code with respect to:

for x in range(-int(self.N_board/2),self.N_board):
  for y in range(-1,self.N_board):

    i = big_sq_size*x + y
    j = big_sq_size*y - x

    #The big square
    for a in range(big_sq_size):
      for b in range(big_sq_size):
        self.insertTile((i+a,j+b),type=1,rot=bigrot)

    #the smaller square
    self.insertTile((i-1,j),type=1,rot=smallrot)

Here, x and y are the coordinates in the “Pythagorean grid”, and you get i and j for each of them.

 

Okay, so at this point I got a little curious. It seems like some patterns give rise to a ton of different paths, while some cause a minimum of them, and I was wondering if I could quantify what to expect, or at least find some pattern in them. One thing you can say is that the number of paths per tile (in a large board of them) is bounded, in general (like, considering other 1×1 tiles I didn’t make but you could). If you had a small 1×1 tile with 3 ticks on each side, but any arrangement of the lines connecting the ticks within it (such that they’re only connected in pairs), the smallest number of paths would be if you just connected each tick to the other tick straight across it, like this:

This would be that orientation doesn’t matter, and that as you add more tiles, it’s always just continuing existing paths, decreasing the (# paths/# tiles) ratio. So if you added another row of N tiles here, you’d get 3 more paths but increase the number of tiles by N, meaning it tends towards 6 paths/N tiles, or 0 for large N.

On the other end, you can only make so many paths per tile. It wasn’t immediately clear how to do it with 3 tick/side (actually, is there a way? or are odd number tick sides more bounded?), so I just sketched it with 4 ticks per side, where you can connect each with a pair, ensuring that there’s 4 paths per tile when you repeat it:

So you’re never getting more than (N_ticks/side) per tile paths, and you can basically get as low as zero paths/tile.

However, I’m still not sure how to predict, given just the tile and how we’ll orient it, how to predict how many paths it could produce.

As a starting point, I plotted the # paths/# tiles for a given layout pattern, for a bunch of sizes of boards. Here’s the one for the simplest, the uniform one:

It goes as the sqrt, which I thought was strange. But, if you look at this one, you can see that it actually makes sense. When you add the next “layer” of tiles, it continues all the paths there were already, but also adds one extra path for each tile:

Something interesting happens if you do it so each tile is placed with random orientation:

I tried to plot lines that seemed like they were similar to what it tends towards, but I dunno (the jumpy parts are where I added a couple samples at that same # tiles to see how much variation in the randomness there is). It seems pretty clear that the ones for low # tiles (which there are a bunch of samples for) do tend towards sqrt(# tiles), but then it evens out towards linear. I also plot the number of closed paths, and I think it’s interesting that it looks like it tracks it as a proportion of the total number fairly well.

For curiosity, here’s a random one:

I won’t try it today, but I think one approach that could work for this (the random one) is using some statistical mechanics-y technique. Maybe something where, for a given ensemble of already placed tiles, I try to figure out the chance of another tile placed on the edge cutting off existing paths vs adding a new one. This is one of those things where I bet if I spent a bit of time looking into it, it’s an insanely well known field that many people have written books on. (I mean, I know tessellations are for sure, but this has the paths element to it too. Does anyone know what this might be called?)

I’ll probably look at this stuff in another post, since it’s intriguing me. Well, that’s about all for now. I have a bunch of ideas I’ll try next time. Some more functions of x and y, sequences, etc. I also want to build more “units” (like the Pythagorean tiling), where I can engineer them to have extremely long paths that are nevertheless closed. Speaking of, I want to also characterize the average path length for different configurations (in # tiles it crosses, not counting the actual distance on a tile). I think with engineering bigger unit groups of 1×1 tiles could give some really interesting behavior. I also want to figure out what “rules” would be specific to the 1×1 tile I did, vs any tiles. Lastly, I didn’t even use my 2×2! It turned out that it was complicated enough with just the 1×1.

The (messy) code for all this is here.

Skyscraper fun with OR-Tools!

My friend Mike recently showed me a puzzle game called Skyscrapers, which you can play here. It’s a neat idea, in the general theme of “fill in the numbers with these constraints” puzzles like Sudoku or Verbal Arithmetic.

The rules are like so. You’re given a board like this, representing a group of city blocks (one building per square), with numbers around the sides:

Your goal is to fill in the squares with the numbers 1 to the width of the puzzle (4 in this case), where the number represents the height of the building on that square. There can’t be any repeats of numbers in a given row or column.

For each number on the side, that’s the number of buildings you can see, looking down that row or column, in the direction of the arrow next to it. If there’s a bigger building (number) in front of a smaller building (number) (from the viewpoint of the number on the side), you can’t see the smaller building behind it. So if you were looking down a column that had [1, 2, 4, 3] in that order, you would see buildings 1, 2, 4, but the building with height 3 is hidden behind the one with height 4.

So, you can always see at least 1 (e.g., if it were [4, 2, 1, 3]), and at most 4 ([1, 2, 3, 4]). You have to place the numbers such that all the “number of buildings seen” from each side panel are satisfied, as well as the constraint I mentioned above about the numbers in each row and column all being different.

Here’s that puzzle solved, to show it:

Note that for each “seen” number on a side, it’s *from that viewpoint*, looking up or to the left or whatever, just to be clear.

One more complication to add. There are ones of bigger sizes, like 8×8 ones, but they also make them harder by removing clues along the sides, and give you hints by adding numbers that have to be in the solution. For example:

So I wanted to solve this using techniques I’ve been learning. There are probably a few ways to go about it. I actually tried both Genetic Algorithms and Simulated Annealing, with varying success, but I’ll save that for another post because I think they can do better that they are currently if I tweak them a bit.

This immediately appeared to me as a Constraint Satisfaction Problem (CSP), like we did in our Coursera Discrete Optimization course, which I’ve made a few posts about in the past. CSP are basically where you set up a set of constraints that represent the problem, such that if you find a model that satisfies all of them, you’ve found the solutions. The actual algorithms you use to solve these CSP are some things we used in the DO course (like branch and bound), but in practice you probably use a CP solver that someone else has already written, because it will probably do something special like look at the structure of the problem to set it up in an optimal way. If you do this, then you simply get a CP solver and set up the variables and constraints, which can actually be tricky itself.

There are many, many subtypes of CSP, and it’s an insanely important, dense field (that’s actually doing a lot of work behind the scenes that you might not know of). There’s actually a related (/subfield?) of CP called Integer Programming (IP), where all the variables are restricted to be integers, so I guess we’ll technically be doing that. To be honest, it wasn’t totally clear to me what the difference was, but this and this shed a little light on the distinctions. I think we’ll actually be doing CP now, because I use a few constraints like Min and Max, whereas IP only uses linear in/equalities.

We actually used Gurobi for our course, mostly because Phil knew the most about CP solvers and suggested it. It was actually really straightforward and pleasant to use in python, and we used it to solve a Vehicle Routing Problem, which is basically the Traveling Salesman Problem on crack. My only qualm was that it seemed a little annoying to install, and it’s commercial, so you can either get a free license that limits the number of variables you can use, or get an academic license for free if you’re part of a school.

I instead opted to use OR-Tools, Google’s Optimization Tools (it’s “operational research”). I did it partly because I was curious, partly because I usually like Google’s style, partly because I didn’t want to have to deal with the Gurobi license thing, and partly because it was super easily installed through pip3. Literally just “pip3 install ortools”. I was actually flying back home from Washington state on a plane that had surprisingly fast free wifi, so I downloaded it and was off to the races.

 

Now, on to the problem!

 

I mostly hacked around with code from the OR-tools guides they have here, since there are some details that probably don’t matter immensely for my simple application. I’ll go through my code bit by bit, and use this 9×9 puzzle as an example:

The first part was to actually write the puzzle in code, which is probably going to be messy no matter what. I opted to do it as a list of 4 lists, one for each side, in the order [left, right, top, bottom], where the left and right sides are read in the order top to bottom, and the top and bottom sides are both read left to right. I call this see_list, since that’s what you’d see from the sides. If any aren’t given (like in some puzzles), I make them a 0. I also define the list of the given numbers (if there are any) as const_list, a list of tuples, each of which is the location and value of the given number. I count down and then right, starting at index 0, for the indices, so the first const_list entry is ([1,0],3). So here’s the above puzzle:

ss_99 = [[1,4,5,2,3,2,3,2,4],[2,2,2,3,4,3,1,3,5],[1,4,3,3,4,3,3,2,2],[4,2,3,2,1,3,2,3,3]]
ss_99_constlist = [([0,3],6),([0,7],2),([1,0],3),([1,8],6),([2,0],5),([2,3],7),
([2,6],2),([3,1],1),([3,5],2),([3,6],8),([4,6],7),([4,7],5),
([5,1],4),([5,3],1),([5,7],7),([5,8],3),([6,1],3),([6,3],5),
([6,4],1),([7,5],3),([7,7],8),([8,5],7)]

see_list = ss_99
const_list = ss_99_constlist

Next, I create the solver object and variable list:

# Creates the solver.
solver = pywrapcp.Solver("simple_example")

#Create the variables we'll solve for
ss_vars = np.array([[solver.IntVar(1, size, "a_{}{}".format(i,j)) for j in range(size)] for i in range(size)])

solver.IntVar() creates an integer that’s bounded between 1 and size, inclusive, and you can give it a name. So we actually have a numpy array of these solver variable objects.

Now we have to add the constraints!

The first constraints are having all the numbers in each row and column different. I think this is the first part that makes what I’m doing CP rather than IP, because I get to use the handy AllDifferent() constraint rather than having to specify them all individually. Note that I can very handily slice the numpy array, but it has to be converted to a traditional python list before getting handed to AllDifferent(), or it whines:

#CONSTRAINTS

# All rows and columns must be different.
for i in range(len(ss_vars)):
    solver.Add(solver.AllDifferent(ss_vars[i,:].tolist()))
    solver.Add(solver.AllDifferent(ss_vars[:,i].tolist()))

Next, we have to add the constraints for see_list. This is the part, if any, that is a little tricky. It’s pretty easy to look at the puzzle and say “yeah, you can see 3 buildings looking down that row from the right”, but it’s not as immediately clear (to me anyway) how you would actually take the row of numbers and extract the number of ones you can see (and then set that equal to the number you’re supposed to see).

This code is pretty ugly, but I’m not sure of a cleaner way to do it. Here’s what I did. I add the constraints in a loop for each entry of a side (so 1 to the size of the puzzle), and for each iteration, I first add the constraints for the left/right sides, then the top/bottom sides. I’ll just show the first one for now, the constraints looking from the left, to illustrate the principle:

for entry in range(size):
    #left and right
    sidepair = 0
    left_top = 2*sidepair
    right_bot = 2*sidepair + 1
    #print('adding constraint for left/right sidepair {}, entry {}: {} and {}'.format(sidepair,entry,see_list[left_top][entry],see_list[right_bot][entry]))
    if see_list[left_top][entry]!=0:
        solver.Add((1 + solver.Sum([solver.Min(solver.Max(ss_vars[entry,:j+1].tolist()) - solver.Max(ss_vars[entry,:j].tolist()),1) for j in range(1,size)])) == see_list[left_top][entry])

The sidepair, left_top, and right_bot things are just indices to get the relevant element of see_list. The if statement is just making sure the value isn’t 0, i.e., there actually is a value we need to constrain (not a blank, like for the harder puzzles).

The instrumental part is the last line. What it’s doing is the following. It’s basically starting at the first element in the row (from the left in this case), and then taking two subsets of elements of the row, in order from left to right. The first subset goes from indices [1,i] and the second subset goes from [1,i+1]. The first subset represents the buildings you can see counting just the ones from 1 to i, and the second is the buildings from 1 to i+1. It takes the max of each of these (note that because we’re adding a constraint, not just calculating it, we have to use the solver’s Max function, not the python one). The idea here is that, as you include the “next” building (the one in the i+1 position), if the max changes, that means you could see another building (so you have to add 1 to the building count) but if it doesn’t, the max was already in the range [1,i], so you don’t. So we want to iterate over i such that this process will cover every subset in the row, adding 1 to the building count each time the max increases.

Because you just want a count of 1 even if the max changes by more than one (i.e., if adding the i+1 variable increased the max from 2 to 4), it seemed like I had to use something like the Heaviside step function, which I don’t think is in OR-tools, but I was able to figure out a sneaky workaround. If the next building doesn’t increase the max, then the difference between the maxes will be 0, which is what we want to add to the building count anyway. If the next building does increase the max, then their difference will be at least 1, if not more (but never negative, because it can only increase when we take into account more buildings). Therefore, we can take the Min (again, the solver version) of this difference and 1.

Then, we take the Sum (the fancy solver version) of these Min’s, plus 1 (because you always see the fist building), and set that equal to the number of buildings we should see. Now that I look at it, you could actually just use the value at the i+1 index, not the subset, since that’s the only one that matters, but you’d still need to use the subset for the [1,i] range I think. I think you could also get rid of the whole subset thing by doing it in an explicit loop for each one, keeping an updated “max seen so far” variable, but I did this and it works.

I won’t go over it, but you have to do the same for see_list from the right, but you have to reverse the subsets. You also then have to change the sidepair variable so it’s doing it on the top and bottom, and just slice the var matrix differently, but it’s the same idea.

Lastly, we add the constraints for the given constants:

#Add constraints for given constants, if there are any
for const in const_list:
    ind = const[0]
    val = const[1]
    solver.Add(ss_vars[ind[0],ind[1]] == val)

Now to actually solve it, we have to use a bit of ~~MaGicK!~~. We need a “collector”, which basically just collects the solution. We also need a “decision builder”, which we pass a few magic options. Then, we just hit Solve!

#Soluion collector
collector = solver.AllSolutionCollector()
collector.Add(ss_vars.flatten().tolist())

#The "decision builder". I just used the one from:
#https://developers.google.com/optimization/cp/cp_tasks
db = solver.Phase(ss_vars.flatten().tolist(), solver.CHOOSE_FIRST_UNBOUND, solver.ASSIGN_MIN_VALUE)

#Solve it!
time_limit_s = 1
solver.TimeLimit(1000*time_limit_s)
print('\n\nstarting solver with {}s time limit!'.format(time_limit_s))
start_time = time()
solver.Solve(db, [collector])
print('\ndone after {:.2f}s'.format(time()-start_time))

#print solutions
print('\nthis many solutions found:',collector.SolutionCount())
for sol_num in range(collector.SolutionCount()):
    sol = np.array([[collector.Value(sol_num,ss_vars[i,j]) for j in range(size)] for i in range(size)])
    print('\nsolution #{}:\n'.format(sol_num))
    print(sol)

I added the time limit because it seems like if you give it a broken puzzle (like, you enter a wrong number), it just hangs and ctrl+c won’t kill it, so you have to exit that terminal. However, the time limit doesn’t seem to work. Hmmm. I also made it print out all solutions it finds (though it’s usually just 1, unless you give it a really simple general puzzle).

How does it do?

It cranks the 9×9 from above in half a second:

That was actually an ‘easy’ one though, not having any blanks. For the hardest one I can find, the 8×8 hard, it actually takes about 5 minutes of sitting there on my Asus Zenbook, but it gets it!

The website notes that larger puzzles are harder than smaller ones, such that the easy 8×8 is “far harder” than the hard 5×5, by the way.

 

Welp, you get the point. I’m pretty sure it’ll slam anything that doesn’t have too many more blanks. I’ll probably make a post soon about my attempts on this puzzle through other, more handmade means, since this is honestly pretty black-box-y and feels a little like cheating (though it’s a very valuable tool!). I know only the very, very basics of what CP solvers are actually doing under the hood, so it’d be cool to solve it with something where I actually know how it functions.