Sudoku solving

Posted in computers on November 11th, 2011 by karrth

One of our projects for my into to artificial intelligence class this semester was to create a sudoku solver using a MRV (minimum remaining values) heuristic and backtracking. It finds all possibilities for each square, then tries all possibilities for one of the squares with the lowest number of possible values. Here’s an example of it’s use (X6800 cpu):

$ time ./sudoku.pl puzzle.hard.txt
- - 8 7 4 - - - -
- 2 - - - 5 - - 4
- - 3 - - 2 1 - -
0 - - - - 1 2 - -
- 5 - 0 - - 4 - -
7 - - - - - - 0 1
- - - 8 1 - - - 0
- - - - - 0 5 - -
- - - 2 - - - 6 8

Solving...

Solved!
5 1 8 7 4 3 0 2 6
6 2 7 1 0 5 8 3 4
4 0 3 6 8 2 1 7 5
0 8 6 4 7 1 2 5 3
3 5 1 0 2 6 4 8 7
7 4 2 5 3 8 6 0 1
2 6 5 8 1 7 3 4 0
8 7 4 3 6 0 5 1 2
1 3 0 2 5 4 7 6 8

real 0m0.170s
user 0m0.167s
sys 0m0.000s

While it is not the most efficient, it will solve any hard-level sudoku puzzle of any size. It takes the puzzle file as an argument, or it will prompt you for the file path if you don’t include it. It will take puzzles with values that range from 0-9 and A-Z after that.

I’ve included in the tarball 2 harder puzzles that my program does not solve in anything close reasonable time (as in… it didn’t solve either one after running for 24 hours) if you’d like to try and improve the code yourself :). There are many ways you could improve the program, as talked about here (not my school/class). This is the website for the book we use in class – I’d highly recommend it for anybody interested in AI programming. Enjoy!

  • Sudoku Solver and example problems
  • Tags: , ,

    Adventures with the Droid 3

    Posted in computers on November 1st, 2011 by karrth

    I was finally able to renew my contract and upgrade to a Droid 3 from my OG Droid (may it rest in peace). After lots of tweaking (which will never be done), I’ve decided to post what I’ve done, as it may help others.

    Rooting

    Of course the first thing to do is to root that beauty, right? Right? You can find instructions on how to do so using Windows, Mac, or Linux in this post at the rootzwiki.com forums.

    Bloatware

    One of the first complaints many people have about smartphones these days is the amount of bloatware that they come with. It’s almost as bad as buying a desktop computer a couple years ago (or a laptop today, for that matter)… The two things I found to be most useful in reducing bloat are:

    1. Doing a factory reset as soon as you get your phone (no reason to configure things twice…). If you want to backup your settings, make sure you do it to an external SD card, not the internal storage, as this will be wiped with a factory reset.
    2. If you rooted your phone (which you did, right? After doing the factory reset that is…), grab a copy of TitaniumBackup. You can use this to backup all of your data as well (make sure it’s to an SD card!!!) if you waited to do a factory reset.

    After installing TitaniumBackup, the real fun begins. While it’s tempting to straight up uninstall unwanted apps, this can cause system instability, and since the bootloader is still locked, it is not possible to do a fresh reset if you mess something up. I found some great lists of apps you can safely freeze in this thread at the AndroidCentral forums. This post in particular is pretty comprehensive.

    Removing the wrong apps can cause a boot-loop, and even leaving some frozen when doing a factory reset can cause a loop issue. I’ve seen it noted by some forum users that freezing the Backup Assistant app can cause a factory reset to go awry (probably because it is brought up during the setup process), so be sure to unfreeze it before a reset.

    Here’s a list of apps I have frozen:

    • Apps (Verizon Apps Store)
    • Backup Assistant
    • Backup Assistant Client
    • Desk Home
    • Email
    • Email Authenticator
    • Email Engine – freezing this causes the Calendar to crash when adding a new event
    • Gallery (see next section for further explanation)
    • Help Center
    • Messaging
    • Motorola Dock Service
    • News
    • Smart Dock
    • Social Location
    • Social Messaging
    • Social Networking
    • Social Sharing
    • Social Status

    These are only the ones I have frozen for now. I suspect that there are other things that can be frozen, such as the MOTOBLUR Indexing Service, but I have not tested these yet. You might not want to freeze some of these items if you use them, such as the Universal Inbox (Email) and the various Social applications. More on that later.

    The Gallery

    Personally, the Gallery app that comes with this phone is horrid. Makes me want to puke. Luckily, there’s an easy way to get the old Gallery back, as found here at the xda-developers forum. It worked beautifully for me.

    Motorola Terms of Service

    I’m not sure how many people actually read these things (I’m told not many do…), but this is one that needs to be read. When adding more accounts to your phone, such as Facebook, LinkedIn, Flickr and Yahoo!Mail through the built in “My Accounts”, the Gallery (the one that came with the phone), or the various built in Social apps, you are presented with two documents. I have not agreed to these documents because they describe, in great detail, how they will then collect all (ok, not all, but most) of your personal information, such as your:

    • purchase history
    • calendar
    • social networking credentials
    • SIM card ID
    • location (via GPS, WiFi, or cell tower triangulation)

    …among other things. It then says lower down that they will be using this information to provide you with information about things you might be interested in, and that it will be sharing it with third parties. And that your information will be subject to those party’s individual privacy policies. You can even check the second box (done for you already) so that you can share even more! Like your browsing history and demographics information from your social networks.

    All in all, I do not like what these documents are saying. If you don’t believe me, read it yourself. If you don’t care about your personal information, then have fun! It saddens me greatly that Motorola would build in such a system to their phones, and is part of why I froze all of the built in Social apps, Universal Inbox, and the default Gallery, and the News app, since they are all integrated into this system.

    Some Apps

    As a quick aside, here are some of my favorite apps:

    • LauncherPro homescreen replacement
    • Subsonic music streamer and it’s accompanying server software.
    • DroidWall is an Android iptables implementation. Root required.
    • ConnectBot ssh client
    • TitaniumBackup is a great backup tool, especially if you have root.
    • Wifi Analyzer wifi scanning tool
    • SetCPU is a great under/overclocking tool that I use to underclock and save battery. Unfortunatly, it has caused some system instability for me, so I wouldn’t recommend using it unless you want to fiddle around with it to find stable settings. I’ll update if I do find settings that work for me.

    Have a good day!

    Tags: ,