-
Notifications
You must be signed in to change notification settings - Fork 1.3k
New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
Tiles puzzles always unsolvable? #41
Comments
All the tiles puzzles are guaranteed to be solvable. If the code generates a tiles puzzle that is unsolvable then please include a screenshot. The code to produce the scrambled puzzle is in load(): tiles[mark] = None # One tile is removed - "mark" is the empty tile.
for count in range(1000): # Do a thousand "swaps".
neighbor = choice(neighbors) # Choose a random neighbor.
spot = mark + neighbor # Calculate an adjacent tile based on mark and neighbor
if spot in tiles: # If the randomly chosen neighbor is in the set of tiles (e.g. it's valid)
number = tiles[spot] # Swap the randomly chosen "spot" with the current "mark"
tiles[spot] = None
tiles[mark] = number
mark = spot # Update the "spot" to be "mark" The code simulates a thousand moves of the tiles (at random) to produce the scrambled version. Since the tiles were moved from the "solution" state to the "scrambled" state using valid swaps then it must be possible to undo them. Therefore every scrambled puzzle must be solvable. |
Thanks for the reply! I understand the code much better now, and while I understand what you're saying, the game always seems to land on unsolvable puzzles. Not sure why, I'm thinking about it now. I confirmed that they are indeed always unsolvable. I tossed my code and just added back the logic to check for inversions and which row the blank is on. Please see attached screenshot and modified tiles game file. I was able to make it so that odd-width games work by modifying the 'tap' function so that it finds which box you're clicking instead of using a float to normalize the number to match a box. I added variables for board width, height, tile size, etc. This has been a fun learning experience. I'm sure you're much more experienced than I am, but should I send what I have so you can see what I've done in case you want to pull it? |
Sorry, I'm realizing I didn't explain the screenshot very well. For an even-width grid, if the blank is on an even row, the number of inversions needs to be odd. If the blank is on an odd row, the inversions need to be even. As you can see in the screenshot, it's always generating puzzles that don't meet those criteria. I clicked through about 5 puzzles and ended up with 15 and 14 swapped, which is unsolvable. That's when I entered the rabbit hole haha |
Your criteria is wrong. Try setting the 1,000 in the code I showed you to 10 and printing all the shuffle steps. |
Sorry, what do you mean by my criteria being wrong? The rules I laid out are unarguably the rules that decide whether a puzzle is solvable, and this is born out by trying to solve the puzzles. If you feed the orientations into a tool like this: You'll see that the results are unsolvable. Although, I don't think this tool takes into account which row the blank is on so keep that in mind. Can you describe why I'd be setting 1000 to 10? This is just the number of shuffles that the puzzle gets right? |
they are generated backwards pulled fresh from github (1 in the bottom left corner). I think the array should be reversed before shuffling, as 1 goes at the top left not the bottom. |
Pull request welcome. |
It may be just me, but I started building in a "solvable" check for the tiles generated. To boil it down, I used two rules:
If neither of these rules are true, the puzzle is unsolvable.
The problem is, when I put this logic into place, the game generated puzzles that were unsolvable 100% of the time.
I was able to fix the problem by taking the values (numbers) of tiles variable and shuffling that, then rejoining the keys and values of the tiles dictionary. Once this was done, the game generates solvable puzzles as often as not.
It may be obvious by now that I have no idea what I'm doing haha but I'm trying to learn!
Is it just me, or are the puzzles always unsolvable, and why might this be? I'm staring at the original code, but I have no idea how 1-15 is arrived upon, as the ranges involved are much larger, such as 100, -200, 100, etc...
I'm not sure if it'd be worth doing a pull request for the 'check solvable' logic when done; I'm sure many other people who actually know what they're doing are involved in this project. Maybe it could be described as a suggested exercise at the beginning of the file?
The text was updated successfully, but these errors were encountered: