I'm trying to solve a problem using backtracking. I must use backtracking, given the appearance of an n * n array(arr), and n <= 20. I should make a given shape with all the buttons not pressed. I may have multiple answers, but I should print the answer with the minimum number of times you press the button.
Pressing the button changes the status of the pressed button and the up, down, left, and right buttons. # is not pressed button, O is pressed button
For example,
4
O O O O
O O O O
O O O O
O O O O
Is given as an input
# O # #
# # # O
O # # #
# # O #
Should be output.
This means that you can make the shape given by the input with four operations (push the button in the O position).
My source code will take about 1 minute in worst case if n is given as 20.
Is there a way to reduce the time it takes?
But I do not get a sense of what to do.
The current non-promising condition I am using is that arr[row-1][col] and temarr[row-1][col] are not the same when manipulating the button at temans[row][col].
This is because I can not change the appearance of temarr [row-1] [col] after this position.
start:
button in 1,1 position: p np
button in 1,2 position: p np p np
...
button in i,j position: p np...p np
button in n,n position: p np...p np
I have solved this by showing the number of all cases of pressed(p) and not pressed(np) the button at a specific position in a tree form.
I solved this problem
Is there a way to reduce the time it takes?
Run it on a better computer ? Just joking ^^.
It seems you are a student and it really looks like a homework, so I'm just giving some hints & leads.
arr and temarr. You also know that count - temcount == 3 (you can press only 2 buttons if you want to find a better solution). How likely are you to find a better solution ?compare function: let's say I place 20*20 = 4,000 playing cards on a table. After counting for 30min, I know that 1,800 are "face up", and 2,200 are "face down". Now I flip 3 cards from "face up" to "face down", and I flip 2 different cards the other way. Do I have to spend 30min counting again to get the 2 totals ?temarr, do you have to recompare all its values to arr's values to test if they are different ?temarr for the sole purpose of comparing it to arr, and you are doing the comparison quite often. You can work directly on the "difference" of the two arrays: meaning you have a single array telling which value is "right" or "wrong".