Brute-forcing a seemingly simple number puzzle

Re:Brute-forcing a seemingly simple number puzzle by kevinwang on Wednesday December 05, 2018 @01:02PM (#18610729)

> The fact that Board is immutable means we don't have to perform any cleanup when backtracking. What does it mean? When one of the branches is stuck in a dead end, we must slowly go back, trying to take all other possible moves. Mutating Board would require cleaning it up. Immutable Board can be simply thrown away once it's no longer needed. Also immutability enables concurrent exploration (soon to come).

Someone correct me if I'm wrong, but I believe backtracking actually requires a mutable array and would be faster (since you wouldn't have to build 100x100 arrays all the time: you could just build the 100x100 array one time and mutate it.)

[ Parent | on HN ]

Re:Brute-forcing a seemingly simple number puzzle by taeric on Wednesday December 05, 2018 @03:36PM (#18612256)

Backtracking doesn't require a mutable anything, per se. Just the ability to get back to where you were.

Now, it can be somewhat easily reasoned that a mutable board can more quickly let you go back to previous settings, since you could potentially lose the GC steps of the immutable version.

Of course, the immutable is more easily reasoned for parallelizing, since you can just throw paths to different workers without them stepping on each other.

So, tradeoffs.

[ Parent | on HN ]

Re:Brute-forcing a seemingly simple number puzzle by kevinwang on Wednesday December 05, 2018 @08:46PM (#18614677)

My argument is that the version with a single mutable board would be 100x100=10000 times faster, since you won't need to make a new array for every move

[ Parent | on HN ]

Re:Brute-forcing a seemingly simple number puzzle by taeric on Wednesday December 05, 2018 @08:57PM (#18614721)

Oh, in that, I agree. I would hope a more friendly datastructure would be used for the immutable version. Data sharing should be possible.

[ Parent | on HN ]