Tags

, , , , , , , , , ,

fifteen.c output -- 9x9 game, solved by God Mode

fifteen.c output -- a 9x9 game, auto-solved by God Mode!

Course: Harvard’s CS50

Problem Set 3: The Game of Fifteen

pset3/hacker3 is where things start getting interesting.

This is where you go beyond simple, few lines of code and get into the world of bigger programs (well not so big). There is nothing particularly difficult to it other than the learning curve with managing code with more than just one main() function.

By now you have already been, or you will be, introduced to:
  • make and Makefiles.
  • random numbers. rand() and srand().
  • headers (.h)
  • programs split across multiple files. (ie. making your own library, or just compartmentalizing.)
  • various sorting algorithms.
  • binary search.
  • gdb.
  • (hacker3:) Path finding Algorithms.

For this problem set you get to:
  • choose a sorting algorithm and implement it.
  • implement binary search.
  • make your own Game of Fifteen implementation.
  • (hacker3:) Look into how and when a sorting function can be O(n). (This really is a special case, not a general application)
  • (hacker3:) generate a random initial state for the game of fifteen, that is valid (solveable)
  • (hacker3:) make a game of fifteen auto-solver.

pset3

FIND

Pretty straight forward, the most fancy thing you could possibly do is xor swap in your sorting function. You are introduced to many different sorting functions during class. That animated sorting algorithms demo happens to have source code in it… What more do you need? 😉

You’re instructed to not touch find.c and helpers.h, so leave those alone.

helpers.c (view | download)

GAME OF FIFTEEN

The pset3 version of game of fifteen is easy enough to implement and it’s a non-trivial/boring thing to work on; I suggest you don’t spoil it by looking at the source here. The distribution code is already 180 lines long; the solved end result should not be more than twice that many lines (quite less really). Just don’t over-think it.

fifteen.c (view | download)

hacker3

FIND

The hint you are given may not be straightforward enough:

‘…’ because you may assume that each of the array’s numbers will be non-negative and less than LIMIT,’…’ leverage that assumption.

There are two things you should think of; once you do, the answer will land itself in your brain. This is a major ‘Duh!’ moment when you figure it out, especially if you’ve worked on Perl or PHP before.

  1. Even though in the scope of find.c/helpers.c, MAX(N) == LIMIT == HAY_MAXpretend you don’t `know’ that.
  2. You have N elements of ‘something’ where ‘something’ is between 0 and 65536. Think this problem from the perspective of a HUGE N. Ignore small Ns near the LIMIT. Think BIG. Think 1,000,000 times, or more, larger.

Got it? good 😉 Didn’t get it? There’s a link on this dot right here —> .

GAME OF FIFTEEN

You probably have already looked at: Dijkstra’s algorithmA* algorithmsaml.pdf (mirror) and pami94.pdf (mirror). Right?

I Implemented the auto-solver the way it is described in saml.pdf with a limited use of (see: a bastardization of) Dijkstra’s algorithm.

First things first: forget nano! Use a text editor or an IDE that will help you get it done and still remain sane. ie: Notepad++, EditPlus, SciteNetbeans. I use all of these at different times. If using the VM, you can run SciTe or netbeans from within it. If you’re using some other ‘remote’ setup a quick thought would be to mount the remote /path/to/src/ you usually work on as a local path/drive.

As an aside: If you actually are a student at Harvard, you probably should finish up pset3 first, ‘just in case’. ‘Cause hacker3 can take a while to get through… and you should not look at my code!

OCW users might want to watch a few more of the lectures/sections first, and/or re-watch the last few and take a second look at the lecture sources provided. You will find this problem set much easier if you have some more tools and syntax ‘well known’ to you. ie. recursion, multidimensional arrays, pointers, structs, linked lists…

Play with them in small scale. To get your feet wet…

Thinking… part 1 — struct.c

I started with this; while my solution for the Game of Fifteen auto-solver was still a speck in my mind.

struct.c (view | download)

Thinking… Part 2 — path.c

The next logical step is to try to implement a (bastardized) Dijkstra algorithm in a simple-ish way.

This demonstrates the ‘steps’ it takes to move to the next square.

output of path.c: 9x9 grid showing steps it takes to go from top right square to green square. Red=Blocked,Blue=Not visited.

There’s plenty of room for improvement there, but by now the general concept should start making sense. In a better solution the searching would stop at ~2*taxicab_distance(p_start, p_goal), because more moves than that make no sense in the context of game of fifteen (they do on any other context). It should also stop right after finding the target (and roll back to investigate the paths, or whatever); but then again, this is not proper Dijkstra, it’s a bastardization of it.

The pathrecurse() function here is almost identical to the one I use in the final solution.

path.c (view | download)

Thinking… Part 3 — the possible moves

I plotted most (all?) possible moves here.

Here’s a thought: a two-dimensional array holding known (specific) nodes of a linked list.
Does this data structure idea make sense to you? If not, then my code will probably not make sense.

End Result

Keep in mind that there probably is an easier (and better) way to do this (especially if you’re coming from an OO perspective) but this is how I did it when I was following this course. My thought at the time was something like: a linked list with nodes I could directly refer to from an alternate perspective than just from within the list… It made sense at the time I guess, and it still does! (nodes=tiles of the board).

This is the 3rd or 4th iteration of the code — as in: getting stuck and starting over.

I split the code so it was easier to manage.

fifteen.c (view | download)
fifteen.h (view | download)
fifteen_solver.c (view | download)

Build by using something like:

gcc.exe -std=c99 -Wall -Wformat=0 -c -g -Werror -MMD -MP -MF fifteen.o.d -o fifteen.o fifteen.c
gcc.exe -std=c99 -Wall -Wformat=0 -c -g -Werror -MMD -MP -MF fifteen_solver.o.d -o fifteen_solver.o fifteen_solver.c
gcc.exe -std=c99 -Wall -Wformat=0 -o hacker3_fifteen fifteen.o fifteen_solver.o -lcs50

This took quite a while to finish, and it could still use some re-touching up. Every time I look at the code I keep finding things to improve. ie. those mzToX functions are leftovers from a previous logic I was using, that I have since dropped; so they should be removed altogether at a later re-touching. This solution is not optimal because: To begin with, it doesn’t do diagonal moves.. And what’s more, a more optimal algorithm would use an A* search algorithm; ie entire board states in a linked list and all possible moves investigated w/ a heuristic formula in mind and best over-all path chosen for the whole solution.

Enjoy!

P.S. If I was to write it from scratch, now, I’d probably try an A* implementation. The hard part is making a heuristic formula, once that’s done the rest should be easy… maybe.