|
| View previous topic :: View next topic |
| Author |
Message |
| Lunatic
 | | Joined: 11 Mar 2007 | | Posts: 166 | | : | | Location: Ghent - Belgium |
Items |
|
 Posted: Fri May 15, 2009 8:05 am Post subject: |
 |
|
| PIsaacson wrote: | | The ALS-XZ help states that it is not yet implemented. Any projected dates for completion??? I only ask because ALS chains and Death Blossom are my (current) special area of interest. |
I wish it was allready done, ALS-XZ, but for now, i have no idea for a good approach on how to handle ALS-XZ. I asked for help on that a while ago, but there was little response: http://www.setbb.com/sudoku/viewtopic.php?t=1601&start=0&postdays=0&postorder=asc&highlight=&mforum=sudoku
| PIsaacson wrote: | | BTW: I had a hard time seeing the help examples in FireFox due to the back-slashed file names for the gifs. |
Thanks for letting me know, I was not aware of this. I didn't even know my links had backslashes in their path. Apparently, my html-editor handles this incorrectly. I will change it as soon as possible.
_________________
Marc
~~~<><~~~<><~~~<><~~~<><~~~ |
|
| Back to top |
|
 |
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Fri May 15, 2009 12:00 pm Post subject: Re: Recursion |
|
|
| gsf wrote: | | m_b_metcalf wrote: | So I added code to the function valid that, on row 4 (box-1 in the general case), keeps a count of the number of remaining distinct values available, taking account of those already used in the first 3 rows of the box 5. If, at any point along the row, there are fewer than 5 values left available (they'll be needed for row 4 of box 5) we can back up staightaway. This brought the time to produce a 25x25 down from 155s to 11s 
|
this is a form of forward checking
it can be worthwhile depending on the domain
doing it at every move usually doesn't pay off
but you found a neat way to do it for groups of moves in the sudoku domain |
Thanks, but it has its limitations. I had several attempts to produce a 36x36 but none even reached row 6 (one attempt lasted an hour). Given that I already have a program that can produce a 36x36 in 0.3s, this is not worth pursuing further. But it was an interesting exercise and I learned that row box-1 is a real hump with this approach. It also demonstates a very simple way of producing 9x9s at a rate of a million every 3 minutes.
| Quote: |
re: recursion vs goto
there's another alternative: roll your own stack via arrays
(the way fortran programmers used to do it:)
|
Well, I'll take your word on that 
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Mon May 18, 2009 6:37 pm Post subject: |
|
|
Just for the record, I used the generator code posted earlier as the basis of a solver, see below. It takes 5s to solve an average 17-clue puzzle but is ten times faster for 20+ puzzles. Of course, it has no prior pruning with any logic such as singles, nor any reordering. I got it to solve two 112-clue 16x16 puzzles; one took 24s the other 1067s, although the second was simply the transpose of the first.
Regards,
Mike Metcalf
[Edited to randomize the search within each cell.]
| Code: |
program solve
implicit none
integer, parameter :: box = 3, size = box*box, size2 = size*size
integer, dimension(size2) :: sudoku
integer, dimension(size, size2) :: order, turn
integer :: cell_index, j, ll
logical :: complete, fix(size2)
open(1, file='c:\sudoku\hope\hope\17.txt')
do ll = 1, 10
read(1, '(81i1)') sudoku
call stab
complete = .false.
cell_index = 0
call cell
write(*,'(81i1)') sudoku
end do
contains
recursive subroutine cell
integer :: ii, jj, top
! Finds next valid value for this cell, and backs up one cell otherwise
cell_index = cell_index + 1
if(fix(cell_index)) then
top = 1
else
top = size
end if
do jj = 1, top
ii = turn(jj, cell_index)
if(order(ii, cell_index) == 0) cycle
if(.not.valid(order(ii, cell_index))) cycle
sudoku(cell_index) = order(ii, cell_index)
if(cell_index == size2) then
complete = .true.
return
else
call cell !!! <--------------The recursive call
if(complete) return
end if
if(.not.fix(cell_index)) sudoku(cell_index) = 0
end do
if(.not.fix(cell_index)) sudoku(cell_index) = 0
cell_index = cell_index - 1
end subroutine cell
logical function valid(value)
integer, intent(in) :: value
integer :: r_ind, c_ind, b_ind, bb
! Checks the row/column/box constaints
valid = .true.
if(fix(cell_index)) return
r_ind = ((cell_index - 1)/size) * size
c_ind = cell_index - r_ind
if(any(sudoku(r_ind + 1 : r_ind + size) == value)) then
valid = .false.
return
else if(any(sudoku(c_ind : c_ind + (size-1)*size : size) == value)) then
valid = .false.
return
else
b_ind = ((cell_index -1)/(size*box))*size*box + c_ind
b_ind = ((b_ind - 1)/box)*box + 1
do bb = 0, box - 1
if(any(sudoku(b_ind + bb * size : b_ind + bb * size + box - 1) == value)) then
valid = .false.
return
end if
end do
end if
end function valid
subroutine stab
integer :: r_ind, c_ind, b_ind, bb, value
! Initialize the search space; random within each cell
do j = 1, size2
order(:, j) = (/ (ll, ll = 1, size) /)
turn(:, j) = scatter(size)
end do
fix = .false.
where(sudoku /= 0)
order(1, :) = sudoku
turn(1, :) = 1
fix = .true.
end where
do j = 1, size2
if(.not.fix(j)) cycle
value = sudoku(j)
r_ind = ((j - 1)/size) * size
c_ind = j - r_ind
where(.not.fix(r_ind + 1 : r_ind + size)) order(value, r_ind + 1 : r_ind + size) = 0
where(.not.fix(c_ind : c_ind + (size-1)*size : size)) &
order(value, c_ind : c_ind + (size-1)*size : size) = 0
b_ind = ((j -1)/(size*box))*size*box + c_ind
b_ind = ((b_ind - 1)/box)*box + 1
do bb = 0, box - 1
where(.not.fix(b_ind + bb * size : b_ind + bb * size + box - 1)) &
order(value, b_ind + bb * size : b_ind + bb * size + box - 1) = 0
end do
end do
end subroutine stab
function scatter(num)
integer, intent(in) :: num
integer :: scatter(num), ii, index
real :: numbers(num)
! Array-valued function that returns the integer values 1 to num in random order
call random_number(numbers)
do ii = 1, num
index = minloc(numbers, dim=1)
scatter(ii) = index
numbers(index) = 2.0
end do
end function scatter
end program solve
|
Last edited by m_b_metcalf on Tue May 19, 2009 6:22 am; edited 1 time in total |
|
| Back to top |
|
|
| PIsaacson
| | Joined: 17 Jan 2006 | | Posts: 47 | | : | | Location: Campbell, CA |
Items |
|
| Posted: Mon May 18, 2009 11:30 pm Post subject: |
|
|
Mike,
This bears repeating, even if it is well known:
Searching in a linear manner with the cell_index is not the optimal way to traverse the solution search space.
Graph theory and sudoku logical rules combine to show that the fastest way to traverse the solution tree is through a node (cell to test) list that is sorted on the number of constraints for each cell to examine, and then by random order within each equal number of constraints. Think of it this way -- each bi-value or bi-local (locality is often overlooked) should be considered in the solution search tree before any tri-value or tri-local, which should be considered before any quad-value or qual-local ...
Within each equal level (bi-value/local, tri-value/local, quad-value/local...) graph theory has pretty much proven that randomizing the order for each level will, over the long run, always lead to finding the overall shortest path through the solution tree. The same randomness should also be used for testing the individual candidate values of each cell under consideration.
All references using the cell_index would need to be modified to use the cell pointed to by this sorted+randomized redirection list. The list should be generated just after stab builds the RC constraints, but you'll also need to generate the Rn/Cn/Bn constraints at that time as well in order to test/sort by locality.
That said, I have no idea of how difficult this is to implement in VB, but it would be interesting to see the difference in timings.
Hope this is clear and forgive me again if this is presumptuous...
Cheers,
Paul |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Tue May 19, 2009 6:34 am Post subject: |
|
|
| PIsaacson wrote: | This bears repeating, even if it is well known:
|
A very clear and succinct statement of how it should be done.
| PIsaacson wrote: |
That said, I have no idea of how difficult this is to implement in VB, but it would be interesting to see the difference in timings.
|
Nor have I, but in Fortran 95 implementing a random search within each cell is trivial and I have edited the posted code accordingly (see the auxiliary array turn). It reduces the time for 10 17-clue puzzles by 10% and for a 16x16 from 24.1s to 18.7s.
| PIsaacson wrote: |
Hope this is clear and forgive me again if this is presumptuous...
|
| m_b_metcalf wrote: |
Of course, it has no prior pruning with any logic such as singles, nor any reordering. |
Not at all. You may have overlooked the fact that this was merely a programming exercise in avoiding the harmful goto. Rest assured that I don't use this method when generating a 100x100 or for playing the Patterns Game!
Regards,
Mike Metcalf |
|
| Back to top |
|
|
| m_b_metcalf
| | Joined: 13 Mar 2006 | | Posts: 210 | | : | | Location: Berlin |
Items |
|
| Posted: Mon May 25, 2009 7:11 am Post subject: |
|
|
| m_b_metcalf wrote: | Nor have I, but in Fortran 95 implementing a random search within each cell is trivial and I have edited the posted code accordingly (see the auxiliary array turn). It reduces the time for 10 17-clue puzzles by 10% and for a 16x16 from 24.1s to 18.7s.
|
I played around with this further. Changing the order of the cells only according to the number of candidates in each turns out to be disastrous as it ruins locality. Timings increased by factors of ten or more. The real improvement comes from reordering the horizontal bands by order of population and the rows within the bands similarly. Then solving ten 17-clue puzzles takes just 2.8s and the 16x16 only 2s.
It just shows how sensitive simple methods are to ordering, as Paul pointed out.
Regards,
Mike Metcalf |
|
| Back to top |
|
|
|
|
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum
|
Powered by phpBB © 2001, 2005 phpBB Group
Igloo Theme Version 1.0 :: Created By: Andrew Charron |
FAQ
Search
Memberlist
Usergroups
Register
Profile
Log in
Log in to check your private messages
