Archive

Posts Tagged ‘artificial intelligence’

Hidoku Solver in Python: branch cutting, intelligent successor generation and some simplifications

In this post we are implementing a Hidoku solver (Hidoku is yet another fine number puzzle) that uses a depth first search, branch cutting, limited (intelligent) successor generation and some automatic simplification. Usually, a Hidoku is a quadratic board consisting of n x n fields – but rectangular or other forms would be possible as well. With each Hidoku, some fields are already pre-filled with numbers at the beginning.

Hidoku Sample

Hidoku Sample

The game goal is to fill in all other numbers so that an ascending number queue is built: each number has to be adjacent to it’s successor, with adjacent meaning in an adjacent horizontal, vertical or diagonal field. Those adjacent fields are what we call a field neighborhood. The first and last number (e.g. with a 10×10 board they will be 1 and 100) are usually amongst those pre-filled into the board – for the player knowing where the queue starts and ends. See e.g. here or here to try out some online Hidoku examples for yourself.

Within our solver we use a similar puzzle representation which we read from a text file. E.g. the sample from above would look like this:

__,__,93,__,__,__,___,__,__,57
__,__,__,22,__,53, 54,40,__,__
__,__,18,23,52,__,100,__,__,__
__,__,__,__,__,99, 33,__,__,__
__,__,__,__,__,25,___,__,__,__
__,__,__,__,__,__,___,__,__,29
14,__, 7,__,__,__,___,__,__,__
__,__,__,65,__,__, 46,72,77,__
__, 9,__,__,__,__,___,__,80,76
 1,__,__,11,__,68, 82,__,__,__

Solving a Hidoku

With our solver we want to obtain all possible solutions to a Hidoku (although it should ideally only have 1). Therefore we utilize a depth first search with branch cutting, intelligent successor generation and some automatic simplification. Besides the simple game board representation (positions with numbers) we also use some additional variables for speeding up the search (see Board.__init__() for details):

  • self.nparray: the standard n x m numpy array representation of the game board, with the numbers present on the board written to the y/x position of the array.
  • self.nrs_yx_dict: dictionary of numbers filled to the board and their corresponding tuple of y/x positions. This allows fast lookup of the y/x position a number is filled to.
  • self.nrs_left_to_place: list of numbers that still need to be placed on the board. Allows for slightly faster lookup of still missing numbers.
  • self.nrs_placement_possibilities: list of possible placements as numbers and their corresponding y/x positions (representing positions this numbers could be filled to, given the current state of the board). This list enables much faster access to where numbers could get placed on the board. It is created initially (for the first node in the search tree) and for all successor nodes in the search tree possibilities that became impossible just get removed.
  • self.field_connection_status: lists how many connections each field in the board currently has (0 to 2). A connection exists if the number preceding or succeeding to the number in the field is present in the field neighborhood (with the neighborhood including all adjacent fields: vertical, horizontal and diagonal). These connection stats enable quick checks if the board is already invalid (more on that later). The connection stats get handed over to preceding nodes in the search tree by updating the neighborhood and the field itself the number was filled to.

We now look closer at how some of these are created and later used inside branch cutting.

Determining those fields that a number could be filled to

With the first node in the search tree, self.nrs_placement_possibilities gets created and filled. Succeeding nodes obtain a copy of it with those possibilities removed that became invalid by placing preceding number to the board (by doing the distance checks described below again).

Given the numbers pre-filled to the board, all other numbers can be filled to those fields only that lie within the allowed distance of numbers already filled to the board. An example: if nr. 2 if filled to the top left field (position 0/0), nr. 2 can only be placed within vertical, horizontal and diagonal distance 1 of field 0/0, nr. 3 within distance 2 etc. Hence, this boils down to a simple (but pretty effective in reducing computation complexity) series of distance checks, in which each number X gets checked against each number Y already filled to the board. These checks are only performed if abs(X-D) < max(board_height, board_width) - 2 (otherwise the numbers can be placed on the board without any restrictions caused by each other, as the board is too small for such). The core of such a distance check is rather simple: nr. X can be placed to a certain y/x position on the board, if the horizontal and the vertical distance to the position of nr. Y is at max. abs(X-Y).

Branch cutting and its requirements

