Server Help

Non-Subspace Related Coding - Mathmatical Number Game Problem

tcsoccerman - Fri Oct 17, 2008 5:49 pm
Post subject: Mathmatical Number Game Problem
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 - Fri Oct 17, 2008 9:32 pm
Post subject:
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 - Fri Oct 17, 2008 10:17 pm
Post subject:
and what would that be?! i think we have a communication problem.
SamHughes - Fri Oct 17, 2008 10:40 pm
Post subject:
Just follow the path Aaaa...Bbbb...Cccc...

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

SamHughes - Fri Oct 17, 2008 10:49 pm
Post subject:
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 - Sat Oct 18, 2008 1:10 pm
Post subject:
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 - Sat Oct 18, 2008 10:48 pm
Post subject:
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 - Sun Oct 19, 2008 11:36 am
Post subject:
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 - Mon Oct 20, 2008 9:13 pm
Post subject:
So to be clear, from square 6 there are 6 possible squares one could visit next?
tcsoccerman - Tue Oct 21, 2008 3:37 pm
Post subject:
yes
YonatanNaamad - Sun Mar 22, 2009 7:26 pm
Post subject: Prolog solution
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 - Sun Mar 22, 2009 9:13 pm
Post subject:
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 - Wed Mar 25, 2009 1:33 am
Post subject:
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.
All times are -5 GMT
View topic
Powered by phpBB 2.0 .0.11 © 2001 phpBB Group