A 4x4 Challenge

Question

There exists a brain game called Enumerate (which I made, based on Takuzu). Your challenge is to play this game.

---

Task

Solve a game of 4x4 Enumerate/Takuzu.

• Receive a starting grid via STDIN or command line.
• Output the solved grid via STDOUT or writing to file.

---

Rules

A game is characterized by a 4x4 board, made up of red and purple cells.

• There must be the same number of red and purple cells in each row and column (2 red and 2 purple in each).

• There must be no identical rows or columns.

---

Input

The starting grid will be given as a 16 character/byte string consisting of only 0, 1, and 2. Here is an example:

0001100002001200

1 represents a red cell and 2 represents a purple cell. All input boards will be solvable.

---

Note: If your language does not support string literal input, you may take input as an array of integers. Please state in your answer that this is the case. So there is no confusion, this is what said array should look like:

[0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 0, 1, 2, 0, 0]

No nested arrays are allowed.

---

Output

The solved board should be output in the same format as above; a 16 character/byte string, consisting of only 1 and 2. Here is the solution for the input above:

2121112222111212

Again, 1 represents a red cell and 2 represents a purple cell.

---

Bonuses

A -25 byte bonus is offered for any answer that outputs the solved board as an ASCII grid. Here is an example of the previously mentioned board.

2|1|2|1
-+-+-+-
1|1|2|2
-+-+-+-
2|2|1|1
-+-+-+-
1|2|1|2

---

A -50 bytes bonus is offered for any answer that outputs the solved board in color. This can be output as an image or colored text.

If colored text is chosen, the output should look like this:

2121
1122
2211
1212

However, if an image is the chosen output method, the resulting file should be 20x20 pixels, where each cell is a colored 5x5 pixel block. Here is an example:

Here are the color codes:

Red      -   #a73cba   OR   (167,  60, 186)
Purple   -   #f94a32   OR   (249,  74,  50)

---

Samples

In:  0020010100000100
Out: 1221212112122112

In:  0010000200121000
Out: 2211112221121221

In:  1000100102000000
Out: 1122122122112112

Answer 1

CJam (score 13)

With coloured text bonus, only printable characters: 64 chars - 50 = 14

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~{27c'[@_4*27+'m@}f%N*

This can be improved by one char using a non-printable character: 27c'[@ becomes "^["\ where ^ represents character 27, giving a score of 13. xxd version:

0000000: 6c3a 7e3a 4c2c 4562 322a 6521 346d 2a5f  l:~:L,Eb2*e!4m*_
0000010: 3a7a 267b 5f4d 2a4c 3124 2e65 7c2e 3d31  :z&{_M*L1$.e|.=1
0000020: 2d21 2a5f 262c 343d 7d2c 7e7b 221b 5b22  -!*_&,4=},~{".["
0000030: 5c5f 342a 3237 2b27 6d40 7d66 254e 2a    \_4*27+'m@}f%N* 

---

Straight solution with no bonus: 42 chars

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},

Online demo

---

With grid bonus: 59 chars - 25 = 34

l:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~'|f*2N*'-4*'+***

Online demo

---

With image output, 83 chars - 50 = 33. Output is in netpbm format.

'P3NKSKS255Nl:~:L,Eb2*e!4m*_:z&{_M*L1$.e|.=1-!*_&,4=},~4f*M*:("§<ºùJ2":i3/f=4f*M*S*

Online demo

Answer 2

CJam, 74-50=24 bytes (color output)