In our search tree we need to detect dead ends early (boards that cannot yield a valid solution anymore) in order to exclude them from further search, hence speeding up the complete search.

With keeping track of possible placements of numbers to fields on the board using self.nrs_placement_possibilities, we can do 2 types of checks:

  • for each number left to be placed on the board: is there still at least one field left that number can be placed on?
  • for each field still empty: is there at least one number left that can be placed on that field?

If at least one is not fulfilled: the board is invalid an can be excluded from further search.

We also use field connection stats (self.field_connection_status) within branch cutting. Fields initially have 0 connections. If the field is filled with a number, for each of the preceding and succeeding number present in its neighborhood (the adjacend fields, maximum 8), the number of connections goes up by one – so the maximum amount of connections per field is 2. Using these field connection stats we can check:

  • if the field is filled: does it have its preceding and succeeding numbers placed in its neighborhood, or enough free fields in the neighborhood for them to be placed there in the future? If not the board is invalid.
  • if the field is not filled: does it allow to be a connection for any pair of numbers in its neighborhood? Can it still be reached (entered and exited) from the outside? E.g. an empty field with fully filled neighborhood can only be reached if there can a number be placed on that field that has its preceding and succeeding number already filled to the neighborhood (or a free field in the neighborhood in its place). This essentially boils down to neighborhood number permutation check: if we don’t find a valid (still possible) permutation of numbers in the neighborhood for which we can fill a still available and valid number to that field, the board is invalid.

Successor generation

For the solved board the order of how fields got filling does not matter. Therefore, within our depth first search, we do not care for the search path, but only for the obtained board state (we do not care how a board could have evolved to it’s current state).

The question is: how to generate the required subset of successors (as this will influence the future search complexity)? We only generate successors from filling a single field on the board (with all numbers that can be filled to it) – as we can generate all possible board states from this, without searching multiple search paths (which all lead to the same results). As field to be filled we chose the one with the least possible amount N of numbers that can be filled to this field – and generate one successor per number possible. If there is a number that can be placed only on an amount A of fields that is smaller than N, we instead fill this one number to all those fields and generate one successor per filled field (as we only obtain A instead of N successor nodes then). This way we minimize the amount of branches and keep the overall branching factor low – something a rational human player would strive for as well. Note that we do not miss any possible solutions as a result of this limited successor generation. As a side effect, this also results in basic board simplification: if there is a field that only one number can be filled to, it will be filled next – and generate a single successor only, which is usually called simplification. The same is true if we have a number that can only be filled to a single field.

Implementation

# Hidoku solver implementation using depth first search, branch cutting, intelligent successor generation and a little simplification.
# Rainhard Findling
# 2015/04
#
# possible improvements:
# - use a path finding algorithm, e.g. A* + manhattan distance instead of using max(y_dist,x_dist) to determine possible minimum distances.
#
import numpy
import itertools
from copy import copy

# STATICS
EMPTY = -1

def main():
    """gets executed if in __main__ (see bottom of file)."""

    # parameters
    board_file = '../boards/10x10_2.txt'

    # load board, initialize it, print some statistics
    board = Board(read_board(board_file))
    board.initialize()
    print board
    print 'nrs left', board.nrs_left_to_place
    print 'nrs_placement_possibilities', len(board.nrs_placement_possibilities)
    tmp = board.placements_splitted_per_nr()
    print 'placements per nr', map(lambda t:(t,tmp[t][0]), tmp.keys()), '\n'
    board.is_valid()
       
    # depth first search
    list_open = [board]
    solutions = []
    nodes_opened = 0
    nr_of_successors = []
    while(len(list_open) > 0):
        cur = list_open.pop()
        nodes_opened = nodes_opened + 1
        print 'looking at', cur
        print 'list_open', len(list_open)
        successors = cur.successors()
        if(len(successors)==0):
            print 'all successors invalid, reverting.'
        for s in successors:
            nr_of_successors = nr_of_successors + [len(successors)]
            if s.is_solved():
                solutions = solutions + [s]
                #break # enable to quit search after the first solution, disable to search the complete search space
            else:
                list_open = list_open + [s]
        else:
            continue
        break
    print 'done.'
    if len(solutions) == 0:
        print 'no solutions found.'
    else:
        print 'solution paths:', map(lambda s:s.solution_path(), solutions)
        print 'solutions:', solutions
        print 'solutions', len(solutions)
        print 'nodes_opened', nodes_opened
        print 'nr_of_successors', sum(nr_of_successors)
        print 'avg branching (not including reduction by simplification-drive-successor-generation)', sum(nr_of_successors)/float(len(nr_of_successors))
    
