Dugu Chessboard Featured

Written by

Dugu chessboard is a puzzle chessboard I came across at grade 10.  It is a suprisingly interesting mathametical problem.  Here present two independent solutions formulated by me.  Examine closely the two solutions yield another hybrid solution that is extremely simple.  A detailed discussions on these solutions are presented.

 

Background

This is a puzzle chessboard I came across at grade 10. At the time there were some text-based multi-player online games known as MUD (Multi-User Dungeon).  These were the ancestors of MMORPG.  In one particular MUD game call  Eastern Story II (which was the only MUD game I spent some time on), there was a quest chessboard.  One had to solve the following chessboard puzzle in order to apprentice a unique master call Dugu, so I call the board the Dugu chessboard.

I and one of my friends (Andy) realized that this puzzle is a good challenging computer problem, and began a sleepless pursue to solve it.  Of course, a trivial solution to solve the board would be the brute-force method (try all solutions).  It would require 225 trials, which would take days for a PC at that time.  Furthermore, a trivial solution would not satisfy our deep desire to crack the problem in an elegant manner.  After two sleepless days, I was the first to propose a solution based on the idea of reduced complexity.  Two years later, I proposed another independent solution base on binary linear algebra.  I never learnt the formulism of linear algebra acting on binary number space, so there is some re-invent the wheel in the solution.  I am very proud of this solution, and it provided much more insight to the problem than I initially had.

Objective

The objective of the board quest is simple.  Initially there is a pattern on a 5x5 board.  Each square is a button, and can have a value of yellow or blue.  Press a buttons will flip its value as well as its neighbor's value.  The goal is to clear the pattern, (make all yellow), by pressing the right set of buttons.  

Solution 1: Complexity Reduction

The idea of complexity (row) reduction is simple.  Consider an initial pattern with three blue boxes in the first row as shown, we can always clear them by mirroring the pressing pattern on the second row (as shown in red).  In doing so, we generated a new pattern that begins on the second row.

 Dugu board Example A1

By repeating this process row by row, we can always reduce any 5x5 pattern to a 5x1 pattern in the last row, thus reduced the complexity from 225 (33554432) to 25 (32).  For example:

 Dugu Example A2

For now, we have not yet touched the first row.  If we press the correct set of buttons in the first row, corresponding to the pattern seen in the last row, and follow the same row reduction process, we can clear the board.  Since there is only 32 possible patterns, we can solve it with the brute force method with ease .  TaDa!! Solution!

Hey wait, we can further simplify the case by considering that the board has a mirror symmetry. For example, a pattern with one blue box at the lower left corner, is symmetrically equivalent to a blue box at the lower right corner.  Of those 32 possible patterns in the last row, there are 8 patterns that are symmetrical (eg: XOXOX), while the remaining 24 patterns has a symmetric partner (eg: XXXOO  <=>  OOXXX).  The number of non-symmetrically repeating patterns is then (32-8)/2 + 8 = 20.  Of those 20, 1 of them is the solution (all yellow).  So, there are only 19 possible independent solutions, which we can tabulate very easily.

 

 

 

 

 

 

 

 

 

Please read solution 2, we can further simplify the problem.

Solution 2: Binary Linear Algebra solution (Generalized)

We can solve it directly with linear algerbra.  I only realize this solution after I learnt linear algerbra at university.  At school, I'd never learnt linear algerbra can be extended to binary problems.  So, I re-invited the wheel and formulate a solution base on what I refer to as binary linear algebra.  Lets refer the buttons, rows and columns accordingly:

The challenge to this approach is to find the right way to encode the board properly.  We can consider representing the value of a pattern by +1 and -1, while flipping is done by muliplication of -1.  However, during matrix multiplication, operation of addition will destroy the information.  

The proper way to encode the board is to employ the odd-even number representation.  For instance, we can reprsent a pattern by a 25x1 vector, where elements with 'Even' values represent yellow and 'Odd' values  represent blue.  For simplicity, we limits the number space to 0 and 1. Lets employ a 25x1 column vector, p, where its elements are pi, to encode the pattern of a board.

