Pseudoku: Understanding the Game

By Shamus
on Feb 14, 2017
Filed under:
Programming

There’s an old saying that programmers use to explain why you can’t use programming to solve particular problems: “You can’t write a program to do anything you don’t know how to do yourself.” The saying is used less these days now that most adults get what sorts of things computers can and can’t do, but back in the day you needed this for the not-yet-middle-aged baby boomers who thought of these new computer gadgets as magical thinking boxesTo be fair to the boomers: People in popular culture were REALLY bad at explaining them, and the movies of the day were full of nonsense dressed up to sound like computer science.. You needed a way to explain why you couldn’t just write a program to solve a crime, cure cancer, predict the stock market, or whatever it is they wanted a computer to figure out for them.

Writing a program to do something you don’t know how to do is impossible for the same reason that it’s impossible to give someone driving directions to a location you can’t personally find.

But the really goofy problems to solve are the ones where you only think you know how to do something, but really don’t. Or you do know how to do it, but not how to explain it.

Playing Sudoku turned out to be one of the latter types of problems.

Let’s jump back in time to January of 2016 when I was working on Pseudoku…

Playing the Game

I really need a way to make the game play a particular puzzle. I can design puzzles by hand, but that work is slow and if I make a mistake then I’ll end up with a broken puzzle. I need a way to prove that a puzzle is valid with mathematical certainty, as opposed to “I checked twice and it seems good. Ship it.” Because when it comes to logic puzzles, “I double checked it” is not good enough.

For those of you who read these entries but haven’t tried the builds I’ve put up: Sudoku is generally played on a 9×9 grid, but for the purposes of explanation I’m going to show the game being played on the simpler 4×4 grid. It looks like this:

Please do not write on your monitor in attempting to solve this.

Please do not write on your monitor in attempting to solve this.

Four rows, four columns, and four boxes. Each one must contain all four symbols.

In the example above, the right-most column is all filled in except for the bottom space. The only missing number is 1, which means a 1 goes there. That one’s easy. Now look at the space in the second row, second column, which I’ve highlighted in white. That space is part of the upper-left box, and that box already has a 1 and a 2 in it. So this empty space must be 3 or 4. But if you look to the right, there’s already a 3 on the same row. Therefore the highlighted space must be a 4. Which means the top-left is a 3. Which means… you get the idea. Following this sort of process of elimination, you can fill in the entire board.

The important thing is that you can fill in the board without ever making a guess. You could proveTo yourself, or whoever is standing behind you, creepily watching you play puzzle games. that such-and-such a space needs to be a particular symbol before you place it there. In fact, that’s more or less how you’re supposed to play. More importantly, there is one and only one valid way to fill in this board.

When you’re designing puzzles, there are two mistakes you can make. The obvious one is to make a puzzle that can’t be solved:

Bah! This looks easy. You just need to... uh... hang on. Um. Damn it, why can`t I get this?

Bah! This looks easy. You just need to... uh... hang on. Um. Damn it, why can`t I get this?

You can’t fill in those four empty spaces according to the rules. Somewhere, you’ll end up with two of the same symbol in a row, column, or box. This puzzle is broken.

But the more subtle problem is this one:

This puzzle is ambiguous, and ambiguity is forbidden.

This puzzle is ambiguous, and ambiguity is forbidden.

There’s more than one solution to this puzzle. You can put either a 3 or a 2 in the top-left corner and it works out either way. It’s obvious here in this simple example, but if you’re designing an advanced-level 9×9 puzzle – or worse, a 16×16 monster – then spotting these kinds of mistakes can be difficult for the same reason it’s hard for someone to spot typyos in their writingThe word typo was deliberitely wrong for comedic effect.. You know what you meant, and so you assume that’s what you didAlso the word “deliberitely” was wrong in the previous footnote in an attempt to create meta-humor. If there’s a typo in THIS footnote, it’s an accident. Or is it?.

So I need a way to have the computer check my work. Which means I need to make the game capable of playing itself.

Expressing Thoughts in Code

This seems like it should be straightforward. I know how to play Sudoku, so I should be able to write a program to do it. But it actually takes me a long time to drill down and work out the process that’s going on inside my head when I’m playing:

Me: Okay, so once you’ve eliminated the alternatives…

Computer: How do you do that?

Me: Oh. Well, that’s easy. You look for places where possibilities are precluded by other tiles already on the board.

Computer: Which tiles?

Me: Well the… relevant ones?

Computer: Which are…?

Me: Golly. I guess you just look at the board…

Computer: You’ll notice I don’t have eyeballs and I can’t see the gestures you’re making with your primate limbs. What are you asking me to do here?

Me: You know what? I’m asking you to run Witcher 3 now. Screw this coding stuff.

I know there are already implementations of Sudoku out there. There may even be open source versions. But I’m not interested in those because:

  1. I want to do this myself, because I’m like that.
  2. My game isn’t specifically built around the 9×9 layout, and if you read the various “How to beat Sudoku” guides they focus a great deal on layouts. I need a more generalized, abstract solution.

My game CAN do standard 9×9 sudoku layouts, but it can also do crazy non-standard layouts. In fact, the very first “puzzle” in the game is this:

How the hell am I supposed to solve this? Do I look like Ramanujan to you?

How the hell am I supposed to solve this? Do I look like Ramanujan to you?

