bruteforce peg solitaire (english version) solver
Posted: Mon Jun 09, 2008 6:19 am
Just wrote a brute force English version peg solitaire (http://en.wikipedia.org/wiki/Peg_solitaire) solver. uses iterative algorithms to find solutions.
The fact that the board is symmetric (you can flip the board upside down or turn it by 90deg incrementally etc) gives you the advantage of being able to match 7 solutions to any possible board combination
example below, 1 indicates no marble, 2 indicates "no hole" and 0 indicates marble, so the board area is essentially the 1s and the 0s
sample board:
__000__
__000__
0100000
0000000
0000000
__000__
__000__
so if one finds solns for the 1st "1" (hole) being at (2,0), (2,1),(2,2),(3,0),(3,1),(3,2) and (3,3) one can simply flip the board around in different ways and the similar transactions will apply to the rest of the board
The present code does not rely on already found solutions, am adding the same in a while
Right now I have used this code to find the 7 basic solutions only
Code attached below, comments welcome as always
)
The fact that the board is symmetric (you can flip the board upside down or turn it by 90deg incrementally etc) gives you the advantage of being able to match 7 solutions to any possible board combination
example below, 1 indicates no marble, 2 indicates "no hole" and 0 indicates marble, so the board area is essentially the 1s and the 0s
sample board:
__000__
__000__
0100000
0000000
0000000
__000__
__000__
so if one finds solns for the 1st "1" (hole) being at (2,0), (2,1),(2,2),(3,0),(3,1),(3,2) and (3,3) one can simply flip the board around in different ways and the similar transactions will apply to the rest of the board
The present code does not rely on already found solutions, am adding the same in a while
Right now I have used this code to find the 7 basic solutions only
Code attached below, comments welcome as always
)Code: Select all
;we define the board, 2 is not allowed i.e no space, 1 is no marble, 0 is marble present
Global Dim Board.b(32,6,6)
Board(0,0,0)=2
Board(0,0,1)=2
Board(0,0,2)=0
Board(0,0,3)=0
Board(0,0,4)=0
Board(0,0,5)=2
Board(0,0,6)=2
Board(0,1,0)=2
Board(0,1,1)=2
Board(0,1,2)=0
Board(0,1,3)=0
Board(0,1,4)=0
Board(0,1,5)=2
Board(0,1,6)=2
Board(0,2,0)=0
Board(0,2,1)=0
Board(0,2,2)=0
Board(0,2,3)=0
Board(0,2,4)=0
Board(0,2,5)=0
Board(0,2,6)=0
Board(0,3,0)=0
Board(0,3,1)=0
Board(0,3,2)=0
Board(0,3,3)=1
Board(0,3,4)=0
Board(0,3,5)=0
Board(0,3,6)=0
Board(0,4,0)=0
Board(0,4,1)=0
Board(0,4,2)=0
Board(0,4,3)=0
Board(0,4,4)=0
Board(0,4,5)=0
Board(0,4,6)=0
Board(0,5,0)=2
Board(0,5,1)=2
Board(0,5,2)=0
Board(0,5,3)=0
Board(0,5,4)=0
Board(0,5,5)=2
Board(0,5,6)=2
Board(0,6,0)=2
Board(0,6,1)=2
Board(0,6,2)=0
Board(0,6,3)=0
Board(0,6,4)=0
Board(0,6,5)=2
Board(0,6,6)=2
Structure move_store
fromrow.b
fromcol.b
torow.b
tocol.b
EndStructure
Global move=0
Global Dim moves_made.move_store(32,32)
Global Dim move_store_count(32)
;the above array is of the form : move_num , move_stack
;move number is the actual board move and the stack contains upto 32
;moves already made in this movenum
;the moves_store_count keeps track of the number of moves in the stack
Procedure Print_board()
PrintN(":::::::::::::::::::::::::::::::::::::::::")
For m=0 To 31
PrintN(":::::::::::::::::::::"+Str(m)+":::::::::::::::::::::")
For r=0 To 6
For c =0 To 6
Print(Str(Board(m,r,c)))
Next c
PrintN("")
Next r
Next m
;Input()
EndProcedure
Procedure Copy_board (board_from, board_to)
For i=0 To 6
For j=0 To 6
Board(board_to,i,j)=Board(board_from,i,j)
Next j
Next i
EndProcedure
For i = 0 To 32
move_store_count(i)=0
Copy_board(0,i)
Next i
;the algo is as follows:
;at each move apply a mask to find a marble with empty adjacency.
;once u reach 32 moves, check how many are left...
;if at any stage no move to make
;backtrack
;at each move fill the moves_made(movenum)\fromx.fromy,tox,toy
;keep going till one marble left at move 32
;This procedure Brings the board back to the given move num (enter the present movenum too)
;it adjusts all other boards,move,moves_store_count to reflect the game at to_move_num
Procedure Retract_move(from_move_num,to_move_num)
move=to_move_num
For i = to_move_num+1 To from_move_num
move_store_count(i)=0
Copy_board(0,i)
Next i
EndProcedure
Procedure Is_Move_made(movenum,fromrow,fromcol,torow,tocol);check if the move is already made
result=0
If Not(move_store_count(movenum)=0); if there is any move already registered in the store
For i = 1 To move_store_count(movenum)
If (moves_made(movenum,i)\fromrow=fromrow)And(moves_made(movenum,i)\fromcol=fromcol)And(moves_made(movenum,i)\torow=torow)And(moves_made(movenum,i)\tocol=tocol)
result=1
Break
EndIf
Next i
EndIf
ProcedureReturn (result)
EndProcedure
Procedure Update_board_with_move (board_move, fromx ,fromy,tox,toy,removex,removey)
Board(board_move,fromx,fromy)=1
Board(board_move,removex,removey)=1
Board(board_move,tox,toy)=0
move_store_count(board_move)=move_store_count(board_move)+1
moves_made(board_move,move_store_count(board_move))\fromrow=fromx
moves_made(board_move,move_store_count(board_move))\fromcol=fromy
moves_made(board_move,move_store_count(board_move))\torow=tox
moves_made(board_move,move_store_count(board_move))\tocol=toy
EndProcedure
Procedure Make_move(movenum.b);movenum is the move being made
marble_present=0
move_found=0
;PrintN("inside make_move"+Str(movenum))
For row=0 To 6
For column=0 To 6
;we first check if there is a marble at the given position
If Board(movenum-1,row,column)=0
;we have found a marble, now we look around it
marble_present=1
;PrintN ("marble found")
;we now check the 1+adjacencies for a blank square
;1st we check up and if the move is already made (2 rows up, same col, fromx=row, fromy=col,tox=row-2,toy=col)
If Not((row=0) Or(row=1)) And (move_found=0)
If Board(movenum-1,row-2,column)=1 And Board(movenum-1,row-1,column)=0 And Is_Move_made(movenum,row,column,row-2,column)=0
;vacant spot on top found, we can make a move
;1st we copy the board(movenum-1) To board(movenum)
;PrintN("row=0 or row=1")
Copy_Board(movenum-1,movenum)
;then we change board(movenum) for the move
Update_board_with_move(movenum,row,column,row-2,column,row-1,column)
move_found=1
;done with move
Break 2
EndIf
EndIf
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;if no move found up, we look down and see if the move is already made
;(2 rows down, same col, fromx=row, fromy=col,tox=row+2,toy=col)
If Not((row=5) Or(row=6)) And (move_found=0)
If Board(movenum-1,row+2,column)=1 And Board(movenum-1,row+1,column)=0 And Is_Move_made(movenum,row,column,row+2,column)=0
;vacant spot found below, we can make a move
;1st we copy the board(movenum-1) To board(movenum)
;PrintN("row=5 or row=6")
Copy_Board(movenum-1,movenum)
;then we change board(movenum) for the move
Update_board_with_move(movenum,row,column,row+2,column,row+1,column)
move_found=1
;done with move
Break 2
EndIf
EndIf
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;if no move found up, and down we look left and see if the move is already made
;(same row, 2 cols left, fromx=row, fromy=col,tox=row,toy=col-2)
If Not((column=0) Or(column=1)) And (move_found=0)
If Board(movenum-1,row,column-2)=1 And Board(movenum-1,row,column-1)=0 And Is_Move_made(movenum,row,column,row,column-2)=0
;vacant spot found to the left, we can make a move
;1st we copy the board(movenum-1) To board(movenum)
;PrintN("col=0 or col=1")
Copy_Board(movenum-1,movenum)
;then we change board(movenum) for the move
Update_board_with_move(movenum,row,column,row,column-2,row,column-1)
move_found=1
;done with move
Break 2
EndIf
EndIf
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
;if no move found up,down and left we look right and see if the move is already made
;(same row, 2 cols right, fromx=row, fromy=col,tox=row,toy=col+2)
If Not((column=5) Or(column=6)) And (move_found=0)
If Board(movenum-1,row,column+2)=1 And Board(movenum-1,row,column+1)=0 And Is_Move_made(movenum,row,column,row,column+2)=0
;vacant spot found to the right, we can make a move
;1st we copy the board(movenum-1) To board(movenum)
;PrintN("col=5 or col=6")
Copy_Board(movenum-1,movenum)
;then we change board(movenum) for the move
Update_board_with_move(movenum,row,column,row,column+2,row,column+1)
move_found=1
;done with move
Break 2
EndIf
EndIf
;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;;
EndIf;marble_present ends here
marble_present=0
;PrintN(Str(column)+":"+Str(row))
Next column
Next row
;PrintN("Returning from Make_move:"+Str(move_found))
ProcedureReturn move_found
EndProcedure
OpenConsole()
EnableGraphicalConsole(1)
PrintN ("Calculating...")
move=1
Repeat
;PrintN (Str(move))
If Make_move(move)=1
;PrintN ("move found:"+Str(move))
move=move+1
Else
;PrintN ("move not found:"+Str(move))
Retract_move(move,move-1)
;Print_board()
;Input()
EndIf
;If move=31
;Print_board()
;Input()
;EndIf
;If move>29
;PrintN ("move retracted::"+Str(move))
;ConsoleLocate(20,0)
;PrintN(Str(move))
;EndIf
Until move=32
Print_board()
Input()
