I was playing with my kids during the long weekend and we were trying to solve a puzzle, 36 piece Tropical Fish, made by Outset Media. I have to admit that it was indeed “extremely difficult”, which are the words printed on the box. We gave up in the end. But in order to turn this activity into some positive result, I decided to show my kids how one can write a problem and get the computer to do the job for us. And here we start…
Basic Elements
Working with my kids we quickly identified that we need express each piece by its face and four sides. So let’s start with the definition of a piece and its face and sides.
Face enum
With extremely limited knowledge of tropical marine fish. We worked together to came up with below names.
1: public enum Face
2: {
3: Puffer,
4: Tang,
5: Rainbow,
6: Clown,
7: Zebra,
8: Stars,
9: }
Side enum
These names are even more farcical. But our goal was to have something that easy to remember, and each has a different first character so only one letter is needed in the printed out.
1: public enum Side
2: {
3: Red,
4: Angel,
5: WhiteHorse,
6: GreenHorse,
7: Strips
8: }
Piece class
1: public class Piece
2: {
3: public int Id { get; set; } // we assign a unique sequential id to search piece
4: public Face Face { get; set; }
5: public Side Top { get; set; }
6: public Side Bottom { get; set; }
7: public Side Left { get; set; }
8: public Side Right { get; set; }
9:
10: public override string ToString()
11: {
12: return Face + "-" + Id;
13: }
14: }
An Organized Box
Just like when we were doing the puzzle manually, we need a place to store and organize the pieces before they gets put into the puzzle. We let the Box do this job, and we also define all the pieces in the box just as what we got when the box was opened.
1: public class Box
2: {
3: readonly int _count;
4: readonly List<Piece> _pieces =
5: new List<Piece>
6: {
7: new Piece {Face = Face.Clown, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Angel, Left = Side.WhiteHorse,}, //0
8: new Piece {Face = Face.Clown, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.WhiteHorse, Left = Side.Red,},
9: new Piece {Face = Face.Clown, Top = Side.Angel, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.Red,},
10: new Piece {Face = Face.Clown, Top = Side.WhiteHorse, Right = Side.Red, Bottom = Side.Angel, Left = Side.GreenHorse,},
11: new Piece {Face = Face.Clown, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.WhiteHorse, Left = Side.Red,},
12: new Piece {Face = Face.Clown, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.WhiteHorse,},
13:
14: new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.WhiteHorse,}, //6
15: new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.Red, Bottom = Side.GreenHorse, Left = Side.WhiteHorse,},
16: new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.WhiteHorse,},
17: new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.Angel, Left = Side.WhiteHorse,},
18: new Piece {Face = Face.Puffer, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.Red, Left = Side.Strips,},
19: new Piece {Face = Face.Puffer, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Strips, Left = Side.WhiteHorse,},
20:
21: new Piece {Face = Face.Tang, Top = Side.WhiteHorse, Right = Side.Angel, Bottom = Side.Red, Left = Side.GreenHorse,}, //12
22: new Piece {Face = Face.Tang, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.WhiteHorse,},
23: new Piece {Face = Face.Tang, Top = Side.Angel, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Red,},
24: new Piece {Face = Face.Tang, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.WhiteHorse, Left = Side.Red,},
25: new Piece {Face = Face.Tang, Top = Side.Strips, Right = Side.WhiteHorse, Bottom = Side.Angel, Left = Side.GreenHorse,},
26: new Piece {Face = Face.Tang, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.Strips, Left = Side.Angel,},
27:
28: new Piece {Face = Face.Stars, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Red, Left = Side.Strips,}, //18
29: new Piece {Face = Face.Stars, Top = Side.Red, Right = Side.WhiteHorse, Bottom = Side.Angel, Left = Side.GreenHorse,},
30: new Piece {Face = Face.Stars, Top = Side.Strips, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Angel,},
31: new Piece {Face = Face.Stars, Top = Side.Angel, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Strips,},
32: new Piece {Face = Face.Stars, Top = Side.Strips, Right = Side.Red, Bottom = Side.WhiteHorse, Left = Side.GreenHorse,},
33: new Piece {Face = Face.Stars, Top = Side.GreenHorse, Right = Side.Red, Bottom = Side.WhiteHorse, Left = Side.Strips,},
34:
35: new Piece {Face = Face.Zebra, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.Red, Left = Side.GreenHorse,}, //24
36: new Piece {Face = Face.Zebra, Top = Side.Angel, Right = Side.Red, Bottom = Side.GreenHorse, Left = Side.Strips,},
37: new Piece {Face = Face.Zebra, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.WhiteHorse, Left = Side.Red,},
38: new Piece {Face = Face.Zebra, Top = Side.GreenHorse, Right = Side.Angel, Bottom = Side.Strips, Left = Side.Red,},
39: new Piece {Face = Face.Zebra, Top = Side.Red, Right = Side.Angel, Bottom = Side.Strips, Left = Side.GreenHorse,},
40: new Piece {Face = Face.Zebra, Top = Side.Red, Right = Side.WhiteHorse, Bottom = Side.GreenHorse, Left = Side.Angel,},
41:
42: new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.Strips,}, //30
43: new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.GreenHorse, Left = Side.Angel,},
44: new Piece {Face = Face.Rainbow, Top = Side.WhiteHorse, Right = Side.Strips, Bottom = Side.Angel, Left = Side.GreenHorse,},
45: new Piece {Face = Face.Rainbow, Top = Side.Angel, Right = Side.GreenHorse, Bottom = Side.Strips, Left = Side.Red,},
46: new Piece {Face = Face.Rainbow, Top = Side.Strips, Right = Side.GreenHorse, Bottom = Side.Angel, Left = Side.Red,},
47: new Piece {Face = Face.Rainbow, Top = Side.GreenHorse, Right = Side.Strips, Bottom = Side.WhiteHorse, Left = Side.Angel,},
48: };
49:
50:
51: public Box()
52: {
53: _count = _pieces.Count;
54:
55: for (int i = 0; i < _count; i++)
56: {
57: _pieces[i].Id = i;
58: }
59: }
60:
61: public Piece Take(int index, Predicate<Piece> condition)
62: {
63: for (int i = index; i < _count; i++)
64: {
65: var piece = _pieces[i];
66: if (piece == null) continue;
67: if (condition(piece))
68: {
69: _pieces[i] = null;
70: return piece;
71: }
72: }
73: return null;
74: }
75:
76: public void Return(Piece piece)
77: {
78: _pieces[piece.Id] = piece;
79: }
80: }
In the Box class, we first defined all 36 pieces in a list. Then in the constructor Box(), we gave each piece a unique ID, which is same as its position in the list. We then defined two methods to control the taking and returning of the pieces.
When a piece is taken from the box by using the Take() method, we need to specify a starting index and the condition to search for a matching piece. The starting index is important so that we don’t retry pieces that we already did. The condition is passed in according to the rules of the puzzle and the pieces already put on the puzzle.
When we are stuck, we need to be able to return the piece back and try next. The Box’s Return() method does this job by putting the piece back to its original position in the list.
The Solver
The solver has a box and a table to solve the puzzle, they are defined and initialized in line 4 and 5. The Main method is the C#’s entry point. It simply calls FindSolution() method to find the solutions, when no solution is found, it displays an error message.
The core logic resides in two methods, FindSolution() and CheckPiece().
CheckPiece verifies if a new piece fits with pieces were already put on the puzzle. It checks:
- The top edge of the piece matches the bottom of the piece above it, unless the new piece will be put on the first row.
- The left edge of the piece matches the right side of the piece on its left, unless the new piece will be put on the first column.
- There is no piece already on the puzzle in the same row has same face as the one being checked. (Sudoku)
- There is no piece already on the puzzle in the same column has same face as the one being checked. (Sudoku)
FindSolution goes through each spot of the puzzle from left to right and top to bottom. It tires each piece one by one until the last spot is filled. When it is stuck, it returns the last piece back to the box and try next one.
When a solution is found, PrintSolution() method is called to print out the layout of the pieces in the solved puzzle.
1: public class Solver
2: {
3: private const int _size = 6;
4: static Piece[,] _puzzle = new Piece[_size,_size];
5: static Box _box = new Box();
6:
7: public static void Main()
8: {
9: if (FindSoution() == 0)
10: {
11: Console.WriteLine("No Answer :(");
12: }
13: }
14:
15: private static int FindSoution()
16: {
17: var count = 0;
18: var i = 0;
19: for (; ; )
20: {
21: var col = i % _size;
22: var row = i / _size;
23:
24: var index = 0;
25: var piece = _puzzle[row, col];
26: if (piece != null) // if we already tried one or more pieces
27: {
28: _puzzle[row, col] = null; // clear
29: _box.Return(piece); // return it back to box
30: index = piece.Id + 1; // and start search for one after it.
31: }
32:
33: piece = _box.Take(index, x => CheckPiece(row, col, x));
34: if (piece == null)
35: {
36: if (i == 0) return count;
37: i--;
38: continue;
39: }
40: _puzzle[row, col] = piece;
41: if (i != _size * _size - 1)
42: {
43: i++;
44: continue;
45: }
46: ++count;
47: Console.WriteLine("Answer " + count);
48: PrintSolution(Console.Out, _puzzle);
49: }
50: }
51:
52: private static bool CheckPiece(int row, int col, Piece x)
53: {
54: if (row != 0 && _puzzle[row - 1, col].Bottom != x.Top ||
55: col != 0 && _puzzle[row, col - 1].Right != x.Left)
56: {
57: return false;
58: }
59: // comment below two for loop to find all non-sudoku answers
60: for (int i = 0; i < row; i++)
61: {
62: if (_puzzle[i, col].Face == x.Face) return false;
63: }
64: for (int i = 0; i < col; i++)
65: {
66: if (_puzzle[row, i].Face == x.Face) return false;
67: }
68: return true;
69: }
70:
71: private static void PrintSolution(TextWriter writer, Piece[,] pieces)
72: {
73: var rows = pieces.GetLength(0);
74: var cols = pieces.GetLength(1);
75: for (var row = 0; row < rows; row++)
76: {
77: for (var col = 0; col < cols; col++)
78: {
79: writer.Write(string.Format(" {0} ",
80: pieces[row, col].Top.ToString()[0]));
81: }
82: writer.WriteLine();
83: for (var col = 0; col < cols; col++)
84: {
85: var piece = pieces[row, col];
86: writer.Write(string.Format("{0} {1} {2} ",
87: piece.Left.ToString()[0],
88: piece.Face.ToString().Substring(0, 4),
89: piece.Right.ToString()[0]));
90: }
91: writer.WriteLine();
92: for (var col = 0; col < cols; col++)
93: {
94: writer.Write(string.Format(" {0} ",
95: pieces[row, col].Bottom.ToString()[0]));
96: }
97: writer.WriteLine();
98: }
99: }
100: }
Solution
There is only one solution if the Sudoku rules is considered. The program quickly finds the solution below:
R G A W A G G Zebr A A Rain S S Star G G Clow R R Tang W W Puff S S W R A G A S W R A G A W Clow G G Tang A A Zebr W W Puff S S Star R R Rain G A R G G W S A R G G W S W Puff G G Star W W Clow R R Zebr S S Rain G G Tang W S A A W A A S A A W A A A Star W W Puff R R Tang G G Rain S S Zebr R R Clow S G G W A G G G G W A G G W Tang R R Clow A A Rain S S Star W W Puff R R Zebr A S W G G S S S W G G S S R Rain G G Zebr S S Puff A A Tang R R Clow G G Star R A R R S W W
If the Sudoku rules is not considered, there are total 608 solutions. It took the program a few hours to find all of those.
Some additional interesting facts are:
- When Sudoku rule is considered, the program made 647,970 calls to Box.Take() and 8,803,132 calls to CheckPiece() to find the solution in 2 seconds.
- When Sudoku rule is NOT considered, it took 45 seconds to find the first solution after 30,701,706 calls to Box.Take() and 235,103,280 calls to CheckPiece().
No comments:
Post a Comment