{"id":37055,"date":"2017-02-28T06:00:21","date_gmt":"2017-02-28T11:00:21","guid":{"rendered":"http:\/\/www.shamusyoung.com\/twentysidedtale\/?p=37055"},"modified":"2017-02-28T13:14:53","modified_gmt":"2017-02-28T18:14:53","slug":"pseudoku-this-game-needs-filler","status":"publish","type":"post","link":"https:\/\/www.shamusyoung.com\/twentysidedtale\/?p=37055","title":{"rendered":"Pseudoku: This Game Needs Filler"},"content":{"rendered":"

Last time I made a solver to test puzzles for me. Once that was done, I could make puzzles like so:<\/p>\n

    \n
  1. Fill in the board with tiles.\n
  2. Pull tiles off one at a time while the solver looks at what remains. If I pull off a tile and the solver says it’s stuck, then put the tile back and remove a different one.\n
  3. Keep doing step 2 until I have a puzzle of the desired difficulty.\n
  4. Lock down all of the remaining tiles.\n
  5. Done.\n<\/ol>\n

    This is how I produced all of the puzzles in the builds I’ve released. Once this was done I shelved the project for about a year. But now that I’m back on it, I have to say step 1 is now the major roadblock to creating new puzzles.<\/p>\n

    It takes time<\/em> to fill in a board. Filling in the first 8 \/ 9ths<\/sup> of the board is trivial, but getting the last ninth into place can be tricky. Take this example:<\/p>\n


    \n

    You can't place the remaining 1 tile without violating the rules.<\/div>
    You can't place the remaining 1 tile without violating the rules.<\/div><\/p>\n

    This is what it’s like when you get down to the end. I need to add another 1 to the board, but there aren’t any valid spaces for a 1. So I’ll swap a couple of tiles around to make the 1 fit, but now maybe I can’t get the last 2 on the board. So I fix that but then 4 is a problem, and so on. It’s trivial to fix on 4×4 puzzles like the one above, but on a 9×9 this can actually take a while to sort out.<\/p>\n

    In the past I didn’t mind. Creating a filled-in board is basically a puzzle in itself. It was fun to do. But it’s also time-consuming and often not what I want to be working on at the moment. If you played some of my test builds, you may have spotted a few puzzles like this one:<\/p>\n

    You might not notice the repeating patterns right away if I didn't highlight them. But once you do see them, you can't UN-see them.<\/div>
    You might not notice the repeating patterns right away if I didn't highlight them. But once you do see them, you can't UN-see them.<\/div><\/p>\n

    I don’t know if I had any that were quite this flagrant, but this is a good example of a lazy puzzle layout. Rather than make a properly randomized puzzle, I just added things according to a nice orderly little system. The benefit is that you can fill in a 9×9 puzzle in less than a minute. The downside is that if the player notices the repeating patterns<\/a>, it trivializes the entire puzzle. Sudoku puzzles are not<\/strong> supposed to look like this. I circled a couple of repeating patterns for you, but the whole board is filled with groupings like this. I filled in the top row with the digits 1-9 in numeric order, and then changed as little as possible with each subsequent row.<\/p>\n

    I did this a year ago to quickly fill in boards for testing. I figured I’d replace them with proper puzzles if the project ever got off the ground. Then I forgot I’d done this, so when I returned to the project this year I ended up releasing these lazy boards to the public. <\/p>\n

    Whoops. Oh well. Crappy puzzles are a content problem, and generally content problems are easier to solve than technology problems.<\/p>\n

    For the record, a proper sudoku layout should look like this:<\/p>\n

    Ha! I've spotted a pattern: All of these squares contain the digits 1-9.<\/div>
    Ha! I've spotted a pattern: All of these squares contain the digits 1-9.<\/div><\/p>\n

    That’s a nice random layout. But it takes time to make those by hand. I need a way to fill in a board automatically.<\/p>\n

    I assumed there was some mathematical trick for doing this, but no. It turns out that board layouts are made through trial-and-error. Trial and Error<\/h3>\n

    I feel that mathematicians have overlooked the impact of Badonk Blockades on the game of sudoku.<\/div>
    I feel that mathematicians have overlooked the impact of Badonk Blockades on the game of sudoku.<\/div><\/p>\n

    I know the code should be simple to write, but I have no idea how long it will take to run. My hope is that I can get it under five seconds or so. Now that I’ve released my test builds to the public, the #1 requested featureAside from a “next puzzle” button, which I’ve already done.<\/span> is for a way for the game to generate random puzzles. If I can fill in the board in just a few seconds, then I’ll have everything I need to generate puzzles. But if it takes 30 seconds then I’ll just shelve the idea until later.<\/p>\n

    The rules are simple:<\/p>\n

      \n
    1. Working left-to-right, top-to-bottom, pass over the board looking for empty squares. (Instead of starting with a blank board, it can handle pre-existing tiles. This means I can make a puzzle that spells out “A BADONK BLOCKADE” using the letter tileset if I want to.)\n
    2. When it finds an empty square, it randomly places a new tile there that doesn’t violate the rules.\n
    3. If there is no valid tile for that space, then the puzzle is stuck. Back up to the previously placed tile, remove it, and try something different. If THAT one gets stuck, then it will back up to the previous, and so on.\n
    4. Keep doing this until the board is full.\n<\/ol>\n

      It takes about four minutes to fill in a blank 16×16 board. That’s way too long. Although to be fair, I’m deliberately throttling this code. Instead of having the program lock up until it finds an answer, it just works on it a little bit each frame while keeping the program running. It’s even animating stuff, so I can see tiles flying all over the screen at hyperspeed. I’m doing this because I want to watch the process work.<\/p>\n

      It works! The puzzle-filler successfully integrated a Badonk Blockade into a puzzle.<\/div>
      It works! The puzzle-filler successfully integrated a Badonk Blockade into a puzzle.<\/div><\/p>\n

      Sure, I could make the search run faster by having it run exclusively and halting rendering and animation until it’s over, but I’ve got a better idea…<\/p>\n

      When the auto-fill code places a tile, it hands the resulting board off to the solver code I wrote last year. The solver will reply with all of the forced moves. As in, “Based on the tiles currently in play, here are moves you’ll HAVE to make.” This doesn’t do much early in the process, but it’s a huge boost to the latter stages of filling the board. It lets the fill code spot doomed layouts far in advance, instead of needing to work through all of the permutations before giving up. It also means there will be less permutations to test later in the process, since more of the board will be filled in.<\/p>\n

      Now it takes almost exactly 30 seconds to fill in one of these 16×16 monster puzzles. A traditional 9×9 is done in under 5. <\/p>\n

      I now have the two major pieces needed to automatically generate puzzles. It can fill a board, and then pull as many pieces as possible off of it.<\/p>\n

      There’s still the matter of balancing the system. Right now it can only gauge puzzle difficulty by how many tiles are on the board at the start. I’ll need to come up with a way to appraise difficulty if I wanted to make a random puzzle generator. But that’s a problem for later in the project when I’ve got a group of playtesters to work with. In the meantime I have a bunch of annoying technology problems to solve.<\/p>\n","protected":false},"excerpt":{"rendered":"

      Last time I made a solver to test puzzles for me. Once that was done, I could make puzzles like so: Fill in the board with tiles. Pull tiles off one at a time while the solver looks at what remains. If I pull off a tile and the solver says it’s stuck, then put […]<\/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-37055","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\/37055","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=37055"}],"version-history":[{"count":0,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=\/wp\/v2\/posts\/37055\/revisions"}],"wp:attachment":[{"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fmedia&parent=37055"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Fcategories&post=37055"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.shamusyoung.com\/twentysidedtale\/index.php?rest_route=%2Fwp%2Fv2%2Ftags&post=37055"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}