Lisp Quiz #1: Minesweeper

Lisp Quiz challenges and discussion
findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Lisp Quiz #1: Minesweeper

Post by findinglisp » Fri Aug 15, 2008 4:24 pm

This is the first of what will hopefully be a series of Lisp Quizzes, similar to Ruby's famous Ruby Quiz (http://www.rubyquiz.com).

The purpose of Lisp Quiz is similar to Ruby Quiz--it's all for your own enjoyment and to help you learn to program in Lisp. There are no winners and no losers, only learners. You compete only against yourself and your own abilities. In trying to solve the problems yourself and in reviewing the answers submitted by your peers, you're sure to learn something that you didn't know before.

I'd like to follow a similar format for completing each of the quizzes as was used with Ruby Quiz. Each quiz will be announced periodically, as I get time. Immediately following the posting, please don't post any substantial discussion or solutions about the quiz before the 48-hour No-Spoiler Period has elapsed. This should give people some time to consider their own solutions to the stated problem before everybody jumps in with their own answers. After the No-Spoiler Period, please feel free to discuss solutions, post your own solutions as replies to the original quiz thread on LispForum.com (this thread right here). During the No-Spoiler Period, please feel free to post clarifying questions or (gak!) corrections to the original problem statement. The intent isn't to silence all questions or comments, but rather to keep from influencing others who are trying to solve things their own way.

I'll try to come up with interesting challenges that will lead you into interestings parts of the Common Lisp spec without being so large as to consume months of your time coming up with individual solutions. That's difficult, however, and I'm fairly busy with a job and family. Thus, the schedule for new quizzes will be somewhat sporadic, particular if I have to do some programming to set things up.

To help out, you can suggest your own challenges. If you have an idea for an interesting Lisp Quiz challenge, send me an email via LispForum (findinglisp) and we can figure out how to best get it out for people to work on.

Lisp Quiz #1: Minesweeper

When I bought my first PC in 1992, I found that Windows 3.1 had a couple of games that came with it. Minesweeper was simple but tremendously addicting. I always wondered what it would take to build a simple algorithm that could solve Minesweeper. In particular, I wondered what would be the best way to navigate through those sticky situations where you can't quite reason out which of the neighboring board positions has the mine and you have to guess.

Your challenge is to write a program that can play Minesweeper. Rather than write the whole game, I have supplied a simple Minesweeper engine. It resides in the MINESWEEPER package. You can have your program play the game by creating an instance of the GAME class. The :WIDTH and :HEIGHT parameters control the size of the game board. The :MINE-COUNT parameter sets the number of mines in the board.

Each time you select a position on the board, call the REVEAL method with the (X, Y) position of the position. REVEAL returns either :BOOM-GAME-OVER if you select a position with a mine, the number of mines in surrounding locations (0 to 8), or :YOU-WIN when you select the last position without a mine.

Here's a REPL transcript so you can see this in action:

Code: Select all

