Tumblr is where tens of millions of creative people around the world share and follow the things they love.Sign up to find more cool stuff to follow
Rubik's Cube Solver
I have never been able to solve a Rubik’s cube. I can get to the point where one side is correct before getting frustrated. But then I invariably try to get one more piece in place and end up ruining the whole thing. With that in mind, I decided to write a computer program that would solve a Rubik’s cube for me.
First, I wanted a way to display the cube and manipulate it. Displaying a 3D surface on a 2D computer screen is always a bit tricky because you can’t see the entire object. My initial thought was to show the “unwrapped” cube, where the six faces are joined at the appropriate edges. For rotation the user would be able to move any row or column on the front face in either direction. Because they could only manipulate the front face I added the capability to rotate the entire cube to show any of the adjoining faces.
This was a mess.
The “unwrapped” cube creates issues because no matter how you unwrap it one of the faces will be upside-down from what it should intuitively look like. Additionally, it’s restrictive to think about rotating the cube by only manipulating the front face. A quick search showed that there is actually a standard nomenclature for manipulating a Rubik’s cube. F denotes rotating the front (F) face of the cube 90 degrees clockwise. F’ is a counterclockwise rotation.
With this knowledge I modified my display to show each of the six faces independently, with buttons to rotate them clockwise or counterclockwise. I added similar buttons and icons to rotate the entire cube along any of its three axes. In the earlier version I had created a 3D rendering of the cube that displayed the front, up, and left faces. I added a see-through view of the cube next to this so that the back, right, and down faces of the cube would be visible in 3D as well.
Once I had written the code to rotate the faces and cube appropriately I added two buttons. The first to reset the cube to a solved state - the equivalent of peeling the stickers off and putting them back in the right place. The second to randomly perform some number of rotations along different faces and axes until the cube was nicely randomized, but still guaranteed to be solvable. Finally, it was time to add a button to solve the cube.
There are a variety of ways to solve a Rubik’s cube and this is by no means the most efficient. I wanted to follow a structure that led itself to programming and could potentially teach a person how to solve the cube themselves. The process treats the cube as having three layers, like a cake. It starts by solving the top layer, then the middle, then the bottom.
A cross of a single color is formed first on the top layer, and then the corner pieces are put into place. It is important that not only are the colors on the top correct, but the edges as well. Having done this there are only four spots in the middle layer that might need adjusting and only four spots that they could potentially be. To solve the bottom layer the program actually flips the cube over and then solves the upper layer again. However, it uses a more complicated set of rotations to ensure that it doesn’t change anything in the other, completed layers.
With the solver algorithm developed I decided to add a second worksheet that would list the steps so the user could follow along. The idea is a user could color the squares to match a real cube and then run the solver to discover what steps to take in order to solve it. They could then follow each step, rotating their own cube, and see how it is solved. If nothing else, at the end of the process they would have a completed cube to impress and amaze their friends.
Because my solver algorithm follows this layer concept it is by no means the most efficient way of completing a cube. Running it on randomly scrambled cubes I’ve found that it generally takes between 200 and 250 steps to solve it this way. At some point in the future I might look at optimizing my solver to use fewer steps I’m fairly happy right now that the thing actually works. Enjoy!
To Witness and Hold
Just as the warmth of summer
can make a cricket sing,
the quality of being held enlivens the heart.
We have been battered by modern times into obsessive problem solvers, but as life pares us down into only what is essential, it becomes clear that the deepest sufferings of the heart and spirit cannot be solved, only witnessed and held.
I have struggled with this constantly. Just recently, after being away for two weeks, I returned to a tender partner who lovingly uttered, “I really missed you.” Instantly, I reacted by scanning for ways to solve the feeling - to limit my travel or call more often. I instantly tried to change my patterns of being away from the relationship, rather than just feel the poignancy of being loved enough to be missed.
Frequently, this reflex to solve, rescue, and fix removes us from the tenderness at hand. For often, intimacy arises not from any attempt to take the pain away, but from living through together; not from a working out, but from a being with. Trust and closeness deepen from holding and being held, both emotionally and physically.
I’m learning, pain by pain and tension by tension, that after all my strategies fail, the strength of love waits in receiving and not negotiating; in accepting each other and not problem solving each other; in listening and affirming each other, not trying to change or fix those we love.
I find this helpful : )
Sudoku Solver and Generator
When I first posted my Sudoku Solver I mentioned that there are many such programs available. There seem to be far fewer Sudoku Generators, that can create the puzzles in the first place. With this is mind I updated my previous Excel file so that it can generate Sudoku puzzles as well as solve them. Generating a puzzle is tricky and involves more trial and error than solving a puzzle. I found several methods online but wasn’t thrilled with any of them so I decided to create my own concept.
The first thing I need is a completed puzzle that meets all the restrictions of Sudoku (e.g. all nine numbers in each row, column, and 3x3 big box). To start I fill out the three big boxes along the diagonals by inserting the numbers 1 through 9 at random. Next, I fill out the big boxes in the remaining two corners. At this point I can’t randomly assign values because the other two corner boxes restrict where the numbers can be used. The code determines which values are allowable and tries to fill them in. If it gets stuck then it just clears out the entire corner box and starts over again. From there I can run the Solver to fill in the remaining four big boxes. This works properly most of the time but if it gets stuck then I just clear it all out and start over again. I’m sure there’s a more efficient way to fill these out but this works pretty well and doesn’t take too much time.
Okay, so now I’ve got a puzzle solution. At this point I keep removing a cell and its mirrored pair (e.g. the cell in the upper left and the lower right) while making sure the puzzle is still solvable. The two cells are removed and the solver is run. When it finally gets to the point where the puzzle can’t be solved it fills the values back into the last two cells it removed. It then tries to remove a different pair of cells. After a few attempts if the program is unable to remove additional cells without making the puzzle unsolvable it stops. The difficulty of the generated puzzle is then provided to the user. Based on the hand-entered Washington Post puzzles I found that the number of iterations required of the solver is proportional to the difficulty ranking.
I’ve been doing quite a bit of programming in VBA lately, mainly because it’s easier to share Excel files than most other formats. However, I want to keep branching out and trying new things. Over the past few weeks I’ve been starting to learn to program apps for the iPad. I’m still working through some books and examples to learn the idiosyncracies of the SDK and language but I’m making my way up the learning curve. Once I get a bit more familiar my plan is to create a simple tic-tac-toe app. From there I’d really like to get my Sudoku Solver / Generator working as an app. I have an idea for a more ambitious app after that, but it’ll have to wait…