class Board:
    
    def __init__(self, nparray = None):
        self.nparray = nparray # the gameboard as board
        self.nrs_yx_dict = None # the gameboard as dict of nrs and corresponding y,x positions
        self.nr_range = None # range of numbers to be contained in board
        self.nrs_left_to_place = None # numbers left to be placed on the board
        self.nrs_placement_possibilities = None # list of possible placement possibilities
        self.field_connection_status = None # how many connections fields have left [0,2]
        self.parent = None
    
    def __str__(self):
        """str representation of nparray board."""
        sep = '   '
        top1 = '===' + ''.join(['====' for _ in range(len(self.nparray[0]))])
        top2 = '==='  + ''.join(['=='  for _ in range(len(self.nparray[0]))])
        s = '\n' + top1 + sep + top2 + '\n'
        for row_nr in range(len(self.nparray)):
            row = self.nparray[row_nr,:]
            s = s + '| ' + ' '.join(map(lambda x:'___' if x == EMPTY
                                        else '{:3.0f}'.format(x), row)) + ' |'
            fillings = self.field_connection_status[row_nr,:]
            s = s + sep + '| ' + ' '.join(map(lambda x:'x' if x == 0 else
                                              '.' if x == 1 else
                                              ' ', fillings)) + ' |\n'
        s = s + top1 + sep + top2 + '\n'
        return s
    
    def __copy__(self):
         other = Board()
         other.nparray = copy(self.nparray)
         other.nrs_yx_dict = copy(self.nrs_yx_dict)
         other.nr_range = self.nr_range # no need to copy
         other.nrs_left_to_place = copy(self.nrs_left_to_place)
         other.nrs_placement_possibilities = copy(self.nrs_placement_possibilities)
         other.field_connection_status = copy(self.field_connection_status)
         return other
     
    def __repr__(self):
        return self.__str__()

    def __eq__(self, other):
        return (self.nparray == other.nparray).all()
        
    def __ne__(self, other):
        return not self.__eq__(other)
    
    def initialize(self):
        """initialize the board. meant to be called on first board in search tree only."""
        self.nr_range = range(1, len(self.nparray) * len(self.nparray[0])+1)
        self.nrs_left_to_place = self.generate_nrs_left_to_place()
        self.nrs_yx_dict = self.generate_nrs_yx_dict()
        self.nrs_placement_possibilities = self.generate_nrs_placement_possibilities()
        self.field_connection_status = self.generate_all_field_connection_status()
        
    def generate_nrs_yx_dict(self):
        """generate yx position index of nrs."""
        nrs_yx_dict = {}
        for y in range(len(self.nparray)):
            for x in range(len(self.nparray[0])):
                if not self.nparray[y,x] == EMPTY:
                    nrs_yx_dict[self.nparray[y,x]] = (y,x)
        return nrs_yx_dict
        
    def generate_nrs_placement_possibilities(self):
        """1 huge list containing tuples about which nrs are placeable on which fields."""
        nr_placements = []
        for nr in self.nrs_left_to_place:
            for y in range(len(self.nparray)):
                for x in range(len(self.nparray[0])):
                   if(self.can_nr_be_placed_on_field(nr,y,x)):
                       nr_placements = nr_placements + [(nr,y,x)]
        return nr_placements
    
    def generate_all_field_connection_status(self):
        """for all filled fields: generate field connection status."""
        field_connection_status = numpy.ones([len(self.nparray), len(self.nparray[0])], int) * 2
        for y in range(len(self.nparray)):
            for x in range(len(self.nparray[0])):
                field_connection_status[y,x] = self.generate_field_connection_status(y,x)
        return field_connection_status
    
    def generate_field_connection_status(self,y,x):
        """generate field connection status for the given nr on y and x pos."""
        neighborhood = self.get_neighborhood_nrs(y,x)
        nr = self.nparray[y,x]
        dist = map(lambda n:abs(nr-n), neighborhood)
        field_connection_status = 2 - dist.count(1)
        if nr == self.nr_range[0] or nr == self.nr_range[-1]:
            field_connection_status = field_connection_status - 1
        return field_connection_status
    
    def fill_nr_to_field(self, nr, y, x):
        """fill given nr to given field."""
        if not nr in self.nrs_left_to_place:
            raise Exception('cannot place a nr not left to place.')
        self.nrs_left_to_place.remove(nr)
        if self.nparray[y,x] != EMPTY:
            raise Exception('cannot place a nr on a non empty field.')
        self.nparray[y,x] = nr
        self.nrs_yx_dict[nr] = (y,x)
        self.field_connection_status[y,x] = self.generate_field_connection_status(y,x)
        for (iy,ix) in self.get_neighborhood_pos(y,x):
            self.field_connection_status[iy,ix] = self.generate_field_connection_status(iy,ix)
        self.nrs_placement_possibilities = filter(lambda p:self.can_nr_be_placed_on_field(*p), self.nrs_placement_possibilities)
    
    def placements_splitted_per_nr(self):
        """split placement possibilities per nr."""
        splitted = {}
        for nr in self.nrs_left_to_place:
            for_nr = filter(lambda p:p[0]==nr, self.nrs_placement_possibilities)
            splitted[nr] = (len(for_nr), for_nr)
        return splitted
       
    def can_nr_be_placed_on_field(self,nr,y,x):
        """check if given nr is possible on y,x pos in field."""
        # only possible if empty
        if not self.nparray[y,x] == EMPTY:
            return False
        # only possible if nr still available
        if not nr in self.nrs_left_to_place:
            return False
        # check that nr is within range of other nrs on board
        return self.check_distance_to_other_nrs_ok(nr,y,x)

    def check_distance_to_other_nrs_ok(self,nr,y,x):
        """check if given nr on the given y,x is within range of other nrs on the board."""
        # -2 because -1 is max possible distance, therefore no cutoff effect
        d_max = max(len(self.nparray), len(self.nparray[0])) - 2 
        for nr2 in range(nr - d_max, nr + d_max + 1):
            if nr == nr2 or not nr2 in self.nrs_yx_dict:
                continue
            pos2 = self.nrs_yx_dict[nr2]
            # ensure that nr and nr2 are within range
            d = self.distance((y,x),pos2)
            if d > abs(nr-nr2):
                # the distance between the nrs is bigger than the difference between nrs - impossible to place here
                #print 'dist too big (nr, nr2, y, x, dist):', nr, nr2, y, x, abs(nr-nr2)
                return False
        return True

    def generate_nrs_left_to_place(self):
        """generate list of nrs still to placed on the field."""
        nrs = []
        for nr in self.nr_range:
            if not nr in self.nparray:
                nrs = nrs + [nr]
        return nrs
    
    def get_neighborhood_pos(self,y,x):
        """tuples of (y,x) pos of neighborhood."""
        yx = []
        for iy in range(max(y-1,0), min(y+2, len(self.nparray))):
            for ix in range(max(x-1,0), min(x+2, len(self.nparray[0]))):
                if not (y == iy and x == ix):
                    yx = yx + [(iy,ix)]
        return yx
    
    def get_neighborhood_nrs(self,y,x):
        """get all fields that surround the specified field."""
        n = []
        for (iy,ix) in self.get_neighborhood_pos(y,x):
            n = n + [self.nparray[iy,ix]]
        return n
    
    def neigbors_not_fully_connected(self, y, x):
        """get neighbors to the given pos that are not yet fully connected."""
        neighborhood = self.get_neighborhood_nrs(y,x)
        not_fully_connected = []
        for n in neighborhood:
            if n == EMPTY:
                not_fully_connected = not_fully_connected +  [n]
            else:
                (ny,nx) = self.nrs_yx_dict[n]
                if self.field_connection_status[ny,nx] > 0:
                    not_fully_connected = not_fully_connected + [n]
        return not_fully_connected
    
    def check_empty_field_neighbor_permutations_ok(self, y, x):
        """check if the field can be reached from it's neighbors permutations."""
        # attention: this does not handle first and last nr if they are not initially placed on the board
        if(self.nparray[y,x] != EMPTY):
            raise Exception('trying to check a non empty field with the exhausting empty-field check...')
        not_fully_connected = self.neigbors_not_fully_connected(y, x)
        amount_empty = not_fully_connected.count(-1)
        if(amount_empty >= 2):
            # we still have empty entrance and exit, too much effort to check
            return True
        if(amount_empty == 1):
            # if only 1 possibility: plugin + redo check
            possible_fillings1 = set(reduce(lambda a,b:a if b == EMPTY else a + [b-1,b+1], not_fully_connected, []))
            possible_fillings2 = filter(lambda x:x in self.nrs_left_to_place, possible_fillings1)
            if(len(possible_fillings2) > 1):
                # more than 1 possibility, still valid
                return True
            if(len(possible_fillings2)==1):
                # only this one possibility left! plugin, recheck
                self.fill_nr_to_field(possible_fillings2[0], y, x)
                print 'only one possibility left for field (y,x,nr)', y, x, possible_fillings2[0]
                return self.is_valid()
        else:
            if len(not_fully_connected) < 2:
                # impossible to connect if we have only 1 connectable field
                #print 'invalid, as permutations invalid', y, x                
                return False
            permutations = list(itertools.combinations(not_fully_connected, 2))
            diff2 = map(lambda t:(abs(t[0]-t[1]), (t[0]+t[1])/2), permutations)
            # permutations where diff2 is 2 are valid if the nr between them is still placeable. if there is only one: only possibility for that field. if there is none board is invalid
            diff2_valid = filter(lambda t:t[0] == 2, diff2)
            # check which nrs are still available to place
            diff2_available = filter(lambda t:t[1] in self.nrs_left_to_place, diff2_valid)
            if(len(diff2_available) > 1):
                # more than 1 possibility, still valid
                return True
            if(len(diff2_available) == 1):
                # only this one possibility left! plugin, recheck
                print self 
                print 'only one possibility left for field (y,x,nr)', y, x, diff2_available[0][1]
                self.fill_nr_to_field(diff2_available[0][1], y, x)
                return self.is_valid()
        #print 'invalid, as permutations invalid', y, x
        return False
    
    def check_filled_field_valid_connections(self,y,x):
        """check that the given field can still be reached by means of predecessing and successing nr."""
        nr = self.nparray[y,x]
        if(nr == EMPTY):
            raise Exception('trying to check an empty field with too inexact filled field check...')
        neighborhood = self.get_neighborhood_nrs(y,x)
        nr_frees = neighborhood.count(EMPTY)
        #print 'frees', nr_frees
        connected_to_me = [abs(n-nr) for n in neighborhood].count(1) # empty do not count as the will not result in 1 distance as nr 0 does not exist
        #print 'connected_to_me', connected_to_me
        need = 2
        if(nr == self.nr_range[0] or nr == self.nr_range[-1]):
            need = 1
        if(nr_frees + connected_to_me >= need):
            return True
        #print 'invalid, as too less connections filled field (nr, y, x)', nr, y, x
        return False
    
    def successors(self):
        """generate successors of."""
        # nr with least placement possibilities
        placements_splitted_per_nr = self.placements_splitted_per_nr()
        p_amount = map(lambda t:placements_splitted_per_nr[t][0], placements_splitted_per_nr.keys())
        #print 'p_amount', p_amount
        i_min = p_amount.index(min(p_amount))
        #print 'i_min', i_min
        nr = placements_splitted_per_nr.keys()[i_min]
        print 'placing nr', nr
        
        # placement possibilities for nr
        # (nr,y,x)
        nr_possibilities = filter(lambda t:t[0] == nr, self.nrs_placement_possibilities)
        print 'possibilities to place (nr, len(p), p)', nr, len(nr_possibilities), nr_possibilities
        
        # sanity check: would there be a field that has only 1 nr to be filled with?
        yx_amount = {}
        for p in self.nrs_placement_possibilities:
            key = (p[1],p[2])
            if not p in yx_amount:
                yx_amount[key] = [p]
            else:
                yx_amount[key] = yx_amount[key] + [p]
        yx_ones = filter(lambda t:yx_amount[t] == 1, yx_amount.keys())
        if(len(nr_possibilities) > 1 and len(yx_ones) > 1):
            raise Exception('there is a field to fill with one nr instead. implement generating that successor therefore.')
                    
        successors = []
        for p in nr_possibilities:
            suc = copy(self)
            suc.parent = self
            suc.fill_nr_to_field(*p)
            if suc.is_valid():
                successors = successors + [suc] 
        return successors
    
    def solution_path(self):
        """get solution path up to this point."""
        l = [self]
        cur = self
        while(not cur.parent is None):
            l = [cur.parent] + l
            cur = cur.parent
        return l
          
    def distance_nrs(self, nr1, nr2):
        """get distance between nr1 and nr2 on board or None if at least one of the nrs is not present."""
        if not nr1 in self.nrs_yx_dict or not nr2 in self.nrs_yx_dict:
            return None
        pos1 = self.nrs_yx_dict[nr1]
        pos2 = self.nrs_yx_dict[nr2]
        return self.distance(pos1, pos2)
    
    def distance(self, pos1, pos2):
        """distance between pos1 and pos2."""
        return max(abs(pos1[0]-pos2[0]), abs(pos1[1]-pos2[1]))
               
    def is_valid(self):
        """check if board is still valid."""
        #check if each nr can be placed
        for nr in self.nrs_left_to_place:
            if len(filter(lambda t:t[0] == nr, self.nrs_placement_possibilities)) == 0:
                #print 'invalid as nr', nr, 'cannot be placed.'
                return False
        # check that each field if filled is connected or connectable and if not set has permutations of neighbors that allow it to be filled
        for y in range(len(self.nparray)):
            for x in range(len(self.nparray[0])):
                if self.nparray[y,x] == EMPTY:
                    if not self.check_empty_field_neighbor_permutations_ok(y,x):
                        return False
                else:
                    if not self.check_filled_field_valid_connections(y,x):
                        return False
        return True
    
    def is_solved(self):
        """checks if the field is solved."""
        if len(self.nrs_left_to_place) == 0:
            # sanity checks
            if EMPTY in self.nparray:
                raise Exception('no numbers left to place, but still empty fields?')
            return True
        return False
            
