Solve 8-tile sliding puzzle

The name of the pictureThe name of the pictureThe name of the pictureClash Royale CLAN TAG#URR8PPP





.everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0;







up vote
8
down vote

favorite












I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question






















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15

















up vote
8
down vote

favorite












I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question






















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15













up vote
8
down vote

favorite









up vote
8
down vote

favorite











I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;




c++ performance algorithm breadth-first-search sliding-tile-puzzle




share|improve this question














I created a BFS algorithm in order to solve an 8-puzzle, and while it works, it is awfully slow compared to my DFS implementation. My main point of concern is the puzzleExists() function, which determines whether the created puzzle already exists in the list and should therefore be dropped. Currently the algorithm slows down significantly as it has to check all the previous puzzles for duplicates.



Advice on how to aproach this would be appreciated.



Code for DFS and printing omitted for clarity:



#include <iostream>
#include <vector>
#include <chrono>

using namespace std;
using namespace std::chrono;

const int PUZZLE_LENGTH = 9;

const int EMPTY = 0;

struct Puzzle

 int state[PUZZLE_LENGTH];
 int gapLocation;
;

struct breadthPuzzle

 Puzzle puzzle;
 int parent;
;

const Puzzle SOLVED_PUZZLE = 1,2,3,4,5,6,7,8,EMPTY ;

// Check if the provided puzzle is actually solvable or not
// Credit for formula to: http://www.cs.bham.ac.uk/~mdr/teaching/modules04/java2/TilesSolvability.html
bool isSolvable(const Puzzle& puz)

 int inversions = 0;

 for ( int i = 0; i < PUZZLE_LENGTH; i++ )
 for ( int j = i + 1; j < PUZZLE_LENGTH; j++ )
 if ( puz.state[j] > puz.state[i] && puz.state[i] != EMPTY && puz.state[j] != EMPTY )
 inversions++;

 // If the amount of inversions is even the puzzle can be solved
 return inversions % 2 == 0;



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);


bool canNorth(int gapLocation)

 return gapLocation > 2;


bool canEast(int gapLocation)

 return (gapLocation != 2 && gapLocation != 5 && gapLocation != 8);


bool canSouth(int gapLocation)

 return gapLocation < 6;


bool canWest(int gapLocation)

 return (gapLocation != 0 && gapLocation != 3 && gapLocation != 6);


int north(int gap)

 return gap - 3;


int east(int gap)

 return gap + 1;


int south(int gap)

 return gap + 3;


int west(int gap)

 return gap - 1;


Puzzle createNextPuzzle(Puzzle currentPuzzle, int pos)

 int temp = currentPuzzle.state[pos];
 currentPuzzle.state[currentPuzzle.gapLocation] = temp;
 currentPuzzle.state[pos] = EMPTY;
 currentPuzzle.gapLocation = pos;
 return currentPuzzle;


void solvePuzzle(vector<breadthPuzzle>& currentRoute, int i, int futurePos)

 Puzzle currentPuzzle = createNextPuzzle(currentRoute[i].puzzle, futurePos);

 if ( !puzzleExists(currentPuzzle, currentRoute) )
 
 breadthPuzzle candidate currentPuzzle, i ;
 currentRoute.push_back(candidate);
 


void breadthFirst(Puzzle initalPuzzle)

 // Origin has no parent, thus -1 as start.
 vector<breadthPuzzle> breadthVector = initalPuzzle, -1 ;
 int i = 0;

 while ( i < breadthVector.size() && !isSolved(breadthVector[i].puzzle) )
 
 Puzzle currentPuzzle = breadthVector[i].puzzle;
 int gapLocation = currentPuzzle.gapLocation;

 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));
 i++;
 


int main()

 Puzzle toSolve = 1,2,3,4,6,5,8,7,EMPTY, 8 ;
 //Breadth-First: Duration in seconds = 72;
 //Depth-First: Duration in seconds = 15;

 high_resolution_clock::time_point t1 = high_resolution_clock::now();

 if ( isSolvable(toSolve) )
 
 cout << "Puzzle Solvablen";
 breadthFirst(toSolve);
 
 else
 cout << "Puzzle insolvable, stoppingn";

 high_resolution_clock::time_point t2 = high_resolution_clock::now();
 auto durationSec = duration_cast<seconds>(t2 - t1).count();

 cout << "Duration in seconds of function: " << durationSec << endl;





c++ performance algorithm breadth-first-search sliding-tile-puzzle





share|improve this question













share|improve this question




share|improve this question








edited Aug 10 at 12:14









Toby Speight

18.6k13695




18.6k13695










asked Aug 9 at 17:09









Hirtol

433




433











  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15

















  • Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
    – Toby Speight
    Aug 10 at 12:15
















Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
– Toby Speight
Aug 10 at 12:15





Welcome to Code Review! I changed the title so that it describes what the code does per site goals: "State what your code does in your title, not your main concerns about it.". Feel free to give it a different title if there is something more appropriate.
– Toby Speight
Aug 10 at 12:15











