Server Help

[tcsoccerman]

Goal: To try and fill in all the squares without going over one that is already filled by counting to 100.

Directions: Using a 10x10 graph (100 squares), write a 1 in the top left. Now you can either move horizontally 3 squares (4,1) and write in the next number, verically 3 squares (1, 4) or diagonally 2 squares (3,3). Continue doing so until you have filled all squares once. There is 15 million different incorrect solutions and 2 correct solutions.

I'm going to try and make a program to find the solution.

This whole problem came from my math teacher, who said they'd give us a car if we can find the solution. Evidently a past student's dad was a software developer and made a program to find this solution. He had the program running a couple days and the kid actually got the car, a convertible. I think they're even telling the truth.

[SamHughes]

So you can go vertically 3 squares in any direction, and diagonally 2 squares in any direction?

Well, just so you know, I found a solution, by hand, in about five minutes.

[tcsoccerman]

and what would that be?! i think we have a communication problem.

[SamHughes]

Just follow the path Aaaa...Bbbb...Cccc...

Code: Show/Hide ahdahdahda icficficfi gebGebgebg aHdahdahda icfIcficfi gebgebgebg ahDahdahda icFicfiCfi geBgebgEbg Ahdahdahda

[SamHughes]

You know there are more than 2 solutions, because there's 2 ways to get from A to B and then you can reflect both solutions around the diagonal, giving 4 solutions.

Maybe the rules are tighter than I read them to be.

[tcsoccerman]

Yeh i didn't explain it well enough you got the wrong interpetation.

I'll try again

You've got a 10x10 grid (100 squares).

The goal is to fill all of the grid up with the numbers 1-100.

You start by marking a "1" at 1,1 in top left corner.

From there you can either go horizontal 3 (4,1), vertical 3 (1,4) or diagonal 2 (3,3).

Now you would make a 2 where you chose to go. lets say 4,1.

Now you continue that faschion (either go horizontal 3 (4,1), vertical 3 (1,4) or diagonal 2 (3,3)) and mark a 3, 4, 5.... up to 100.

If at anytime you end up on a gridpoint that is already filled in with a number, you have to choose a different path. You can't overwrite. (This is the "catch").

That should be a little harder.

[SamHughes]

Um, what did you say that's different than what you said before?

Are you able to go vertically and horizontally in any direction? Are you able to go diagonally in any direction? Or just down and to the right?

These questions you haven't answered. And if the answer is yes to the first two, then my solution is correct.

[tcsoccerman]

Maybe you do have the answer, lets make sure.



That image is a good example of the rules. (That is only an 8x7 grid though, it should be 10x10). Like i said, you just keep doing that until you fill it all up.

Also look at 6, and note that from 6 i could NOT go up because then i would be at 3.

Does that clarify?

[SamHughes]

So to be clear, from square 6 there are 6 possible squares one could visit next?

[tcsoccerman]

yes

[YonatanNaamad]

Hey. It's my first post, and I know it's a bump of an old post, but whatever.

Anyway, here's some Prolog code that could theoretically come up with a solution to the problem.

Code: Show/Hide in(H,[H|_]). in(H,[_|T]) :- in(H,T). append([],A,A). append([A|B],C,[A|W]) :- append(B,C,W). vs([A,Y],[X,Y],L) :- A > 3, X is A-3, not(in([X,Y],L)). vs([A,Y],[X,Y],L) :- A < 8, X is A+3, not(in([X,Y],L)). vs([A,B],[A,Y],L) :- B < 8, Y is B+3, not(in([A,Y],L)). vs([A,B],[A,Y],L) :- B > 3, Y is B-3, not(in([A,Y],L)). vs([A,B],[X,Y],L) :- A > 2, B > 2, X is A-2, Y is B-2, not(in([X,Y],L)). vs([A,B],[X,Y],L) :- A > 2, B < 9, X is A-2, Y is B+2, not(in([X,Y],L)). vs([A,B],[X,Y],L) :- A < 9, B > 2, X is A+2, Y is B-2, not(in([X,Y],L)). vs([A,B],[X,Y],L) :- A < 9, B < 9, X is A+2, Y is B+2, not(in([X,Y],L)). gvs(_,0,_,[]). gvs(S,N,L,[A|B]) :- N > 0, M is N-1, append(L,[S],NL), !, vs(S,A,NL),gvs(A,M,NL,B). solve(N,B) :- gvs([1,1],N,[],B).

To run it, you just call solve(100,B). I'm running it on my server now to see what the results are. It can find solutions for the first 90 moves pretty quickly.

(PS. Soccerman's post count is pretty beast)

[tcsoccerman]

lol, i just ruined it.

anyways, that's too complex for me to know if what that code does is correct, but the fact that it's so complex makes me think that it is the right code. good work.

[Chambahs]

Sama has a passion for brain teasers that involve math or numbers. I remember his other "turn a name into numbers and ill figure out the equation game" he had us all doing.