Abhiram R <abhi.darkn...@gmail.com>:
> On Thu, Mar 26, 2015 at 8:54 AM, Ian Kelly <ian.g.ke...@gmail.com> wrote:
>> On Wed, Mar 25, 2015 at 8:56 PM, Abhiram R <abhi.darkn...@gmail.com> wrote:
>>> On Mar 26, 2015 5:39 AM, "Ian Kelly" <ian.g.ke...@gmail.com> wrote:
>>>> $ cat sudoku2.dat
>>>> . . . 7 . . . . .
>>>> 1 . . . . . . . .
>>>> . . . 4 3 . 2 . .
>>>> . . . . . . . . 6
>>>> . . . 5 . 9 . . .
>>>> . . . . . . 4 1 8
>>>> . . . . 8 1 . . .
>>>> . . 2 . . . . 5 .
>>>> . 4 . . . . 3 . .
>>>>
>>>> I tried the first puzzle you posted, and it took about a second. I
>>>> then started running it on this one before I started typing up this
>>>> post, and it hasn't finished yet.
>>>
>>> Sooooo... Is it done yet? And if yes, how long did it take?
>>
>> I don't know, I killed it at about 16 minutes.
>
> :( Too bad. I'll give it a go myself. And then try implementing my own
> solution. Have a lot of time on my hands today :D
Early optimization and so on and so forth...
I have optimized my solution slightly:
1. precalculated integer division operations (big savings)
2. interned integers (little savings)
The example above now finishes in 41 minutes on my computer. (The C
version finishes in 13 seconds).
The program runs single-threaded. Taking the trouble to parallelize the
algorithm is out of scope for the purposes of this discussion; it would
necessarily destroy the compactness of the solution.
========================================================================
#!/usr/bin/env python3
import sys
M = 3
N = M * M
P = M * N
Q = M * P
buddies = [ [ buddy
for buddy in range(Q)
if buddy != slot and
(buddy % N == slot % N or
buddy // N == slot // N or
buddy // P == slot // P and
buddy % N // M == slot % N // M) ]
for slot in range(Q) ]
interned = { n : n for n in range(1, N + 1) }
candidates = list(interned.values())
def main():
board = []
for n in sys.stdin.read().split():
try:
board.append(int(n))
except ValueError:
board.append(None)
solve(board)
def solve(board, slot=0):
if slot == Q:
report(board)
elif board[slot] is None:
for candidate in candidates:
if not any(board[buddy] is candidate for buddy in buddies[slot]):
board[slot] = candidate
solve(board, slot + 1)
board[slot] = None
else:
solve(board, slot + 1)
def report(board):
print("\n".join(
" ".join(str(board[row * N + col])
for col in range(N))
for row in range(N)))
print()
if __name__ == '__main__':
main()
========================================================================
Marko
--
https://mail.python.org/mailman/listinfo/python-list
