jkndrkn

Well, I am tasked with creating a solver for the game Numbrix (implemented at the linked site using a Java applet rather than the more logical choice of JavaScript).

So far, I've completed a command-line UI system that will allow a human player to attempt to play such a game. This means that I've already created the game representation and have developed board state validators. The final goal, however, is to write an AI system that can solve a game in less than one minute. This means that brute-force techniques wouldn't make a good choice. Just how poorly would they perform?

Well, if one considers an unsolved Numbrix board, one can readily obtain the values missing from the board and then write code that will test every single board configuration until the correct configuration is detected. Exploring such a technique is a good starting point, and led me to write the following:

(defun list-permutator (lis fun &optional permutation)
  "Iterates through all permutations of LIS, executing FUN on each permutation in turn.
   Useful in brute-force solving strategies."
  (cond 
    ((null lis) nil)
    ((null (rest lis)) 
     (progn
       (funcall fun (append permutation lis))
       lis))
    (t (dolist (x lis)
	 (let ((sublis (remove x lis))
	       (base (list x)))
	   (list-permutator sublis fun (append permutation base)))))))

As the doc string reads, this function will take a list of numbers (or any other kind of elements) and execute a function on each permutation generated by that list. For example, if the values needed to solve a certain Numbrix board are 1, 3, and 8, then this LIST-PERMUTATOR could be run as follows to reveal which permutations would need to be applied to the board to find a solution:

CL-USER> (list-permutator '(1 3 8) #'(lambda (x) (format t "~a~%" x)))
(1 3 8)
(1 8 3)
(3 1 8)
(3 8 1)
(8 1 3)
(8 3 1)
NIL

Just how inefficient is this function? Well, the September 17th Numbrix puzzle has 49 empty squares. Since the number of permutations of a list of size N is the factorial of N:

CL-USER> (defun fac (n)
	   (cond
	     ((= n 0) 1)
	     (t (* n (fac (1- n))))))
FAC
CL-USER> (fac 49)
608281864034267560872252163321295376887552831379210240000000000

Testing potentially 608281864034267560872252163321295376887552831379210240000000000 board positions is really quite impractical. In fact, depending on the efficiency of my application logic, trying to solve the September 17th puzzle will likely take far more than one minute. Instead of using this dumb "brute force" approach, I will be applying a search strategy to find the solution, working in a way similar to which a human player (and other board game computer opponents) might. I will likely start simple and gradually apply constraints on the search to eliminate wasted moves.