C++ - Solving Eternity II

I want to brush up my newbie C++ skills and found the puzzle to be an excellent exercise. I bought the main puzzle and the 2 clue puzzles.

My first class is Piece, it contains all the properties of a piece like color of every direction and number. Any suggestions/comments? Feel free to correct anything, even names of vars or functions.

v 1.2 - Piece.h

#ifndef PIECE_INCLUDE_GUARD
#define PIECE_INCLUDE_GUARD
class Piece
{
public:
   enum Color
   {
      Border = 0,
      OutsideNavyInsideYellow = 1,
      OutsidePinkInsideSkyblue = 2,
      OutsideGreenInsideDarkOliveblue = 3,
      OutsideYellowInsideBlue = 4,
      OutsidePurpleInsideSkyblue = 5,
      OutsidePinkInsideYellow = 6,
      OutsideOrangeInsideSkyblue = 7
   };
   Color getNorth() const;
   Color getEast() const;
   Color getSouth() const;
   Color getWest() const;
   void setNorth(Color c);
   void setEast(Color c);
   void setSouth(Color c);
   void setWest(Color c);
   int getTurns() const;
   void setTurns(int t);
   int getPieceNumber() const;
   void setPieceNumber(int pn);
   Piece()
      : turns(0) {}
   Piece(int number, Color north, Color east, Color south, Color west)
      : piecenumber(number), north(north), east(east), south(south), west(west), turns(0) {}
   ~Piece();
private:
   Color north, east, south, west;
   bool blocked; // Certain pieces, like the starter piece, should stay in the same place
   int turns; // A piece can be turned clockwise so that North, East, South and West return another color
   int piecenumber; // Every piece has a unique number on the back
};
#endif

