{"id":36970,"date":"2017-02-14T06:00:29","date_gmt":"2017-02-14T11:00:29","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=36970"},"modified":"2017-02-14T06:43:55","modified_gmt":"2017-02-14T11:43:55","slug":"pseudoku-understanding-the-game","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=36970","title":{"rendered":"Pseudoku: Understanding the Game"},"content":{"rendered":"

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.<\/span>. 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.<\/p>\n

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. <\/p>\n

But the really goofy problems to solve are the ones where you only think<\/strong> you know how to do something, but really don’t. Or you do know how to do it, but not how to explain it. <\/p>\n

Playing Sudoku turned out to be one of the latter types of problems. <\/p>\n

Let’s jump back in time to January of 2016 when I was working on Pseudoku… <\/p>\n

Playing the Game<\/h3>\n

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.<\/p>\n

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:<\/p>\n

Please do not write on your monitor in attempting to solve this.<\/div>
Please do not write on your monitor in attempting to solve this.<\/div><\/p>\n

Four rows, four columns, and four boxes. Each one must contain all four symbols. <\/p>\n

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. <\/p>\n

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.<\/span> 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<\/strong> valid way to fill in this board. <\/p>\n

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:<\/p>\n

Bah! This looks easy. You just need to... uh... hang on. Um. Damn it, why can't I get this?<\/div>
Bah! This looks easy. You just need to... uh... hang on. Um. Damn it, why can't I get this?<\/div><\/p>\n

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.<\/p>\n

But the more subtle problem is this one:<\/p>\n

This puzzle is ambiguous, and ambiguity is forbidden.<\/div>
This puzzle is ambiguous, and ambiguity is forbidden.<\/div><\/p>\n

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.<\/span>. 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?<\/span>.<\/p>\n

So I need a way to have the computer check my work. Which means I need to make the game capable of playing itself.<\/p>\n

Expressing Thoughts in Code<\/h3>\n

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:<\/p>\n

Me: Okay, so once you’ve eliminated the alternatives…<\/p>\n

Computer: How do you do that?<\/p>\n

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

Computer: Which tiles?<\/p>\n

Me: Well the… relevant ones?<\/p>\n

Computer: Which are…?<\/p>\n

Me: Golly. I guess you just look at the board…<\/p>\n

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?<\/p>\n

Me: You know what? I’m asking you to run Witcher 3 now. Screw this coding stuff.<\/p><\/blockquote>\n

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:<\/p>\n

    \n
  1. I want to do this myself, because I’m like that.\n
  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.\n<\/ol>\n

    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:<\/p>\n

    How the hell am I supposed to solve this? Do I look like Ramanujan to you?<\/div>
    How the hell am I supposed to solve this? Do I look like Ramanujan to you?<\/div><\/p>\n

    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. <\/p>\n

    So really I need to forget the grid-like layout of sudoku and reduce the problem to something more abstract.<\/p>\n

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

    Reducing the Problem to the Abstract<\/h3>\n

    Hm. Is this puzzle broken, or am I just crap at this game? I can't tell without a program to check my work.<\/div>
    Hm. Is this puzzle broken, or am I just crap at this game? I can't tell without a program to check my work.<\/div><\/p>\n

    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.)<\/p>\n

    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.”<\/p>\n

    Again, simple stuff.<\/p>\n

    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<\/a>. 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.<\/p>\n

    To really start cracking the hard ones, we need to use some advanced techniques. <\/p>\n

    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<\/a>.<\/p>\n

    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.<\/p>\n

    \r\n\/\/Often referred to as \"hidden twin strategy\". This involves looking for \r\n\/\/cases where two or more tiles are restricted to the same cells. Example:\r\n\/\/Tile 1 can only go in spaces A or B\r\n\/\/Tile 2 can only go in spaces A or B.\r\n\/\/We don't have enough information to sort out which tile goes in A and which\r\n\/\/in B, but this scenario DOES tell us that all other possibilities can be \r\n\/\/discarded from A and B. This might help reveal answers in other groups.\r\n\r\nbool Solver::ThinkTwins (int group_number)\r\n{\r\n\tvector   positions[CARD_TYPES];\r\n\tGroup*\t\t   g = &_group[group_number];\r\n\tGLcoord2\t   pos;\r\n\tSolverCell*\t   sc;\r\n\tbool\t\t   accomplished_something = false;\r\n\r\n\tif (g->_solved)\r\n\t\treturn accomplished_something;\r\n\t\/\/For all the cells in this group...\r\n\r\n\t(a bunch of code goes here)\r\n\r\n\t\/\/Now the positions array has been filled in. Now we need to compare\r\n\t\/\/lists. We're looking for groups of cards that all have the same \r\n\t\/\/possible spaces, and the number of cards matches the number of spaces.\r\n\t\/\/So we're looking for two cards limited to two cells, or three cards\r\n\t\/\/limited to three cells, etc.\r\n\r\n\t(a bunch more code goes here)\r\n\r\n\t\/\/The matches array is now filled with the numbers of all cards that \r\n\t\/\/have the same possible spaces. However, the number of spaces needs to \r\n\t\/\/be the same as the number of cards. (If three cards share 4 spaces, \r\n\t\/\/then it doesn't help us.)\r\n\tif (matches.size () != positions[candidate].size ())\r\n\t\tcontinue;\r\n\t\/\/We have N cards on N spaces. We can now discount ALL other possible\r\n\t\/\/cards from these spaces.\r\n\r\n\t(a WHOLE BUNCH of code goes here)\r\n\r\n\treturn accomplished_something;\r\n\r\n}<\/pre>\n
    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.<\/p>\n
    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.<\/div>
    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.<\/div><\/p>\n
    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<\/em>, mind you. It’s getting the right answer, but without stepping through the code I often can’t understand the leaps it’s making.<\/p>\n
    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.<\/span>. <\/p>\n
    It’s been doing fine against “Medium” level puzzles from Websudoku<\/a>. 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. <\/p>\n
    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<\/strong> there are much better ones out there. Lots of very smart people have been working on this for a long time. <\/p>\n
    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.<\/p>\n","protected":false},"excerpt":{"rendered":"
    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 […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[66],"tags":[],"class_list":["post-36970","post","type-post","status-publish","format-standard","hentry","category-programming"],"_links":{"self":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/36970","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcomments&post=36970"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/36970\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=36970"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=36970"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=36970"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}