Homework Assignment 5
Tomohiro Oda
1.try to find an answer to this problem!
I designed an algorithm to solve it, implemented it and got the answer that there is no solution. I also googled but found no solution on the net.
2.document briefly your thinking – including all the important intermediate steps and failing attempts (i.e., create a "think-aloud protocol")
I first tried to solve manually on browser's screen. I found it is really hard problem.
I therefore decided to use Smalltalk to solve it.
The basic algorithm I implemented is as follows.
- pick an empty cell of which upper, upper-left and left neighboring cells are all occupied.(out-of-bounds are considered occupied)
- try fitting a domino horizontally (placing at (x, y) and (x+1,y)) and continue the whole procedure recursively
- try vertical (placing at (x, y) and (x, y+1)) and continue
- if neither 2 nor 3 works, backtrack and continue.
I think this algorithm works by the following reason;
- There exists at least one empty cell of which upper, upper-left and left neighbors are occupied unless the board is fully occupied.
- On such a cell, the only two ways to place a domino is to occupy the cell and its right or lower neighbor.
This algorithm tries O(2^n) attempts at most, where n is number of dominos.
I implemented it in Smalltalk and C.
Here are source codes in Smalltalk hw5-tomo-appendixA and C hw5-tomo-appendixB.
They both tell that there is no solution for the problem.
I finally googled "Multilated 8x8 Matrix" to find the solution and got 6 matches. I found two of them describes the same problem.
However, neither one describes the solution.
I also tried google with japanese keywords, but I could not find a page which described the same problem.
3.which resources did you use to solve the problem?
Smalltalk system, C compiler and google
4.which process did you use?
I'm not quite sure about the distinction of process and practice, but I would say;
- I tried by myself.
- I used computer support. (collaboration with computer; programming language and search engine)
- I tried to use other people's outcomes. (collaboration with people)
5.which practice (of you or others) did you use?
I tried manually –> failed.
I designed an algorithm to solve it –> found there is no solution.
I looked for solution on the net –> failed.
6.could computers be useful to solve this problem?
Yes. I totally relied on computation power.
However, I still need verification of the algorithm and the programs in order to prove that there is no solution.
7.what have you learned solving the problem: in general and for our course?
I think the best scenario is that variety kinds of specialists try different specialized approaches and share the solution.
On other words, benefits of the symmetry of ignorance are not in the common part, but sharing outcomes of uncommon knowledge and skills.
In this particular case, I could do nothing without outcomes of compiler designers.
8.what have you learned not being able to solve the problem: in general and for our course?
There are lots of problems which look similar to this problem but can not be practically solved by computer programming.
In such cases, someone else, e.g. logicians or mathematicians, might be able to solve and we could share their outcomes via Internet.