That’s not a sudoku puzzle at all. The point of this puzzle is just to teach the player the basic idea that each group must contain 1 of each symbol. The next puzzle is one where the groups have a little bit of overlap. That is, an individual square might belong to both a row and a column. Once the player grasps how this constrains them in what moves are valid while also informing them of the solution, they’re given another puzzle where there’s even more overlap between the groups.

So really I need to forget the grid-like layout of sudoku and reduce the problem to something more abstract.

In my game, groups may be any size or shape. The only restraint is that all groups contain the same number of spaces.

Reducing the Problem to the Abstract

Hm. Is this puzzle broken, or am I just crap at this game? I can`t tell without a program to check my work.

Hm. Is this puzzle broken, or am I just crap at this game? I can`t tell without a program to check my work.

The first step is pretty obvious. Go over the board and look for occupied spaces. Say it finds a “3”. Go over all of the members of all of the groups this space belongs to, and mark them saying, “A 3 cannot go here.” On a sudoku board “every group” would mean the row, column, and region this space belongs to, because in sudoku every space belongs to exactly one row, one column, and one square region. But in my game groups can be any size and shape. A space might belong to five groups. Or to none. (Although I can’t imagine what gameplay purpose you’d have for a space that belonged to no groups. Still, it’s POSSIBLE.)

Once you’ve done that for the entire board, go over the board again. Look for spaces where all but one possibility has been ruled out. If you’re dealing with a puzzle with 4 tiles, then your logic is: “This space can’t be a 1, 3, or 4, so it MUST be a 2.”

Again, simple stuff.

This is a huge boost to my productivity. Just with this simple logic the code can solve a great number of easy and even some intermediate puzzles. But it can’t solve ALL puzzles. There are a lot of advanced techniques out there. My problem is that I can only make puzzles that my code can solve. (Because otherwise it won’t be able to check my work.) If my solver is too dumb, then my puzzles will be too simple. The better my solver, the more advanced my puzzles can be.

To really start cracking the hard ones, we need to use some advanced techniques.

I add a few that aren’t worth talking about, but they don’t really make a huge difference in the complexity of puzzles my code can handle. The big breakthrough comes when I implement a more complex version of the Hidden Twins technique.

Here’s a block of code from the source. The comments explain it pretty well. (Just read the bits in grey.) Note that within the code I called tiles “cards” because… uh. Look, it’s stupid. It’s also a long story. Maybe I’ll get into it later. Just ignore it for now.

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
//Often referred to as "hidden twin strategy". This involves looking for 
//cases where two or more tiles are restricted to the same cells. Example:
//Tile 1 can only go in spaces A or B
//Tile 2 can only go in spaces A or B.
//We don't have enough information to sort out which tile goes in A and which
//in B, but this scenario DOES tell us that all other possibilities can be 
//discarded from A and B. This might help reveal answers in other groups.
 
bool Solver::ThinkTwins (int group_number)
{
	vector<GLcoord2>   positions[CARD_TYPES];
	Group*		   g = &_group[group_number];
	GLcoord2	   pos;
	SolverCell*	   sc;
	bool		   accomplished_something = false;
 
	if (g->_solved)
		return accomplished_something;
	//For all the cells in this group...
 
	(a bunch of code goes here)
 
	//Now the positions array has been filled in. Now we need to compare
	//lists. We're looking for groups of cards that all have the same 
	//possible spaces, and the number of cards matches the number of spaces.
	//So we're looking for two cards limited to two cells, or three cards
	//limited to three cells, etc.
 
	(a bunch more code goes here)
 
	//The matches array is now filled with the numbers of all cards that 
	//have the same possible spaces. However, the number of spaces needs to 
	//be the same as the number of cards. (If three cards share 4 spaces, 
	//then it doesn't help us.)
	if (matches.size () != positions[candidate].size ())
		continue;
	//We have N cards on N spaces. We can now discount ALL other possible
	//cards from these spaces.
 
	(a WHOLE BUNCH of code goes here)
 
	return accomplished_something;
 
}

Whew. I’m glad I made those comments now. I know for a fact that when I return to this project in February of 2017 I’ll have forgotten all of this.

