# Introduction


Dots and Boxes is a pencil-and-paper game for two players (sometimes more). It was first published in the 19th century by Édouard Lucas, who called it la pipopipette. It has gone by many other names, including the game of dots, boxes, dot to dot grid, and pigs in a pen.

Starting with an empty grid of dots, two players take turns adding a single horizontal or vertical line between two unjoined adjacent dots. The player who completes the fourth side of a 1×1 box earns one point and takes another turn only if another box can be made. (A point is typically recorded by placing a mark that identifies the player in the box, such as an initial). The game ends when no more lines can be placed. The winner is the player with the most points. The board may be of any size. When short on time, a 2×2 board (a square of 9 dots) is good for beginners. A 5×5 is good for experts. (Source Wikipedia)



# Task


Your task is to complete the class called Game. You will be given the board size as an integer board that will be between 1 and 26, therefore the game size will be board x board. You will be given an array of lines that have already been taken, so you must complete all possible squares.


# Rules

1.  The integer board will be passed when the class is initialised.

2.  board will be between 1 and 26.

3.  The lines array maybe empty or contain a list of line integers.

4.  You can only complete a square if 3 out of the 4 sides are already complete.

5.  The lines array that is passed into the play() function may not be sorted numerically!


# Returns

Return an array of all the lines filled in including the original lines.

Return array must be sorted numerically.

Return array must not contain duplicate integers.


# Example 1
## Initialise
Initialise a board of 2 squares by 2 squares where ```board = 2```

## Line Numbering


## Line Input
So for the line input of `[1, 3, 4]` the below lines would be complete

to complete the square line `6` is needed
## Game Play
```python
board = 2
lines = [1, 3, 4]
game = Game(board)
game.play(lines) => [1, 3, 4, 6]
```

# Example 2
## Initialise
```python
board = 2
lines = [1, 2, 3, 4, 5, 8, 10, 11, 12]
game = Game.new(board)
game.play(lines) => [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12]
```
## Solution 


Good luck and enjoy!

# Kata Series
If you enjoyed this, then please try one of my other Katas. Any feedback, translations and grading of beta Katas are greatly appreciated. Thank you.

 Maze Runner
 Scooby Doo Puzzle
 Driving License
 Connect 4
 Vending Machine
 Snakes and Ladders
 Mastermind
 Guess Who?
 Am I safe to drive?
 Mexican Wave
 Pigs in a Pen
 Hungry Hippos
 Plenty of Fish in the Pond
 Fruit Machine
 Car Park Escape

Difficulty: introductory

Starter code:

def __init__(self, board):
	

Solutions:
class Game():
    
    def __init__(self, n):
        k = 2 * n + 1
        self.board = {frozenset(k * r + 1 + c + d for d in (0, n, n + 1, k))
                        for r in range(n) for c in range(n)}

    def play(self, lines):
        lines = set(lines)
        while 1:
            for cell in self.board:
                stick = cell - lines
                if len(stick) <= 1:
                    lines |= stick
                    self.board.remove(cell)
                    break
            else: break
        return sorted(lines)

class Game():
    
    def __init__(self, s):
        self.s = s
        self.sq = [ { d+(2*s+1)*y+x for d in [0, s, s+1, 2*s+1] } for x in range(1,s+1) for y in range(s) ]
        
    def play(self, lines):
        lines, prevlen = set(lines), 0
        while len(lines) != prevlen:
            keep, prevlen = [], len(lines)
            for sq in self.sq:
                if len(sq & lines) >= 3: lines |= sq
                else: keep.append(sq)
            self.sq = keep
        return [n for n in range(1,(2*self.s+2)*self.s+1) if n in lines]

class Game():
    
    def __init__(self, board):
        self.n = board

    def play(self, given):
        n, make, given = self.n, [list(range(1, self.n + 1))] ,set(given)
        for i in range(n - 1) : make.append([k + n + (n + 1) for k in make[-1]])
        possible, i = [[i, i + n, i + n + 1, i + n + 1 + n] for i in sum(make, [])], 0
        while i < len(possible):
            t = [k for k in possible[i] if k not in given]
            if len(t)==1 : given.add(t[0]) ; i = -1
            i += 1
        return sorted(given)

