vooga.aiEngine.Algorithms
Class NPSolver

java.lang.Object
  vooga.aiEngine.Algorithms.AbstractAlgorithm
      vooga.aiEngine.Algorithms.NPSolver

public class NPSolver
extends AbstractAlgorithm

NPSolver.java

Author:

Cody Freeman A framework in case we get a game where we need to plan. An algorithm based on this should only be done as a last resort, as NP problems have awful runtimes, and we can't do this dozens of times a second or the computer is going to die. The NPSolver reads in a big list of possibilities, then up to two lists of constraints, and will read through all possible combinations until it finds something that works. This doesn't have a method included that backtracks, but instead serves as a kind of framework for our own reference.

Constructor Summary

NPSolver()

Method Summary

java.util.ArrayList<java.lang.String>	backtrack(java.util.ArrayList<java.lang.String> in, int level) backtrack - goes back a step to see if the puzzle can be solved given a different parameter.
char[][]	findCrossword(char[][] grid, java.lang.String[] dictionary) findCrossword - given a grid and an array of strings representing a dictionary, this tries to fill in a blank crossword puzzle without clues.
void	perform(java.lang.Object... args) Performs an arbitrary algorithm with arbitrary parameters.

Methods inherited from class vooga.aiEngine.Algorithms.AbstractAlgorithm

performWithDelay, setDelay

Methods inherited from class java.lang.Object

clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait

Constructor Detail

NPSolver

public NPSolver()

Method Detail

findCrossword

public char[][] findCrossword(char[][] grid,
                              java.lang.String[] dictionary)

findCrossword - given a grid and an array of strings representing a dictionary, this tries to fill in a blank crossword puzzle without clues. This isn't fully implemented, but is showing the approach for these problems.

Parameters:

grid - - A Character matrix that lets the computer put in words and double check whether or not every word is in the dictionary.

dictionary - - A string array representing the entire contents of a dictionary.

backtrack

public java.util.ArrayList<java.lang.String> backtrack(java.util.ArrayList<java.lang.String> in,
                                                       int level)

backtrack - goes back a step to see if the puzzle can be solved given a different parameter.

Parameters:

in - - the current list of results, to be checked for completeness or updated to go back a step.

level - - The number of constraints that have been satisfied thus far.

perform

public void perform(java.lang.Object... args)
             throws java.lang.RuntimeException

Description copied from class: AbstractAlgorithm

Performs an arbitrary algorithm with arbitrary parameters. Defines the basic parameters of an algorithm. Algorithms generally require a number of EventObjects which the algorithm fires according to certain specifications.

Specified by:

perform in class AbstractAlgorithm

Throws:

java.lang.RuntimeException