Try in route 13.You can get heart scales everyday from the rock which is near the hidden grotto near the giant chasm.
Now see the picture here.When you go down the steps turn the dowsing machine on and it will activate.There will a rock below the steps,u can get a heart scale from the rock everyday using the dowsing machine.
Other places are Route 6, Route 13 (With Dowsing Machine), Route 18 (With Dowsing Machine), Castelia City, Desert Resort, Relic Castle (With Dowsing Machine), Moor of Icirrus, Undella Town (With Dowsing Machine), Undella Bay (With Dowsing Machine), Route 20 (With Dowsing Machine), Route 23, Castelia Sewers, Join Avenue (Souvenir), Seaside Cave, Humilau City, Humilau City (With Dowsing Machine)
Now,when you see the locations with the dowsing machine in brackets,you can get a heart scale everyday in that place.I dont know where to get that heart scale in that place,but have your dowsing machine and search that place for a heart scale.
Hope this helps!