class Game():
    def __init__(self, board):
        self.board = board
    
    def play(self, lines):
        self.lines = set(lines)
        change = True
        while change:
            change = False
            for row in range(self.board):
                for col in range(self.board):
                    offset = row * (2 * self.board + 1)
                    top = offset + col + 1
                    left = top + self.board
                    right = left + 1
                    bottom = right + self.board
                    cell = [top, left, right, bottom]
                    sides = 0
                    for side in cell:
                        if side in self.lines:
                            sides += 1
                    if sides == 3:
                        self.lines = self.lines.union(set(cell))
                        change = True
        return sorted(list(self.lines))

class Game():    
    def __init__(self, n):
        k = 2 * n + 1
        self.board = [{k*r + 1 + c, k*(r+1) + 1 + c, k*r + n + 1 + c, k*r + n + 2 + c} for r in range(n) for c in range(n)]

    def play(self, lines):
        L, last = set(lines), None
        while self.board != last:
            last = self.board[:]
            for k in [s for s in self.board if len(L & s) == 3]: 
                L |= k
                self.board.remove(k)
        return sorted(list(L))

class Game():
    def ad_line(self,board):
        work=[[] for _ in range(board**2+1)]
        line_list=[[] for _ in range(2*board*(board+1)+1)]
        for i in range(1,board**2+1):
            numwork=((i-1)//board)*(2*board+1)
            numwork+=(i-1)%board+1
            work[i].append(numwork)    #top edge
            line_list[numwork].append(i)
            numwork+=board
            work[i].append(numwork)    #left edge
            work[i].append(numwork+1)  #right edge
            line_list[numwork].append(i)
            line_list[numwork+1].append(i)
            numwork+=board+1
            work[i].append(numwork)    #bottom edge
            line_list[numwork].append(i)
        return work,line_list
        
    
    def __init__(self, board):
        self.box=[0]*(board**2+1)
        work=self.ad_line(board)
        self.box_line=work[0]
        self.line_list=work[1]

    def play(self, lines):
        out=lines[:]
        work_next=[]
        for line in lines:
            for box in self.line_list[line]:
                self.box[box]+=1
                if self.box[box]==3 : work_next.append(box)
        while work_next:
            box=work_next.pop(0)
            for line in self.box_line[box]:
                if line in out : continue
                out.append(line)
                for n_box in self.line_list[line]:
                    self.box[n_box]+=1
                    if self.box[n_box]==3 : work_next.append(n_box)
        return sorted(out)

class Game():
    
    def __init__(self, board):
        self._board = board
        self._lines = []
        self._flines = []
        self._gboard = []
        self._cboard = []
        self._sqcheck = [(0,0),(1,-1),(1,1),(2,0)]
        self._sqctotal = 0
        self._dot = 0
        self._score = 0
        self._inner = "X"
        self._blank = "_"
        
        self.createcompleteb()
            
    def play(self, lines):
        if (lines == []):
            return lines
        self._lines = lines
        
        creategameb(self, self._lines)
        
        breaker = False
        lskip = False
        complete = False
        while not complete:
            breaker = False
            lskip = False
            for y in range(len(self._gboard)):
                if (not lskip):
                    lskip = True
                    if(y != len(self._gboard) -1):
                        for x in range(len(self._gboard)):
                            if(self._gboard[y][x] != self._dot):
                                for sqc in self._sqcheck:
                                    if (self._gboard[y + sqc[0]][x + sqc[1]] != self._blank):
                                        self._sqctotal += 1    
                                if(self._sqctotal == 3):
                                    for sqc in self._sqcheck:
                                        if (self._gboard[y + sqc[0]][x + sqc[1]] == self._blank):
                                            self._gboard[y + sqc[0]][x + sqc[1]] = self._cboard[y + sqc[0]][x + sqc[1]]
                                            self._sqctotal = 0
                                            self._score = 1
                                            breaker = True
                                            break
                                            
                                elif(self._sqctotal == 4):
                                    self._sqctotal = 0
                                    self._score = 1
                                else:
                                    self._sqctotal = 0 
                            else:
                                pass
                    else:
                        complete = True
                else:
                    lskip = False
                
                if(breaker):
                    breaker = False
                    break
                    
        for y in range(len(self._gboard)):
            for x in range(len(self._gboard)):
                if(isinstance(self._gboard[y][x], int) ):
                    if(self._gboard[y][x] > 0):
                        self._flines.append(self._gboard[y][x])
                        
        
        if(self._score):
            return self._flines
        else:
            return self._lines

        
    def createcompleteb(self):
        #create a complete board
        switch = 1 # 0 = number 1 = dot/inner
        doi = 0 # 0 = dot 1 = inner
        count = 1
        tmp = []
        for y in range(self._board + 1 + self._board):
            for x in range(self._board + 1 + self._board):
                if (switch):
                    if (not doi):
                        tmp.append(self._dot)
                        switch = 0
                    else:
                        tmp.append(self._inner)
                        switch = 0
                else:
                    tmp.append(count)
                    count += 1
                    switch = 1
            if(doi == 1):
                doi = 0
            else:
                doi = 1
            self._cboard.append(tmp)
            tmp = []
            
            
            
def creategameb(self, lines):
        #create a game board using provided "lines"
        switch = 1 # 0 = number 1 = dot/inner
        doi = 0 # 0 = dot 1 = inner
        count = 1
        tmp = []
        for y in range(self._board + 1 + self._board):
            for x in range(self._board + 1 + self._board):
                if (switch):
                    if (not doi):
                        tmp.append(self._dot)
                        switch = 0
                    else:
                        tmp.append(self._inner)
                        switch = 0
                else:
                    if (count in lines):
                        tmp.append(count)
                        count += 1
                        switch = 1
                    else:
                        tmp.append(self._blank)
                        count += 1
                        switch = 1
                        
            if(doi == 1):
                doi = 0
            else:
                doi = 1
            self._gboard.append(tmp)
            tmp = []


class Game():
    
    def __init__(self, board):
        self.board_list = []
        for n in range(board): #5 -> 0,1,2,3,4,5
            if n == 0:
                for row in range(1,board+1): #row1 -> 1-5
                    self.board_list.append( [row, row+board, row+board+1, row+board+1+board] )
            else:
                for row in range( (board+(board+1))*n+1, (board+(board+1))*n+board+1):
                    self.board_list.append( [row, row+board, row+board+1, row+board+1+board] )
        
    def play(self, lines):
        lines = set(lines)
        changes = True
        while changes == True:
            changes = False
            for combination in self.board_list:
                if len(set(combination) & lines) == 3:
                    changes = True
                    lines.add(list(set(combination) - (set(combination)&lines))[0])
        return sorted(list(lines))

class Game():
    
    def __init__(self, board):
        self.board = board

    def internal(self, lines):
        result = set()
        retval = False
        pts_per_line = (self.board * 2) + 1
        for by in range(self.board):
            for bx in range(self.board):
                h1 = 1 + (by * pts_per_line) + bx
                h2 = (h1 + pts_per_line)
                v1 = (h1 + self.board)
                v2 = (v1 + 1)

                count = 0
                if h1 in lines:
                    count += 1
                    result.add(h1)
                if h2 in lines:
                    count += 1
                    result.add(h2)
                if v1 in lines:
                    count += 1
                    result.add(v1)
                if v2 in lines:
                    count += 1
                    result.add(v2)

                if count == 3:
                    retval = True
                    result.add(h1)
                    result.add(h2)
                    result.add(v1)
                    result.add(v2)

        ret = list(result)
        ret.sort()
        return ret, retval

    def play(self, lines):
        cont = True
        while cont:
            ret, cont = self.internal(lines)
            lines = ret
        return lines

class Game():
    
    def __init__(self, board):
        self.board=board

    def play(self, lines):
        r=set(lines)
        while(len(r)<2*self.board*(self.board+1)):
            flag=False
            for i in range(self.board):
                for j in range(self.board):
                    x=(2*self.board+1)*i+j+1
                    s={x,x+self.board,x+self.board+1,x+2*self.board+1}
                    if len(r&s)==3:
                        r|=s
                        flag=True
                        break
                if flag:
                    break
            if not flag:
                break
        return sorted(r)