Puzzles

We don't need a computer to illustrate programming and algorithms.

The Fox, the Goose and the Corn

A farmer with a fox, a goose, and a sack of corn needs to cross a river. The farmer has a rowboat, but there is room for only the farmer and one of his three items. Unfortunately, both the fox and the goose are hungry. The fox cannot be left alone with the goose, or the fox will eat the goose. Likewise, the goose cannot be left alone with the sack of corn, or the goose will eat the corn. How does the farmer get everything across the river?

The basic instructions in this programming problem are:

row back (0)
row with the fox to the other side (1)
row with the goose to the other side (2)
row with the sack of corn to the other side (3)

Only instruction (2) can be executed without loosing or the goose, or the corn and then we are stuck ... or not?

It is not prohibited to row back with an item. So supplementary instructions are:

row back with the fox (4)
row back with the goose (5)
row back with the sack of corn (6)

So the sequence of instructions to solve this problem is:

(2) – (0) – (1) – (5) – (3) – (0) – (2)

This puzzle would be easier to solve if the possibility to taking one of the items back was made explicit.

This illustrate an important principle of problem solving. If you are unaware of all possible actions you can take, you may be unable to solve the problem. We can refer to these actions as operations. By enumerating all the possible operations, we can solve many problems by testing every combination of operations until we find one that works.

Sliding Tile Puzzles

A 3×3 grid is filled with eight tiles, numbered 1 through 8, and one empty space. Initially, the grid is in a jumbled configuration. A tile can be slid into an adjacent empty space, leaving the tile's previous location empty. The goal is to slide the tiles to place the grid in an ordered configuration, with tile 1 in the upper left.