def read_board(filepath):
    """read board from a textfile."""
    f = open(filepath, 'r')
    rows = []
    w = -1 # same width for all lines
    for line in f.read().splitlines():
        values = line.split(',')
        if w == -1:
            w = len(values)
        elif w != len(values):
            raise Exception('nr. of columns differ amongst rows.')
        values = map(lambda x:EMPTY if '_' in x else int(x), values)
        rows = rows = rows + [values]
    f.close()
    return numpy.array(rows)
    
if __name__ == "__main__":
    main()

When calling the solver on the sample board from above, it finds and prints the single possible solution (as well as the path how to get there, which we don’t show here for space reasons):

[...]
solutions: [
===========================================   =======================
|  91  92  93  20  21  36  37  38  39  57 |   | x x x x x x x x x x |
|  90  94  19  22  35  53  54  40  56  58 |   | x x x x x x x x x x |
|  89  95  18  23  52  34 100  55  41  59 |   | x x x x x x x x x x |
|  88  17  96  51  24  99  33  61  60  42 |   | x x x x x x x x x x |
|  16  87  50  97  98  25  62  32  43  30 |   | x x x x x x x x x x |
|  15   6  86  49  48  63  26  44  31  29 |   | x x x x x x x x x x |
|  14   5   7  85  64  47  45  27  28  78 |   | x x x x x x x x x x |
|   4  13   8  65  84  70  46  72  77  79 |   | x x x x x x x x x x |
|   3   9  12  66  69  83  71  73  80  76 |   | x x x x x x x x x x |
|   1   2  10  11  67  68  82  81  74  75 |   | x x x x x x x x x x |
===========================================   =======================
]
solutions 1
nodes_opened 1220
nr_of_successors 1646
avg branching (not including reduction by simplification-driven successor generation) 1.3491803

