12
\$\begingroup\$

Task:

Consider the problem: "given a chessboard with one square missing, cut it into 21 L-triominoes". There is a well-known constructive proof that this can be done for any square chessboard size that is a power of two. It works by splitting the chessboard into a smaller chessboard with the hole in it and one big triomino and then observing that that triomino can be cut into four triominoes recursively.

In this task, you are required to cut an 8x8 chessboard into L-shaped triominoes and then to color them with four colors such that no two adjacent triominoes have the same color.

Specification:

Your input is the position of the hole, given as a pair of integers. You may choose which one is the column index and which one is the row index. You may choose if each starts at 0 or at 1 and away from which corner they increase. You may require A..H as the first coordinate instead of 0..7 or 1..8. You may also accept both coordinates packed into a single integer 0..63 or 1..64 in lexicographical order (row-major or column-major, left to right or right to left, up to down or down to up). You may write a full program, or a function.

You may output the tiling as ASCII, as colored ASCII or as graphical primitives. If you choose ASCII output, you may choose any four printable ASCII characters to represent the four colors. If you choose colored ASCII, you may choose any four printable ASCII characters or just one character other than space. The hole must be represented by the space character. If one of your characters is the space character, no triomino adjacent to the hole or at the chessboard edge may be of this color.

If you choose colored ASCII or graphical output, you may choose any four colors out of #000, #00F, #0F0, #0FF, #F00, #F0F, #FF0, #FFF or their closest equivalents available in your environment. If you choose graphical output, your graphical primitives must be filled squares at least 32x32 pixels in size and separated by no more than two pixels of other color. If the above exceeds the screen resolution of your environment, the minimum size requirement is relaxed to the largest square size that still fits on the screen.

You may choose any valid tiling of the given chessboard. You may choose any four-coloring of the tiling you choose. Your choice of four colors must be the same across all outputs, but you aren't required to use every color in every output.

Examples:

Possible output for input = [0, 0] (top left corner)

 #??##??
##.?#..?
?..#??.#
??##.?##
##?..#??
#.??##.?
?..#?..#
??##??##

Another possible output of the same program (input = [0, 7]):

??#??#?
?##?##??
..xx..xx
.?x#.?x#
??##??##
..xx..xx
.?x#.?x#
??##??##

A different program may also produce, for the input of "D1" (note the nonstandard but allowed chessboard orientation),

AABBCCAA
ACBACBAC
CCAABBCC
 ABBAADD
AABDABDC
BBDDBBCC
BABBACAA
AABAACCA
\$\endgroup\$
9
  • 4
    \$\begingroup\$ If there is input it's not really Kolmogorov complexity \$\endgroup\$ Aug 6, 2019 at 13:20
  • \$\begingroup\$ @JonathanAllan the tag description uses who's that pokemon as an example of a kolmogorov complexity question that takes input. It's up to you if you want to compress a set of 64 constant solutions or if you want to implement a procedure to tile the chessboard and then color it. \$\endgroup\$ Aug 6, 2019 at 13:25
  • 1
    \$\begingroup\$ @JonathanAllan meta discussion regarding non-constant kolmogorov complexity questions \$\endgroup\$ Aug 6, 2019 at 13:38
  • 1
    \$\begingroup\$ Aren't three colors enough? \$\endgroup\$
    – Arnauld
    Aug 6, 2019 at 14:25
  • 1
    \$\begingroup\$ @Arnauld I'll allow that. I'll edit. \$\endgroup\$ Aug 6, 2019 at 14:53

2 Answers 2

24
+500
\$\begingroup\$

JavaScript (ES6),  184 ... 171  163 bytes

Takes input as (x)(y), with \$0\leq x\leq7\$ and \$0\leq y\leq7\$. Outputs as a string with 3 colors (marked as \$0\$, \$1\$ and \$2\$).

h=>v=>(a=[...'3232132031021010'],a[5+(v&4|h>3)]^=3,a[v/2<<2|h/2]=v%2*2+h%2,g=x=>y&8?'':(x<8?x-h|y-v?a[y/2<<2|x/2]^y%2*2+x%2?(x^y)&2:1:' ':`
`)+g(-~x%9||!++y))(y=0)

Try it online!

Method

We work on a matrix of \$4\times4\$ triominoes:

$$\begin{pmatrix} t_0&t_1&t_2&t_3\\ t_4&t_5&t_6&t_7\\ t_8&t_9&t_{10}&t_{11}\\ t_{12}&t_{13}&t_{14}&t_{15} \end{pmatrix}$$

Each triomino is one of:

triominoes

The initial configuration of the matrix is as follows:

$$\begin{pmatrix} 3&2&3&2\\ 1&3&2&0\\ 3&1&0&2\\ 1&0&1&0 \end{pmatrix}$$

We alternate the first 2 colors just like we would on any chessboard, which gives:

matrix0

