I've been a zone leader with DZone since 2008, and I'm crazy about community. Every day I get to work with the best that JavaScript, HTML5, Android and iOS has to offer, creating apps that truly make at difference, as principal front-end architect at Avego. James is a DZone Zone Leader and has posted 639 posts at DZone. You can read more from them at their website. View Full User Profile

Excercise Your Coding Muscles

04.12.2012
| 8424 views |
  • submit to reddit

We thought we'd try something different here at JavaLobby. For the next few weeks, every Thursday, we'll publish a code puzzler for you to solve. I'm sure they'll be easy to solve for such a gifted community of readers as we have here, but let's give it a go. Use whatever frameworks/languages you think are appropriate to solve the question.

Note: Even though there really is nothing stopping you from finding a solution to this on the internet, try to keep honest, and come up with your own answer.  It's all about the participation!

The N Queens Puzzle

One of the classic programming challenges. What you need to do is place 8 queens on an 8x8 chess board in a way that no two queens attack each other. For those who don't play chess, this means that no two queens can be on the same row, column or diagonal.  Sounds simple? Go! 

What's the most efficient way to solve this?

Comments

Fabien Bergeret replied on Thu, 2012/04/12 - 8:15am

Datacenter approach: System.out.println("a1,e2,h3,f4,c5,g6,b7,d8");

Fabien Bergeret replied on Thu, 2012/04/12 - 8:57am

Could be optimized by symetry
public class NQ {
	
	private int rowNumber;
	
	public NQ(int rowNumber) {
		this.rowNumber = rowNumber;
		List rows = new ArrayList(rowNumber);
		go(rows);
	}

	private void go(List rows) {
		for ( int i = 0 ; i < rowNumber; i++ ) {
			if ( !rows.contains(i)) {
				rows.add(i);
				if ( ok(rows)) {
					if ( rows.size() == rowNumber) {
						printSol(rows);
					} else {
						go(rows);
					}
				}
				rows.remove(rows.size()-1);
			}
		}
	}

	private void printSol(List rows) {
		boolean first=true;
		for ( int i = 0 ; i < rows.size(); i++) {
			if ( first ) {
				first = false;
			} else {
				System.out.print(',');
			}
			char letter = (char)('a'+i);
			int row = rows.get(i)+1;
			System.out.print(""+letter+row);
		}
		System.out.println("");
	}

	private boolean ok(List rows) {
		int last = rows.get(rows.size()-1);
		for ( int i = 0 ; i < rows.size()-1; i++) {
			int current = rows.get(i);
			int delta1 = rows.size()-1-i;
			int delta2 = current-last;
			if ( (delta1 == delta2) ||( delta1 == -delta2) ) {
				return false;
			}
				
		}
		return true;
	}

	public static void main(String[] args) {
		new NQ(Integer.parseInt(args[0]));

	}

}
gives
a1,b5,c8,d6,e3,f7,g2,h4
a1,b6,c8,d3,e7,f4,g2,h5
a1,b7,c4,d6,e8,f2,g5,h3
...
a8,b2,c5,d3,e1,f7,g4,h6
a8,b3,c1,d6,e2,f5,g7,h4
a8,b4,c1,d3,e6,f2,g7,h5

Erin Garlock replied on Thu, 2012/04/12 - 9:52am

Do you have any particular definition of efficient?  LoC, Execution Time, computations, memory utilization, etc.?

James Sugrue replied on Thu, 2012/04/12 - 10:09am in response to: Erin Garlock

Hey Erin 

I guess the wording was a bit vague..

Efficient to me is execution time / computations. But feel free to aim at it any other type of efficiency.  

 James 

Ray Santiago replied on Thu, 2012/04/12 - 5:26pm

I think if you generalize it to N-dimensions instead of 2 you might find something interesting.

Christian Effertz replied on Fri, 2012/04/13 - 2:42am

Having played chess for a while, I know that Knights can attack a Queen without facing her. So I assumed that if I move the Queens the Knight’s way, they will stand on the board without facing each other.

After creating a test to check this for all starting positions, I found out that I need to tweak the leap over the border. This is where I think it could be improved.

My solution so far

public class ChessCoordinate {

   public static void main(String[] args) {
      ChessCoordinate tmpCoordinate = new ChessCoordinate('A', 1);
      System.out.print(tmpCoordinate.toString());
      for (int i = 0; i < 7; i++) {
         tmpCoordinate.incrementToNextQueenSpot();
         System.out.print("," + tmpCoordinate.toString());
      }
   }

   private int row;
   private int column;
   private int timesCrossed;

   ChessCoordinate(char aColumn, int aRow) {
      column = aColumn - 65;
      row = aRow - 1;
   }

   void incrementToNextQueenSpot() {
      row += 2;
      if (row > 7) {
         row = (row % 8) + 1 - 2 * timesCrossed;
         timesCrossed++;
      }
      column = (column + 1) % 8;
   }

   int getRow() {
      return row;
   }

   int getColumn() {
      return column;
   }

   @Override
   public String toString() {
      return (char) (65 + column) + String.valueOf((row + 1));
   }

}

What should we use to generate some stats and figures about execution time / computations?

Francesco Illuminati replied on Fri, 2012/04/13 - 10:12am