CL-USER> (defvar *game* (make-instance 'minesweeper:game :width 10 :height 10 :mine-count 20))
*GAME*
CL-USER> (minesweeper:reveal *game* 0 0)
0
CL-USER> (minesweeper:reveal *game* 0 1)
1
CL-USER> (minesweeper:reveal *game* 1 0)
0
CL-USER> (minesweeper:reveal *game* 1 1)
1
CL-USER> (minesweeper:reveal *game* 2 0)
0
CL-USER> (minesweeper:reveal *game* 2 1)
1
CL-USER> (minesweeper:reveal *game* 2 2)
1
CL-USER> (minesweeper:reveal *game* 2 3)
3
CL-USER> (minesweeper:reveal *game* 2 4)
3
CL-USER> (minesweeper:reveal *game* 2 5)
4
CL-USER> (minesweeper:reveal *game* 2 6)
3
CL-USER> (minesweeper:reveal *game* 2 7)
:BOOM-GAME-OVER
CL-USER> 
Once the game ends, either because you selected a bomb, or because you won, calling REVEAL again generates an error saying that the game is already complete. There is no way to reinitialize a game that has ended. Simply create another instance of the GAME class and play again.

Your task is to use a superior algorithm to consistently win the game. Note that you cannot generate a perfect algorithm that wins all the time because at least the initial selection must be done at random, with no knowledge of where the mines might be; sometimes you will select a space with a mine on your first guess.

The game engine doesn't keep track of anything it doesn't have to for its own use. In particular, it has no user interface of any sort. Using the publicly exported methods of the MINESWEEPER package, you can only create instances of the GAME class and ask it to REVEAL a location on the board. If you need more than that (and you will), you'll have to keep track of everything else yourself.

There are other methods in the MINESWEEPER package that are not exported. You might find some of them useful to help you debug your own code. For instance, see PRINT-BOARD and PRINT-REVEALED.

Here's the MINESWEEPER package:

Code: Select all

(defpackage #:minesweeper
  (:use #:cl)
  (:export #:game
           #:reveal))

(in-package #:minesweeper)

(defclass game ()
  ((board      :accessor board-of      :initarg :board)
   (revealed   :accessor revealed-of   :initarg :revealed)
   (mine-count :accessor mine-count-of :initarg :mine-count :initform 20)
   (width      :accessor width-of      :initarg :width      :initform 10)
   (height     :accessor height-of     :initarg :height     :initform 10)
   (game-over  :accessor game-over-of  :initarg :game-over  :initform nil)))

(defun print-matrix (array width printer
                         &optional (stream *standard-output*))
  "Print an ARRAY as a matrix with the specified WIDTH. Use the
specified PRINTER to output each array object to the STREAM."
    (loop
       for index from 0 below (length array)
       for value = (aref array index)
       do (funcall printer value stream)
       when (= 0 (mod (1+ index) width))
       do (terpri stream)))

(defgeneric print-revealed (game &optional stream)
  (:documentation "Print out the matrix of revealed locations to the
  specified STREAM."))

(defmethod print-revealed ((game game) &optional (stream *standard-output*))
  (with-slots (revealed width)
      game
    (print-matrix revealed width
                  #'(lambda (value stream)
                      (princ (if value 1 0) stream))
                  stream)))

(defgeneric print-board (game &optional stream)
  (:documentation "Print out the game board on the specified STREAM."))

(defmethod print-board ((game game) &optional (stream *standard-output*))
  (with-slots (board width)
      game
    (print-matrix board width 
                  #'(lambda (value stream)
                      (if (eql value :mine)
                          (princ #\M stream)
                          (princ value stream)))
                  stream)))


(defgeneric linear-to-xy (game index)
  (:documentation "Converts a linear index of board position into
  an (X,Y) coordinate, returned as multiple values."))

(defmethod linear-to-xy ((game game) index)
  (with-slots (width)
      game
    (let ((y (truncate (/ index width)))
          (x (mod index width)))
      (values x y))))

(defgeneric xy-to-linear (game x y)
  (:documentation "Convert an (X,Y) coordinate to a linear position in
  the board array. Returns the zero-based linear index or NIL if
  the (X,Y) position is out of bounds."))

(defmethod xy-to-linear ((game game) x y)
  (with-slots (height width)
      game
    (if (or (< x 0)                     ; check if out of bounds
            (>= x width)
            (< y 0)
            (>= y height))
        NIL
        (+ (* y (width-of game)) x))))

(defgeneric count-a-mine (game x y)
  (:documentation "Return 1 if the specified location, (X,Y), contains
  a mine, or 0 otherwise. If X or Y is out of range of the board,
  return 0."))

(defmethod count-a-mine ((game game) x y)
  (with-slots (board)
      game
    (let ((index (xy-to-linear game x y)))
      (if index
          (if (eql (aref board index) :mine)
              1
              0)
          0))))                         ; out of bounds, so return 0

(defgeneric count-surrounding-mines (game index)
  (:documentation "Return a count of the mines surrounding a given
  position, INDEX, on the board."))

(defmethod count-surrounding-mines ((game game) index)
  (with-slots (height width)
      game
    ;; Convert the linear index to (X,Y) so that we can more easily
    ;; deal with the edges of the board and COUNT-A-MINE can detect
    ;; out-of-bounds values.
    (multiple-value-bind (x y)
        (linear-to-xy game index)
      (+ (count-a-mine game (1- x) (1- y))
         (count-a-mine game x      (1- y))
         (count-a-mine game (1+ x) (1- y))
         (count-a-mine game (1- x) y)
         (count-a-mine game (1+ x) y)
         (count-a-mine game (1- x) (1+ y))
         (count-a-mine game x      (1+ y))
         (count-a-mine game (1+ x) (1+ y))))))

(defmethod initialize-instance :after ((game game) &key)
  (with-slots (board revealed mine-count width height game-over) 
      game
    (let ((board-length (* width height)))
      (setf board (make-array board-length ))
      (setf revealed (make-array board-length :initial-element nil))
      (let* ((clearspots (make-array board-length))
             (clear-length board-length))
        (dotimes (i board-length)
          (setf (aref clearspots i) i))
        (dotimes (i mine-count)
          (let* ((choice-index (random clear-length))
                 (choice (aref clearspots choice-index)))
            (setf (aref board choice) :mine)
            (setf (aref revealed choice) t) ; mark mine locations as
                                            ; already revealed. This
                                            ; makes all-revealed-p
                                            ; simpler.
            (decf clear-length)
            (setf (aref clearspots choice-index) 
                  (aref clearspots clear-length)))))
      (dotimes (i board-length)
        (unless (eql (aref board i) :mine)
          (setf (aref board i) (count-surrounding-mines game i)))))))

(defgeneric location (game x y)
  (:documentation "Returns the contents of the board at the
  specified (X,Y) location. This can either be :MINE if there is a
  mine present, or the number of surrounding mines (0 - 8) if there is
  nothing at that location."))

(defmethod location ((game game) x y)
  (aref (board-of game) (xy-to-linear game x y)))

(defgeneric mine-p (game x y)
  (:documentation "Returns NIL if there is not a mine at the
  specified (X,Y) location."))

(defmethod mine-p ((game game) x y)
  (eql :mine (location game x y)))

(defgeneric mark-revealed (game x y)
  (:documentation "Mark that the user has seen this particular (X,Y)
  position."))

(defmethod mark-revealed ((game game) x y)
  (with-slots (revealed)
      game
    (let ((position (xy-to-linear game x y)))
      (setf (aref revealed position) t))))

(defgeneric all-revealed-p (game)
  (:documentation "Return true if every board position has been
  revealed; NIL otherwise. The user wins when every board position has
  been revealed without him selecting a position with a mine. This is
  the case because the positions with mines are marked as being
  revealed in INITIALIZE-INSTANCE."))

(defmethod all-revealed-p ((game game))
  (every #'identity (revealed-of game)))

(defgeneric reveal (game x y)
  (:documentation "Reveals the content of the game board location
  specified by X and Y. Returns the number of mines surrounding the
  location if the location does not contain a mine, or :BOOM-GAME-OVER
  if the location contains a mine. If the user selects all the free
  spaces on the board, the function returns :YOU-WIN instead of the
  number of surrounding mines."))

(defmethod reveal ((game game) x y)
  (when (game-over-of game)
    (error "This game is already over."))
  (if (mine-p game x y)
      (progn
        (setf (game-over-of game) t)
        :boom-game-over)
      (progn
        (mark-revealed game x y)
        (if (all-revealed-p game)
            (progn
              (setf (game-over-of game) t)
              :you-win)
            (location game x y)))))
Let the games begin!
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

Rich_Robot

Re: Lisp Quiz #1: Minesweeper

Post by Rich_Robot » Sun Aug 17, 2008 2:30 am

Playing Minesweeper is an NP Complete problem.

Was this an intentional choice? If it was then Lisp programmers are freaking hardcore. :D

Check Out Clay Mathematics Institute - Popular Lectures - Minesweeper

anton
Posts: 5
Joined: Tue Jul 15, 2008 1:45 am

Re: Lisp Quiz #1: Minesweeper

Post by anton » Sun Aug 17, 2008 4:39 am

Rich_Robot wrote:Playing Minesweeper is an NP Complete problem.

Was this an intentional choice? If it was then Lisp programmers are freaking hardcore. :D

Check Out Clay Mathematics Institute - Popular Lectures - Minesweeper
Rich_Robot, IMHO this note is inappropriate during the 48-hour No-Spoiler Period.

dmitry_vk
Posts: 96
Joined: Sat Jun 28, 2008 8:01 am
Location: Russia, Kazan
Contact:

Re: Lisp Quiz #1: Minesweeper

Post by dmitry_vk » Sun Aug 17, 2008 10:35 am

Rich_Robot wrote:Playing Minesweeper is an NP Complete problem.
Being NP Complete does not mean that it is not fun to try to solve it :)

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Lisp Quiz #1: Minesweeper

Post by findinglisp » Sun Aug 17, 2008 11:15 am

Rich_Robot wrote:Playing Minesweeper is an NP Complete problem.

Was this an intentional choice? If it was then Lisp programmers are freaking hardcore. :D

Check Out Clay Mathematics Institute - Popular Lectures - Minesweeper
Many interesting problems are NP complete for optimal solutions. Heuristics can typically be invented to come up with nearly-optimal solutions, however. This is one of those cases. The intent of the challenge is not to create an algorithm that wins every time. Indeed, that's impossible because, as stated in the challenge description, you have to guess on at least your first selection. Rather, the challenge is to create an algorithm that plays a very good game and exploits whatever information it can find to play optimally given the random nature of the initial mine distribution.

Good luck!

BTW, the reference to the Clay Mathematics Institute returns a "403 Forbidden" for me. I would be interested in reading that after the No-Spoiler Period.
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

findinglisp
Posts: 447
Joined: Sat Jun 28, 2008 7:49 am
Location: Austin, TX
Contact:

Re: Lisp Quiz #1: Minesweeper

Post by findinglisp » Sun Aug 17, 2008 4:25 pm

The No-Spoiler Period has now officially ended. Feel free to discuss and post solutions at will. If you do post a solution, be sure to include a description of your overall technique. The more you describe what you have done, the more others can learn from it.

Also, make sure you deal with tabs in your code, per the tips here:
viewtopic.php?f=32&t=115
Cheers, Dave
Slowly but surely the world is finding Lisp. http://www.findinglisp.com/blog/

milfredcubiclex

Re: Lisp Quiz #1: Minesweeper

Post by milfredcubiclex » Sun Aug 17, 2008 4:49 pm

Recently I wrote in my blog about writing a minesweeper solver in lisp: http://www.stephenlombardi.com/blog/?p=11. Maybe it will give people some ideas...

vegard
Posts: 7
Joined: Sun Jun 29, 2008 11:12 am

Re: Lisp Quiz #1: Minesweeper

Post by vegard » Mon Aug 18, 2008 12:51 pm

As much as I wanted to make an entry, I really hadn't got the time to actually sit down and write the thing. Anyways, let the clever solutions present themselves. I look forward to the next quiz :)

Exolon
Posts: 49
Joined: Sat Jun 28, 2008 12:53 pm
Location: Ireland
Contact:

Re: Lisp Quiz #1: Minesweeper

Post by Exolon » Tue Aug 19, 2008 5:53 pm

I'm going to take this one on in slow-time, since it seems like just the right kind of mini-project to help me learn Lisp. I'd expect a simple heuristic mind would do quite well though without needing clever AI, at least in small, finite Minesweeper worlds.

implausibleusername
Posts: 6
Joined: Sun Aug 24, 2008 2:11 pm

Re: Lisp Quiz #1: Minesweeper

Post by implausibleusername » Sun Aug 24, 2008 4:01 pm

Ok, I made a stab at this to kick start the competition.
It's a bit horrific, it weighs in at 200ish lines of code + some small commented out tests.

I started writing, and never backed up to edit unless the code didn't work.
So the algorithm is sub-optimal, it should be rewritten for a better order performance, the deterministic branch and bound takes O(n 2^n) rather than O(2^n) worst case, and there are various other inefficiencies.

It is composed of two parts ~ a conservative solver that only marks squares if the alternate state(bomb/not bomb) is proven impossible; and a naive Bayesian guesser, that model's the probability of drawing a bomb in a neighborhood of a known square as being independent of all other known squares. This takes over when the conservative method can't get anywhere.

On 10 by 10 grids with 20 mines, it wins more often than it loses, and the main bottle neck seems to be the REPL.
I haven't tried it on harder problems.

Code: Select all

;We track the state of the grid in an array. mark the areas we believe a bomb to be with 'bomb,
;unknown regions with nil and square without a bomb in with the number of *unmarked* bombs around it
;When building a hypothesis squares may be marked with 'not-bomb
;Launch code with "(again) (run (make-array 10 10) 20)"

(declaim (optimize (debug 3)))

(defvar *total-unknown-bombs* 20)
;Needed for the Naive Bayesian GUESS
;Modified by RUN, SET-BOMB, and SET-NIL
(defparameter *game* (make-instance 'minesweeper:game)) 
;Glue used by CHECK to hook into minesweeper package
;Modified by AGAIN

;Utilities
(defun get-nhood(x y array)
  (loop for i from (max 0 (- x 1)) to (min (1- (array-dimension array 0)) (+ x 1))nconc
       (loop for j from (max 0 (- y 1)) to (min (1- (array-dimension array 1)) (+ y 1))
	  unless (and (= i x) (= j y)) collect (cons i j))))

(defun get-marked-bombs(x y array)
  (remove-if-not (lambda(x)(eq 'bomb (aref array (car x)(cdr x)))) (get-nhood x y array)))

(defun get-safe(x y array)
  (remove-if-not (lambda (x)(numberp (aref array (car x)(cdr x)))) (get-nhood x y array)))

(defun get-unknown(x y array)
  (remove-if (lambda(x)(aref array (car x)(cdr x))) (get-nhood x y array)))

(defmacro new-loop (name fn)
  `(defmacro ,name ((i j x y array) &rest body)
     `(loop for (,i . ,j) in (,',fn ,x ,y ,array) do
	   ,@body)))

(new-loop doun get-unknown)
(new-loop dosafe get-safe)
;Assignment operators
(defun query (x y array &aux (val (check x y)))
  (when (aref array x y) (break)) 
  (if (numberp val)
      (setf (aref array x y) (- val (length (get-marked-bombs x y array))))
      (throw 'you-are-dead t)))

(defun set-bomb (x y array)
  (when (aref array x y) (break)) 
  (setf (aref array x y) 'bomb)
  (decf *total-unknown-bombs*)
  (let ((contradiction))
    (dosafe (i j x y array)
	    (when (< (decf (aref array i j)) 0)
	      (setf contradiction t)))
    (when (or contradiction (< *total-unknown-bombs* 0))
      (throw 'contradiction t))))

(defun set-not-bomb (x y array);Only used to build hypothesis
  (when (aref array x y) (break)) 
  (setf (aref array x y) 'not-bomb)
  (dosafe (i j x y array)
	  (when (< (length (get-unknown i j array)) (aref array i j)) 
	    (throw 'contradiction t))))

(defun set-nil (x y array)
  (when (eq (aref array x y) 'bomb)
	    (dosafe (i j x y array)
		    (incf (aref array i j))))
  (setf (aref array x y) nil)
  (incf *total-unknown-bombs*)
  nil)
	     
;Conservitive setter
;Uses branch and bound to find a node that is safe to choose
 
(macrolet ((safe-amb (set-fn)
	     `(unwind-protect;We are using unwind-protect to emulate dynamic scope
		   (progn  ;for elements within our array
		     (,set-fn x y array)
		     (apply #'amb array rest)
		     nil)
		(set-nil x y array))))

(defun amb(array &rest args);Analagous to McCarthy's amb operator http://gd.tuwien.ac.at/languages/scheme/tutorial-dsitaram/t-y-scheme-Z-H-15.html
  (when args                ;Returns nil if no contradiction is found
    (destructuring-bind ((x . y) . rest) args
      (when (catch 'contradiction
	      (safe-amb set-bomb)) 
	(safe-amb set-not-bomb)))))
	     
(defun init-amb (array &rest args)
  (when args
    (destructuring-bind ((x . y) . rest) args
      (if (catch 'contradiction
	    (safe-amb set-bomb))
	  (progn
	    (query x y array)
	    (apply #'init-amb array rest)
	    t)
	  (when (catch 'contradiction
		  (safe-amb set-not-bomb))
	    (set-bomb x y array)
	    (apply #'init-amb array rest)
	    t))))))

(defun build-dependency (safe-node array)
  "Finds dependent regions that must be handled together by branch and bound"
  (let (collect)
    (do ((known-unknown (make-hash-table :test 'equal))
	 (known-safe (make-hash-table :test 'equal))
	 add-un (add-sa (list safe-node)))
	((not (or add-un add-sa)))
      (let ((new-sa (pop add-sa)))
	(when new-sa
	  (dolist (new-un (get-unknown (first new-sa) (rest new-sa) array))
		   (unless (gethash new-un known-unknown)
		     (push new-un collect)
		     (setf (gethash new-un known-unknown) t)
		     (dolist (n-sa (get-safe (first new-un) (rest new-un) array))
		       (unless (equal new-sa n-sa)
			 (push n-sa add-sa)))))))
      
      (let ((new-un (pop add-un)))
	(when new-un
	  (dolist (new-sa (get-safe (first new-un) (rest new-un) array))
	    (unless (gethash new-sa known-safe)
	      (setf (gethash new-sa known-safe) t)
	      (dolist (n-un (get-safe (first new-sa) (rest new-sa) array))
		(unless (equal new-un n-un)
		  (push n-un add-un))))))))
     collect))

(defun change-first (array list)
  "changes first element as branch-bound operator only tries to elimate first point in list"
  (dolist (e (copy-seq list))
    (setf (cdr (last list)) (list e)
	  list (rest list))
    (when (apply #'init-amb array list)
      (return t))))

(defun build-regions (array)
  "Builds a spanning set of dependent regions"
  (Let (regions)
    (dotimes (x (array-dimension array 0))
      (dotimes (y (array-dimension array 1))
	(when (numberp (aref array x y))
	  (let ((first (first (get-unknown x y array))))
	    (unless (some (lambda(x) (member first x :test #'equal)) regions)
	      (push (build-dependency (cons x y) array) regions))))))
    ;(format t "Regions:~a~%" regions)
    regions))
	      
(defun make-safe-move(array)
  (let (worked?)
    (dolist (e (build-regions array))
	     (setf worked? (or (change-first array e) worked?)))
    worked?))

(defun make-all-safe-moves(array)
  (do ()((not (make-safe-move array)))))

(defun guess(array)
  "Naive Bayesian estimator ~
    Models distribution about each point as independent
   Guesses away from known points if that seems safer"
  (let ((unknown 0)
	(score))
    (dotimes (x (array-dimension array 0))
      (dotimes (y (array-dimension array 1))
	(unless (aref array x y)
	  (incf unknown))
	(when (and (numberp (aref array x y)) (/= 0 (aref array x y)))
	  (push (list (/ (length (get-unknown x y array)) (aref array x y)) x y) score))))
    (let ((total-ratio (when (/= 0 *total-unknown-bombs*)
			 (/ unknown *total-unknown-bombs*)))
	  (best (first (sort score #'> :key #'first))))
      (unless (and score total-ratio (> (first best) total-ratio))
	(dotimes (x (array-dimension array 0))
	  (dotimes (y (array-dimension array 1))
	    (unless (or (aref array x y) (get-safe x y array))
	      (return-from guess (query x y array))))))
      (let ((temp (first (get-unknown (second best) (third best) array)))) 
	     (query (first temp) (rest temp) array)))))
	  
(defun run(array bombs)
  (setf *total-unknown-bombs* bombs)
  (catch 'you-are-dead 
    (do ()(nil)
      (format t "Guessing~%")
      (guess array)
      (Format t "Safe moves~%")
      (make-all-safe-moves array)))
  array)
      
#|;Test cases

(defun check (x y)(declare (ignore x y)) 0)

(let ((a1 (make-array '(2 3) :initial-element nil))
      (a2 (make-array '(3 3) :initial-element nil))
      (a3 (make-array '(3 4) :initial-contents '((0 nil 0 nil)
						 (nil nil nil 1)
						 (nil nil nil nil))))
     (a4 (make-array '(3 4) :initial-contents '((1 nil 1 nil)
						(nil nil nil 1)
						(nil nil nil nil)))))
  
  (setf (aref a1 0 1) 0)
  (setf (aref a2 1 1) 8)
  (init-amb a1 '(0 . 0) '(1 . 0) '(1 . 1) '(0 . 2) '(1 . 2))
  (print a1)
  (print (build-dependency '(1 . 1) a2)) 
  (apply #'init-amb a2 (build-dependency '(1 . 1) a2))
  (print a2)
  (apply #'init-amb a3 (build-dependency '(0 . 0) a3))
  (print a3)
  (print (build-regions a3))
  (make-all-safe-moves a3)
  (print a3)
  (make-all-safe-moves a4)
  (print a4)
  (guess a4)
  (print a4))
|#
(defun check (x y)
  (let ((temp (minesweeper:reveal *game* x y)))
  (format t "X:~a Y:~a result:~a~%" x y temp)
  temp))

(defun again ()
  (setf *game* (make-instance 'minesweeper:game))) 
Sample Run:

Code: Select all

CL-USER> (again) (run (make-array '(10 10) :initial-element nil) 20)
Guessing
X:0 Y:0 result0
Safe moves
X:1 Y:0 result0
X:0 Y:1 result0
X:1 Y:1 result0
....Snipped....
X:9 Y:9 result1
X:2 Y:9 result1
X:3 Y:9 resultYOU-WIN
#2A((0 0 0 0 0 0 0 0 0 BOMB)
    (0 0 0 0 0 0 0 0 0 BOMB)
    (0 0 0 0 0 BOMB 0 BOMB 0 0)
    (BOMB 0 BOMB 0 0 BOMB 0 0 0 NIL)
    (0 0 0 0 0 BOMB 0 0 BOMB BOMB)
    (0 0 0 BOMB 0 BOMB BOMB 0 0 BOMB)
    (0 0 0 0 0 0 BOMB BOMB 0 0)
    (0 0 0 BOMB 0 BOMB 0 0 0 0)
    (0 0 0 0 0 0 0 0 0 0)
    (0 0 0 0 BOMB 0 0 0 BOMB 0))
CL-USER> (again) (run (make-array '(10 10) :initial-element nil) 20)
Guessing
X:0 Y:0 result2
Safe moves
Guessing
X:0 Y:2 result2
Safe moves
Guessing
X:0 Y:1 resultBOOM-GAME-OVER
#2A((2 NIL 2 NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL)
    (NIL NIL NIL NIL NIL NIL NIL NIL NIL NIL))
Feel free to ask questions about how it works/point out things I did the hard way.

Can I suggest we pick an easier/shorter problem next time? Maybe sudoku or something from the Ruby quiz.

Post Reply