#!/usr/bin/python
import itertools

class Cube36:
    def __init__(self, board):
        self.possible_positions = board
        size = len(self.possible_positions[0])
        print "The board: "
        print print_matrix(self.possible_positions)
        self.board = [ [ '*' for i in range(size) ] for j in range(size) ]
        colors = ['p','r','c','o','y','g','m','t','b'][:size]
        self.color_permutations = list(itertools.permutations(colors))

    def __str__(self):
        return print_matrix(self.board)

    def solve(self, n=1):
        if n == len(self.possible_positions[0]) + 1:
            print "Solution: "
            print self
            return True
        for colorcombo in self.color_permutations:
            colorcombo = list(colorcombo)
            if self.check_and_fill_table(colorcombo, n) == True:
                self.solve(n+1)
            else:
                self.make_stars(n)

    def make_stars(self, n):
        for linenum, line in enumerate(self.possible_positions):
            for colnum, value in enumerate(line):
                if value == n:
                    self.board[linenum][colnum] = '*'


    def check_and_fill_table(self, colorcombo, n):
        for rownum, row in enumerate(self.possible_positions):
            for colnum, value in enumerate(row):
                if value == n:
                    color = colorcombo.pop(0)
                    if self.color_in_row(color, rownum):
                        return False
                    if self.color_in_column(color, colnum):
                        return False
                    self.board[rownum][colnum] = color
        return True

    def color_in_row(self, color, linenum):
        return color in self.board[linenum]

    def color_in_column(self, color, colnum):
        for row in self.board:
            if row[colnum] == color:
                return True

def print_matrix(matrix):
    output = ""
    for row in matrix:
        output += "|"
        output += " ".join([str(col).center(2) for col in row])
        output += "|\n"
    return output.strip()


# The board, as viewed by casual observer. (36 officers)
#gameboard = [ [1,2,5,4,6,3],
#              [5,3,6,1,4,2],
#              [4,6,3,5,2,1],
#              [2,1,4,3,5,6],
#              [3,5,2,6,1,4],
#              [6,4,1,2,3,5] ]

# The board in reality.
gameboard = [ [5,3,2,1,4,6],
              [4,1,5,2,5,3],
              [6,5,3,4,1,2],
              [1,2,6,3,6,4],
              [2,4,1,6,3,5],
              [3,6,4,5,2,1] ]

# A 3x3 arrangement of officers. (test)
#gameboard = [ [1, 2, 3],
#              [2, 3, 1],
#              [3, 1, 2] ]

game = Cube36(gameboard)
game.solve()