Here I have the edit interface enabled, so the solver is studying the board. It`s really hard to see in this screenshot, but the solver is saying a 3 should go in the bottom right, just to the left of the 9. This is correct, but without stepping through the code I can`t see how it`s getting that. It seems like the space above that one could ALSO have a 3, but the solver has apparently already proven that this is not the case.
Here I have the edit interface enabled, so the solver is studying the board. It's really hard to see in this screenshot, but the solver is saying a 3 should go in the bottom right, just to the left of the 9. This is correct, but without stepping through the code I can't see how it's getting that. It seems like the space above that one could ALSO have a 3, but the solver has apparently already proven that this is not the case.

This is a really powerful technique, and it overshadows just about everything else I’ve tried. The solver now sees possibilities I don’t. It sees so many that at first I think it’s a bug. I set up the solver to display the moves it has in mind, and in many cases I don’t get where it’s getting the moves from. They’re correct, mind you. It’s getting the right answer, but without stepping through the code I often can’t understand the leaps it’s making.

Which means that, in a strange way, it feels like I’ve violated the rule where you can’t write a program to do something you don’t know how to doI haven’t, of course. I understood the code I wrote. But it FEELS like I’ve broken the rule..

It’s been doing fine against “Medium” level puzzles from Websudoku. So now I try giving it a few “Hard” puzzles. It does fine with those, so I try “Evil”. It’s still able to crack them. In fact, I find an Evil puzzle where I can remove a tile and it’s still able to solve it.

I’m not claiming that I’ve made the greatest Sudoku bot in history or anything. This one still gets stumped by the occasional top-tier puzzle. I know there are much better ones out there. Lots of very smart people have been working on this for a long time.

But the important thing is that the bot is smart enough to help me create solid puzzles. What I’ve got is good enough for the creation of this game.

Enjoyed this post? Please share!

Footnotes:

[1] To be fair to the boomers: People in popular culture were REALLY bad at explaining them, and the movies of the day were full of nonsense dressed up to sound like computer science.

[2] To yourself, or whoever is standing behind you, creepily watching you play puzzle games.

[3] The word typo was deliberitely wrong for comedic effect.

[4] Also the word “deliberitely” was wrong in the previous footnote in an attempt to create meta-humor. If there’s a typo in THIS footnote, it’s an accident. Or is it?

[5] I haven’t, of course. I understood the code I wrote. But it FEELS like I’ve broken the rule.


2020202010There are now 90 comments. Almost a hundred!

From the Archives:

  1. Demo says:

    I don’t understand how the example is an application of ‘hidden twins’. It seems immediate that that square can’t be a 1,2,4,5,6,7,8 or 9 just from the other tiles it shares a group with. Am I looking at the correct tile ( (7,2) counting (horizontal,vertical) from the bottom left), not seeing the shapes of the groups or is this just a bad example?

    • Daemian Lucifer says:

      Its not the example of that specific rule,just how the end product can see stuff that Shamus cannot.

    • Shamus says:

      Like DL said, this might not be an example of the Hidden Twins. It’s hard to prove one way or another.

      But here is how it might be arriving at that conclusion:

      The bottom-right region needs an 8, a 2, and a 5. None of those can go on row 8. Which means it’s noticed that 8-2-5 all MUST go in the top 3 spaces, making them twins. You can’t tell what order they go in but it does prove that the top 3 spaces MUST contain them, and therefore the other space (the one where it’s suggesting a 3) CAN’T contain them.

      • silver Harloe says:

        It seems it could place a 3 there just by the first pass of the “can’t go” check. It can eliminate 1, 4, 6, 7, 9 by “in the same big square” and 2, 5, 7, 8, 9 by “in the same row” and 4 and 7 by “in the same column”, which only leaves 3.

        • Decius says:

          That is the trivial way.

          I find I can do most Sodoku just by alternating passes of “which nodes have all but one value trivially excluded” and “which values are excluded from all nodes in a group except one”, without needing to use the advanced techniques often.

  2. Thomas says:

    Loved this post!

    Also I don’t know what logic your code used, but the reason a 3 has to go in the bottom right corner is because that 3×3 square needs a 2, 3, 5 and 8 and there’s already a 2, 5 and 8 in the row where the empty space is.

  3. Martin Ender says:

    Minor typyo: “That space is part of the upper-right box, and that box already has a 1 and a 2 in it.” Should be “upper-left”, I think.

    Also your rule for what can be programmed probably needs a caveat for machine learning algorithms. It’s still true in that you could work through the algorithm by hand but I doubt most people understand how the computer ends up solving the problem. :)

    • Primogenitor says:

      “You can’t write a program to do anything you can’t do yourself given infinite time and resources.” is somehow less catchy.

    • WJS says:

      Not really; training an AI on a task is not programming, so the rule doesn’t apply. The entire point of machine learning is that you can get the behaviour you want without writing a specific algorithm yourself.

  4. Daemian Lucifer says:

    It’s getting the right answer, but without stepping through the code I often can’t understand the leaps it’s making.

    So did you add code later that while suggesting a move it also displays what technique was used for it?Because that would help you get on the right track.

    • silver Harloe says:

      Of course, the output for “what technique was used” in a given square would be something like
      * this can’t be a 1 because ReasonA
      * this can’t be a 2 because ReasonB
      * this can’t be a 4 because ReasonC
      etc

    • Zak McKracken says:

      Suggestion: Have the code display the lists of numbers excluded and/or not-excluded from any given tile, and maybe highlight hidden-twin couples. That should make it much easier to spot such things — if understanding the algorithm from within the GUI is something you want to be able to do.

  5. Da Mage says:

    I really like it when code starts to interact with itself to do things you never of thought of.

    I recently wrote a bunch of AI code and was testing it. After I while of testing I dropped another NPC into the level nearby, but assigned them to a different faction. When they got within sight (as determined by a ‘sight’ module) the faction system decided they were enemies, which kicked off the combat AI, so they ran at each other equipping armor and weapons, and fought to the death.

    I hadn’t written any code to deal with inter-NPC fighting, and yet the whole thing worked perfectly first go. None of the code is really very complex either, the combat AI is just a flowchart and the other stuff is simple line of sight and ‘happiness’ values. Yet it is really cool how you can lock down some really simple rules for a system, but it can appear like so much more.

  6. silver Harloe says:

    With neural networking and genetic algorithms, it’s actually possible to program a computer to do things you don’t know how to do, as long as you can tell when it’s been done (I don’t know how to play a guitar, but I can tell when someone is doing it right, and even often when they’re doing it wrong).

    For example: I don’t know how to tell letters apart. I mean, I can perform the task of telling letters apart, but I can’t describe how I do it. I just see an A and know it’s an A, even if it’s fuzzy, partially obscured by a foreground object, turned upside down, missing some pieces, or has to be inferred from the negative space of foreground objects that don’t entirely encompass where the A is. But programs have been written that can tell letters apart almost as well as I can – not that anyone knows how they do it, either. They were just trained (or evolved) to do it (most likely trained). Now some clever people have come up with partial algorithms, and whole pile of heuristics, to tell letters apart, and those can inform the design of the neural network (i.e. you can bias it towards edge detection by the connection layout, much like the layer of cells that does the same in our eyes), but I don’t believe anyone can sit down and just write “bool contains_letter( char letter, Image field )”

    Of course, I could be wrong in the specific example. I’ve not really kept up with AI much since college (which was 88-92, so, you know, a while ago), but I believe my first paragraph to be true.

    • Ian says:

      My favourite example of this is Google translate, which doesn’t “understand” a single word, yet manages to do a fairly good job anyway.

    • Daimbert says:

      Although it’s utterly hilarious when they get it wrong by finding a commonality in the test patterns that you didn’t think of. I remember the story of the connectionist system that learned to tell the difference between pictures of camouflaged tanks and ones that didn’t have them, got through the tests perfectly, but on the next test set failed miserably. They couldn’t figure out why until they realized that by coincidence the images with the tanks had sunny weather and the ones without were cloudy, and the system learned that pictures with sunny weather contained tanks [grin].

    • Daemian Lucifer says:

      But programs have been written that can tell letters apart almost as well as I can – not that anyone knows how they do it, either.

      But people

      do

      know how computers do it.

      Here,a video(part of a series) explaining in noob friendly terms how neural networks train to differentiate shapes:

      https://www.youtube.com/watch?v=BFdMrDOx_CM

      • Retsam says:

        I think you’re missing their point. They weren’t suggesting that neural networks just showed up one day out of the blue and nobody knows where they came from or how they work (obviously). But training a neural net is an algorithm that generate algorithms: understanding how the neural network training algorithm in general works isn’t the same as understanding a particular neural network works.

    • Retsam says:

      By definition you’re training the neural network to do something that you already know how to do. You can’t train the neural network to play guitar, either, but you can train the neural network to identify when guitar is being played well or not. You can use neural networks to solve problems that you can solve but can’t explain how you solve it.

      Evolutionary algorithms are perhaps a better example of “training a computer to do something I don’t know how to do”. If you can write an algorithm that identifies when music sounds good or bad (perhaps a neural network), you could then use that network as a fitness function on an evolutionary algorithm which would try to “evolve” sequences of notes that sounds good, according to the neural network.

  7. Mephane says:

    Shamus, how long does it take for the solver to solve, say, a standard 9×9 puzzle? Would it be feasible to write a Monte-Carlo style puzzle generator that essentially works like this:

    10: The board is empty.
    20: Place a random number in a random empty field.
    30: Call the solver and check what it says.
    40: Solver says puzzle works. GOTO 70.
    50: Solver says puzzle is ambiguous. GOTO 20.
    60: Solver says puzzle is invalid. Undo last step and then GOTO 20.
    70: END.

    • Echo Tango says:

      (My comment is related, so it goes here.)

      Shamus:
      In the blog post, you keep saying that some puzzles “cannot” be solved by your solver, but you never mention speed. Was your solver just too slow, so it’d need a supercomputer* to solve; or were there just some puzzles, where your solver ran out of valid ways to add new pieces, and still had spaces left to fill in?

      * Or waiting around for 1000 years for an answer.

      • Matt Downie says:

        There’s a Sudoku Solving Algorithms page on Wikipedia. Essentially, the fewer clues you have, the bigger the search space, so if you’ve got one of those minimalist 17 number grids, you’ve got a problem.

      • Shamus says:

        I’ve never really timed the solver, but it’s fast “enough”. In edit mode it attempts to solve the puzzle every time you change the board. It’s generally fast enough that you can’t “feel” it happen, which means it runs in a faction of a second. On the big 16×16 puzzles you can feel the interface hitch for a split second when there’s a lot of empty squares, so I’d say the largest puzzles take maybe a half second to solve.

        It makes no attempt to brute-force a solution. If it can’t narrow the possibilities down, then it gives up and says it’s stuck.

        • James Bennett says:

          I wrote a solver for 9 x 9 sudoku grids a while back that used various techniques. It could solve most puzzles deductively, but there were a few that it would get stuck on. I studied those grids and I couldn’t figure out a good technique to solve them deductively. I added code so that if the solver got stuck it would make a guess about what one of the squares was and move forward from there. If the board was unsolvable it would back up, remove that number from the list of possibilities for that square, and try again.

        • newplan says:

          Here’s an alternative approach that will get you 100% of the possible puzzles – not sure about how computationally expensive it is.

          1) Solve as much as you can with your current methods

          If it gets stuck:

          2) Brute force the rest of the puzzle
          3) Check the generated solution for ambiguity – either in a clever way or by doing checking each cell if swapping with each other cell in each group (rows, columns and squares) results in a legal puzzle. If you can’t swap any cells, congratulations – you have a unique solution. If you can, discard the puzzle.

          My amateur $0.02.

    • Daemian Lucifer says:

      If you are to brute force a sudoku,theres no need for randomness.Start from the first epmty square and fill them in as you go along.

      • Echo Tango says:

        Yeah, stuff like Monte Carlo is more useful where you have some algorithm which is known to only give a probably-very-good solution, and not a guaranteed-perfect solution*, and the solution depends on some changeable input besides just the problem you’re actually trying to solve. i.e. Randomize my starting state, get good solution, randomize again, get another solution, keep going until my solutions are within some bounds of “close” to each other in “goodness”, or until maximum time has elapsed.

        * Those types of problems are usually not 100% solvable in practical amounts of time.

      • Exasperation says:

        I think you’re misunderstanding what they’re asking here. They’re not talking about starting with a puzzle and brute-forcing a solution. They’re talking about starting with an empty board and randomly generating puzzle elements until they have enough elements in place that the (non-brute-force) solver can provide a unique, valid solution, and then stopping (to get a procedurally-generated random-but-solvable puzzle). Taking the randomness out of it would give you an algorithm that always produces the same puzzle, which isn’t very useful for producing content.

  8. Ian says:

    I wrote a Kakuro solver once, and ended up coding the exact same thing. Kakuro has similar rules to Sudoko in that each number can only appear once in a given set of “tiles”, which leads to the same hidden twins/triples/etc problem.

    I coded a bunch of different solution algorithms in the end, but never managed to solve this beast.

    • Echo Tango says:

      After heavily skimming that Wikipedia page, it seems like Sudoku is just a simplification / subset of Kakuro. :P

      • Syal says:

        …sort of? Kakuro have actual math, include dead spaces on the board like crosswords do, and don’t require equal number distribution.

        • Echo Tango says:

          Correct. It is a strict superset[1], because if you disallow dead spaces, change the math to be “all rows and columns always add up to X”, and the number distribution to be “every row or column must contain every number” – that’s Sudoku! i.e. Sudoku is just a simplified / degenerate instance of Kakuro. :)

          [1] Again, I haven’t read the full rules of either game, but from what I know of them, this appears to be the case.

          • Axehurdle says:

            Is this true? I haven’t done much Kakuro but from my experience it doesn’t have any system that replicates the box regions in a sudoku puzzle. You can write a kakuro with an empty grid where every row and column add up to 45 but you can’t make every 3×3 box have to add to 45 without introducing additional rules. So you can’t exactly replicate a sudoku puzzle in normal kakuro. I think.

            • Syal says:

              Standard Kakuro also starts empty, no number placements, only sums, so that’s another change.

              I think the superset is actually “deductive puzzle without external clues”. You’ve got your Kakuros, your Sudokus, your Picross.

            • WJS says:

              At least according to wiki, Kakuro doesn’t have any rules about how many of each number there must be, just the sum. There are far more ways to sum 9 numbers to 45 than simply the numbers 1-9. For example, fill the grid entirely with fives. All rows, columns, and 3×3 squares will sum to 45, but it’s not a valid Sudoku answer.

  9. mzlapq says:

    A significant part of the advancement in AI comes from the increased power of computers. The computer does stuff people can’t do because of the slow and easily distracted human brain.
    I think that you’re writing a lot of code to do things you know how to do and describe instead of letting the computer sort it out recursively, checking if all partial solution of a recursion agree for some tile/position.
    All methods described in the hidden twins link seem to be methods to select the depth of the recursion and the next tiles/positions to focus on .
    When you get a good solver, the real problem is how to decide the difficulty for humans.

  10. Louis says:

    I think you would have better luck if you didn’t try to teach it to solve sudoku like a person would with a set of specific techniques. If you express the problem as a series of constrains on each square and then use a constraint solver it will cover all possible cases without special casing them. I would look at https://en.m.wikipedia.org/wiki/AC-3_algorithm for some pseudo code.

    If I remember correctly though, some harder sudoku problems come to an ambiguous point where the solver is required to make a guess, continue solving, and then backtrack if the guess resulted in an incorrect board.

    • silver Harloe says:

      writing your sudoku solver in Prolog is cheating :)

    • Nixitur says:

      I’m pretty sure that constraint satisfaction solvers in general do not guarantee a unique solution. So, while it’s useful for solving sudokus, it’s not useful for testing if you’ve generated a valid one. The pseudocode is a bit vague, but I think this applies to AC-3 as well.

  11. Piflik says:

    Not sure if you implemented this, since you didn’t mention it in the Hidden Twins section, but having 1 and 2 in cells A and B does not only remove all other numbers from A and B, but also eliminates 1 and 2 in all other cells that belong to groups that contain both A and B.

    • Decius says:

      It also prohibits any cases where a group that contains A xor B contains 1 and 2, which can create additional information.

      I end up counting them as fractional numbers; if I have what is here called a “twin”, I treat it like half a 1 and half a 2 in each node, and apply the constraint that no group can have as much as 2 of any number.

      I’m sure that causes some problems because I occasionally fail using methods that I have given equal rigor to developing.

  12. Dev Null says:

    So we’re looking for two cards limited to two cells, or three cards limited to three cells, etc.

    I played with a solver of my own at one point. Couple of points about this rule, which I’m sure you’re aware of, but I found kind of interesting:

    1) You’re using that rule to conclude that the N cells can have no other cards. But once you’ve identified them, you can also conclude that no other cells that share the same groups with those N cells can have those cards. (e.g. a row with only two cells that have a 1 and a 2 in them. Those cells can only be 1 or 2, _and_ no other cells in the row can be 1 or 2.)

    2) Once you implement #1, you can generalise your first simplistic step – eliminating duplicates – as simply the case where N=1, and use the same code. (e.g. a row with a cell that has only a 3 in it can only be 3, _and_ no other cells in row can be 3.)

    It pleased me when the simple obvious rule turned out to just be a special case of a more complex one, rather than something separate? Yeah ok; so I’m weird.

  13. EricF says:

    Solving really is just alternating between two algorithms:

    1. Are there exactly N numbers that can legally go in these N locations (within a group)?

    2. Are there exactly N locations for these N numbers (within a group)?

    In the beginning, consider all numbers to be valid options for all locations. Ask the above questions for each possible permutation, and each time you get a “yes” eliminate all other numbers from those cells, and eliminate those numbers from any other cells within the group.

    Start with N = 1, and move up from there. When you reach N > max/2, re-start at N = 1.

    This will solve everything but the most fiendish puzzles, where the “hidden twins” actually jump across groups.

  14. Philadelphus says:

    Regarding puzzles being ambiguous: eh, just market it as a “systems-based game with multiple solutions.” People like those, right? Increases replayability.

    But seriously, interesting stuff reading about the solver.

    • Syal says:

      Ooh, Sudoku with branching paths; you solve a puzzle one way, it leads to another puzzle, you solve it the other way it leads somewhere else.

      And then you can lock new tilesets behind the other paths! The Sudoku of Isaac!

  15. D-z says:

    This reminds me of a recursive implementation of a Towers of Hanoi solver I had to do back in school. The algorithm was dead simple: to move N disks from A to C, move N – 1 disks from A to B, move the bottom disk from A to C, then move the N – 1 disks from B to C. Two recursive calls, three lines of code. It felt like it didn’t do a hundredth of what it needed to — yet it worked.

    I still can’t solve the towers of Hanoi myself.

  16. King Marth says:

    I had some phone sudoku game that I played on and off to fill time, and I remember the moment when some new technique clicked for me – I don’t remember the technique itself, but it could’ve been Hidden Twins. I could suddenly jump up a difficulty tier without trouble, and the timewasting easy puzzles with at least one obvious move at all times became boring.

    One of my favourite definitions of computer science is “Explaining how to solve problems so simply that even a computer can understand it.”

  17. Dt3r says:

    “…in many cases I don’t get where it’s getting the moves from. They’re correct, mind you. It’s getting the right answer, but without stepping through the code I often can’t understand the leaps it’s making.”

    Haha, that sounds like me using machine learning to build models for biological datasets. Even when you understand the building blocks, the combined result can sometimes get away from you. Thankfully you can actually look at the code. For some techniques (e.g. artificial neural networks) this gets a lot more problematic…

  18. Steve C says:

    Are you going to use the solver as a system to give in-game hints to players?

  19. Benjamin Hilton says:

    In my experience the confusion about what computers can and can’t do still exists today, even in younger generations. Just a few years ago in college, a friend of mine asked myself and another CS major help her with a project, and we quickly realized that she thought computers were….like AI or something. Whenever we told her something wasn’t feasible she would say “well can’t you just tell the computer to do X?”
    And for the record this wasn’t a ditzy person either. She had published books out even in while still in school and was an accomplished pianist….she just had some serious misconceptions about technology.

  20. Ingvar says:

    Last time I ended up writing a sudoku solver, I implemented a somewhat guided almost-brute-force solver with backtracking (and thanks to having the weirdest exception handling known to man, used “exceptions” to handle both “board solved” and “board has more than one solution” conditions).

    And by the “weirdest exception handling known”, I simply mean that there’s a mode where you can signal an exception and handle it without unwinding the call stack. That means that you can do wonderfully useful (but weird) stuff.

    Typical run-time for a 9×9 classic board was, um, “definitely sub-second”, but I can’t recall how sub-second. I also cannot recall the exact heuristic used, but I think it was “find possible moves using only the square, row and column; randomly pick one of the possible moves from one of the squares with the most possible moves” (that does, in general, tend to weed the call tree the most) and at each level simply remove moves that have proven (at that board position) impossible.

    The implementation that actually reasoned about Sudoku was slower and required an awful lot more intelligence to write. It was, arguably, more fun to write, though.

  21. The Rocketeer says:

    This post was a fantastic success at making me want to play more Picross. Granted, this is not difficult to accomplish.

    More seriously, it reminds me of a specific trouble I’d been having with Picross lately— specifically, with a certain mode in Pokémon Picross.

    Now, I’m an old hand at Picross; Super Mario Picross for the SNES is one of my most-played games of all time, and one I return to periodically as a sort of palate cleanser between more substantial games. So, most Picross techniques are second nature to me.

    But in Pokémon Picross, you can unlock an “Alt Mode” after completing all standard puzzles, and these represent the numbers in a different way, using a number in a black box stretched across two rows or columns to indicate that these two rows or columns share a contiguous block of the indicated number of marked spaces. You can see one such puzzle solved here, for instance.

    Where this becomes relevant to this post is that, as part of the “Pokémon” conceit of the game, the player can set a party of up to five Pokémon (“captured” by solving the puzzle that depicts them), each of which has some ability related to their type: abilities that automatically solve rows or columns, abilities that stop or slow the timer, abilities that automatically correct player mistakes, etc. The relevant ability, called Blue Force, indicates rows or columns that contain squares which may be filled or x-ed out by logical deduction, indicating this by representing in blue the numbers by the rows or columns in question.

    This is probably the handiest ability, and I was impressed and pleased that even in standard mode, Blue Force’s insistence that a row or column could be progressed logically despite my blindness to the means led to rare improvements even in my practiced technique.

    In Alt-Mode, though, Blue Force revealed just how out of my depth I was with the unfamiliar conjoined rows and columns, frequently insisting that logical progress was possible in places where I couldn’t begin to comprehend, and even now I feel I haven’t quite come to grips with the mode’s higher nuances despite having recently 100%’ed the game. I’m keenly interested in rounding out my technique with the challenging alternate mode, but, unfortunately, I don’t think the puzzles in Pokémon Picross are very good, for the most part. (Part of the problem is that Pokémon, the sole domain of the puzzles, naturally enough, don’t look like fucking anything when reduced to even the largest grids (15×20) used in the game.)

    • silver Harloe says:

      Part of the problem is that Pokémon, the sole domain of the puzzles, naturally enough, don’t look like fucking anything when reduced to even the largest grids (15×20) used in the game

      https://pics.onsizzle.com/when-i-was-your-age-this-was-a-dragon-and-13758381.png

    • Syal says:

      …and you’re sure Blue Force wasn’t just confused and broken by the new layout?

      • The Rocketeer says:

        Without a perfect understanding of the logic or some sort of conclusive proof it’s wigging the hell out, I can’t really say. Frequently, I would spend lots of time looking at one of these linked rows when Blue Force indicates there’s a deduction to be made, even when I don’t see how, until I suddenly realized how I was supposed to arrive at the conclusion it was hinting at. More generally, I’m predisposed to trust a computer’s evaluation of a logical system over my unpracticed incredulity.

        • Decius says:

          Does it assume that the marked pixels are correct when telling you that the deduction is trivial?

          Because the only way I know to solve he entire line is when the total of pixels to be marked and groups is one more than the length of the line. Subdividing the line into smaller lines and finding paritial solutions based on overlaps (if there are a small number of possible results and all of them have pixels in common…) is the only fun part.

  22. tmtvl says:

    This article made me look up Rosetta Code. Now I kinda want to try and work it out in UML.

  23. Allen says:

    Ironically, this article is why sodokus bore me – they set off my “I could just solve for this” radar and then it just feels like drudge work to be doing by hand something I should be automating. :)

  24. John Beltman says:

    Hi Shamus,

    I am not sure exactly what you are using this for in the game but I feel like, conceptually, you are doing the wrong thing.

    You are writing a game to create Sudoku puzzles, so you should have written a tool to create Sudoku puzzles.

    What you seem to be doing is attempting to create a puzzle, then using the procedure described above to attempt to solve the puzzle and determine if it is valid.

    What you could have done is start with complete grids of whatever size or shape you decide, then remove numbers from it according to the rules selected.

    This way you are only creating valid puzzles.

    This has the added benefit that you can manipulate:
    – how many numbers you remove, and
    – what rules you choose to use
    to manipulate the difficulty of the puzzles created.

    Regards,
    John.

  25. John Beltman says:

    So I think what you are doing is this:

    1. While puzzle is not solvable
    2. create puzzle
    3. try to solve puzzle
    4. end while

    What you could have done is this:

    1. create puzzle

    • tmtvl says:

      And how do you propose to do that without:
      A) Having a solver test the puzzle at each iteration to make sure you’re not creating an unsolvable puzzle and
      B) Simply re-using the same puzzle over and over again?

      • John Beltman says:

        As I suggested above, build a tool that will create valid puzzles. Then you don’t need a solver to check it.

        I don’t know how to do it. I think going the other way is more time consuming but also easier.

        The strange thing is that people have been creating sudokus for years and I doubt that they had a brute force tool to check their work. So how are they making sure there is only one way to solve their puzzles? I assume they must be using some rules to create them.

    • Nixitur says:

      No, he couldn’t have done that. Did you even read the article? Guaranteeing that there is a solution is not that hard, but makin it unique is the problem. Shamus explicitly mentions that.

  26. Blue_Pie_Ninja says:

    Footnote 4 has a schrodingers typo in it. ‘Honor’ is a typo in the English sense, but is not a typo in American English, so it is both a typo and not a typo at the same time. Too meta?

  27. “So I need a way to have the computer check my work. Which means I need to make the game capable of playing itself.”

    Sure. But depending on the type of puzzle you could also do it the opposite way. Create some simple code that generate the solutions, then you make some code that create the problem.

    If you always start with the solution it will always be solvable, provided that the… let’s call it “the scrambler” isn’t bugged.

  28. MaxEd says:

    A few years ago, I decided to re-create a puzzle from Electronics mini-game from Sid Meier’s Covert Action (do try this game – even though Sid himself dislikes it, it actually has some great ideas which I would like to see reused someday!).

    I really had no idea how to solve those puzzles on hard levels though (I always played on low difficulty). So power of AI to the rescue! I wrote a genetic algorithm that generates a valid layout of a board (a solution), and then switches a few elements around to create a puzzle (without violating the rules, of course). This way, I was able to teach the computer to do something I had no idea how to do myself :) That’s why I love AI techniques such as genetic algorithms and neural networks.

  29. Decius says:

    There’s always the seive method of ensuring uniqueness: generate all legal complete Pseudoku of the arrangement desired, and each time you add a number remove all inconsistent ones from the array and count the first two.. When exactly one remains, the solution is unique.

    The resulting puzzle might not be soluble by any method known to man.

  30. Mike says:

    Was rather enjoying the game. About halfway through I switched computers and went from Windows 7 to Windows 10, and now have problems. The main problem is that the bottom 5% or so of the screen doesn’t seem to be reachable by the mouse. It looks like there’s an offset or something so when I would get down to the bottom 5% it instead goes to my taskbar. It also runs off the top of the screen, which isn’t nearly as big an issue. I’ve tried alt-space, X to maximize it (since I can’t see the control icons in the top right), but that didn’t work. Considering I really don’t like the shapes and prefer numbers, but can only change that with an icon at the bottom of the screen, that’s a problem…

    • Mike says:

      BTW, if anyone is looking at this and having the same issue (or if Shamus wants to address the issue in the code), I updated the “Change the size of text, apps, and other items” in the Display settings under System in Windows 10 from 150% to 125%, with a resolution of 1920×1028, and it now works correctly with the mouse not running off the window before I actually get to the bottom of the window.

  31. WJS says:

    Interesting, since my solution would have been to store which tiles could be placed at each location, then iterate removing ones that were blocked by other tiles. It’s functionally identical, of course, but my instinct would have been the exact opposite.

    I think an interesting question is how much assistance to give players? I can see a number of hints you could give:
    – When holding a tile, highlight all similar tiles on the grid
    – When holding a tile over a slot, highlight tiles that would block that placement in red
    – When you place a tile in a slot, highlight tiles that block each other in red
    – When you mouse over a slot, show which tiles could possibly go in that slot
    …and so on, and so on. It might be cool to be able to turn hints like these on for players who are struggling with the game and for whom the tutorial isn’t quite enough.

  32. Some nerd says:

    Maybe you don’t want to, because it’s looking at someone else’s solution, but I recommend taking a read through Peter Norvig’s Sudoku solver paper.

    http://www.norvig.com/sudoku.html

    Apparently, Sudoku is NP hard in the general case, but 9×9 still doesn’t take too long. You could add a depth-first brute forcer to your solver and it would be able to solve every puzzle that can be solved. That’s how I made mine way back when I played with this stuff: get as far as possible using simple rules, then guess and check. Of course Dr. Norvig’s code is better than mine was.

    It will even help you prove uniqueness, if you tweak it a bit.

  33. Magicnation says:

    I just want to say that as a longtime Sudoku enthusiast, I’ve really enjoyed the formatting of your little game thus far! It’s really attractive and simplistic and I like the variation in layout.
    I also want to thank you and congratulate you for doing a good job on the tutorial/introduction levels. I just sat with my little(est) brother while he went through them. He’s only nine and has never played Sudoku before and never wanted to, but your tutorial levels were very effective at both teaching him and capturing his interest. We’ve played through several of the levels together already. You’ve done a great job with this, I think, and if we encounter any problems we’ll be sure to let you know! Thanks again!

  34. kdansky says:

    Implicitly, this demonstrates why I think most Puzzle games are bad: If I can write a relatively simple algorithm that does not rely on pure brute force alone, then what’s the point of me doing the puzzle at all? At that point, I can literally just go through the motions myself, and execute the algorithm in my head. That is not a challenge or interesting, that is just tedium.

    It’s like asking me to sum up all the numbers between 1 and 10’000 without knowing the short-cut formula: Doable, boring and not exactly a puzzle.

    Sudoku falls in that category: It’s not really a puzzle, it’s just a time-consumer.

  35. Brandon says:

    Maybe this comment won’t prove helpful to you, but I hope it does. I have no interest whatsoever in playing anything like this on my PC, but I could see buying 4 copies for my parents and in-laws tablets in a heartbeat. I realize the Android, Amazon, and Apple app stores are a whole other can of worms. But know that once this is out there, if it proves popular, you will be cloned in those markets. My advice is head it off now. There are some dev environments that will let you do multiplatform development for mobile. For a concept like this, definitely worth it.

Leave a Reply

Comments are moderated and may not be posted immediately. Required fields are marked *

*
*

Thanks for joining the discussion. Be nice, don't post angry, and enjoy yourself. This is supposed to be fun.

You can enclose spoilers in <strike> tags like so:
<strike>Darth Vader is Luke's father!</strike>

You can make things italics like this:
Can you imagine having Darth Vader as your <i>father</i>?

You can make things bold like this:
I'm <b>very</b> glad Darth Vader isn't my father.

You can make links like this:
I'm reading about <a href="http://en.wikipedia.org/wiki/Darth_Vader">Darth Vader</a> on Wikipedia!

You can quote someone like this:
Darth Vader said <blockquote>Luke, I am your father.</blockquote>