A few things:
1. #pragma once is a VC extension; don't use this if you intend this to work on other compilers; use the standard #ifndef approach to prevent multiple inclusion instead.
2. Your capitalization is inconsistent (Turns is the only member that starts with a capital, piecenumber doesn't have Number capitalized).
3. Why is blocked a public field, while the others use accessors?
4. Why do the accessors for North, South, etc. return int, and not Color?
5. You might want to mark the get accessors (and any other methods that don't alter the object's state) as const.

ZippyV wrote:

I want to brush up my newbie C++ skills and found the puzzle to be an excellent exercise. I bought the main puzzle and the 2 clue puzzles.

My first class is Piece, it contains all the properties of a piece like color of every direction and number. Any suggestions/comments? Feel free to correct anything, even names of vars or functions.

You realise you have 1.15 × 10⁶⁶¹ permutations to check by dec 31 2008?


http://en.wikipedia.org/wiki/Eternity_II_Puzzle


Also has links to the distributed effort to solve the puzzle, - i'm guessing PS3/Cell processors are being considered.

Yes, I know there a lot of permutations possible but:
- The clue puzzles are a lot smaller,
- The main puzzle has 3 certain pieces (+2 in 2008).

I'm not going to try to brute-force every possible combination and hope to find the winning one. I'd rather let the program play by the rules and put pieces down that are valid so I can still get the grid filled up as much as possible.

The only thing worse than failing to solve it would be finding out you were the 2nd one to solve it.

If somebody already proved that it was solvable, then whoever solved it is already technically the second person to have solved it.

Three more minor comments:

1. You don't need to give the inclusion guard a value, just "#define _PIECE_INCLUDE_GUARD_" will do.
2. The name of _PIECE_INCLUDE_GUARD_ should be change so it doesn't start with _ followed by a capital. The ISO C++ standard reserves names that start with an underscore and a capital letter and names that contain a double underscore for the implementation. This means that compiler writers get to define symbols with names like that, but programs shouldn't do it. Just cut the underscore off at the start and you should be fine (yes, I know VC-generated headers use a guard with a similar, non-standards-compliant, name; that's no reason why you should do it).
3. It is not necessary in C++ to put void in an empty argument list. This is a relic from C. In C++, Piece() has exactly the same semantics as Piece(void). Putting void in there isn't wrong, but it's not necessary.

To elaborate a little on point two, the reason for this is that it allows compiler writers to extend the language in a way that doesn't break standards-compliant source. For instance, VC defines many extension keywords like __declspec. Introducing extension keywords would introduce the possibility that some program uses this keyword as an identifier, and this program would then no longer compile under that compiler because it would treat it as a keyword. The underscore rule means that compilers can safely introduce extension keywords that contain a double underscore or start with an underscore and a capital, because they can be sure no standards-compliant program uses these as identifiers.

This is specified in section 17.4.3.1.2 of the ISO C++ standard:
"Each name that contains a double underscore (__) or begins with an underscore followed by an uppercase letter (2.11) is reserved to the implementation for any use."

Additionally: "Each name that begins with an underscore is reserved to the implementation for use as a name in the global namespace."

Note that this last one does not prevent you from having class members or local variables that start with an underscore; only names with global scope must confirm to that rule. The first rule however applies to names in any scope.

Great, Piece.h and Piece.cpp are implemented. On to the next problem: I'm working on Board.h and I need a way to store all the pieces on the board.
In Visual Basic this would be pretty simple: create a dynamic 2 dimensional array and store all the piece objects in it but creating dynamic 2 dimensional arrays doesn't seem possible in C++.

My reason for having a dynamic array is because the application should be able to solve the smaller clue puzzles (6x6, 6x16 and 2 future unknowns) as well as the main puzzle (16x16). If it would be easier, I could make the the sizes a constant so that the app would require a recompilation for each puzzle. For this small app it wouldn't be a big deal.

std::vector<std::vector<Piece> >

Note that there's a space between the final two >'s. That's necessary, unlike C# it won't work without it.

This approach is comparable to having a List<List<Piece>> in C#. You'll have to initialize each row separately and it's up to you to make sure they're all the same length, but there's no way around that.

While I have no intention of seriously attempting to solve Eternity II, I may mess around with solving this type of problem on a smaller scale.

I'm curious about the semantics you have planned for your solver.

Larsenal wrote:

I'm curious about the semantics you have planned for your solver.

Ok, couple of things. It's getting to be my default line now.

1. Since you are including "Piece.h" in the header, what's the point of the check right below it? Remove the check.
2. Don't put "using namespace std;" in a header. By doing that you force everyone who at some point in the future wants to use your header to have namespace std imported into the global namespace. When you're writing code just for yourself and no one else it's not so much a problem, but it's a bad habit.
3. Be aware that your getBoard and setBoard function is going to make copies of the whole vector structure. This isn't C#, copying object can be an expensive operation. I would change both to a "const std::vector<std::vector<Piece> > &" instead, as a reference is much cheaper to copy than an entire object. Same applies to get/setPieceList.
   As a general rule, if something is more complicated than an int, it's better to use a const reference when passing it to functions. Another reason (besides avoiding the copying) is that if you have a parameter to a class type you cannot safely pass a derived class. If you have a "class Foo : public Bar" and a function that takes a Bar, you cannot pass it a Foo. This is because the compiler allocates stack space for the size of Bar, and Foo might be bigger. If on the other hand the function takes a "const Bar &" you can safely pass a Foo because only the reference sits on the stack which is always the same size.
   Add classes with non-trivial copy constructors to the mix and you have even more reason why you'd want to use references for parameters.

Wrote a little solver that works well with the sample puzzle on the Eternity II website.  Next, I'll try it on an 8x8.

There are obviously a lot of optimizaitons you can do with a small puzzle where edges and corners make up the majority of the pieces.  With an 8x8 puzzle, I'll be able to work on optimizations for the "inside" pieces.

Or you could work on the 6x6 clue puzzle 1.

ZippyV wrote:

Or you could work on the 6x6 clue puzzle 1.

AdrianJMartin wrote:

You realise you have 1.15 × 10⁶⁶¹ permutations to check by dec 31 2008?


http://en.wikipedia.org/wiki/Eternity_II_Puzzle


Also has links to the distributed effort to solve the puzzle, - i'm guessing PS3/Cell processors are being considered.