1 Answer
1






active

oldest

votes

















up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16










Your Answer




StackExchange.ifUsing("editor", function ()
return StackExchange.using("mathjaxEditing", function ()
StackExchange.MarkdownEditor.creationCallbacks.add(function (editor, postfix)
StackExchange.mathjaxEditing.prepareWmdForMathJax(editor, postfix, [["\$", "\$"]]);
);
);
, "mathjax-editing");

StackExchange.ifUsing("editor", function ()
StackExchange.using("externalEditor", function ()
StackExchange.using("snippets", function ()
StackExchange.snippets.init();
);
);
, "code-snippets");

StackExchange.ready(function()
var channelOptions =
tags: "".split(" "),
id: "196"
;
initTagRenderer("".split(" "), "".split(" "), channelOptions);

StackExchange.using("externalEditor", function()
// Have to fire editor after snippets, if snippets enabled
if (StackExchange.settings.snippets.snippetsEnabled)
StackExchange.using("snippets", function()
createEditor();
);

else
createEditor();

);

function createEditor()
StackExchange.prepareEditor(
heartbeatType: 'answer',
convertImagesToLinks: false,
noModals: false,
showLowRepImageUploadWarning: true,
reputationToPostImages: null,
bindNavPrevention: true,
postfix: "",
onDemand: true,
discardSelector: ".discard-answer"
,immediatelyShowMarkdownHelp:true
);



);













 

draft saved


draft discarded


















StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201308%2fsolve-8-tile-sliding-puzzle%23new-answer', 'question_page');

);

Post as a guest

















1 Answer
1






active

oldest

votes








1 Answer
1






active

oldest

votes









active

oldest

votes






active

oldest

votes








up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16














up vote
8
down vote



accepted










Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer




















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16












up vote
8
down vote



accepted







up vote
8
down vote



accepted






Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.






share|improve this answer












Here's the code you want to speed up:



// Checks if the 2 provided puzzles are the same
bool puzzleTheSame(const Puzzle& puz1, const Puzzle& puz2)

 for ( int length = 0; length < PUZZLE_LENGTH; length++ )
 if ( puz1.state[length] != puz2.state[length] ) return false;
 return true;


bool puzzleExists(const Puzzle& currentPuzzle, vector<breadthPuzzle>& currentRoute)

 for ( int i = 0; i < currentRoute.size(); i++ )
 if ( puzzleTheSame(currentRoute[i].puzzle, currentPuzzle) )
 return true;
 return false;


// Checks if the provided puzzle is solved
bool isSolved(const Puzzle& solution)

 return puzzleTheSame(SOLVED_PUZZLE, solution);



It's a linear search over the array currentRoute: O(n) comparisons where n is the length of the current route.



For stylistic reasons, let's use the C++ syntax for "sameness" instead of the English words TheSame. Since everyone knows what == means in C++, we no longer need the code comment explaining what puzzleTheSame does.



