Search code examples
pythonpython-3.xalgorithmsearchtic-tac-toe

Tic Tac Toe algorithm to find diagonals in a board that is bigger than 3x3


So I worked on a small Tic Tac Toe game in python and it worked really well, and I did talk about it here to improve it in some way. However, I had a neat idea to make the board bigger and Implemented that pretty well - besides the fact that diagonal were only be able to be done on square grids and only straight through the middle. Then I added a way for the user to modify the board size, and that worked well. This is what that looked like before the road block.

import os
base_columns = [chr(x+97) for x in range(26)]
base_rows = [x for x in range(26)]
blank_spot = "-"
player_tracker = 0
player_character = ('X', 'O')
num_wins = {p:0 for p in player_character}
win_type = "Draw"
choice = ("y", "n")
game_running = True

def create_coords(s):
    global coords, columns, rows
    try:
        y = s.index('x')
        rows = base_rows[:int(s[:y])]
        columns = base_columns[:int(s[y+1:])]
        coords = {c:[blank_spot]*len(rows) for c in columns}
    except (IndexError, ValueError):
        create_coords("3x3")
        
def info_checker(s):
    s = s.lower()
    if 'x' in s and len(s) >= 3 and s.count('x') == 1:
        y = s.index('x')
        if y > 0 and s[:y].isnumeric() and s[y+1:].isnumeric():
            return True
    return False
    
def info_input(q, e="Not viable info"):
    x = input(q)
    while not(info_checker(x)):
        print(e)
        x = input(q)
    else:
        create_coords(x.lower())

def intro():
    intro_text = ["Welcome to Tic Tac Toe", "The Goal is to get 3 characters in a row", "Player 1 is 'X'; Player 2 is 'O'","You play the game on a board that's a grid","You have to input coords to place your character", "To input the coord for you charcter (Ex: a0, b2, c1):", "- First, put the letter column you want", "- Second, then put the number row"]
    for text in intro_text:
        print(text, end="\n\n")
    y = choice_input("Want to change the board size (y/n)? ")
    if y == choice[0]:
        board_text = ["Format: (Y)x(Z); Y is rows, Z is columns", "Ex: 3x3, 2x2, 3x2", "Note: If you enter a # greater than 26\nProgram defaluts to 3x3", "You can change this at the end of games"]
        print("")
        for text in board_text:
            print(text, end="\n\n")
        info_input("Input info to change board: ")
    else:
        create_coords("3x3")
    print("")
    input("Press enter to start playing ")
    os.system('clear')

def print_board():
    print("     " + "   ".join([c for c in columns]), end="\n\n")
    rows_formatted = []
    for r in rows:
        row_elements = []
        for c in columns:
            row_elements.append(coords[c][r])
        space = " "*((len(str(r))%2)+1)
        rows_formatted.append(f"{r} {space} {' | '.join(row_elements)}\n")
    seperator = "   " + "----"*len(columns) + "-\n"
    print(seperator.join(rows_formatted))
   
def coord_checker(s):
    try:
        if len(s) == 2 and s[0].lower() in columns and int(s[1]) in rows:
            if coords[s[0].lower()][int(s[1])] == blank_spot:
                return True
            else:
                return False
    except ValueError:
        return False
        
def coord_input(q, e="Not a selectable coord"):
    print(f"It's Player {player_tracker+1}'s  turn ({player_character[player_tracker]})")
    x = input(q)
    while not(coord_checker(x)):
        print(e)
        x = input(q)
    return x
    
def choice_input(q, e=f"Not '{choice[0]}' or '{choice[1]}', expecting 1 of them"):
    x = input(q).lower()
    while not(x in choice):
        print(e)
        x = input(q).lower()
    return x

def place_tac(c):
    global player_tracker
    coords[c[0].lower()][int(c[1])] = player_character[player_tracker]
    player_tracker = (player_tracker+1)%2
    
def someone_won():
    global win_type
    for c in columns:
        if all([coords[c][r] == coords[c][rows[0]] != blank_spot for r in rows]):
            win_type = coords[c][rows[0]]
    for r in rows:
        if all([coords[c][r] == coords[columns[0]][r] != blank_spot for c in columns]):
            win_type = coords[columns[0]][r]
    if len(rows) == len(columns):
        length = len(rows)
        if all([coords[columns[i]][rows[i]] == coords[columns[0]][0] != blank_spot for i in range(length)]):
            win_type = coords[columns[0]][0]
        elif all([coords[columns[0+i]][rows[(length-1)-i]] == coords[columns[0]][length-1] != blank_spot for i in range(length)]):
            win_type = coords[columns[0]][length-1]
    if win_type != "Draw":
        return True
    return False
        
