Puzzles and Recreation
Computer Science
Visualization & Graphics

Solving the NQueens Problem

Use the recursive backtracking algorithm to solve the NQueens problem on a chessboard

Open in Cloud
Download Notebook

Create a chessboard and a matrix of positions:

In[1]:=

nchessboard=10;With[{num=nchessboard},chessboard=Boole@NestList[RotateLeft,EvenQ/@Range[num],num-1];boardpos=Array[List,{num,num}];];boardposcopy=boardpos;

Draw the chessboard with N queens:

In[2]:=

drawgrid[grid_]:=ArrayPlotchessboard,ColorRules{0LightBlue,1LightPink},EpilogInsetRasterizeStyle[♕,250],BackgroundNone,#-1,#-1,1&/@Positiongrid,♛;

Define a function to check the line of sight for a queen:

In[3]:=

QueensLineOfSight[{row_,col_}]:=Block[{currentcol,currentrow,diagL,diagR},currentcol=boardpos〚All,col〛;currentrow=boardpos〚row〛;diagR=Diagonal[boardpos,col-row];diagL=Diagonal[Reverse[boardpos,2],nchessboard-row-col+1];Union[currentcol,currentrow,diagR,diagL]];

The chessboard state is recorded only if the base case is reached, i.e., all N queens are successfully placed. For any non-viable move, the queen is removed from the current position (backtracking) and other positions are explored (in a recursive manner):

In[4]:=

NQueensSolve[nchessboard+1,_]:=Sow[boardposcopy];NQueensSolve[row_Integer:1,attackedPos_:{}]:=ScancolIf!MemberQ[attackedPos,{row,col}], boardposcopy[[row,col]]=♛; NQueensSolve[row+1,Union[attackedPos,QueensLineOfSight[{row,col}]]]; boardposcopy[[row,col]]={row,col};,Range[nchessboard];

Generate all possible solutions for 10 queens:

In[5]:=

solution=Reap[NQueensSolve[]]〚2,1〛;Print[Text["Number of solutions found for "<>ToString[nchessboard]<>" queens: "],Length@solution];

Number of solutions found for 10 queens:

724

Display one solution:

In[6]:=

drawgrid@*RandomChoice@solution

Out[6]=

Display all possible solutions:

In[7]:=

FrameListVideo[drawgrid/@solution,FrameRate15]

Out[7]=

Publisher Information

Contributed by: Ali Hashmi