Tic-Tac-Toe and Chess, with fewest [distinct] characters

Question

In this form of the game Tic-Tac-Chec, the goal is to move chess pieces to get four-in-a-row. Your goal here is to figure out if a position has a winning move.

Rules

The rules are similar, but not identical, to those of Tic-Tac-Chec.

The board is 4 by 4 squares. Each player has a rook, bishop, knight, and queen. On your turn, you have two options. You can move one of your pieces already on the board, following standard chess rules. Or you can place a piece not already on the board, on any unoccupied place.

If you move an existing piece onto an opponent's piece, their piece is taken off the board and returned to them. However, you may not place a new piece on top of an opponent's piece.

As soon as one player has all of their pieces in a row (or column, or diagonal), they win.

Challenge

Write a full program that accepts a board from STDIN, and outputs whether the white player can win on the next turn.

Input

Four strings of 4 characters each. Each character is either a space or a chess piece. Only rooks, bishops, knights, and queens are used, and at most one of each (per color) may appear. Neither player already has a four-in-a-row.

You can choose whether to accept as input the Unicode symbols for the chess pieces, or letters. If you choose letters, RBKQ represents white pieces, and rbkq represents black pieces.

Output

If the white player can win on the next turn, output true or 1. Otherwise, output false or 0.

Program

Choose a number X. Your program may contain at most X distinct characters, and no character may appear more than X times.

Winning

Lowest X wins. In case of a tie, fewest characters wins.

Examples

These examples assume the input uses letters to represent the pieces.

rkb 


RB Q
true - the white player can place the knight to complete the bottom row.
-----------------------------------
rk    


RBbQ
false - the black bishop prevents the white knight from completing the row.
-----------------------------------
rk  
 K  

RBbQ
true - the white knight can capture the black bishop and complete the row.
-----------------------------------
rkRB

 Qb 
K   
true - the white rook can move down one to complete the diagonal.

Answer 1

C, 53 distinct chars

This uses "#%&()*+,-./01234569;<=>BKQR[\]acdefghilmnoprstu{|}, space and newline, distributed as follows: 24×\n, 33×, 20×", 2×#, 3×%, 16×&, 46×(, 46×), 13×*, 12×+, 35×,, 10×-, 2×., 2×/, 18×0, 9×1, 4×2, 4×3, 4×4, 4×5, 3×6, 3×9, 34×;, 6×<, 46×=, 2×>, 2×B, 2×K, 3×Q, 2×R, 8×[, 1×\, 8×], 39×a, 23×c, 5×d, 19×e, 15×f, 1×g, 22×h, 36×i, 5×l, 1×m, 35×n, 9×o, 33×p, 44×r, 20×s, 43×t, 15×u, 8×{, 14×|, 8×}.

#include <stdio.h>
#include <string.h>
int n(char*a,char*e,int i)
{int c=0;for(;a<e;)c+=*a++=="\n"[0];return c==i;}

int p(char *t, int r, int u)
{char h[]=" RBQK";char*p=t+r;char*a;int c=0;
for(int i=0;i<=3;++i,p+=u){char*s=strchr(h,*p);if(s&&s==h==0){++c;*s=" "[0];}else{a=p;}}
if(c-3)return 0;
char o=h[strspn(h, " ")];
p=strchr(t, o);
if(p==0)return*a==" "[0];
if(p<a){char*s=p;p=a;a=s;}
if(o=="K"[0])return(p-a)==3&&n(a,p,1)||(p-a)==2+5&&n(a,p,1)||(p-a)==9&&n(a,p,2)||(p-a)==11&&n(a,p,2);
if((p-a)%5==0||n(a,p,0))return (int)strchr("RQ", o);
return((p-a)%4==0&&n(a,p,(p-a)/4)||(p-a)%6==0&&n(a,p,(p-a)/6))&&strchr("BQ",o);}

int f(char *t)
{for(int i=0;i<4;++i)if(p(t,i,5)||p(t,i*5,1))return 1;
return p(t,0,6)||p(t,3,4);}

int main()
{char t[20];fread(t,19,1,stdin);t[19]=0;
if(f(t))puts("true");else puts("false");}

Explanation

