It's Your Turn ! (Renju)

Question

EDITS:

• Added link to the plain-text (multiple strings) test data
• Added BLANK,EDGE and TIE2 test cases (see Test Data section) (11/25)
• Updated the JSON test cases (some lines were ill-formatted) (11/24)

Renju match gone bad ! (well, technically these guys are playing Go, but who cares) Wikisource

TL;DR

Take a 15x15 grid of characters (made of '.', '0' and '*'), as an input, replace one of '.' s with '*', in such a way that an unbroken horizontal, vertical or diagonal line of exactly five '*' chars is formed.

           *        *    * 
           *       *      *
 ******    *      *        *
           *     *          *
           *    *            *

Output the coordinates of your '*', or string - 'T' if there is no solution.

Creating a line of more than 5 '*' long (directly or indirectly) is not allowed, this is called an "overline".

Some examples of overlines:

 ****.** - replacing . with * will result in a horizontal overline


 *.***  - replacing . with * will result in a diagonal overline 
   *
    *
     *
      *
       *

Full Version

Abstract

Renju - is an abstract strategy board game (a simpler version of it is also known as Gomoku).

The game is played with black and white stones on a 15×15 gridded Go board.

Black plays first if white did not just win, and players alternate in placing a stone of their color on an empty intersection. The winner is the first player to get an unbroken row of five stones horizontally, vertically, or diagonally.

Computer search by L. Victor Allis has shown that on a 15×15 board, black wins with perfect play. This applies regardless of whether overlines are considered as wins.

Renju eliminates the "Perfect Win" situation in Gomoku by adding special conditions for the first player (Black).

(c) Wikipedia

Objective

Consider you are a part of a Renju match, you are playing black, and there is just one turn left for you to win.

Take the current board position as an input, identify one of the winning moves (if there is one), and output it (see below for the data formats and restrictions).

Sample input board:

    A B C D E F G H J K L M N O P       . - vacant spot (intersection) 
 15 . . . . . . . . . . . . . . . 15    0 - white stone
 14 . . . . . . . . . . . . . . . 14    * - black stone
 13 . . . . . . . . . . . . . . . 13    X - the winning move
 12 . . . . . . . . . . . . . . . 12    
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . X . . . . . . .  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

(axis labels are for illustration purposes only and are not part of the input)

Sample output:

H5

Rules

For the purpose of this challenge, only the following subset of Renju rules apply:

• You can place your stone on any vacant intersection (spot);

• Player who achieved an unbroken row of five stones horizontally, vertically, or diagonally, wins;

• Black (you) may not make a move which will result (directly or indirectly) in creation of an "overline" i.e. six or more black stones in a row.

Data Formats

Input data is a 15x15 grid of characters (".","*","0"]), ASCII-encoded, in any acceptable format, e.g. a two-dimensional character array or a newline separated set of strings e.t.c.

You may not however modify the input alphabet in any way.

Output data is a string, denoting the alpha-numeric board position, as illustrated by the sample board above.

Note that original horizontal axis numeration (A..P), does not include 'I', you MAY use 'A..O' instead, w/o penalty.

If there is no winning move available, output "T" instead.

Scoring

This is code-golf, so the shortest answer in bytes wins !

Some Tests Cases

Tie

Input:

    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . 0 . . . . . . . 10
  9 . . . . . . . * . . . . . . .  9
  8 . . . . . . . * . . . . . . .  8
  7 . . . 0 . . . * . . . . . . .  7
  6 . . . 0 0 . . * . . . . . . .  6
  5 . . . . . . . Z . . . . . . .  5
  4 . . . . . . . * . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

 "T", the only "winning move" is H5 (denoted with "Z"), but that would create an overline H4-H9

Overline

Input:

    A B C D E F G H J K L M N O P
 15 . . . . . . . . . . . . . . . 15
 14 . . . . . . . . . . . . . . . 14
 13 . . . . . . . . . . . . . . . 13
 12 . . . . . . . . . . . . . . . 12
 11 . . . . . . . . . . . . . . . 11
 10 . . . . . . . . . . . . . . . 10
  9 . . . . . 0 . . . . 0 . . . .  9
  8 . . 0 . . . . . . * 0 0 . . .  8
  7 . . 0 . . . . . * . . 0 . . .  7
  6 . . 0 * . 0 . * . . 0 0 . . .  6
  5 . . 0 . * . * X * * * . . . .  5
  4 . . . . . Z . . . . . . . . .  4
  3 . . . . . . * . . . . . . . .  3
  2 . . . . . . . * . . . . . . .  2
  1 . . . . . . . . * . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

 "H5", the other possible winning move is "F4", but that would result in J1-D6 diagonal overline.

Multiple winning moves

Input:

    A B C D E F G H J K L M N O P
 15 . * * * . . * * * . . . . . . 15
 14 . * . . . . . * . . * . . . . 14
 13 . * . . . . . . . . . . . * . 13
 12 . . . . . 0 0 0 0 0 0 0 . * . 12
 11 . . . . 0 . . X . . . 0 . * * 11
 10 . . . . 0 X * * * * X 0 . . * 10
  9 . . . . 0 . . * . . . 0 . * *  9
  8 . . . . 0 0 . * . . 0 0 . * .  8
  7 . . . . . 0 . * . . 0 . . * .  7
  6 . . . . . 0 . X . . 0 . . . .  6
  5 . . . . . 0 0 0 0 0 0 . . . *  5
  4 . . . . . . . . . . . . . . .  4
  3 . . . . . . . . . . . . . . .  3
  2 . . . . . . . . . . . . . . .  2
  1 . . . . . . . . . . . . . . .  1
    A B C D E F G H J K L M N O P