Branching factor and search speed

Limited successor generation and branch cutting greatly influence the branching factor, therefore the overall runtime. With enabling both, you can see that the branching factor is around 1.35, and that the complete search space can successfully be searched. For me, disabling both resulted in the solver not even being able to find the solution in feasible time – but just try and see for yourself! 😉

Mastermind: code guessing helper in Prolog

March 29, 2013 Leave a comment
Mastermind Board

Mastermind board seen from the codemakers perspective.

You may know Mastermind, the 2 player board game where one player becomes the codemaker, who creates the code, and the other player becomes the codebreaker, who tries to guess/derive the code. A classic Mastermind board may look like the one shown on the left — seen from the perspective of the codemaker, with the code hidden in the first line. There are other layouts too, like I myself used to play Mastermind on a board with 8 colors (+1 more color, which was “empty”), and 6 code pegs per code line.

Game rules

One player becomes the codemaker, the other the codebreaker. At the start the codemaker secretly choses a code, which he sets with the colored code pegs on the hidden, first line on his side of the board. There are no limits on a valid code: color duplicates are allowed, in the version known to me even free slots are allowed (which simply increases the total amount of colors by 1). The color and position of each code peg matters — this is what the codebreaker tries to guess now: for each try, the codebreaker sets a code line with code pegs to the next free line, starting at his side of the board. After the guess has been set, the codemaker checks the following:

  1. how many code pegs in the guess and the actual code are equal in position and color. He sets this amount in black key pegs next to the line then. All code pegs equal that fit this criteria don’t get counted in 2. any more.
  2. how many code peg pairs (one peg in the guess, one in the code) share the same color, but not the same position. This does not include code pegs already counted for 1., and no duplicates: e.g. if the code contains 2 green code peg and the guess 3 green code pegs, which are not on the correct position, this counts for 2. The codemaker sets this amount in white key pegs next to the line then.

