开发者

Compact way of representing all valid "rows" in a tic-tac-toe grid

I've been writing tic-tac-toe in a variety of languages as an exercise, and one pattern that has emerged is that every representation I've come up with for the defining valid winning rows has been disappointingly hard-coded. They've generally fallen into two categories:

First, the board is represented as a one- or two-dimensional array, and rows are explicitly defined by triplets of positions (numbers are empty spaces):

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

This has the advantage of non-magical explicitness, but it seems verbose.

The other approach is to use an array of arrays and map+reduce the rows. It's slightly better, but doesn't get 开发者_开发百科me all the way:

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

Vertical and horizontal matches are great, but I'm still hardcoding the diagonals.

Can anyone think of a way to characterize the diagonals (or a wholly different approach) that doesn't rely on explicit addresses?

My pseudocode is Rubyish, but please feel free to post in any language you like. I saw the tic-tac-toe code golf, and while some of those solutions are ingenious (especially the magic squares!) I'm looking for something a bit less obfuscating.


A system that's a lot faster and more compact is to use one bit for every square. Current position can be kept in two variables: X holding all the "X" marks, and O holding all "O" marks. A possible encoding for the 9 squares is for example

 1   2   4
 8  16  32
64 128 256

With this encoding the first row is 1+2+4=7 and top/left->bottom/right diagonal is 1+16+256=273.

Checking if X won on the first row is just if ((X & 7) == 7), other checks are similar but with different numbers instead of 7. The full victory checking routine becomes...

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

上一篇:

下一篇:

精彩评论

暂无评论...
验证码 换一张
取 消

最新问答

问答排行榜