Tuesday, July 26, 2011

Problem 96 Complete (more or less)

So...

After more hours than I'm proud of, I was able to create a sudoku solver that works rather well. Beside the obvious eliminations to possible solutions to just one box (veritcal, horizontal and quadrant eliminations) I tried to add some more logical solutions. When I solve Sudoku puzzles (easy ones anyways) I use a method of checking for which number each box can be. In words, if I get a puzzle like the following:
I would start with the number 2. You can see that the first row has a 2 in it, and the second row has a 2 in it. This implies that there needs to be a 2 in the third row as well, which HAS to be found in the top right quadrant of numbers. In this top right 3x3 quadrant, there are only two spaces that can be that 2 and one of them has a 2 in its column already. That means that only one box in this top right quadrant can be a 2, and I fill it in. Apparently, after some googling, I found out this is called hidden singles. Upon adding this selection method and re-iterating (as well as adding a solution counter), I was able to solve 40 of the 50 problems.

At this point I conceded the logical method and began implementing a bruting method. I just looked for the first empty box that had between 2 and 4 possible numbers, chose the first "guess" and selected that as an answer. If a contradiction was found, the guess was broken and the next "guess" for that same box was taken.  I let the guess run through each box until a solution was found and the loop would break.

Unfortunately, this now works for 49/50 of the problems. In fact, it is problem 49 that my code fails to solve. After some frustration, I solved it by hand and submitted my solution which was correct. Maybe I'll return to this one later.

Wednesday, July 20, 2011

Ugh...

So my file solves the first sudoku no problem, but gets stuck on the second one. Need to go through and see if my elimination method is not enough to complete this problem. I may need to add some guessing script to start guessing a number and basically brute forcing it from there... Frustrating.

More problems on 96...

So I have tried to get everything working on problem 96, but I seemed to run into some small error in my eliminations. By setting the eliminations to run until it finds the value of the first (top left) number, I get a 5 instead of 4. The solution puzzle it is giving me is slightly off. Need to go through and figure out which line is sending the wrong elimination out.

Solution so far:

5     0     3     9     2     1     6     7     4
9     0     4     3     7     5     8     2     1
2     7     1     8     0     6     4     0     0
0     0     8     1     0     2     9     0     0
7     0     9     5     0     4     1     0     8
0     0     6     7     0     8     2     0     0
0     0     2     6     8     9     5     0     0
8     0     0     2     5     3     7     0     9
6     9     5     4     1     7     3     8     2

The zeros reflect unknown solutions.

Edit:
So it turns out I had a typo and I was replacing the wrong zero with the solved number, go figure.

Problem 96

I decided today to try and conquer problem 96 and it's proved to be a bit of a challenge. I've spent maybe 40 minutes on it and have made pretty good progress.

I figured the best thing to do was to read each puzzle number by number. By taking a solution matrix that was 81  x 9 (each row represents all of the possibilities of each square in the 9 x 9 puzzle) I replaced each possible number with a zero if it could not be a solution. So far I have only been able to eliminate each row and column that was already given a number from the .txt file. Now I'm going to figure out a way to eliminate each square from the given numbers, and then edit my loops a little bit to check when there is only 1 possible number left in each of the 81 spots. Finally, when there is only one number the process will repeat and eliminate these new choices vertically, horizontally and in squares.

Solving the first puzzle given (doesn't solve all the way, obviously) takes about 0.04 seconds and I'm afraid that my code will be VERY slow for 50 problems. Maybe I can find a way to break when I finish the top left numbers instead of solving the entire puzzle.

Monday, July 18, 2011

Site moved

For easier organization and with the discovery of a workaround for the lack of a comment box, I am moving everything over to Google sites.

This should help a lot with ease of viewing and makes it so that I can have unlimited static sites. The url is:

This blog will be used to update my status on the problems as I solve them. Might be helpful to some as I'll go over where I get stuck or potential problems that I find as I go about solving the problem.

Layout

I'm still doing a lot of modifying to the general layout of this page. I'm currently organizing my posts in a chunking method that can be viewed to the right of the page. If you click the problem set you can choose each problem individually from there. Commenting is enabled so feel free to ask questions, give suggestions, or pose similar problems.

Also, I'm open to suggestions for page layout and site mapping, so feel free to give any suggestions here.

Welcome!

My name is Andrew, and I am a fourth year mechanical engineering student. I have very little experience with Matlab, but I recently started solving Project Euler problems using Matlab. Unfortunately, whenever I need to look around for help I seem to only find sites dedicated to solving them in Python, Java, etc. Thus, I wanted to create a site in which I outline my thought pattern and code that I used in Matlab. I have no formal programming experience and I admit my code can be quite barbaric at times, but again this site is not for advanced Matlab users or computer scientists, just engineers hoping to get more practice with Matlab by solving fun little math challenges. Also, I would love for people to make recommendations or question parts of my code. Oftentimes my method of solving the problems is rarely the most elegant and I can use help in optimizing my code/approach.

Finally, I'm a complete novice when it comes to website design, so please bear with. If you have any recommendations to formatting or site mapping feel free to let me know and I'll try to get this site more visually appealing.