The next steps are:

  1. According to the quadrant in which the hole is located, we rotate one of the 4 center triominoes (\$t_5\$, \$t_6\$, \$t_9\$ or \$t_{10}\$) by 180°.
  2. We rotate the triomino on which the hole is located (it may be the same triomino as in step #1), so that it does not cover the hole.
  3. We fill the holes with the 3rd color (except the 'real' hole).

For instance, assuming that the hole is located at \$(3,0)\$, this gives:

matrix1

And it that case, the final matrix is:

$$\begin{pmatrix} 3&\color{red}1&3&2\\ 1&\color{red}0&2&0\\ 3&1&0&2\\ 1&0&1&0 \end{pmatrix}$$

Commented

h => v => (                       // (h, v) = hole coordinates
  a = [...'3232132031021010'],    // a[] = flat representation of the 4x4 matrix
  a[5 + (v & 4 | h > 3)] ^= 3,    // first rotation, achieved by XOR'ing with 3
  a[v / 2 << 2 | h / 2] =         // second rotation according to the
    v % 2 * 2 + h % 2,            // position of the hole within the triomino's square
  g = x =>                        // g is a recursive function that converts the 4x4
                                  // matrix into a 8x8 ASCII art
    y & 8 ?                       // if y = 8:
      ''                          //   stop recursion and return an empty string
    :                             // else:
      ( x < 8 ?                   //   if this is not the end of the row:
          x - h | y - v ?         //     if this is not the position of the hole:
            a[y / 2 << 2 | x / 2] //       if this part of the triomino located at this
            ^ y % 2 * 2 + x % 2 ? //       position is 'solid':
              (x ^ y) & 2         //         use either color #0 or color #2
            :                     //       else:
              1                   //         use color #1
          :                       //     else:
            ' '                   //       the hole is represented with a space
        :                         //   else:
          `\n`                    //     append a linefeed
      ) + g(-~x % 9 || !++y)      //   append the result of a recursive call
)(y = 0)                          // initial call to g with x = y = 0

Graphical output

Click on the picture to set the position of the hole.

f=
h=>v=>(a=[...'3232132031021010'],a[5+(v&4|h>3)]^=3,a[v/2<<2|h/2]=v%2*2+h%2,g=x=>y&8?'':(x<8?x-h|y-v?a[y/2<<2|x/2]^y%2*2+x%2?(x^y)&2:1:' ':`
`)+g(-~x%9||!++y))(y=0)

;(u = (x, y) => { for(out = '', a = f(x)(y).split('\n'), y = 0; y < 8; y++) for(x = 0; x < 8; x++) out += `<div class="b b${a[y][x] == ' ' ? 'H' : a[y][x]}"></div>`; o.innerHTML = out; })(0, 0); o.onclick = e => u(e.clientX >> 4, e.clientY >> 4)
body { margin: 0; padding: 0; }
#o { width: 128px; height: 128px; }
.b { float: left; width: 14px; height: 14px; border: solid 1px; }
.b0 { background-color: #44f; border-color: #66f #22d #22d #66f; }
.b1 { background-color: #652e65; border-color: #874f87 #430c43 #430c43 #874f87; }
.b2 { background-color: #ffc90e; border-color: #ffeb2f #dda70c #dda70c #ffeb2f; }
.bH { border-color: #000; }
<div id="o"></div>

\$\endgroup\$
2
  • \$\begingroup\$ Constructive proof that three colors are always sufficient, very nice! \$\endgroup\$ Aug 6, 2019 at 15:25
  • 6
    \$\begingroup\$ Love the clickable graphical output! \$\endgroup\$ Aug 6, 2019 at 16:39
4
\$\begingroup\$

Charcoal, 78 bytes

NθNη”{⊞⊟¦≦⁶q×fΣ\⊙t×_⊟✳-Y⁴℅=⁶υ”≔›θ³ζ≔›η³εFζ≦⁻⁷θFε≦⁻⁷ηJ⊕÷θ²⊕÷η²§#$⁺ⅈⅉJθη Fζ‖Fε‖↓

Try it online! Link is to verbose version of code. Outputs using #$% characters. Explanation:

NθNη

Input the co-ordinates of the blank square.

”{⊞⊟¦≦⁶q×fΣ\⊙t×_⊟✳-Y⁴℅=⁶υ”

Output a compressed string. It contains newlines so to avoid breaking up the flow of this explanation you'll find the string at the end of the answer.

≔›θ³ζ≔›η³εFζ≦⁻⁷θFε≦⁻⁷η

If either co-ordinate is greater than 3 then remember that fact and subtract the co-ordinate from 7.

J⊕÷θ²⊕÷η²§#$⁺ⅈⅉ

Jump to the nearest % of the top-left square of %s and overwrite it with a # or $ as appropriate. (But this will get overwritten by the blank if it was already in this square.)

Jθη Fζ‖Fε‖↓

Blank out the square at the reduced co-ordinates and then reflect the output as necessary to get the blank to the original position.

##$$##$$
#%%$#%%$
$%%#$$%#
$$##%$##
##$%%#$$
#%$$##%$
$%%#$%%#
$$##$$##

I tried starting with the square of %s in the centre and working my way out to the desired co-ordinates but that took 90 bytes.

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.