Payal Prabhu
Assignment 5
Due: February 6th, 10:00am
Covering the Mutilated 8x8 Matrix
Note: I believe this problem to be different from the "Mutilated Chessboard" problem where the board has the squares colored black/white.
- Try to find an answer to this problem.
I didn't really try too hard to solve this problem since I was familiar with the Mutilated Chessboard problem and intuitively knew that a similar strategy could be applied to this case.
- Briefly document your thinking
I believe I "cheated" in my thought process since I was already aware of the reasoning that went into solving a similar problem. I knew there were 64 squares to be covered with 62 (paired) blocks. The problem lies in not being able to place a pair (domino) diagonally. With the restriction of placing it only horizontally or vertically, I knew I could either try placing them strictly in one direction, or using a combination of both vertical-and-horizontal placements. Once I had these two strategies, I decided to start once from a complete (finished) corner, and a second time from an incomplete (unfinished) corner. Either way, I would try to do a greedy placement where each (current) square on the matrix would be covered before picking up the next domino. When I reached the last row, this plan failed miserably since I was always left with one square that was a diagonal misfit.
- Which resources did you use to solve the problem?
I used multiple printouts of the empty 8x8 mutilated matrix and used a pencil to draw-in the dominoes using the above mentioned strategies. I also used simple math to understand the problem of covering 64 squares with an odd number of dominoes.
- Which process/practice did you use?
Note: The difference between a process and practice wasn't clear to me so I clubbed them together
Instinctively, I used the "scientific approach" where I tried to solve the problem by experimenting. After trying out a few combinations, I found that they all failed to cover the matrix completely. Eventually this led me to believe that the board could not be covered. Yet I can never really be sure (empirically) that this is an accurate conclusion. There could be numerous other arrangements that I did not attempt which could have led to the correct solution?!
- Could computers be useful to solve this problem?
In solving similar problems, computers would be a help. However, I believe using a simple/straight-forward program would result in a solution (if at all) with high time and space complexity.
- What have you learned (not) being able to solve the problem?
In doing this assignment, I talked to Dipti to find out how she approached the matrix-covering problem. Her reasoning seemed to be more "based in logic" than mine. Rather than trying to arrive at a solution through a trial-and-error method, she chose to develop a logical argument towards finding a solution to the problem. I think her argument would serve to solidifying the scientific approach I adopted. The idea of collaboratively working was extended to sharing individual strategies to arrive at a conclusion, which although the same, would not have been as concrete without the other approach.
          
|