Façon compacte de représenter toutes les «rangées» valides dans une grille de tic-tac-toe

Question

J'ai écrit tic-tac-toe dans une variété de langues comme un exercice, et un modèle qui a émergé est que chaque représentation que je Avons trouvé pour les lignes gagnantes définissant valides a été décevant dur codé. Ils ont généralement diminué en deux catégories:

En premier lieu, la carte est représentée comme une matrice à une ou deux dimensions, et les rangées sont explicitement définie par des triplets de positions (chiffres sont des espaces vides):

board = [1, x, 3, 4, o, 6, 7, 8, x] 

def match3(x,y,z) 
    board[x] == board[y] && board[y] == board[z] 
end 

def winner 
    match3(1,2,3) || match3(4,5,6) || ... 
end 

Ceci a l'avantage de l'explicite non-magique, mais il semble verbeux.

L'autre approche consiste à utiliser un tableau de tableaux et à réduire les lignes. Il est un peu mieux, mais ne me reçoit pas tout le chemin:

board = [[nil, 1, nil], [nil, -1, nil], [nil, nil, 1]] 

def diag(x,y,z) 
    [board[x/3,x%3], board[y/3,y%3], board[z/3,z%3]] 
end 

def winner 
    rows = board + board.transpose << diag(0,4,8) << diag(2,4,6) 
    rows.map { |r| r.reduce(:&) }.reduce { |m,c| m || c } 
end 

verticales et horizontales sont grands matchs, mais je suis toujours hardcoding les diagonales. Quelqu'un peut-il penser à un moyen de caractériser les diagonales (ou une approche totalement différente) qui ne repose pas sur des adresses explicites?

Mon pseudo code est Rubyish, mais n'hésitez pas à le poster dans n'importe quelle langue que vous aimez. J'ai vu le code de tic-tac-toe golf, et bien que certaines de ces solutions soient ingénieuses (en particulier les carrés magiques!), Je cherche quelque chose d'un peu moins obfusant.

Answer 1

Un système beaucoup plus rapide et plus compact consiste à utiliser un bit pour chaque carré. La position actuelle peut être conservée dans deux variables: X tenant toutes les marques "X" et O contenant toutes les marques "O". Un codage possible pour les 9 carrés est par exemple

1 2 4 
8 16 32 
64 128 256 

Avec ce codage de la première rangée est 1+2+4=7 et haut/gauche> bas/droite diagonale est 1+16+256=273.

Vérification si X a gagné sur la première ligne est seulement if ((X & 7) == 7), d'autres contrôles sont similaires, mais avec des chiffres différents au lieu de 7. La victoire complète devient ... la routine de vérification

def winner(p): 
    for m in (7, 56, 448, 73, 146, 292, 273, 84): 
     if p & m == m: return True 
    return False