bool operator==(const Puzzle& puz1, const Puzzle& puz2)

 return std::equal(std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExists(const Puzzle& currentPuzzle,
 const std::vector<breadthPuzzle>& currentRoute)

 for (auto&& elt : currentRoute) 
 if (elt.puzzle == currentPuzzle) 
 return true;
 
 
 return false;



We can also inline this next helper function everywhere it's used; having the name isSolved for it is not helpful anymore. By the way, your name for the parameter was misleading: the parameter is a puzzle, but it is not necessarily a solution. The whole point of the function is to find out whether it is a solution or not!



bool isSolved(const Puzzle& puzzle)

 return puzzle == SOLVED_PUZZLE;



Okay, so how do we speed it up? We get rid of the linear search in favor of a binary search!



bool operator<(const Puzzle& puz1, const Puzzle& puz2)

 return std::lexicographical_compare(
 std::begin(puz1.state), std::end(puz1.state),
 std::begin(puz2.state), std::end(puz2.state));


bool puzzleExistsInSet(const Puzzle& puzzle,
 const std::set<Puzzle>& seenPuzzles)

 return seenPuzzles.find(puzzle) != seenPuzzles.end();



Notice that this means we need to store the seen puzzles twice — once in the order we traversed them, in currentRoute, and again in sorted order, in seenPuzzles. So this improves our big-O asymptotic running time, but it might increase our "constant factor" so much as to erase that gain.



Speaking of naming, I notice that your solvePuzzle function is totally misnamed — it in no sense "solves" a puzzle. Appropriate names would be like slideBlock or makeMove — or just inlining it into its one caller.



But its one caller calls it four times! Can we fix that?



 if ( canNorth(gapLocation) ) solvePuzzle(breadthVector, i, north(gapLocation));
 if ( canEast(gapLocation) ) solvePuzzle(breadthVector, i, east(gapLocation));
 if ( canSouth(gapLocation) ) solvePuzzle(breadthVector, i, south(gapLocation));
 if ( canWest(gapLocation) ) solvePuzzle(breadthVector, i, west(gapLocation));


Yes. And that triggers a new refactoring that will reduce duplicated code elsewhere:



for (auto&& m : north(gapLoc), south(gapLoc), east(gapLoc), west(gapLoc) ) 
 if (isLegalMove(m)) 
 makeMove(breadthVector, i, m);



Keep going in this iterative fashion: Find an infelicity; think of how you want the code to look instead; and then refactor until it does look that way. Rinse and repeat.







share|improve this answer












share|improve this answer



share|improve this answer










answered Aug 9 at 18:24









Quuxplusone

10.1k11752




10.1k11752











  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16
















  • Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
    – Hirtol
    Aug 9 at 20:39






  • 1




    In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
    – Quuxplusone
    Aug 10 at 1:16















Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
– Hirtol
Aug 9 at 20:39




Thanks, after reading a questions came up: This is the first time I've seen rvalue references, so I'm probably wrong, but if I understood my quick google search correctly they are essentially references to a temporary variable (returned from function) and are used in order to avoid copying (Like you did for the auto&& m for the north, int results). What is the use for it in the puzzleExists function then? Wouldn't a normal reference suffice as you are referring to a permanent variable in the vector? Thanks again, didn't know about std::set and a binary search makes a lot more sense
– Hirtol
Aug 9 at 20:39




1




1




In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
– Quuxplusone
Aug 10 at 1:16




In for (auto&& elt : range), the construction auto&& is actually not an rvalue reference but a "forwarding reference," which basically means "I don't want to think about reference categories; just give me whatever kind of reference is appropriate for the right-hand side." auto&& always compiles, never dangles, and never makes a copy, in the specific context of a range-for-loop. It is rarely correct in any other context.
– Quuxplusone
Aug 10 at 1:16

















 

draft saved


draft discarded















































 


draft saved


draft discarded














StackExchange.ready(
function ()
StackExchange.openid.initPostLogin('.new-post-login', 'https%3a%2f%2fcodereview.stackexchange.com%2fquestions%2f201308%2fsolve-8-tile-sliding-puzzle%23new-answer', 'question_page');

);

Post as a guest
































































Comments

Post a Comment

Popular posts from this blog

Long meetings (6-7 hours a day): Being “babysat” by supervisor

Image
Clash Royale CLAN TAG #URR8PPP .everyoneloves__top-leaderboard:empty,.everyoneloves__mid-leaderboard:empty margin-bottom:0; up vote 31 down vote favorite 4 I hold a PhD in mechanical engineering with a 7 year background in self-guided, self-paced research including 2 years as a graduate level course instructor and a subject matter expert for various engineering projects in a university setting in the United States. For the last 10-11 months, I am working in a research industry in France where my task is to debug C++ spaghetti code written over a period of several years by my current supervisor. It is a team of 2: just I and my supervisor. Diurnally, I am posed with a "bug of the day" to get out of this C++ code. My supervisor generally gives me about 15-30 minutes to solve it and then accosts me about whether or not the task is completed and then rinses and repeats this until the end of the day. Off-late, my supervisor has been holding 6-7 hour long "meetin
Read more

Is the Concept of Multiple Fantasy Races Scientifically Flawed? [closed]

Image
Clash Royale CLAN TAG #URR8PPP up vote 2 down vote favorite Many fantasy worlds have multiple humanoid species (elves, orcs, humans, etc) living in the same world, in addition to that, they often have the ability to interbreed. And I can't help but question their believability... fantasy-races reproduction interspecies-relations share | improve this question edited Aug 9 at 14:46 Michael Kjörling ♦ 21.1k 10 85 161 asked Aug 9 at 13:13 Chlodio 118 6 closed as unclear what you're asking by MichaelK, Gryphon, John, Vincent, Frostfyre Aug 9 at 15:25 Please clarify your specific problem or add additional details to highlight exactly what you need. As it's currently written, it’s hard to tell exactly what you're asking. See the How to Ask page for help clarifying this question. If this question can be reworded to fit the rules in the help center, please edit the question. 3 Stack Exchange exist to
Read more

Confectionery

Image
Prepared foods made with a lot of sugar or other cabohydrates "Sweetmeat" redirects here. For the racehorse, see Sweetmeat (horse). Not to be confused with Sweetbread. This Kransekake is a traditional Scandinavian baker's confection. Confectionery is the art of making confections , which are food items that are rich in sugar and carbohydrates. Exact definitions are difficult. [1] In general, though, confectionery is divided into two broad and somewhat overlapping categories, bakers' confections and sugar confections. [2] Bakers' confectionery, also called flour confections , includes principally sweet pastries, cakes, and similar baked goods. Sugar confectionery includes candies ( sweets in British English), candied nuts, chocolates, chewing gum, bubble gum, pastillage, and other confections that are made primarily of sugar. In some cases, chocolate confections (confections made of chocolate) are treated as a separate category, as are sugar-free versions of
Read more