DE2 Project - Matchstick Riddle
Introduction to the DE2 board project and software
This hub describes how to implement a famous matchstick riddle for the Altera DE2 board using 64-bits Quartus II version 7.1. The Altera DE2 board was designed to assist students in easily learning digital logic, computer organization, and FPGAs (Field-Programmable Gate Arrays). Quartus is an essential program in digital logic development with easy to use software. This group project deals with a semester long investigation into aspects of digital logic design and the DE2 board.
Try the riddle yourself!
The Matchstick Riddle
The origins of the matchstick riddle can be traced as far back as the 19th century when matches were first manufactured. Matchstick companies started to print these puzzles on their boxes and a new form of entertainment emerged as matchsticks grew in popularity. Matchstick riddles are rearrangement puzzles where a specific amount of matchsticks are arranged as quadrilaterals. The format of the riddle is usually “move n matchsticks to make m squares.” Where n is the amount of matchsticks moved, and the person solving the riddle cannot exceed the amount of n. It is assumed that the puzzle cannot be solved if less than n matchsticks are moved. The variable m is the amount of squares obtained after the required matches are moved, the riddle expects no more and no less squares than m.
Implementation of the project on the Altera DE2 Board
The theory is that the matchstick riddle can be recreated on the Altera DE2 board using low complexity combinational and sequential logic design. The matchstick riddle has many variations, however this particular riddle was chosen because of the use of the HEX display on the board. We can use combinational logic so users can choose a matchstick to move to solve the riddle using the Altera DE2 board.
The design of the projects starts with selecting the specific segment that represents a matchstick the user can move. Then the user can toggle the select segment off to represent that they have removed the matchstick and turn the segment on to represent that a matchstick has been moved to a different location. The toggle is connected to a counter that will ensure that the user is only provided the amount of moves the riddle dictates. Failure to solve the riddle before the counter reaches its limit will display an error message as well as lock the controls so that no further attempts can be made until the riddle has been reset. Successfully solving the puzzle will display a congratulatory message for the user, and provide the user bragging rights to his and her colleagues and the self-assurance that they are incredibly witty and smart.
An Example of the Matchstick Riddle on the DE2 Board
Schematics and Diagrams
Setting the pins for the AlteraDE2 board was not difficult but still very tedious. Below is a diagram of the design to determine the toggle and switches used to implement the matchstick riddle.
It was acknowledged that the 7-segments had to have an initial state to mimic the matchstick riddle. This was an obstacle that required the group to deviate from the original matchstick puzzle was that there were two segments in the display that represent one matchstick. It was determined that if the design had to be adapted to the 7-segment display. To simplify the program, we altered the initial state of the matchsticks so that it still mimics the riddle on the 7-segment display but have only one possible solution. Figure 3 below is the diagram used in the design process to determine which segments had to be turned on for the initial state.
The 7-segment displays are used without a 7447 Decoder Chip, they were connected directly into the output and logical 0 lights up the segment and logical 1 will turn off the segment. Figure 4 below shows what the user will see at the start of the riddle and Figure 5 will be the solution state if the user is able to answer the solve the riddle.
The display of the riddle on the 7-segment display the design had to be made into a block diagram in order to compartmentalize the functions that were required to implement the matchstick riddle. The matchstick riddle needed the following functions 1) be able to control 28 segments from four 7-segement displays; 2) toggle on and toggle off function; 3) memory function for each of the 28 segments; 4) a counter to keep track of the moves made by the user; 5) a way to detect when the amount of moves allowed have been exhausted; 6) once the detector has been triggered the user will not be allowed anymore moves; 7) an error message will display to indicate failure to solve the puzzle; 8) if the puzzle has been solved a message will display to indicate that the user has succeeded in answering the riddle; 9) allow the user to reset the puzzle so that it can be used again.
Matchstick Project Riddle
The schematic design for selecting individual segment had many revisions. The goal was to make it as minimized as possible, using less the least possible amount of switches to make to make it easier to use but still be able to control all 28 segments. The concept used to solve this problem is the use of a decoder. The first is a 2-to-4 decoder to allow the user to select one of the four 7-segment displays. Figure 6 below is the decoder made using inverters and 2 input and gates. This was derived from multiplexers and the 7447 decoder.
Quartus II Schematics
Figure 7: Simulation waveform for 2-to-4 decoder
This logic was expanded to have 3 bits of input so that we could have a 3-to-8 decoder to select a segment. However since there were only 7-segments that needed to be initialized per display the design of the 3-to-8 decoder does have any output connected if all inputs were 0. Figure 8 shows the schematic for the 3-to-8 decoder and Figure 9 is its functional waveform simulation. The theory behind this is similar to the first decoder mentioned above. The truth tables for both decoders are shown below:
The design and implementation of the two decoders provides a very simple but yet elegant solution to minimizing the switches necessary to select a specific segment in a specific 7-segment display. The user selects the display that contains the segment they want to turn on and off using the first decoder and then uses the second decoder to select the specific segment they want to use. The output of these two decoders are connected with an AND gate so that the segments are only accessible if its corresponding row and segment are selected simultaneously.
The memory function for the matchstick riddle is very straight forward. Each segment is connected to a D Flip-Flop. The value of the input is 1 if the corresponding row and column are chosen. The toggle or clock is connected to an AND gate so that one toggle can be used for all 28 segments. If the corresponding row and column are not selected than the clock will not be activated. Figure 10 below is the sample of the schematic for a 1 bit memory cell that is used in the project; however there are 28 memory cells in total in the whole design.
The counter used to keep track of the moves uses three JK Flip – Flops with a 1-bit memory cell. The counter was designed to count each time the toggle was pressed to turn the segments on or off. Due to this design the group had to alter the rules of the riddle since it was impossible to solve the puzzle in two moves using combinational logic. The number of moves was increased to four moves instead of two on the original riddle. Attached to the counter is an OR Gate and an AND Gate that would trigger the 1-bit memory cell to block any more moves by disabling all of 28 memory cells for the segments and also display the message “NO” to indicate that the user has failed. As seen in figure 11 below the OR and AND gate are connected such that once the counter reaches the value of 101 (five moves) or higher, then the fail and block mechanism is triggered and the only way to change it is to reset.
Blocks 5 through 7 are very simple and straight forward. The group utilizes the remaining four 7-segments displays left in the AlteraDE2 board. A four input AND gate is used to detect if the correct two segments were turned off and the correct two were turned on to solve the puzzle, if these requirements are satisfied then the memory cell that triggers the message to show that the user has successfully solved the riddle. As for the display of the messages the group does not utilize the 7447 decoder and the segments are connected directly into the output and logical 0 lights up the segment and logical 1 will turn off the segment. As for the reset after the user has failed to solve the puzzle, the reset switch is one switch that resets the entire puzzle as they are connected.
The complete schematic of the system is shown in figure 12 below:
Complete Schematic of the Matchstick Riddle Project
Possible Changes for the project
- Consider connecting segments B and F and C and E together so that they act as one segment. During the building of the schematic it was realized that this was not absolutely necessary but would make the matchstick riddle more realistic on the Altera DE2 board.
- Connect a breadboard to the AlteraDE2 board to make bigger puzzles so there is no limit to what puzzle is used.