Just started doodling with Snap app Edgyhttp://snapapps.github.io/edgy/
and am curious to see if anyone here would find this of interest.
Big picture - finding symmetrical things (equivalence classes) in tiling puzzles by describing them as subgraphs and then searching for them. Pulls together introductory concepts of group and graph theory with a perhaps a taste of topology.
Inspiration here -
Equivalence Classes Among Pentomino Tilings of the 6x10 Rectangle
My doodling -
how do I get those new categories.
It's an extension of Snap! for graph theory.
The original message is about teaching a particular topic in graph theory, not about how Edgy works. I think it's okay.
Thanks. I am making some progress.
Can I add to this topic with pics?
Yes, click the pencil icon on the post to edit it.
Thanks!
Making some progress.
Trying to write a SNAP!/Edgy solver -
Sixl is a simple 3x3 cube puzzle. All of the shapes that can be made from 3 or less cube.
3 cube - stick 3 cube - vee 2 cube stick 1 cube dot These four shapes will tile a 3x3 square in six unique symmetry constrained ways. A solver in SNAP!/Edgy should be pretty straight forward and a nice intro to graph theory and programming
Files that show it is possible to set up possible piece positions on graphs here -
https://github.com/EdV2/SomaCubeAndConnectionGraphsSixlSolverCallPiecesFromFilesITems1and2.xml
BlueVee.csv
RedDot.csv
YellowStick.csv
I am able to play with the blocks I made and make a "Pause and Click Blocks" solver but when I try to automate it things get "sticky" with yellow.
I know nobody here is an Edgy expert but are there maybe some purely SNAP! tiling puzzle solvers? I looked for pentominoes with no luck.
Thoughts?
text got crunched into url
I'm confused about "cube" vs. "square." Are we trying to pack a cube? May we use as many of each shape as we want? (E.g. a trivial solution uses nine green sticks.)
I would be inclined to program this in Prolog. Someday When Things Slow Down™ I'm going to write a Prolog library (that is, a resolution library) for Snap!.
I haven't looked at Prolog in many years. A SNAP! library that helps folks get a feel for logic programming. As I recall and sort of understand - making a series of statements about some things and their relationship and then running a query over those statements to generate a new relation "a level up" (I guess)
Thanks for having a look.
Oh. Then this is much too easy to bother using a computer! :~)
We can prove that the green can't be in the middle: You need two consecutive rows to fit the blue vee, QED. So without loss of generality we put green at the bottom, as you've done.
The problem now reduces to three pieces in a 2x3 grid. I find it easier to think about if we name the pieces 1,2,3 instead of red,yellow,blue respectively. We still have symmetry around the vertical axis, so we can decide not to put 3 in the first column.
The remaining permutations of numbers are 1,2,3; 1.3.2; 2.1.3; 2.3.1. The way we associate permutations with block arrangements is to start by putting 1 in one of the columns -- never mind yet which row. Then yellow is in either one column, in which case that's where we put 2, or in two columns, in which case we pick the one that doesn't already have 1. (A horizontal yellow has to share a column with red because if not the blue vee won't fit.)
It then turns out that 1,3,2 is not realizable -- try it.
We're left with three permutations. Each permutation can have two layouts, depending on whether the red square is in the top or bottom row. That's six solutions...
I'm not sure what you meant about "a sort of rotational symmetry."
PS: This reminds me of the time I was a Stanford CS grad student. We had to pass a comprehensive exam, which had a three-hour written part plus a weeklong programming problem. I passed the written part only because the year I took it, the numerical analysis question was way too hard, so nobody else got it either except for the NA specialists, so they didn't count it. :~)
But it's the programming problem that brings this to mind. We had to count the isomorphically distinct semigroups of order 4. Counting all the semigroups was easy without using a computer at all; what made this a hard problem was the "isomorphically distinct" part.
I wrote a horrible brute-force solution just so I'd know if I had the correct number, and then spent a few days trying to think of a better way. (The brute-force solution was ruled out because there was a time limit on how long the program could run.) Then, in the middle of a Chinese restaurant banquet at which we had a different wine with each course, I suddenly realized I could prove that every such semigroup must have an element such that x◦x=x. (This isn't obvious because what makes something a semigroup is that it doesn't have to have an identity element.) So you put that element first, and that immediately reduced the solution space by a factor of four, and made the remaining isomorphism checks simpler too.
So things like putting the green piece at the bottom brought that to mind.
Thanks again for having a look.
Oh. Then this is much too easy to bother using a computer! :~) - Conway says the same about the Soma cube puzzle in Winning Ways I think. My purpose for writing this program is to develop a middle school age math activity for Leonardo's Basement that involves hands on puzzles. . Sixl is a much simpler puzzle to start with. Analysis of the puzzle leads to a simpler computer algorithm and since the solution set is so small (because we analysed it first) it is easy to verify that SNAP! did what we wanted.
I'm not sure what you meant about "a sort of rotational symmetry." - My group theory education is spotty and from general readership books so I am apt to misuse terms. What I am trying to say is that the Blue Vee and Red Dot can form a "tight" two piece combination that if you ignore the interior lines and piece colors (maybe fit into an opaque costume or hull) it can be rotated on its large flat surface and still have a Sixl 3x3 tiling. Four of them.
This is Leonardo's basement. I have volunteered here since 2006. Never a dull moment and very hands on.
https://leonardosbasement.org/
I want a math/CS activity that fits into our "build stuff, see it do something, learn from that and build/learn some more. SNAP!/Edgy ares so accessible and can be facilitated as algorithmic art on the physical Sixl and Soma blocks and the geometry of their solution sets.
Thanks again for the conversation. It really helps me stay motivated.
That does look like a lot of fun.
Okay, you inspired me to write my first Prolog program:
#
% set up the geometry
cell(1).
cell(2).
cell(3).
cell(4).
cell(5).
cell(6).
cell(7).
cell(8).
cell(9).
horizontal_adjacent(1,2).
horizontal_adjacent(2,3).
horizontal_adjacent(4,5).
horizontal_adjacent(5,6).
horizontal_adjacent(7,8).
horizontal_adjacent(8,9).
vertical_adjacent(1,4).
vertical_adjacent(4,7).
vertical_adjacent(2,5).
vertical_adjacent(5,8).
vertical_adjacent(3,6).
vertical_adjacent(6,9).
% now for shape placement
can_red(A) :- cell(A).
adjacent(A,B) :- horizontal_adjacent(A,B).
adjacent(A,B) :- vertical_adjacent(A,B).
can_yellow(A,B) :- adjacent(A,B).
can_green(A,B,C) :- horizontal_adjacent(A,B), horizontal_adjacent(B,C).
can_green(A,B,C) :- vertical_adjacent(A,B), vertical_adjacent(B,C).
can_blue(A,B,C) :- horizontal_adjacent(A,B), vertical_adjacent(B,C).
can_blue(A,B,C) :- vertical_adjacent(A,B), horizontal_adjacent(B,C).
:- use_module(library(lists)).
solution([A,B,C],[D,E,F],[G,H],I) :-
can_green(A,B,C),
can_blue(D,E,F),
can_yellow(G,H),
can_red(I),
is_set([A,B,C,D,E,F,G,H,I]).
This doesn't take symmetries into account. I haven't decided yet how much I can tell the program explicitly (e.g., put the green thingy on the bottom) without it being cheating.
Here's the first result I got:
?- solution([A,B,C],[D,E,F],[G,H],I).
A = 1,
B = 2,
C = 3,
D = 4,
E = 5,
F = 8,
G = 6,
H = 9,
I = 7
I could constrain the green piece by saying, e.g.,
?- solution([1,2,3],[D,E,F],[G,H],I).
And similarly for the other pieces.
The interesting parts of the program are the can_color rules. In the solution rule, I use is_set to make sure I haven't put two pieces in the same space. (A set is a list with no duplicated items.)
P.S. It's your class, but you pushed one of my buttons with "Let's use Snap! to..." Curriculum writers all do this, and I find it terribly dishonest, and I bet kids do too. Not quite as bad as "Let's play 52 Pickup," but it similarly suggests a symmetry of roles that just isn't the case.
P.P.S. I'm sure any minute now Ken will tell me how I should have written it! :~)
Whoa, if I just constrain the green piece to the bottom I get exactly your six solutions, except that three of them are flipped around the vertical axis (reversing each row).
I have no idea why I'm not getting each of these twice, flipped around the axis and not flipped around the axis.
Back to the drawing board...
Never mind, I figured it out; when I said, e.g.,
horizontal_adjacent(1,2).
I should also have said
horizontal_adjacent(2,1).
in order to get the results I was expecting. :~/
(Is there a word "misbug" analogous to "misfeature" to describe something that should have been a bug but actually makes the program work better?)