l:~:L;5ZbGm*{_L.-L.*:|!\[4/_z]_:::+e_6-!\__.&=**},s4/{"["\_~4*27+'m@}f%N*

I don't think this is very well-golfed, but it works! Try it here. Warning: slow.

l:~:L; reads a line of input into L. Then, 5Zb is [1 2], and we take the 16^th Cartesian power (Gm*) of this list, to get all possible solutions [[1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1] [1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 2] ...]. The filter { }, contains the Takuzu logic.

I added a ANSI code color output bonus:

This doesn't work on the website, of course. There is an unprintable ESC byte in the string "[".

Answer 3

C (function) (with gcc builtins), 283

This seemed like an interesting challenge to tackle in C. Pretty sure it can be golfed more, but here's a start:

#define m(a,b)for(j=0;j<4;j++){l[j]=i&a<<j*b;if(__builtin_popcount(l[j])-2)goto l;for(k=0;k<j;k++)if(l[j]==l[k])goto l;}
i,j,k,l[4];f(char*s){for(i=0;i<65536;i++){m(15,4)m(4369,1)for(j=0;j<16;j++)if((!(i&1<<j)==s[j]-49)&&(s[j]!=48))goto l;for(j=0;j<16;j++)putchar(50-!(i&1<<j));l:;}}

Input passed as string to function f(). Output to STDOUT.

Try it online.

Answer 4

JavaScript (ES6), 263 300

g=>{[...g].map(c=>(t+=t+(c>1),u+=u+(c&1)),u=t=0);for(m=15,n=4369,i=0;i++<6e4;){for(x=y=i,s=new Set;x;x>>=4,y>>=1)[3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>(x&m)==v|(y&n)==v&&s.add(v));if(s.size>7&!(i&u)&!(~i&t))return g.replace(/./g,c=>1+(i>>--p&1),p=16)}}

Given the constraints, the number of possible solution seems surprisingly small: 72

The whole board can be seen as a 16 bit number.
Allowed values for rows (masking 1111): 0011, 0101, 0110 and the inverted values 1100, 1010, 1001

Same for for columns, just with different masking and intermixed bits (masking 1000100010001): 0...0...1...1, 0...1...0...1, 0...1...1...0 and the inverted values

Note that rows and columns bit arrangements are different, so to check for uiniqueness you can add both rows and columns to a set and verify that the set size is == 8.

Code to enumerate all possible solutions in a grid 4x4

for(m=0xf,n=0x1111,t=i=0;i<0x10000;i++)
{
  // loop condition: row != 0, as valid values have 2 bits set in each row
  for(x=y=i,s=new Set; x; x>>=4, y>>=1) 
    [3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>((x&m)==v||(y&n)==v)&&s.add(v))
  if (s.size==8)
    console.log(++t,i.toString(2))
}

Test

F=g=>{ // input as a string
  [...g].map(c=>(t+=t+(c>1),u+=u+(c&1)),u=t=0);
  for(m=15,n=4369,i=0;i++<6e4;) // max valid is 51862
  { 
    for(x=y=i,s=new Set;x;x>>=4,y>>=1)
      [3,5,6,9,10,12,17,257,272,4097,4112,4352].map(v=>(x&m)==v|(y&n)==v&&s.add(v));
    if(s.size>7&!(i&u)&!(~i&t))
      return g.replace(/./g,c=>1+(i>>--p&1),p=16) 
  }
}  

// Basic test

console.log=x=>O.textContent+=x+'\n'

;[
['0020010100000100','1221212112122112'],
['0010000200121000','2211112221121221'],
['1000100102000000','1122122122112112']
].forEach(t=>{
  var i = t[0], x=t[1], r=F(i);
  console.log(i+' -> '+r+(r==x?' OK':' Fail (Expected '+x+')'))
})

<pre id=O></pre>

Answer 5

Ruby, 196 bytes

->g{[o=?1,p=?2].repeated_permutation(16).find{|x|a=x.each_slice(4).to_a
t=a.transpose
a.uniq.size==4&&t.uniq.size==4&&(a+t).all?{|y|y.count(o)==2}&&x.zip(g.chars).none?{|y|y==[o,p]||y==[p,o]}}*''}

repeated_permutation, why must your name be so long? -_-

This simply goes through all possible solutions until one of them matches the input pattern.

Answer 6

C, Score 278 257

^{(328 307 bytes - 50 bytes for coloured output, or 291 bytes without colour bonus)}

t,b,c,u,r,p;v(g){for(b=0,u=59799;b<16;b+=4)u&(c=1<<(g>>b&15))?b=u:0,u|=c;return b>16;}main(i,a)char**a;{for(char*A=a[1];*A;p=p*2|*A++>49)r=r*2|*A==49;for(;++i<6e4;t=0){for(b=16;b--;)t|=(i>>b&1)<<b%4*4+b/4;if(!(p&i^p|r&~i^r|v(i)|v(t))){for(b=16;b--;)printf("\x1b[3%s%s",i&1<<b?"5m2":"1m1",b&3?"":"\n");break;}}}

This is a brute-force method which prints the first matching grid. It actually works on a 180-degree rotated grid to simplify some loops, and uses a lookup table (59799) to figure out which rows are valid. Internally all grids are just 16-bit numbers. It takes a single string input from its arguments.

Due to the escape codes used for colouring, you might want to reset your terminal styling after running this (execute printf "\x1b[0m")

Breakdown:

// Globals initialise to 0
t, // Transpose of current guess
b, // Bit counter for loops
c, // Current row value when validating
u, // Invalid row mask when validating
r, // Red squares mask (1s in input)
p; // Purple squares mask (2s in input)

// Validation function for rows (returns 0 if valid, shell-style)
v(g){
    for(b=0,u=59799;b<16;b+=4) // "magic" value 59799 is a map of invalid rows
        // For each row:
        u&(c=1<<(g>>b&15))?b=u:0,  // Check if row is valid
        u|=c;                      // Add row to mask (rows cannot be duplicates)
    return b>16; // b = <some massive number> + 4 if a check failed
}

main(i,a)char**a;{ // K&R style function declaration to save 2 bytes
    // Read input (in reverse to save some bytes when reading & printing)
    for(char*A=a[1];*A;
        p=p*2|*A++>49) // Find 2s (input is strictly 012) and go to next
        r=r*2|*A==49;  // Find 1s
    for(;++i<6e4;t=0){ // Brute-force grids (<3 and >=60000 are invalid anyway)
        for(b=16;b--;)t|=(i>>b&1)<<b%4*4+b/4; // Calculate transpose
        if(!(                           // Check...
            p&i^p|                      //  Matches input purples
            r&~i^r|                     //  Matches input reds
            v(i)|                       //  Rows are valid
            v(t)                        //  Columns are valid
        )){
            // Display grid (use ANSI escape codes for colour)
            for(;b--;) // b starts at 16 from last v() call
//              printf(b&3?"%c":"%c\n",(i>>b&1)+49); // no colour variant
                printf("\x1b[3%s%s",i&1<<b?"5m2":"1m1",b&3?"":"\n");
            break; // Stop search
        }
    }
}

So what's 59799?

There are only 16 possible states for each row/column (it's a 4-bit binary number). Out of those, the valid options are:

0011 =  3 (decimal)
0101 =  5
0110 =  6
1001 =  9
1010 = 10
1100 = 12

Taking those values as bit indexes, we can create a mask:

0001011001101000 = 5736 (dec)

But here we want to know the invalid rows:

1110100110010111 = 59799 (dec)