eight queens in java
COMP 333 Prolog Project #1: Eight Queens Part 1: Backtracking Based Solution for Eight Queens in Java In Part 2 of this project, you will write a Prolog program to solve the Eight Queens problem. But before trying to solve it in Prolog, you will first solve it in Java. The reason for this is that you first need to understand the problem and its solution without trying to learn Prolog at the same time. Another reason is that solving it in Java requires you to implement backtracking explicitly. This experience will be useful when you solve in Prolog since Prolog provides backtracking automatically as part of its unification and backtracking search strategy. Java Solution Here is a description of the solution to the Eight Queens problem for implementation in Java. We will define the size of the board by a variable named n: int n; We will set n to 8 to represent a traditional chess board holding 8 queens. But the value can be changed later to find solutions to a generalized version of the problem with a different number of queens. Tracking Queen Positions The goal of the program is to find one or more solutions to the problem of positioning all queens on the board such that no queen attacks another (no conflicts). There are a total of n queens, and we will find the solution by positioning the queens one column at a time. For each column, we will choose a row position for the queen in that column and check that the position creates no attacks or conflicts for any previously positioned queen. When we successfully position the last queen in column n-1, then we have “solved” the problem by finding a solution. We will keep track of the current solution with an array of n elements, where each index represents a column and the value at that index represents the row position of the queen for that column. int [] queensPositions; The initial value of the array will be all positions marked -1. { -1, -1, -1, -1, -1, -1, -1, -1 } This value indicates that none of the queens have been given a position yet. Later on, positions of queens will be marked in each column. For example, the array { 7, 3, 0, 2, 5, 1 ,6 , -1 } means queen in column 0 is in row 7, queen in column 1 is in row 3, queen in column 2 is in row 0, and so on. Tracking Tried and Untried Row Positions in Each Column The solution proceeds by finding a row position for the queen in a specific column that has no conflicts with the queens already positioned in previous columns, then moving on to the next column. If we try a row position for some column but it generates conflicts, we have to mark that row position for that column as tried and try another untried row position in the same column. So for each column, we have to keep track of which rows in that column have been tried so far and which rows haven’t. Since rows are tried in numerical order, for each column we only have to record the index of the first untried row for that column. int [] firstUntried; For example, the array { 3, 4, 2, 6, 0, 0, 0, 0 } means that in column 0, rows 0 through 2 have already been tried, so the first untried row is row 3, and similarly for other columns. A value of 0 means none of the rows have been tried yet. A value of n means that all the rows have been tried and we will soon be backtracking to keep the search for a solution alive. Functions on Queen Position Array void initQueensPositions() allocate space for the array based on value of n set all position values to -1 to indicate no queen positions have been chosen yet boolean hasConflict(int a, int b, int bpos) check for conflicts between columns a and b assume a < b get current queen position for column a from queenspositions array find out if row position bpos in column b has a conflict with column a if has conflict return true if no conflict return false see figure below for more visualization boolean hasconflictcumulative(int b, int bpos) check for conflicts between column b and all previous columns 0 through b – 1 use previous function to check for conflicts with specific columns void setqueenposition(int col, int pos) set queen position for column col to be pos int getqueenposition(int col) get queen position for column col and return it string getpositionssnapshot() create a string showing the current values of all queen positions for all columns so that it can be printed out, this is for tracing and debugging functions for managing tried and untried row positions or states for each column void initstates() allocate space for the firstuntried array based on value of n set all index values to 0 to indicate no row positions have been tried yet int getuntriedposition(int col) return the value of the first untried row position for that row if the first untried row equals n, then there are no remaining untried rows, so return -1 otherwise return the value of the row position void setpositiontried(int col) increment the first untried row position for that column this indicates that current row position is marked tried and the next try will use next row void setallpositionsuntried(int col) reset first untried row position for that column back to 0 this means that we are erasing the tried positions for that column and starting over this happens during backtracking when we erase all the tries for the current column and backup to the previous column how to check for conflicts between columns solving the puzzle proceeds by setting the position of the queen for each column, one column at a time. supposing we are working on column c, we pick an unused row r for column c as a potential position for the queen in column c. we then have to check if row r in column c creates a conflict with any of the previous columns 0 through c-1. • column conflict: there can be no column conflicts in this solution because there is only one queen per column • row conflict: if we pick row r for column c, then there is a row conflict if any of the previous columns 0 through c-1 also have row value r. • diagonal conflict: let a and b be two column indexes and assume a b="" get="" current="" queen="" position="" for="" column="" a="" from="" queenspositions="" array="" find="" out="" if="" row="" position="" bpos="" in="" column="" b="" has="" a="" conflict="" with="" column="" a="" if="" has="" conflict="" return="" true="" if="" no="" conflict="" return="" false="" see="" figure="" below="" for="" more="" visualization="" boolean="" hasconflictcumulative(int="" b,="" int="" bpos)="" check="" for="" conflicts="" between="" column="" b="" and="" all="" previous="" columns="" 0="" through="" b="" –="" 1="" use="" previous="" function="" to="" check="" for="" conflicts="" with="" specific="" columns="" void="" setqueenposition(int="" col,="" int="" pos)="" set="" queen="" position="" for="" column="" col="" to="" be="" pos="" int="" getqueenposition(int="" col)="" get="" queen="" position="" for="" column="" col="" and="" return="" it="" string="" getpositionssnapshot()="" create="" a="" string="" showing="" the="" current="" values="" of="" all="" queen="" positions="" for="" all="" columns="" so="" that="" it="" can="" be="" printed="" out,="" this="" is="" for="" tracing="" and="" debugging="" functions="" for="" managing="" tried="" and="" untried="" row="" positions="" or="" states="" for="" each="" column="" void="" initstates()="" allocate="" space="" for="" the="" firstuntried="" array="" based="" on="" value="" of="" n="" set="" all="" index="" values="" to="" 0="" to="" indicate="" no="" row="" positions="" have="" been="" tried="" yet="" int="" getuntriedposition(int="" col)="" return="" the="" value="" of="" the="" first="" untried="" row="" position="" for="" that="" row="" if="" the="" first="" untried="" row="" equals="" n,="" then="" there="" are="" no="" remaining="" untried="" rows,="" so="" return="" -1="" otherwise="" return="" the="" value="" of="" the="" row="" position="" void="" setpositiontried(int="" col)="" increment="" the="" first="" untried="" row="" position="" for="" that="" column="" this="" indicates="" that="" current="" row="" position="" is="" marked="" tried="" and="" the="" next="" try="" will="" use="" next="" row="" void="" setallpositionsuntried(int="" col)="" reset="" first="" untried="" row="" position="" for="" that="" column="" back="" to="" 0="" this="" means="" that="" we="" are="" erasing="" the="" tried="" positions="" for="" that="" column="" and="" starting="" over="" this="" happens="" during="" backtracking="" when="" we="" erase="" all="" the="" tries="" for="" the="" current="" column="" and="" backup="" to="" the="" previous="" column="" how="" to="" check="" for="" conflicts="" between="" columns="" solving="" the="" puzzle="" proceeds="" by="" setting="" the="" position="" of="" the="" queen="" for="" each="" column,="" one="" column="" at="" a="" time.="" supposing="" we="" are="" working="" on="" column="" c,="" we="" pick="" an="" unused="" row="" r="" for="" column="" c="" as="" a="" potential="" position="" for="" the="" queen="" in="" column="" c.="" we="" then="" have="" to="" check="" if="" row="" r="" in="" column="" c="" creates="" a="" conflict="" with="" any="" of="" the="" previous="" columns="" 0="" through="" c-1.="" •="" column="" conflict:="" there="" can="" be="" no="" column="" conflicts="" in="" this="" solution="" because="" there="" is="" only="" one="" queen="" per="" column="" •="" row="" conflict:="" if="" we="" pick="" row="" r="" for="" column="" c,="" then="" there="" is="" a="" row="" conflict="" if="" any="" of="" the="" previous="" columns="" 0="" through="" c-1="" also="" have="" row="" value="" r.="" •="" diagonal="" conflict:="" let="" a="" and="" b="" be="" two="" column="" indexes="" and="" assume="">