#include <stdio.h>
#include <string.h>

/* count newlines */    
int n(char *a, char *e)
{
    int c = 0;
    for (;a<e;) c += *a++=='\n';
    return c;
}

/* check a single row, column or diagonal */
int p(char *t, int start, int stride)
{
    char h[] = " RBQK"; /* pieces not in line */
    char *p = t+start;
    char *a;
    int c = 0;
    for (int i = 0;  i <= 3;  ++i, p+=stride) {
        char *s = strchr(h, *p);
        if (s && s == h == 0) {
            /* a white piece */
            ++c;
            *s = " "[0];
        } else {
            /* candidate target square */
            a = p;
        }
    }

    /* did we find three white pieces in this line? */
    if (c != 3)
        return 0;

    char o = h[strspn(h, " ")];

    p = strchr(t, o);

    if (p==0)
        return *a == " "[0];

    /* ensure a < p */
    if (p < a) {
        char *s = p;
        p = a;
        a = s;
    }

    /* knight moves */
    if (o == 'K')
        return (p-a)==3 && n(a,p)==1
            || (p-a)==7 && n(a,p)==1
            || (p-a)==9 && n(a,p)==2
            || (p-a)==11 && n(a,p)==2;

    /* rook moves */
    if ((p-a)%5 == 0 || n(a,p)==0)
        return 0==strchr("RQ", o)==0;

    /* bishop moves */
    return
        ((p-a)%4==0 && n(a,p)==(p-a)/4 ||
         (p-a)%6==0 && n(a,p)==(p-a)/6)
        && strchr("BQ", o);
}

/* main predicate function */
int f(char *t)
{
    /* try rows and columns */
    for (int i = 0;  i < 4;  ++i)
        if (p(t, i, 5) || p(t, i*5, 1))
            return 1;
    /* try diagonals */
    return p(t, 0, 6) || p(t, 3, 4);
}

int main()
{
    char t[20];
    fread(t, 19, 1, stdin);
    t[19]=0;
    if (f(t)) puts("true"); else puts("false");
}

It works by looking for a row, column or diagonal containing three of the white pieces; a points to the target position (not already containing a white piece). Then the missing piece (o) is identified - it's the one we didn't remove from string h as we saw it.

If the piece is not on the board, it must be in the hand, and it can only be played into a space. Otherwise (if we found it on the board), it must be in a position where it can move into the target square. Since moves are reversible, we swap if necessary, so that a < p.

We test knight moves first - there are four legal downwards moves, and we avoid wrapping around the left/right edges of the board by verifying the number of newlines we pass.

After that, we test rook moves, and then bishop moves, using a similar algorithm (and a queen can use either of these moves).

Test program

int expect_true(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (!f(board)) {
        fprintf(stderr, "Expected true, but got false, for\n%s\n\n", board);
        return 1;
    }
    return 0;
}

int expect_false(char *board)
{
    if (strlen(board) != 19) {
        fprintf(stderr, "Wrong length board:\n%s\n\n", board);
        return 1;
    }
    if (f(board)) {
        fprintf(stderr, "Expected false, but got true, for\n%s\n\n", board);
        return 1;
    }
    return 0;
}


int main()
{
    return
        + expect_true("rkb \n"
                      "    \n"
                      "    \n"
                      "RB Q")
        + expect_false("rk  \n"
                       "    \n"
                       "    \n"
                       "RBbQ")
        + expect_true("rk  \n"
                      " K  \n"
                      "    \n"
                      "RBbQ")
        + expect_true("rk  \n"
                      "    \n"
                      "K   \n"
                      "RBbQ")
        + expect_true("rkRB\n"
                       "    \n"
                       " Qb \n"
                       "K   ")
        + expect_true("rk  \n"
                      "    \n"
                      "K   \n"
                      "RBbQ");
}

Counting program (in C++)

#include<algorithm>
#include<iostream>
#include<map>

int main()
{
    std::map<char,int> m;
    for (int c;  (c = getchar()) != EOF; )
        ++m[c];

    for (auto e: m)
        std::cout << e.first;

    std::cout << "\n distributed as follows: ";
    for (auto e: m)
        std::cout << e.second << "×`" << e.first << "`, ";
}