Object Classes

Solver

Solves a latin square.

class LatinSquareSolver.solver.Solver

__str__()

Pretty output

loadSquare(rawString)

Load a latin square from a string

Parameters:rawStr (str) – The latin square as string

Notes

The elements must be intgers seperated by spaces. The holes are denoted as non-integer, non-space elements, such as ‘*’, or ‘_’. For example:

0 1 2 3 4
1 2 3 4 _
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

randSquare(n, k, seed=None, randomise=True)

Initialize a random latin square.

Parameters:

• n (int) – The side length of the square
• k (int) – The number of holes in the grid
• seed (int) – The seed for the random number generator
• randomize (bool) – Whether to randomize the grid, or leave with the basic grid layout

Notes

The Latin Square generated will be solveable, though the solution is not guarteed to be unique. If randomize is not selected the square will remain in the basic state where each row is one offset from the previous. Ie for N = 5:

0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

solveSquare()

Solve the loaded latin square.

LatinSquare

Represents a Latin Square and includes methods needed to search for a solution

class LatinSquareSolver.latinSquare.Hole(n)

Represent a square in a Latin square that needs to be filled in, aka a hole in the square.

Notes

Keeps track of the location of the hole, the possible values that the hole can take, and whether the value has been set.

class LatinSquareSolver.latinSquare.LatinSquare

__str__()

Pretty output. Hole values are postfixed with ‘.

Returns:The pretty output. Return type:str

addHoles()

Randomly initializes the holes in the grid.

Notes

This randomly adds K holes to the graph. The result will be a solvable Latin square, but there may be more then one solution to it.

checkHoleOptions()

Removes possible options from each hole based on the non-hole values.

isSolved()

Determine is the current square is correctly solved

Returns:True if it is correctly solved. Return type:bool

Notes

Determines if the square is correct by making sure that each row and column contains all of the elements from 0 to n. This method will fail quicker than counting the values for each row and column and making sure there are no duplicates.

isValid()

Whether a partially filled in Latin square has valid hole values

Returns:True if everything is valid so far, False otherwise Return type:bool

loadSquare(rawStr)

Load a latin square from a string

Parameters:rawStr (str) – The latin square as string Raises:RuntimeError – Invalid Square Given

Notes

The elements must be intgers seperated by spaces. The holes are denoted as non-integer, non-space elements, such as ‘*’, or ‘_’. For example:

0 1 2 3 4
1 2 3 4 _
2 3 4 0 1
3 * 0 1 2
4 0 1 2 3

nextStates()

Generate all the squares corresponding to the options of the hole with the least number of options.

Returns:List of squares corresponding to selecting one of the possible values of the hole h, where h has the smallest number of possible values out of all the holes. Return type:[latinSquare]

Notes

The list of squares is calculated lazily, where the value is not calculated until it is actually used. This cuts down on the number of expensive deepcopy calls needed.

randSquare(n, k, seed=1337, randomise=True)

Initialize a random latin square.

Parameters:

• n (int) – The side length of the square
• k (int) – The number of holes in the grid
• seed (int) – The seed for the random number generator
• randomize (bool) – Whether to randomize the grid, or leave with the basic grid layout

Raises:

RuntimeError – if K > N.

Notes

If randomize is not selected the square will remain in the basic state where each row is one offset from the previous. Ie for N = 5:

0 1 2 3 4
1 2 3 4 0
2 3 4 0 1
3 4 0 1 2
4 0 1 2 3

randomise()

Takes a correct Latin square and randomizes the entries.

Notes

The randomization is done by performing an in place randomization of the rows, and then of the columns. As long as the Latin square was valid before, it will be valid afterwards.

strHoles()

Pretty output. Holes are marked with an *.

Returns:The pretty output. Return type:str

updateHoleOptions(h)

Removes possible options from each hole based on the values of the given hole.

Parameters:h (Hole) – The hole to check all the other holes against

validCols()

Determines whether the columns are valid.

Returns:True if the columns are valid, False otherwise. Return type:bool

Notes

Determines validity by making sure no value is repeated twice in each column. This is more expensive than the method used in isSolved, but necessary since there could be holes in the grid.

validHoles()

Determine if the values for the holes is valid.

Returns:If the holes have valid values will return True Return type:bool

Notes

Determines validity by checking that each non-set hole has at least one option for it’s value.

validRows()

Determines whether the rows are valid.

Returns:True if the rows are valid Return type:bool

Notes

Determines validity by making sure no value is repeated twice in each row. This is more expensive than the method used in isSolved, but necessary since there could be holes in the grid.