For the next round, the codebreaker shall use all information from the past code guesses to derive the actual code. Target of the game for the codemaker is to chose a code which the codebreaker will not guess/derive, and for the codebreaker, to guess/derive it in as least rounds as possible.

Deriving possible solutions from past guesses

As I played around a bit with Prolog the last few days and accidentally came across Mastermind again (and noticed, that it’s proven to be a NP-complete problem), I was interested in building a lightweight Mastermind helper for deriving those codes still possible from having seen the result of previous guesses. This would enable me to simply do some good code guess, type in the guess and it’s result and see which codes are still possible — which is basically what I find interesting about such games 😉 Mastermind further is a perfect example of what’s easy to solve in Prolog: there’s one exact solution we’re searching for, and we can conclude some facts from the results of previous guesses. The basic idea is easy:

  • We search for a code C where each position is a color.
  • We have results from known guesses, where we know for each guess a) the number B of code pegs in C and our guessed code G which are equal in position and color, and b) the number W of code pegs in C and G which share the same color, but are on wrong positions.

To code this in Prolog, we basically have to specify that:

  1. A guess unifies C, G, B and W. After multiply tries multiply guesses are valid, for which G, B and W will vary, but C will always be the same.
  2. C and G share the same amount B of code pegs with same position and color.
  3. C and G share the same amount W of code pegs with same color, but wrong positions. This can be unified with counting the amount of occurrences of each color in C and G and taking the minimum for each of those pairs. B+W unifies with the sum of those minimums then.

