Create an n to the d tic tac toe win-checker Create the shortest program to check who has won in an nd tic tac toe game.

Your program should work when n (width) and d (dimension number) are in these ranges:

n∈[3,6]∩ℕ  ie a number from this list: 3,4,5,6
d∈[2,5]∩ℕ  ie a number from this list: 2,3,4,5


n = 3; d = 2 (32 ie 3 by 3):

[][][]
[][][]
[][][]


n = 3; d = 3 (33 ie 3 by 3 by 3):

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]

[][][]
[][][]
[][][]


n = 6; d = 2 (62 ie 6 by 6):

[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]
[][][][][][]


And so on.

Winning (If you've played enough multi-dimensional tic tac toe, this is the same.)

In order for there to be a win, one player must have all the adjacent squares along a line. That is, that player must have n moves on a line to be a winner.

Adjacent:


each tile is a point; for example (0,0,0,0,0) is a point in d=5
adjacent tiles are tiles such they are both points on the same unit d-cube. In other words, the Chebyshev distance between the tiles is 1.
in other words, if a point p is adjacent to a point q, then every coordinate in ps corresponding coordinate in q differs from it by no more than one. Additionally, at least on coordinate pair differs by exactly one.


Lines:


Lines are defined by vectors and a tile. A line is each tile hit by the equation: p0 + t&lt;some vector with the same number of coordinates as p0&gt;


Input:

Input will be to STDIN. The first line of input will be two numbers, n and d in the form n,d. 

After this will be a line consisting of coordinates specifying the moves that have been done. Coordinates will be listed in the form: 1,1;2,2;3,3. The upper left corner is the origin ( 0,0 for 2D). In the general case, this list will be like 1,2,...,1,4;4,0,...,6,0;... where the first number represents left-right-ness, the second up-down-ness, the third through the 3rd dimension, etc. Note that the first coordinate is Xs first turn, the second is Os first turn, ....

The input will be followed by a newline.

Output:

Output will be to STDOUT. Simply indicate who won if someone won, or if it is a tie. If it is neither a tie nor a win, don't output anything.

Additionally, indicate if there is a move clash, that is, if there are at least two moves in the same location.

If there was a win/draw before the input ended, your program can do whatever it wants.

Test cases (anyone want to suggest any more?):

Input:

4,3
0,0,0;1,1,1;1,0,1;2,0,2;0,0,1;2,0,0;2,0,1;3,0,2;3,0,1


Example Output:

X wins


Another possible output (requires explanation):

1
Not an answer - Java

I was curious to see how many different ways there were to win for a given n,d so I wrote this code to list them all.  

import java.util.*;

public class MultiDTTT {
    static Set&lt;Win&gt; wins = new HashSet&lt;Win&gt;();
    static final int d = 3;
    static final int n = 3;
    static final char maxChar = (char)(n-1) + '0'; 

    public static void main(String[] args) throws Exception {
        String pad = "";
        for(int i=0; i&lt;d; i++) pad = pad + "0";
        for(int i=0; i&lt;Math.pow(n,d); i++) {
            String s = Integer.toString(i,n);
            s = pad.substring(s.length()) + s;
            buildWin(s,"",0);
        } 
        System.out.println(wins.size());
        for(Win w : wins) System.out.println(w.toString());
    }

    static void buildWin(String s, String p,int i) {
        if(i&lt;d) {
            if(s.charAt(i) == '0') {
                buildWin(s,p+"u",i+1);
                buildWin(s,p+"s",i+1);
            }
            else if(s.charAt(i) == maxChar) {
                buildWin(s,p+"d",i+1);
                buildWin(s,p+"s",i+1);
            }
            else {
                buildWin(s,p+"s",i+1);
            }
        }
        else {
            if(p.contains("u") || p.contains("d")) wins.add(new Win(s,p));
        }
    }

    static class Win {
        String start;
        String pattern;
        Set&lt;String&gt; list = new HashSet&lt;String&gt;();

        Win(String s, String p) {
            start = s;
            pattern = p;
            char[] sc = s.toCharArray();
            for(int i=0; i&lt;n; i++) {
                list.add(new String(sc));
                for(int j=0; j&lt;d; j++) {
                    switch (p.charAt(j)) {
                        case 'u':
                            sc[j]++;
                            break;
                        case 'd':
                            sc[j]--;
                            break;
                        case 's':
                            break;
                    }
                }
            }
        }

        public String toString() {
            String s = ""; //start + ", " + pattern + "\n    ";
            for(String ss : list) s = s + ss + " ";
            return s;
        }

        public boolean equals(Object x) {
            return (x instanceof Win) &amp;&amp; this.list.equals(((Win)x).list);
        }
        public int hashCode(){
            return list.hashCode();
        }
    }
}


I hand-tested it on n,d = 2..3,2..3 and it appears to work… after that the number of possible ways to win grows quickly as shown below: 

n       1       2       3       4       5       6
d                           
1       1       1       1       1       1       1
2       1       6       8       10      12      14
3       1       28      49      76      109     148
4       1       120     272     520     888     1400
5       1       496     1441    3376    6841    12496
6       1       2016    7448    21280   51012   107744


Having generated all wining sets, I could extend the program to check the given input against winning sets but, of course, that method would never win the golf.  So I was content to stop here - except it looked like I could find a closed-form solution for the number of ways to win as a function of n and d… It is Number of ways to win = 0.5( (n+2)^d - n^d).