Similarily, we can encode the function of each button in the same manner.  For example, pressing button 1 will flip the value of button 1, 2 and 6.  Then, the (25x1) column vector representing the function would have a value of 1 (odd) in position 1, 2 and 6, while the remaining elements have a value of 0 (even).  Let bi denote the column vectors corresponding to the function of ith button.  By joining all b i into a 25x25 matrix, B, namely:

(eq1)                  B = { bi }    for i in [ 1 .. 25],                                             

then, we can write the solution equation as:

(eq2)                   B . x = p ,                                                                

where x is the unknown (25x1) column vector, with binary elements representing the pressing pattern that will clear the board (1 = press, 0 = ignore ).  Anyone attempts to solve this equation will quickly realized that: 1) the matrix  B is symmetrical, and 2) matrix B is singular, it only has 23 degree of freedom! ( <= important! ).  Base on these two properties, we can solve the equation by ignoring any two buttons, and since it is symmetrical, we can also ignore any two corresponding pi.  In mathematical terms, can we select any arbutrary subset of B, x and p of rank 23.  Lets ignore the first two buttons, thus, remove {b1, b2, x1, x2, p1, p2}, and let the subspace be denoted by prime, then eq2 can be rewritten as:

(eq3)                  B' . x' = p'

To solve x' , we just need to find the inverse of B', namely:

(eq4)                   x' = ( B-1  B' ). x= B'-1. p'

Perform Echelon row operation on  < B' | I > gives us the inverse matrix, B'-1.  It will have its elements in fraction less than 1.   Now, this is the tricky part, where need to apply reasoning to make sense out of it.  Since we operate in binary mode, (ie press or not press), the norm of the matrix in meaningless.  So, we make B' -1 fraction-less by multiplying its elements with the largest common denominator, k.  It is 33 in this case.  Then, we can enforce all integer elements into the number space of 0 and 1, by modulation of 2.  Lets refer the the final matrix as C', then:

(eq5)                  C'i,j = (B'-1)i,j  mod 2

And apply the same reasoning to x', we get the solution as:

(eq6)                  x'j = ( C'i,j  * p') mod 2.

TaDa! Solution!

Please read the next section.

Ultimate Solution: Hybrid Approach

By combining the two methods, we can further simplify the solution.  It also allow us to gain deeper insight into the nature of the problem.  

The most important realization from the linear algerbra approach is that there are only 23 degree of freedom.  That means some sets of combinations of buttons are equivalent.  For example, pressing button 1 and 5 is equivalent to pressing button 3 after row reduction.  That implies:

1) one can keep two buttons untouched.

2) which implies that there are only 23 = 8 possible solutions when we consider the row reduction method.  ( kept two buttons in the first row untouched )

3) there exist unsolvable patterns, and they are the majority.  The number of solvable patterns is 223. while the total number of pattern is 225.  Which implies that only 1/4 or 25% of all possible board patterns are solvable.


Combining the two solutions, while ignoring button 1 and 2, we get:

x3 = ( p4 + p6 + p7 + p9 + p10 + p14 + p16 + p17 + p18 + p22 ) mod 2

x4 = ( p3 + p4 + p5 + p13 + p14 + p15 + p17 + p19 + p21 + p22 + p23 ) mod 2

x5 = ( p4 + p5 + p6 + p8 + p10 + p11 + p13 + p14 + p18 + p21 + p22 ) mod 2

The rest is row reduction mentioned in solution 1.


But wait, we can yet further simplify the solution!  Consider performing row reduction first, reducing a pattern to 5x1 pattern in the last row, then the ultimate solution is:

x3 =  p22

x4 = ( p21 + p22 + p23 ) mod 2

x5 = ( p21 + p22 ) mod 2

After that, we perform another row reduction, and the board should be cleared.  Note that the two degrees of ignored freedom are conserved during row reductions, such that the final solution is not dependent on p24 and p25.  Give the solution a try, it should be very easy to evaluate by hand.  Hope you enjoy this solution!

 

Read 4647 times

MY PROJECTS

These are projects and problems I encountered in the past, some of them are still in progress.  These are my pride and love!  The page was initially meant to serve as a documentary archieve for my-self and my friends.  But I decided to make it public, so that someone like you can by-chance come across this site, and share my love.  I hope you enjoy these projects as much as I do.  Feel free to leave some comments.

List of articles