Implementation

% list of existing colors. to reduce colors change color(X) below!
color1(red).
color2(blue).
color3(green).
color4(yellow).
color5(orange).
color6(brown).
color7(black).
color8(white).
color9(none).

% how many code pegs can be set - how the layout looks. only change amount here!
layout(X) :- X=[_,_,_,_,_,_].

% color space - change amount of colors only here!
color(X) :- color1(X).
color(X) :- color2(X).
color(X) :- color3(X).
color(X) :- color4(X).
color(X) :- color5(X).
color(X) :- color6(X).
color(X) :- color7(X).
color(X) :- color8(X).
color(X) :- color9(X).

% check if all elements of a list fulfill certain criteria
all([],_).
all([H|T],Function) :- call(Function,H),all(T,Function).

% one guess that has the real code (C), the guessed code (G), the nr of correct pos+colors (B) and the nr of other correct colors (W).
guess(C,G,B,W) :-
%check code layout fits
layout(C),
all(C,color),
%check that correct amount of positions+colors fits
cnt_pos_equal(C,G,B),
%check that correct amount of colors only fits
color1(C1),color_cooccurrence(C,G,C1,Cnt1),
color2(C2),color_cooccurrence(C,G,C2,Cnt2),
color3(C3),color_cooccurrence(C,G,C3,Cnt3),
color4(C4),color_cooccurrence(C,G,C4,Cnt4),
color5(C5),color_cooccurrence(C,G,C5,Cnt5),
color6(C6),color_cooccurrence(C,G,C6,Cnt6),
color7(C7),color_cooccurrence(C,G,C7,Cnt7),
color8(C8),color_cooccurrence(C,G,C8,Cnt8),
color9(C9),color_cooccurrence(C,G,C9,Cnt9),
W is 0 - B + Cnt1 + Cnt2 + Cnt3 + Cnt4 + Cnt5 + Cnt6 + Cnt7 + Cnt8 + Cnt9.