Output:

"H6" or "H11" or "F10" or "L10" (one of)

Test Data

The test data in a bit more machine-friendly form (JSON) is available HERE

Added BLANK,EDGE and TIE2 test cases: UPDATED TEST SUITE

You can use the following JS snippet to convert it to multiline strings, if necessary:

for(B in RENJU) { console.log(B+"\n"+RENJU[B].map(l=>l.join``).join`\n`); }

or just download them here

Answer 1

JavaScript (ES6), 161

Input as multiline string.

Note: could save 1 byte using A..O instead of A..P

s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

Less golfed

s=>
[...s].some( 
  (q, p) => // execute for each character q in position p, stop when true
  (
    [1, 15, 16, 17].map( // offset for 4 directions
      d => // for each direction d
      (
        // recursive function to find adjacent '*' in direction -d
        r = p => s[p-d] == '*' ? r(p-d) : p,
        // I need 4 adjacent '*' in at least 1 direction
        // but no more in any direction
        a = p, // current position in a, could be the answer
        q = r(p), // look back (reuse variable q)
        d = -d, q -= r(p), // then look forward
        q = q/d, // number of '*' in q
        x = q > x ? q : x // keep the max in any direction
      ),
      // init x to 0 if the current position is empty
      // else init x to 5, so it will be not valid in any case (too big)
      x = q !='.' && 5
    ),
    // if 4 '*' found, exit the loop
    x==4
  )
) // return true if solution found (solution in a)
? 'ABCDEFGHJKLMNOP'[a % 16] + (15 - ( a >> 4))
: 'T'

Test

F=
s=>[...s].some((q,p)=>([1,15,16,17].map(d=>x=(q=((r=p=>s[p-d]=='*'?r(p-d):p)(a=p)-r(p,d=-d))/d)>x?q:x,x=q!='.'&&5),x==4))?'ABCDEFGHJKLMNOP'[a%16]+(15-(a>>4)):'T'

out=x=>O.textContent+=x+'\n\n'

;renju = {
"BLANK":"...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............\n...............",
"EDGE":"...........****\n.0.............\n.0.............\n.0.............\n.00000.........\n.....0.........\n.....0.........\n.....0.........\n.....0.........\n...............\n...............\n.....*........*\n....*.........*\n...*..........*\n..*...........*",
"TIE":"...............\n...............\n...............\n...............\n...............\n.......0.......\n.......*.......\n.......*.......\n...0...*.......\n...00..*.......\n...............\n.......*.......\n...............\n...............\n...............",
"TIE2":"...............\n.....0****000..\n...............\n.*0............\n..*.0..........\n..0*...0.......\n.......*.......\n.......*.......\n.......*.00....\n.......*.......\n.......0.......\n...............\n...............\n...............\n...............",
"OVERLINE":"...............\n...............\n...............\n...............\n...............\n...............\n.....0....0....\n..0......*00...\n..0.....*..0...\n..0*.0.*..00...\n..0.*.*.***....\n...............\n......*........\n.......*.......\n........*......",
"MULTIPLE":"...............\n...............\n...............\n.....0000000...\n....0......0...\n....0.****.0...\n....0..*...0...\n....00.*..00...\n.....0.*..0....\n.....0....0....\n.....000000....\n...............\n...............\n...............\n..............."
};

for(k in renju) {
  var r=F(renju[k])
  out(k+' '+r+'\n   ABCDEFGHJKLMNOP\n'+renju[k].split`\n`.map((v,i)=>(115-i+' ').slice(1)+v).join`\n`)
}

<pre id=O></pre>

Answer 2

PHP, 205 203 201 246 257 238 bytes

requires PHP<7.1 (relies on empty negative string offsets)

third approach, finally really complete, and I think I have left nothing to golf.

for($p=240;(!$l|$o)&&$p--;)for($k=4,$l=$o=0;$k--;$l|=preg_match("#\*{5}#",$s),$o+=preg_match("#\*{6}#",$s))for($s="*",$i=0;"."==($g=$argv[1])[$p]&&$i++<5;)$s=$g[$p-$i*$d=!$k?:$k+14].$s.$g[$p+$d*$i];echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

takes multiline string with Linux style linebreaks (1 character) from command line argument.
For 2 character linebreak: add one each to 14, 15 and 16 and replace 240 with 255.

Run with -r.

breakdown

for($p=240;(!$l|$o)&&$p--;)     // loop through positions while (no line or has overlines)
    for($k=4,$l=$o=0;$k--;          // loop through four directions
        $l|=preg_match("#\*{5}#",$s),   // post condition: set flag for line
        $o+=preg_match("#\*{6}#",$s)    // and count overlines
        )
        for($s="*",                     // assume asterisk at current position
            $i=0;
            "."==($g=$argv[1])[$p]      // if character is "."
            &&$i++<5;)                  // look 5 fields in +/- direction:
            $s=$g[$p-$i*
                $d=!$k?:$k+14               // map [3,2,1,0] to offset [17,16,15,1]
            ].$s.$g[$p+$d*$i];              // add characters
                                // output
echo$p<0?T:chr(65+$p%16).(15-($p/16|0));

uses columns A..O. For A..H+J..P, append +($p/8&1) to the chr parameter.