def who_won():
    if win_type == "Draw":
        print(f"It was a draw! {num_wins['X']}-{num_wins['O']}")
    else:
        num_wins[win_type] += 1
        print(f"{win_type} won! {num_wins['X']}-{num_wins['O']}")
    
def game():
    turn_tracker = 0
    while not(someone_won()) and turn_tracker < len(rows)*len(columns):
        print_board()
        c = coord_input("Choose a coord: ")
        place_tac(c)
        os.system('clear')
        turn_tracker += 1
    print_board()
    who_won()
    
def reset():
    global coords, player_tracker, win_type
    coords = {c:[blank_spot]*len(rows) for c in columns}
    if win_type != "Draw":
        player_tracker = (player_character.index(win_type)+1)%2
        win_type = "Draw"
    
def replay():
    global game_running
    x = choice_input("Do you want to keep playing (y/n)? ")
    if x == choice[0]:
        y = choice_input("Change the board size (y/n)? ")
        if y == choice[0]:
            info_input("Input info (Ex: 2x2, 3x3, 3x2) ")
        os.system('clear')
    else:
        print("Thanks for playing")
        game_running = False

intro()
while game_running:
    game()
    reset()
    replay()

However, In practice a larger board makes this harder to play and win. Especially since you HAVE to have characters in a row in the length or width of the board. So a friend suggested that I make the way to win is to have 3 characters in a row - unless the board is less than 3x3.

I have been able to do most of this by myself

The function to tell if 3 'tacs' are in a row (Parameter, 'tics', is a list of bools)

def tic_tac_toe(tics):
    toes = 0
    if len(coords[columns[0]]) >= 3:
        for t in tics:
            if t:
                toes += 1
        if toes >= 3:
            return True
    else:
        return all(tics)
    return False

And 2 functions to find who had a column or row win

def find_column_tics(c):
    count = 1
    previous = coords[c][rows[0]]
    for r in rows:
        current = coords[c][r]
        if current in player_character:
            if r != rows[0] and previous == current:
                count+=1
            else:
                count = 1
            previous = current
            if count >= 3:
                return current
    
def find_row_tacs(r):
    count = 1
    previous = coords[columns[0]][r]
    for c in columns:
        current = coords[c][r]
        if current in player_character:
            if c != columns[0] and previous == current:
                count+=1
            else:
                count = 1
            previous = current
            if count >= 3:
                return current

And within 'someone_won()' they all look like this

def someone_won():
    global win_type
    # For finding a win in columns
    for c in columns:
        for r in rows:
            if tic_tac_toe([coords[c][i] == coords[c][r] != blank_spot for i in rows]):
                    win_type = find_column_tics(c)
    # For finding a win in rows
    for r in rows:
        for c in columns:
            if tic_tac_toe([coords[i][r] == coords[c][r] != blank_spot for i in columns]):
                    win_type = find_row_tacs(r)

This all worked really well but then I got to trying to solve diagonals. In a 4x4 board there are 8 ways to win by diagonal, but have no idea how to create an algorithm for this. I've tried several things and all of them don't work. I wanted to figure this out by myself but I don't think have the experience for it, I am wondering if y'all have any ideas or solutions. As of writing this I have tried a find a way to do this for 3 DAYS, and I really hope that this is possible.


Solution

  • You could try something like this:

    def check_diagonals(board, color):
        # upper left to bottom right
        for i in range(len(board) - 2):
            for j in range(len(board[0]) - 2):
                if board[i][j] == color and board[i + 1][j + 1] == color and board[i + 2][j + 2] == color:
                    return True
        
        # bottom left to top right
        for i in range(2, len(board)):
            for j in range(len(board[0]) - 2):
                if board[i][j] == color and board[i - 1][j + 1] == color and board[i - 2][j + 2] == color:
                    return True
        
        return False
    
    
    board = [
        "0001",
        "0010",
        "0100"
    ]
    
    print(check_diagonals(board, "1"))  # True
    

    Because there are, in effect, two types of diagonals going in opposite directions, just check all diagonals that could be possible.