% count color cooccurrences in C and G list
color_cooccurrence(C,G,Color,Cnt) :-
countall(C,Color,CCnt),
countall(G,Color,GCnt),
min(GCnt,CCnt,Cnt).

% count occurrence in list
count([],X,0).
count([X|T],X,Y):- count(T,X,Z), Y is 1+Z.
count([X1|T],X,Z):- X1\=X,count(T,X,Z).
countall(List,X,0) :-
sort(List,List1),
\+ member(X,List1),!.
countall(List,X,C) :-
sort(List,List1),
member(X,List1),
count(List,X,C).

% min of two objects
min(X,Y,X) :- X&lt;Y,!.
min(X,Y,Y) :- X&gt;=Y.

% count how many elements in 2 list are equal in position and object
cnt_pos_equal([],[],0).
cnt_pos_equal([H1|T1],[H2|T2],Cnt2) :- H1=H2,!,cnt_pos_equal(T1,T2,Cnt1),Cnt2 is Cnt1+1.
cnt_pos_equal([H1|T1],[H2|T2],Cnt) :- \+ H1=H2,!, cnt_pos_equal(T1,T2,Cnt).

Example game

An example game, showing how the game advances and which Prolog queries correspond to each guess is shown below. The guesses are actually pretty bad, but good for demonstration purposes.

  1. The codemaker secretly sets a code [yellow, none, green, yellow, orange, blue].
  2. The codebreaker (randomly) guesses [red,red,blue,blue,green,green]. This results in 0 black key pegs, 2 white key pegs. The codebreaker enters a Prolog query containing this information:
    guess(C,[red,red,blue,blue,green,green],0,2).

    and gets presented a very long list of possible codes.

  3. The codebreaker now (randomly) guesses [yellow,yellow,orange,orange,brown,brown]. This results in 1 black key pegs, 2 white key pegs. The codebreaker extends his Prolog query with this information:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2).8

    . He still sees a very long list of possible codes.

  4. The codebreaker now (randomly) guesses [black,black,white,white,none,none]. This results in 0 black key pegs, 1 white key peg. The new Prolog query is:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1).
  5. Next guess: [none,white,black,brown,orange,yellow], results in: 1 black key peg, 2 white key pegs. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2).
  6. Next guess: [brown,brown,red,red,red,yellow], results in: 0 black key pegs, 1 white key peg. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1)
  7. Next guess: [orange,orange,brown,brown,brown,green], results in: 0 black key pegs, 2 white key pegs. New prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2)
  8. Next guess: [brown,orange,yellow,green,blue,red], results in: 0 black key pegs, 4 white key pegs. New Prolog query:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2),guess(C,[brown,orange,yellow,green,blue,red],0,4)
  9. Finally, the codebreaker decides to guess a combination that’s still possible according to the output of his previous Prolog query: [yellow, green, none, yellow, orange, blue]. This results in: 4 black key pegs, 2 white key pegs. The new Prolog query now is:
    guess(C,[red,red,blue,blue,green,green],0,2),guess(C,[yellow,yellow,orange,orange,brown,brown],1,2),guess(C,[black,black,white,white,none,none],0,1),guess(C,[none,white,black,brown,orange,yellow],1,2),guess(C,[brown,brown,red,red,red,yellow],0,1),guess(C,[orange,orange,brown,brown,brown,green],0,2),guess(C,[brown,orange,yellow,green,blue,red],0,4),guess(C,[yellow, green, none, yellow, orange, blue],4,2).
  10. Executing this query reduces the amount of possible codes to 2. Now the codebreaker can do the rest on his own 😉 Btw: if the codebreaker would have guessed more wisely, he would have “cracked the code” most probably much earlier.