I want to implement knight tour and run it with different search algorithms like bfs,dfs,a* and so on.User selects a place on chessboard and then things will be done.The question is after choosing, should i create the whole graph, like all possible moves from first location then from the second one and so on, or should i take it step by step and then, according to its algorithm, create children in the first level of search and then children of children in the next levels? I hope my question was clear and sorry for my english.
In each iteration, a node is popped from the queue until the destination is arrived. The repeated-moves are abandoned by using a list to record the previous history moves. To simplify the implementation, every time, the current move history array is also pushed into the queue. This is clearly a BFS (Breadth First Search) algorithm, which will guarantee the first route found is a shortest one.
you don't search the chessboard; search the space of placements:
Initial state: no knight is placed
Valid move: place a knight on any unoccupied tile
Goal state: all tiles are either occupied or attacked
basic algorithm (BFS of the state space):
push the initial state to the BFS queue. while there is something in the queue: remove one state from the queue. for every unoccupied tile: create a copy of the current state. add one knight to that tile. if the new state doesn't exist in the queue: if the new state is a goal state, finish. else add it to the queue.