4 ms·

I don't think it would be too difficult to find a candidate who could at least talk through or whiteboard out an imperative solution to this. If a candidate co

• bluecalm 13y ago
  I'd give bonus points for pointing out some implementation decisions: -when searching is it better to use copy-make or move/undo approach ? (copy make is faster on modern pc's, at least for things like 8Q's, it's also much easier to implement as you don't need any code for undoing moves) -what is the best way to check if given move (placing the queen) is valid ? (you need three 0-1 arrays for rows and diagonals in both direction this a neat trick, very difficult to come up with but which speeds the whole thing immensely) -how do you break out of the recursion if the task is changed to find one solution ? I know all those things because I am a hobbyist who wrote a lot of solvers and dabbled into chess programming. I am probably in top 0.1% of people if I get question like this. I am incompetent when it comes to things needed in most commercial applications as I've never worked on big commercial projects. This question filters for people like me. I can't imagine how this a good thing for anything practical (unless the task is to produce the best chess program or something).
  • kenjackson 13y ago
    What is copy/make vs move/undo? I'm not familiar with that terminology...
    • bluecalm 13y ago
      When you search you have a choice of: 1)having only one board and make/undo moves on it. So every time you put a new queen on the board you add it to the representation of the board and every time you go back in recursion you need to do an undo before exiting the function (so you new branch won't have queens placed on the board from previous branch) 2)storing as many boards as many steps deep in the recursion you are (max 8 in 8 queens problem) so every time you go deeper into recursion you create new board then you copy current state there and then you make a move (place a queen) on this new board; this way when you go back in recursion you do nothing as this new board is taken care of by stack pointer going back. The cost of copy make is memory (you need memory for new board representation for every step deeper into recursion) but it's usually not much of a problem. The benefit is that you don't need to code undo logic (which in case of some games is quite complicated) and undo is much faster which usually outweights costs of copying the memory. Some top chess programs are move/undo and some are copy/make, chess board representation usually takes about 200 bytes and variations may go as deep as 100 half moves which means you may need like 20kb additional memory for every thread doing searching. In case of 8 queens it's of course trivial though. Some more information (for chess, so way more advanced): https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Copy-Make https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Make+Move https://chessprogramming.wikispaces.com/Unmake+Move https://chessprogramming.wikispaces.com/Unmake+Move
      • kenjackson 13y ago
        Is this equivalent to a depth vs breadth first search? Sounds very similar...