Op 6 feb 2014, om 16:46 heeft Simon Slavin het volgende geschreven:
On 6 Feb 2014, at 7:15am, big stone <stonebi...@gmail.com> wrote:
If we wish to have SQLite + Python combination to become "reference
choice"
in education, I would think that priority list should be :
Just to remind you that you're posting to the SQLite list. Most of
those are things that would be done by the Python maintainers, not
the SQLite maintainers.
Simon.
I find the subject of Sudoku solving still interesting and have an
other quey here. This derives from Bigstone's 1st solution, defining a
neighbourhood relation between sudoku cells. New is that I tried
bitmaps instead of a characterstring to represent the sudoku. Below is
the result. Conclusions
- bitmaps are hard to debug as they can not be easily viewed
- but the solution is much fater (four times)
- the recursion tends to go breath first by default which is not
optimal for speed.
- using a seperate (temporary) table for a non-trivial sub-queriy,
instead of a CTE. is worth when used at several places.
create temporary table ind (
ind integer primary key, -- sudoku cell (1..81)
word0, -- bitmap of ind, bits 1..54
word1, -- bitmap of ind, bits 55..81
neighbours0, neighbours1) -- bitmap of neighbour cells
;
/*
initializing the neighbour bitmaps was the
most tricky part: one must probably turn the
soduku upside down and view it through a mirror
to see the x,y coordinates as used here.
*/
insert into ind
select ind,
case when iword=0 then 1<<ibit else 0 end AS word0,
case when iword=1 then 1<<ibit else 0 end AS word1,
--neighbours0
--horizontal
CASE WHEN iword=0
THEN (512-1)<<(y*9)
ELSE 0
END |
--vertical
((1+512*(1+512*(1+512*(1+512*(1+512)))))<<x) |
--box
CASE WHEN iword=0
THEN ((8-1)*(1+512*(1+512)))<<(y/3*3*9+x/3*3)
ELSE 0
END
AS neighbours0,
--neighbours1
--horizontal
CASE WHEN iword=1
THEN (512-1)<<((y%6)*9)
ELSE 0
END |
--vertical
((1 + 512 * (1 + 512)) << x) |
--box
CASE WHEN iword=1
THEN ((8-1)*(1+512*(1+512)))<<((y%6)/3*3*9+x/3*3)
ELSE 0
END
AS neighbours1
from (
with xy AS (SELECT 0 AS xy UNION ALL SELECT xy+1 FROM xy WHERE xy
< 80)
select xy+1 AS ind,
xy%9 AS x,
xy/9 AS y,
xy/54 AS iword,
xy%54 AS ibit
from xy
)
;
.mode line
with z AS (
SELECT 0 AS z -- zero is used for fixed input
UNION ALL
SELECT z+1 FROM z WHERE z < 9
)
,
input as (
select sud,
cast (substr (sud, 1, 1) as int) as z,
1 as ind,
0 as w0, 0 as w1, -- bitmap covering all digits
0 as w10, 0 as w11, -- bitmap of 1's
0 as w20, 0 as w21, -- bitmap of 2's
0 as w30, 0 as w31, -- bitmap of 3's
0 as w40, 0 as w41, -- bitmap of 4's
0 as w50, 0 as w51, -- bitmap of 5's
0 as w60, 0 as w61, -- bitmap of 6's
0 as w70, 0 as w71, -- bitmap of 7's
0 as w80, 0 as w81, -- bitmap of 8's
0 as w90, 0 as w91 -- bitmap of 9's
from (
select
--'53
..
7
....
6
..195....98....6.8...6...34..8.3..17...2...6.6....28....419..5....8..79'
'1
....
7.9
..
3..2...8..96..5....53..9...1..8...26....4...3......1..4......7..7...3..'
as sud
) sud
union all
select sud,
cast (substr (sud, ind.ind+1, 1) as int),
ind.ind+1,
w0 | case when z>0 then word0 else 0 end,
w1 | case when z>0 then word1 else 0 end,
w10 | case when z=1 then word0 else 0 end,
w11 | case when z=1 then word1 else 0 end,
w20 | case when z=2 then word0 else 0 end,
w21 | case when z=2 then word1 else 0 end,
w30 | case when z=3 then word0 else 0 end,
w31 | case when z=3 then word1 else 0 end,
w40 | case when z=4 then word0 else 0 end,
w41 | case when z=4 then word1 else 0 end,
w50 | case when z=5 then word0 else 0 end,
w51 | case when z=5 then word1 else 0 end,
w60 | case when z=6 then word0 else 0 end,
w61 | case when z=6 then word1 else 0 end,
w70 | case when z=7 then word0 else 0 end,
w71 | case when z=7 then word1 else 0 end,
w80 | case when z=8 then word0 else 0 end,
w81 | case when z=8 then word1 else 0 end,
w90 | case when z=9 then word0 else 0 end,
w91 | case when z=9 then word1 else 0 end
from input
join ind
on ind.ind = input.ind
)
,
sudoku as (
select 1 as ind,
w0, w1,
w10, w11,
w20, w21,
w30, w31,
w40, w41,
w50, w51,
w60, w61,
w70, w71,
w80, w81,
w90, w91
from input
where ind>81
union all
select sudoku.ind+1,
w0 | word0,
w1 | word1,
w10 | case when z=1 then word0 else 0 end,
w11 | case when z=1 then word1 else 0 end,
w20 | case when z=2 then word0 else 0 end,
w21 | case when z=2 then word1 else 0 end,
w30 | case when z=3 then word0 else 0 end,
w31 | case when z=3 then word1 else 0 end,
w40 | case when z=4 then word0 else 0 end,
w41 | case when z=4 then word1 else 0 end,
w50 | case when z=5 then word0 else 0 end,
w51 | case when z=5 then word1 else 0 end,
w60 | case when z=6 then word0 else 0 end,
w61 | case when z=6 then word1 else 0 end,
w70 | case when z=7 then word0 else 0 end,
w71 | case when z=7 then word1 else 0 end,
w80 | case when z=8 then word0 else 0 end,
w81 | case when z=8 then word1 else 0 end,
w90 | case when z=9 then word0 else 0 end,
w91 | case when z=9 then word1 else 0 end
from sudoku
join ind on ind.ind = sudoku.ind
join z on
case when w0&word0 OR w1&word1
then z=0
else
case z
when 1 then not neighbours0&w10 and not neighbours1&w11
when 2 then not neighbours0&w20 and not neighbours1&w21
when 3 then not neighbours0&w30 and not neighbours1&w31
when 4 then not neighbours0&w40 and not neighbours1&w41
when 5 then not neighbours0&w50 and not neighbours1&w51
when 6 then not neighbours0&w60 and not neighbours1&w61
when 7 then not neighbours0&w70 and not neighbours1&w71
when 8 then not neighbours0&w80 and not neighbours1&w81
when 9 then not neighbours0&w90 and not neighbours1&w91
end
end
order by ind desc --go depth first
)
,
output as (
select 1 as ind,
w10, w11,
w20, w21,
w30, w31,
w40, w41,
w50, w51,
w60, w61,
w70, w71,
w80, w81,
w90, w91,
'' as sudoku
from sudoku
where ind>81
union all
select output.ind + 1,
w10, w11,
w20, w21,
w30, w31,
w40, w41,
w50, w51,
w60, w61,
w70, w71,
w80, w81,
w90, w91,
sudoku || replace (cast (
case 1
when w10&word0 OR w11&word1 then 1
when w20&word0 OR w21&word1 then 2
when w30&word0 OR w31&word1 then 3
when w40&word0 OR w41&word1 then 4
when w50&word0 OR w51&word1 then 5
when w60&word0 OR w61&word1 then 6
when w70&word0 OR w71&word1 then 7
when w80&word0 OR w81&word1 then 8
when w90&word0 OR w91&word1 then 9
else 0
end
as char), '0', '.')
from output
join ind on ind.ind = output.ind
)
select substr (sudoku, 1*9-8, 9) as line1,
substr (sudoku, 2*9-8, 9) as line2,
substr (sudoku, 3*9-8, 9) as line3,
substr (sudoku, 4*9-8, 9) as line4,
substr (sudoku, 5*9-8, 9) as line5,
substr (sudoku, 6*9-8, 9) as line6,
substr (sudoku, 7*9-8, 9) as line7,
substr (sudoku, 8*9-8, 9) as line8,
substr (sudoku, 9*9-8, 9) as line9
from output
where ind>81
;
_______________________________________________
sqlite-users mailing list
sqlite-users@sqlite.org
http://sqlite.org:8080/cgi-bin/mailman/listinfo/sqlite-users
