تا آنجایی که من می دانم این مسئله راه حل خاصی ندارد و باید از روش عقبگرد(Backtracking) استفاده شود البته با هرس کردن های ابتکاری، در مورد *A هم فکر می کنم ایجاد توابعی برای محاسبه هزینه در اینجا مفهومی نداشته باشد البته شاید بتوان از الگوریتم ژنتیک استفاده کرد (اگر این روش را هوشمندانه بدانیم)
این زیر تقریبا تمام الگوریتم های حل سودوکو اومده:
Sudoku algorithms - Wikipedia, the free encyclopedia
موفق باشید.