The Fabien Bergeret's solution looks pretty optimal to me. It uses a fail fast solution tree wich leaves are the solutions of the problem. My approach is similar but, having just read the Fork-Join article by Ricardo Zuastri, I tried to apply his lesson and build the algorithm in a parallel way. To accomplish that I had to rewrite the List so to avoid having to remove anything from it (or being forced to duplicate it). My solution is a reversed linked list where each successive element points back to its parent. It is both fast and memory efficient for our purpose (if you don't mind reading the list backwards).

The performances are really impacted by the outputting of data (using System.out.println()), so, commenting out the lines that actually performs the printing it seems that the parallel algorithm employs 60% of the time spent by the sinlge threaded algorithm so gaining a significant advantage (my test machine is equipped with 4 processors).

public class Solution {
    private AtomicInteger solutionNumber = new AtomicInteger(0);
    private Queue<String> output = new ConcurrentLinkedQueue<>();

    public static Solution findSolutions(final ForkJoinPool pool) {
        final Solution solution = new Solution();
        pool.invoke(new Step(solution));
        return solution;
    }

    public void addSolution(final Sequence sequence) {
        solutionNumber.incrementAndGet();
        // in a multithreaded environment System.out.println() blocks
        // so it must be avoided
        output.add(sequence.toString());
    }

    public int getSolutionNumber() {
        return solutionNumber.get();
    }

    public String getOutput() {
        final StringBuilder buf = new StringBuilder();
        for (String str: output) {
            buf.append(str).append('\n');
        }
        return buf.toString();
    }

    public static void main(String[] args) {
        Solution solution = findSolutions(new ForkJoinPool());
        System.out.println(solution.getOutput());
        System.out.println("found " + solution.getSolutionNumber() + " solutions.");
    }
}
public class Step extends RecursiveAction {
private static final long serialVersionUID = 1L;
private final Sequence sequence;
private final Solution solution;

public Step(final Solution solution) {
this(solution, new Sequence());
}

private Step(final Solution solution, final Sequence sequence) {
this.solution = solution;
this.sequence = sequence;
}

@Override
protected void compute() {
final int column = sequence.size();
if (column == 8) {
solution.addSolution(sequence);
} else {
final List<Step> solutions = new ArrayList<>(8);
for (int row = 0; row < 8; row++) {
final Queen queen = new Queen(row, column);
if (sequence.isFriendlyWith(queen)) {
solutions.add(new Step(solution, sequence.add(queen)));
}
}
invokeAll(solutions);
}
}

}
/**
 * It's a reversed linked list with the characteristic that a new element
 * is always added to an existing list so avoiding having to copy the list.
 *
 * @author fra
 */
public class Sequence implements Iterable<Queen> {
    private final int size;
    private final Entry head;

    private static class Entry {
        final private Queen queen;
        final private Entry next;

        public Entry(final Queen queen, final Entry next) {
            this.queen = queen;
            this.next = next;
        }
    }

    public Sequence() {
        this(null, 0);
    }

    private Sequence(final Entry entry, final int size) {
        this.head = entry;
        this.size = size;
    }

    /** Returns a new list with the new element on top */
    public Sequence add(final Queen queen) {
        final Entry entry = new Entry(queen, head);
        return new Sequence(entry, size + 1);
    }

    public boolean isFriendlyWith(final Queen queen) {
        for (final Queen q: this) {
            if (q.attack(queen)) {
                return false;
            }
        }
        return true;
    }

    public int size() {
        return size;
    }

    @Override
    public String toString() {
        final StringBuilder buf = new StringBuilder();
        for (final Queen q: this) {
            buf.append(q).append(' ');
        }
        return buf.toString();
    }

    /** The list is iterated in reverse order */
    @Override
    public Iterator<Queen> iterator() {
        return new Iterator<Queen>() {
            private Entry current = new Entry(null, head);

            @Override
            public boolean hasNext() {
                return current != null && current.next != null;
            }

            @Override
            public Queen next() {
                current = current.next;
                return current.queen;
            }

            @Override
            public void remove() {
                throw new UnsupportedOperationException("Not supported yet.");
            }
        };
    }

}
public class Queen {
    private final int row, column, diagonalLeft, diagonalRight;

    public Queen(final int row, final int column) {
        this.row = row;
        this.column = column;
        this.diagonalLeft = row + column;
        this.diagonalRight = row - column;
    }

    public boolean attack(final Queen queen) {
        return this.row == queen.row ||
                this.column == queen.column ||
                this.diagonalLeft == queen.diagonalLeft ||
                this.diagonalRight == queen.diagonalRight;
    }

    public int getColumn() {
        return column;
    }

    public int getRow() {
        return row;
    }

    @Override
    public String toString() {
        return "" + ((char)(row + '1')) + ((char)(column + 'a'));
    }
}

EDIT: sorry I forgot to use AtomicInteger instead of int in Solution because of the concurrency in accessing it.

EDIT 2: sorry again, in my performance test I didn't print out anything thus the big speed difference.

EDIT 3: (This isn't really my day), I forgot to add a class: Step.

Comment viewing options

Select your preferred way to display the comments and click "Save settings" to activate your changes.