In [1]:

    
using TikzPictures
TikzPicture(L"""
    \node at (0,0) [minimum size=0.5cm, align=center, draw] {3};
    \node at (0.6,0) [minimum size=0.5cm, align=center, draw] {5};
    \node at (1.2,0) [minimum size=0.5cm, align=center, draw] {};
    \node at (0,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (0.6,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (1.2,0.6) [minimum size=0.5cm, align=center, draw] {1};
    \node at (0,1.2) [minimum size=0.5cm, align=center, draw] {4};
    \node at (0.6,1.2) [minimum size=0.5cm, align=center, draw] {7};
    \node at (1.2,1.2) [minimum size=0.5cm, align=center, draw] {2};
    \node at (4,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (4.6,0) [minimum size=0.5cm, align=center, draw] {8};
    \node at (5.2,0) [minimum size=0.5cm, align=center, draw] {};
    \node at (4,0.6) [minimum size=0.5cm, align=center, draw] {4};
    \node at (4.6,0.6) [minimum size=0.5cm, align=center, draw] {5};
    \node at (5.2,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (4,1.2) [minimum size=0.5cm, align=center, draw] {1};
    \node at (4.6,1.2) [minimum size=0.5cm, align=center, draw] {2};
    \node at (5.2,1.2) [minimum size=0.5cm, align=center, draw] {3};
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[1]:

In this puzzle, the problem is not overlooking the possible actions. From any given configuration, from two to four tiles may be adjacent to the empty space, and any of those tiles can be slid into the empty space.

Moving the tiles randomly is not a good choice because we can not measure progress. We need a strategy to solve this puzzle. To illustrate a possible approach, let's consider the puzzle for a smaller grid.



In [2]:

    
TikzPicture(L"""
    \node at (0,0) [minimum size=0.5cm, align=center, draw] {5};
    \node at (0.6,0) [minimum size=0.5cm, align=center, draw] {4};
    \node at (1.2,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (0,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (0.6,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (1.2,0.6) [minimum size=0.5cm, align=center, draw] {};
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[2]:

If you play around with these tiles for just a few minutes, you will probably hit upon a solution. From playing around with small-count tile puzzles the following observation can be made: a circuit of tile positions that includes the empty space forms a train of tiles that can be rotated anywhere along the circuit wile preserving the relative ordering of the tiles.



In [3]:

    
TikzPicture(L"""
    \node at (0,0) [minimum size=0.5cm, align=center, draw] {5};
    \node at (0.6,0) [minimum size=0.5cm, align=center, draw] {4};
    \node at (1.2,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (0,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (0.6,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (1.2,0.6) [minimum size=0.5cm, align=center, draw] {};
    \draw[dashed, gray,-latex] (1.2, 0) -- (0, 0) -- (0, 0.6) -- (1.2, 0.6);
    \node at (2,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (2.6,0) [minimum size=0.5cm, align=center, draw] {};
    \node at (3.2,0) [minimum size=0.5cm, align=center, draw] {8};
    \node at (2,0.6) [minimum size=0.5cm, align=center, draw] {4};
    \node at (2.6,0.6) [minimum size=0.5cm, align=center, draw] {5};
    \node at (3.2,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \draw[dashed, gray,-latex] (3.2, 0) -- (2.6, 0);
    \node at (4,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (4.6,0) [minimum size=0.5cm, align=center, draw] {8};
    \node at (5.2,0) [minimum size=0.5cm, align=center, draw] {};
    \node at (4,0.6) [minimum size=0.5cm, align=center, draw] {4};
    \node at (4.6,0.6) [minimum size=0.5cm, align=center, draw] {5};
    \node at (5.2,0.6) [minimum size=0.5cm, align=center, draw] {6};
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[3]:

This can be used to solve larger sliding tile puzzles.



In [4]:

    
TikzPicture(L"""
    \node at (0,0) [minimum size=0.5cm, align=center, draw] {3};
    \node at (0.6,0) [minimum size=0.5cm, align=center, draw] {5};
    \node at (1.2,0) [minimum size=0.5cm, align=center, draw] {};
    \node at (0,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (0.6,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (1.2,0.6) [minimum size=0.5cm, align=center, draw] {1};
    \node at (0,1.2) [minimum size=0.5cm, align=center, draw] {4};
    \node at (0.6,1.2) [minimum size=0.5cm, align=center, draw] {7};
    \node at (1.2,1.2) [minimum size=0.5cm, align=center, draw] {2};
    \draw[dashed, gray,-latex] (0.6, 0) -- (0.6, 1.2) -- (1.2, 1.2) -- (1.2, 0);
    \node at (2,0) [minimum size=0.5cm, align=center, draw] {3};
    \node at (2.6,0) [minimum size=0.5cm, align=center, draw] {2};
    \node at (3.2,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (2,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (2.6,0.6) [minimum size=0.5cm, align=center, draw] {1};
    \node at (3.2,0.6) [minimum size=0.5cm, align=center, draw] {};
    \node at (2,1.2) [minimum size=0.5cm, align=center, draw] {4};
    \node at (2.6,1.2) [minimum size=0.5cm, align=center, draw] {5};
    \node at (3.2,1.2) [minimum size=0.5cm, align=center, draw] {6};
    \draw[dashed, gray,-latex] (3.2, 1.2) -- (2, 1.2) -- (2, 0) -- (2.6, 0) -- (2.6, 0.6) -- (3.2, 0.6);
    \node at (4,0) [minimum size=0.5cm, align=center, draw] {5};
    \node at (4.6,0) [minimum size=0.5cm, align=center, draw] {4};
    \node at (5.2,0) [minimum size=0.5cm, align=center, draw] {7};
    \node at (4,0.6) [minimum size=0.5cm, align=center, draw] {6};
    \node at (4.6,0.6) [minimum size=0.5cm, align=center, draw] {8};
    \node at (5.2,0.6) [minimum size=0.5cm, align=center, draw] {};
    \node at (4,1.2) [minimum size=0.5cm, align=center, draw] {1};
    \node at (4.6,1.2) [minimum size=0.5cm, align=center, draw] {2};
    \node at (5.2,1.2) [minimum size=0.5cm, align=center, draw] {3};
    \draw[dashed, gray,-latex] (4.6, 0.6) -- (5.2, 0.6);
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[4]:

The number of tile movements is too large to plan out a complete solution from an initial configuration. However, this does not prevent us from making a strategy to systematically solve the puzzle. It's better to develop an algorithm than to start programming through trial and error.
The "train" technique was developped from fiddling around with a small puzzle. Often experimenting with a reduced version of a programming problem produces valuable insights.
Sometimes problems are divisible in ways that are not immediately obvious. One might think that a slide tile puzzle must be solved all in one step, not in stages. Looking for a way to divide a problem is usually time well spent.

Sudoku

A 9×9 grid is partially filled with single digits (from 1 to 9), and the player must fill in the empty squares while meeting certain constraints: in each row and each column, each digit must appear exactly once, and further,in each marked 3×3 area, each digit must appear also exactly once.



In [5]:

    
TikzPicture(L"""
    \draw[step=0.5, gray, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \draw[step=1.5, black, ultra thick, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \node at (1,0) {5};\node at (2,0) {4};\node at (3,0) {6};\node at (3.5,0) {9};
    \node at (0,0.5) {6};\node at (0.5,0.5) {7};\node at (1.5,0.5) {1};\node at (2,0.5) {5};
    \node at (1,1) {9};\node at (3,1) {5};\node at (4,1) {7};
    \node at (0,1.5) {1};\node at (0.5,1.5) {4};\node at (1.5,1.5) {8};\node at (2,1.5) {2};\node at (2.5,1.5) {5};
    \node at (1,2) {2};\node at (1.5,2) {4};\node at (2.5,2) {6};\node at (3,2) {8};
    \node at (1.5,2.5) {9};\node at (2,2.5) {1};\node at (2.5,2.5) {3};\node at (3.5,2.5) {6};\node at (4,2.5) {2};
    \node at (0,3) {5}; \node at (1,3) {3}; \node at (3,3) {2};
    \node at (2,3.5) {8}; \node at (2.5,3.5) {2}; \node at (3.5,3.5) {3}; \node at (4,3.5) {9};
    \node at (0.5,4) {9}; \node at (1,4) {1}; \node at (2,4) {6}; \node at (3,4) {7};
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[5]:

If you have played this game before, you probably already have a set of strategies for completing a square in the minimum time. Let's focus on the key strategy. The question is, which squares should we attempt to fill in first?

Remember the puzzle constraints. Each of th nine digits must appear in every row, in every column, and in every 3×3 area marked by the heavy border. These rules dictate where we should begin our efforts.



In [6]:

    
TikzPicture(L"""
    \draw[step=0.5, gray, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \draw[step=1.5, black, ultra thick, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \node at (1,0) {5};\node at (2,0) {4};\node at (3,0) {6};\node at (3.5,0) {9};
    \node at (0,0.5) {6};\node at (0.5,0.5) {7};\node at (1.5,0.5) {1};\node at (2,0.5) {5};
    \node at (1,1) {9};\node at (3,1) {5};\node at (4,1) {7};
    \node at (0,1.5) {1};\node at (0.5,1.5) {4};\node at (1.5,1.5) {8};\node at (2,1.5) {2};\node at (2.5,1.5) {5};
    \node at (1,2) {2};\node at (1.5,2) {4};\node at (2.5,2) {6};\node at (3,2) {8};
    \node at (1.5,2.5) {9};\node at (2,2.5) {1};\node at (2.5,2.5) {3};\node at (3.5,2.5) {6};\node at (4,2.5) {2};
    \node at (0,3) {5}; \node at (1,3) {3}; \node at (3,3) {2};
    \node at (2,3.5) {8}; \node at (2.5,3.5) {2}; \node at (3.5,3.5) {3}; \node at (4,3.5) {9};
    \node at (0.5,4) {9}; \node at (1,4) {1}; \node at (2,4) {6}; \node at (3,4) {7};
    \node at (2,2)[fill=gray, minimum size=0.5cm]{ };
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[6]:



In [7]:

    
TikzPicture(L"""
    \draw[step=0.5, gray, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \draw[step=1.5, black, ultra thick, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \node at (1,0) {5};\node at (2,0) {4};\node at (3,0) {6};\node at (3.5,0) {9};
    \node at (0,0.5) {6};\node at (0.5,0.5) {7};\node at (1.5,0.5) {1};\node at (2,0.5) {5};
    \node at (1,1) {9};\node at (3,1) {5};\node at (4,1) {7};
    \node at (0,1.5) {1};\node at (0.5,1.5) {4};\node at (1.5,1.5) {8};\node at (2,1.5) {2};\node at (2.5,1.5) {5};
    \node at (1,2) {2};\node at (1.5,2) {4};\node at (2.5,2) {6};\node at (3,2) {8};
    \node at (1.5,2.5) {9};\node at (2,2.5) {1};\node at (2.5,2.5) {3};\node at (3.5,2.5) {6};\node at (4,2.5) {2};
    \node at (0,3) {5}; \node at (1,3) {3}; \node at (3,3) {2};
    \node at (2,3.5) {8}; \node at (2.5,3.5) {2}; \node at (3.5,3.5) {3}; \node at (4,3.5) {9};
    \node at (0.5,4) {9}; \node at (1,4) {1}; \node at (2,4) {6}; \node at (3,4) {7};
    \node at (2,2){7};
    \node at (2,1)[fill=gray, minimum size=0.5cm]{ };
    \node at (2,3)[fill=gray, minimum size=0.5cm]{ };
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[7]:



In [8]:

    
TikzPicture(L"""
    \draw[step=0.5, gray, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \draw[step=1.5, black, ultra thick, xshift=-0.25cm,yshift=-0.25cm](0,0) grid (4.5,4.5);
    \node at (1,0) {5};\node at (2,0) {4};\node at (3,0) {6};\node at (3.5,0) {9};
    \node at (0,0.5) {6};\node at (0.5,0.5) {7};\node at (1.5,0.5) {1};\node at (2,0.5) {5};
    \node at (1,1) {9};\node at (3,1) {5};\node at (4,1) {7};
    \node at (0,1.5) {1};\node at (0.5,1.5) {4};\node at (1.5,1.5) {8};\node at (2,1.5) {2};\node at (2.5,1.5) {5};
    \node at (1,2) {2};\node at (1.5,2) {4};\node at (2.5,2) {6};\node at (3,2) {8};
    \node at (1.5,2.5) {9};\node at (2,2.5) {1};\node at (2.5,2.5) {3};\node at (3.5,2.5) {6};\node at (4,2.5) {2};
    \node at (0,3) {5}; \node at (1,3) {3}; \node at (3,3) {2};
    \node at (2,3.5) {8}; \node at (2.5,3.5) {2}; \node at (3.5,3.5) {3}; \node at (4,3.5) {9};
    \node at (0.5,4) {9}; \node at (1,4) {1}; \node at (2,4) {6}; \node at (3,4) {7};
    \node at (2,2){7};
    \node at (2,1){3};
    \node at (2,3)[]{9};
"""; options="very thick, scale=3, transform shape", preamble="""
    \\usepackage{newtxmath}
    \\renewcommand{\\familydefault}{\\sfdefault}
""")









    Out[8]:

The main lesson from sudoku is that we should look for the most constrained part of the problem. While constraints are often what make a problem difficult to begin with, they may also simplify our thinking about the solution because they eliminate choices.

The same technique can often be applied to programming problems. If one of the problem is heavily constrained, that's a great place to start because you make progress without worrying that you are spending time on work that will later be undone. A related corollary is that you should start with the part that's obvious. If you can solve part of the problem, go ahead and do what you can.

General Problem Solving Techniques

Always have a plan
Restate the problem
Divide the problem
Start with what you know
Reduce the problem
Look for analogies
Experiment
Don't get frustrated