1
$\begingroup$

AC-3 with 4-queen

This is the illustration of the AC-3 algorithm for four queens from exhaustive study of essential constraint satisfaction problem techniques based on N-Queens problem by Md. Ahsan Ayub, Kazi A Kalpoma, Humaira Tasnim Proma, Syed Mehrab Kabir and Rakib Ibna Hamid.

I am confused whether this is pure AC-3 or AC-3 with backtracking. Which one is it?

Improve this question
$\endgroup$
1
0
$\begingroup$

The Fig. 5 in the question depicts AC-algorithm with backtracking.

In fact, without backtracking, checking arc-consistency alone can hardly solve the 4-Queen problem. Unless it happens that choices made so far will be extended to a desired configuration, any algorithm to solve CSP have to backtrack so as to check other possibilities.

Here is a relevant excerpt from the article.

Conversely, if it does not become possible to place a Queen at the pointed column, like in Fig. 5(c), backtracker will backtrack the previous assigned Queen’s column to reassign the conflicted Queen to a newly safe cell at the same column. Then, it will, at first, clear the constraints it created by calling the implemented modular function.

Improve this answer
$\endgroup$
7
  • $\begingroup$ if so,this article is used the algorithm of kti.mff.cuni.cz/~bartak/constraints/propagation.html ,is it? @Apass.Jack $\endgroup$ – Cecelia Feb 13 '19 at 1:24
  • $\begingroup$ Not sure what you meant (your sentence seems broken). If you meant that that articles also explains the idea that backtracking goes hand in hand with (arc) consistency checking, yes. $\endgroup$ – John L. Feb 13 '19 at 1:30
  • $\begingroup$ if so,the pseudo code in fig5 is [procedure AC3-BT(cv) Q <- {(Vi,Vcv) in arcs(G),i<cv}; consistent <- true; while not Q empty & consistent select and delete any arc (Vk,Vm) from Q; consistent <- REVISE(Vk,Vm) endwhile return consistent end AC3-BT] $\endgroup$ – Cecelia Feb 13 '19 at 1:40
  • $\begingroup$ The pure AC-3 algorithm puts all arcs in queue.If AC-3 combines with backtracking ,how to put arcs in queue? $\endgroup$ – Cecelia Feb 13 '19 at 3:59
  • 1
    $\begingroup$ Write the variable assignments with backtracking mechanism as pseudocode or programming code first. Then add AC3 as another procedure to that. $\endgroup$ – John L. Feb 13 '19 at 4:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.